Codeforces Round #449 (Div. 2)

乌鲁木齐确实是一番独特的体验

晚上赶在热身赛和现场赛之间开了一场cf，那么就来呗

其实这场也是命途多舛，忘了registration，结果通过extra如果，无奈多了20min罚时，要知道我有一个好友20min时已经两A了

然而，不要放弃，不到最后时刻，一切都还有希望

而这场，传奇的测评机注定将成为一大经典回忆，判题时间30min++，也算这场一大花絮吧，还好最后做出了3题，icpc前最后一场cf，也可能是退役之战了，成功涨分到职业生涯新高，也算是一件还挺可以接受的事吧，但愿不要败了明天的人品咯

看看这三题吧

A. Scarborough Fair

思路：这题真心签到啊，就按题意强行暴力模拟咯，对数组遍历，将对应字母修改，ok

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <string>
#include <queue>
#include <stack>

using namespace std;

const int maxn = 110;

char s[maxn];

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        scanf("%s",s);
        for(int i=0;i<m;i++)
        {
            int l,r;
            char c1,c2;
            scanf("%d%d %c %c",&l,&r,&c1,&c2);
            //cout << l << " " << r << " " << c1 << " " << c2 << endl;
            for(int j=l-1;j<r;j++)
            {
                //cout << s[j] << endl;
                if(s[j]==c1)
                {
                    s[j] = c2;
                }
            }
        }
        printf("%s\n",s);
    }
    return 0;
}

B. Chtholly's request

思路：这题的关键，就是长度为偶数的回文串的构造方法，写个按位操作，一旦构造出来之后，一切就好办了

不过一个小坑点就是有可能溢出，要long long，然而由于这次判的太慢了，我交完b，连c都差不多写完后，b的判题结果才下了，改完之后，b的分已经gg了，还是细节问题

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <string>
#include <queue>
#include <stack>

using namespace std;

const int maxn = 1e5+10;

long long a[18] = {1LL,10LL,100LL,1000LL,10000LL,100000LL,1000000LL,10000000LL,100000000LL,1000000000LL,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};

int main()
{
    int k,p;
    while(scanf("%d%d",&k,&p)!=EOF)
    {
        int len = 2;
        long long sum = 0;
        int pos2 = len/2,pos1 = pos2-1;
        long long num = 0;
        while(k--)
        {
            while(num/a[pos1]%10LL==9LL)
            {
                num -= 9LL * a[pos1];
                num -= 9LL * a[pos2];
                pos2++;
                pos1--;
                if(pos1<0)
                {
                    num = 1LL;
                    len += 2;
                    num += a[len-1];
                    pos2 = len/2;
                    pos1 = pos2-1;
                    num -= a[pos1];
                    num -= a[pos2];
                    break;
                }
            }
            num += a[pos1];
            num += a[pos2];
            pos2 = len/2;
            pos1 = pos2-1;
            //cout << num << endl;
            sum = (sum + num) % p;
        }
        printf("%d\n",sum);
    }
    return 0;
}

C. Nephren gives a riddle

思路：这题就是个深层迭代嵌套问题，看题型倒是有点类似于ccf的大模拟，经过之前ccsp的磨练，感觉倒是对这种题不太畏惧了，代码过程中时时检查，一遍过，最终有个可以接受的结果了吧

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <string>
#include <queue>
#include <stack>

using namespace std;

const int maxn = 1e5+10;

char f[] =  "What are you doing at the end of the world? Are you busy? Will you save us?";
char ff[] = "What are you doing while sending \"What are you doing at the end of the world? Are you busy? Will you save us?\"? Are you busy? Will you send \"What are you doing at the end of the world? Are you busy? Will you save us?\"?";
char fa[] = "What are you doing while sending \"\"? Are you busy? Will you send \"\"?";
char f1[] = "What are you doing while sending \"";
char f2[] = "\"? Are you busy? Will you send \"";

long long num[maxn];
long long len =  strlen(fa);
int pos1 = strlen(f1);
int pos2 = strlen(f2);

char game(int n,long long k)
{
    if(n==0)
    {
        if(k>num[0])
        {
            return '.';
        }
        else
        {
            return f[k-1];
        }
    }
    else
    {
        if(k>pos1)
        {
            k -= pos1;
        }
        else
        {
            return f1[k-1];
        }
        if(k>num[n-1])
        {
            k -= num[n-1];
        }
        else
        {
            return game(n-1,k);
        }
        if(k>pos2)
        {
            k -= pos2;
        }
        else
        {
            return f2[k-1];
        }
        if(k>num[n-1])
        {
            k -= num[n-1];
        }
        else
        {
            return game(n-1,k);
        }
        if(k==1)
        {
            return '"';
        }
        else if(k==2)
        {
            return '?';
        }
        else
        {
            return '.';
        }
    }
}

int main()
{
    //freopen("1.txt","r",stdin);
    int q;
    /*cout << strlen(f) << endl;
    cout << strlen(ff) << endl;
    cout << strlen(fa) << endl;
    cout << strlen(f1) << endl;*/
    num[0] = strlen(f);
    for(int i=1;;i++)
    {
        num[i] = 2*num[i-1] + len;
        if(num[i]>1e18)
        {
            break;
        }
        //cout << i << " " << num[i] << endl;
    }
    for(int i=53;i<=1e5;i++)
    {
        num[i] = 1e18+10;
    }
    while(scanf("%d",&q)!=EOF)
    {
        while(q--)
        {
            int n;
            long long k;
            scanf("%d%I64d",&n,&k);
            printf("%c",game(n,k));
        }
        printf("\n");
    }
    return 0;
}

*icpc加油

文章地址：http://blog.csdn.net/owen_q/article/details/78743213