Codeforces Round #449 (Div. 2)

传送门：http://codeforces.com/contest/897

A. Scarborough Fair

题意：给定长度为N的字符串，进行m次操作，每次将l−>r范围内为C1的字符改成C2，输出操作完的字符串。
思路：模拟即可。

#include<bits/stdc++.h>
using namespace std;
int main ()
{
    //yyy_3y
 //   freopen("1.in","r",stdin);
    int n ,m; cin >> n >> m;
    string s; cin >> s;
    for (int i = 1; i <= m; i++){
        char c1,c2;
        int l,r; cin >> l >> r >> c1 >> c2;
        for (int i = l - 1; i <= r - 1; i++){
            if (s[i] == c1) s[i] = c2;
        }
    }
    cout << s << endl;
    return 0;
}

B. Chtholly’s request

题意：前K个长度为偶数的回文数相加%p；
思路：可以直接构造zcy number回文串。

#include<bits/stdc++.h>
using namespace std;
long long a[110000];
int cnt = 1;
long long pp(long long ss)
{
    long long ans = 1;
    for (int i = 1; i <= ss; i++) ans = ans * 10;
    return ans;
}
void change (long long x)
{
    long long b = 0;
    long long tt = 0;
    long long temp = x;
    while (temp){
        b++;
        tt = tt*10 + temp % 10;
        temp = temp / 10;
    }
    x = x * pow (10,b) + tt;
    a[cnt++] = x;
}
int main ()
{
    //yyy_3y
    freopen("1.in","r",stdin);

    for (long long  i = 1; i <= 100010; i++){   //位数
        change(i);
    }
    long long sum = 0;
    int n ,k; cin >> n >> k;
    for (int i = 1; i <= n; i++){
        sum = (a[i] % k + sum) % k;
    }
    printf("%lld\n",sum);
    return 0;
}

C. Nephren gives a riddle

题意：　

S1: [What are you doing at the end of the world? Are you busy? Will you save us?]
S2: [What are you doing while sending “]
S3: [“? Are you busy? Will you send “]
S4: [“?]
（中括号内为给出的字符串，问号、引号、空格也算在内）

定义字符串f[0] = A，递推式f[n] = B + f[n-1] + C + f[n-1] + D

比如：

f[0] = [What are you doing at the end of the world? Are you busy? Will you save us?]

f[1] = [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?”?]

　　然后有q个询问，每个询问有两个整数n,k，让你输出f[n]的第k个字符。如果f[n]没有第k个字符，则输出’.’。
　　思路：递归。

#include <iostream>  
#include <stdio.h>  
#include <string.h>  
#include <queue>  
#include <vector>  
#include <array>  
#include <algorithm> 
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int N = 1e5+100;
ll len[N];
ll len1,len2,len3,len4;
const string s1 = "What are you doing at the end of the world? Are you busy? Will you save us?";
const string s2 = "What are you doing while sending \"";
const string s3 = "\"? Are you busy? Will you send \"";
const string s4 = "\"?";
void dfs(ll n, ll k)
{
    if(n==0) printf("%c",s1[k-1]);
    else if (k<=len2) printf("%c",s2[k-1]);
    else if(k<=len2+len[n-1]){
        k-=len2;
        dfs(n-1,k);
    }
    else if(k<=len2+len[n-1]+len3) printf("%c",s3[k-1-(len2+len[n-1])]);
    else if(k<=len2+len[n-1]+len3+len[n-1]){
         k=k-len2-len[n-1]-len3;
        dfs(n-1,k);
    }
    else {
         k=k-len2-len[n-1]*2-len3;
         printf("%c",s4[k-1]);
    }
}
int main ()
{
    // yyy_3y
    //freopen("1.in","r",stdin);
    len1=s1.length();
    len2=s2.length();
    len3=s3.length();
    len4=s4.length();
    len[0]=len1;
    for(int i=1;i<N-1;i++){
        len[i]=min(len2+len[i-1]+len3+len[i-1]+len4,inf);
    }
    ll q,n,k; scanf("%lld",&q);
    for(int i=1;i<=q;i++){
        scanf("%lld%lld",&n,&k);
        if(!n&&k<=len[0]) printf("%c",s1[k-1]);
        else if (k<=len[n]) dfs(n,k);
        else printf(".");
    }
    printf("\n");

}