首页 > 代码库 > Codeforces Round #265 (Div. 2)

Codeforces Round #265 (Div. 2)

A.inc ARG

  感觉题意不是很清楚,看样例才看懂,就是一串二进制数,左边是低位,就扫一遍记录下改变的bit数

#include <iostream>#include <cstdio>#include <cstdlib>using namespace std;const int maxn = 200;int n, cnt;char lis[maxn];int main(void){#ifdef LOCAL    freopen("465A.in", "r", stdin);#endif    scanf("%d", &n);    getchar();    for(int i = 0; i < n; i++)        scanf("%c", lis+i);    int tmp = 1;    for(int i = 0; i < n; i++) {        if(tmp) cnt++;          if(tmp && lis[i] == 1)    tmp = 1;        else    tmp = 0;    }    printf("%d\n", cnt);    return 0;}

 

B.Inbox (100500)

  简单模拟题,已经打开某封信的时候,如果下一封在下一个位置,那么直接跳下一页,否则回到主页再跳转过去,注意考虑特殊情况,比如全部都读过

#include <iostream>#include <cstdio>#include <cstdlib>using namespace std;const int maxn = 1000+50;int n, ans;int st[maxn];int main(void){#ifdef LOCAL    freopen("465B.in", "r", stdin);#endif    scanf("%d", &n);    for(int i = 0; i < n; i++)        scanf("%d", st+i);    for(int i = 0; i < n; i++) {        if(st[i] == 0)  continue;        if(ans == 0 || i == 0)  ans++;        else    ans += (st[i-1] == 1? 1: 2);    }       printf("%d\n", ans);    return 0;}

 

C.No to Palindromes!

  我也是卡了很久...才摸索出正确思路

  关于回文串的一个性质(LEN >= 2),中间一定aba型或者aa型,由此可以得到一个判定一个串是否有回文字串的简单方法,存在某个位置的字符满足那两种情况之一

这题是要输出字典序最小的没有回文子串的串,那么对于他的每一个位置都不满足上述条件即可

  我构造的方法是:原字符串已经满足上述条件,要求答案字典序最小,那么我们就从改变最右边一边,最右边两位....来构造答案:左边是确定的,右边只需要每个字符满足条件,从左向右,对于每个位置,搜索第一个不超过限制且不与前面两个字符形成回文串的字符(为什么不是枚举每一种情况?因为右边部分是任意的???

  ...坑爹了,脑子有点乱 题解到此为此 = =  详情见代码吧!

#include <iostream>#include <cstdio>#include <cstdlib>using namespace std;const int maxn = 1000+50;const int dx[] = {-2, -1, 1, 2};int n, p;char upper;char lis[maxn], ban[4];bool ok;bool checkLeft(int x){    for(int i = 1; i <= 2; i++)        if(x - i >= 0 && lis[x] == lis[x-i])    return false;    return true;}bool fillRight(int x){    for(int i = x; i < n; i++) {        bool canfill = false;        for(char c = a; c <= upper; c++) {            lis[i] = c;            if(checkLeft(i)) {                canfill = true;                break;            }        }        if(!canfill)    return false;    }    return true;}int main(void){#ifdef LOCAL    freopen("465C.in", "r", stdin);#endif    scanf("%d%d", &n, &p);    scanf("%s", lis);    upper = a+p-1;    for(int i = n-1; i >= 0; i--) {        for(char c = lis[i]+1; c <= upper; c++) {            lis[i] = c; //          if(i == 2 && c == ‘d‘)  cout << checkLeft(2) << endl;               if(!checkLeft(i))   continue;            if(fillRight(i+1)) {                ok = true;                printf("%s\n", lis);                break;            }        }        if(ok)  break;    }    if(!ok) printf("NO\n");    return 0;}

 

Codeforces Round #265 (Div. 2)