Codeforces Round #539 (Div. 2)

Posted by

http://codeforces.com/contest/1113

A. Sasha and His Trip

考虑使用贪心。当v>=n时,直接输出n-1即可。 否则每次以当前价格购进1升油,直到剩余的油足够跑完剩下路程,输出答案即可。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
using namespace std;
int n,v,ans;
inline int read(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int main(){
    n=read();v=read();
    if(v>=n) return 0&printf("%d\n",n-1);
    ans+=v;
    for(int i=2;i<=n;i++){
        if(n-i+1==v) break;
        else ans+=i;
    }
    printf("%d\n",ans);
    return 0;
}

B. Sasha and Magnetic Machines

把所有数排序后,因为越小的数乘以一个相同的数,增值越小。故考虑外部循环枚举约数,内部循环从a[n]a[2],更新与a[1]的最大答案。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
static const int MAXN=50050;
using namespace std;
int n,sum,ans,Max,a[MAXN];
inline int read(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];
    sort(a+1,a+n+1);
    for(int x=2;x<=100;x++){
        for(int i=n;i>1;i--){
            if(a[i]%x==0) Max=max(Max,a[1]+a[i]-(a[1]*x+a[i]/x));
        }
    }
    printf("%d\n",sum-Max);
    return 0;
}

C. Sasha and a Bit of Relax

由于异或的性质满足前缀的性质,考虑维护异或前缀和。 即

    \[ sum[i]=sum[i-1] \oplus a[i]; \]

由于异或具有可逆性,我们只需要异或前缀和相同且满足题意的个数。在这里使用二维数组来记录,第一维用来记录i的奇偶性。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll;
static const int MAXN=1<<21;
using namespace std;
int n,p[3][MAXN];
ll x,y,ans;
inline ll read(){
    ll x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int main(){
    n=read();
    p[1][0]=1;
    for(int i=0;i<n;i++){
        x=read();
        y^=x;
        ans+=p[i%2][y];
        p[i%2][y]++;
    }
    printf("%I64d\n",ans);
    return 0;
}

D. Sasha and One More Name

由于保证了源字符串时回文,那么答案要么为12,要么不存在。 对于不存在情况的讨论,我们需要判断是否字符串每个元素都相同,以及是否前len/2个字符都相同,当且仅当是这两种情况时,不存在答案。 若存在答案,对于len为奇数的,则答案为2。 对于偶数,依次枚举分割的部分,使用函数substr,若满足回文且与源字符串不相同,则输出1。 其余情况则输出2即可。
#include <cstdio>
#include <cctype>
#include <iostream>
#include <cstring>
#include <set>
using namespace std;
string s,s1,s2;
set<char> n;
inline bool check(){
    bool flag=0;
    for(int i=0;i<s.length();i++) n.insert(s[i]);
    if((int)n.size()==1) return 1;
    n.clear();
    for(int i=1;i<s.length()/2;i++){
        if(s[i]!=s[i-1]){
            flag=1;
            return 0;
        }
    }
    if(!flag) return 1;
    return 0;
}
inline bool check1(){
    for(int i=0,j=s2.length()-1;i<=j;i++,j--){
        if(s2[i]!=s2[j]) return false;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>s;
    if(check()) return 0&printf("Impossible\n");
    if(s.length()%2==1) return 0&printf("2\n");
    for(int i=1;i<s.length();i++){
        s1.clear();s2.clear();
        s1=s.substr(0,i);
        s2=s.substr(i,s.length()-s1.length());
        s2+=s1;
        if(check1()&&s2!=s) return 0&printf("1\n");
    }
    printf("2\n");
    return 0;
}
  ]]>

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注