codeforces Educational Codeforces Round 53部分题解

交题的时候断网是真的坑…
A题：

A. Diverse Substring

A substring of string s is a continuous segment of letters from s.
For example, “defor” is a substring of “codeforces” and “fors” is not.
The length of the substring is the number of letters in it.

Let’s call some string of length diverse if and only if there is no letter to appear strictly more than 2 times. For example, strings “abc” and “iltlml” are diverse and strings “aab” and “zz” are not.

Your task is to find any diverse substring of string s
or report that there is none. Note that it is not required to maximize or minimize the length of the resulting substring.
根据题意只要存在两个连续不相同字符就一定可以满足条件，直接遍历一遍即可。

#include <bits/stdc++.h>
using namespace std;
#define maxn 1005
#define ll long long
char str[maxn];
int main()
{
    int n;
    cin>>n;
    scanf("%s",str);
    bool seven=false;
    for(int i=1;i<n;i++)
    {
        if(str[i]!=str[i-1])
        {
            seven=true;
            printf("YES\n");
            printf("%c%c\n",str[i-1],str[i]);
            break;
        }
    }
    if(!seven)
        cout<<"NO\n";
    return 0;
}

B. Vasya and Books

Vasya has got n books, numbered from 1 to n, arranged in a stack. The topmost book has number a1, the next one — a2, and so on. The book at the bottom of the stack has number an. All numbers are distinct.

Vasya wants to move all the books to his backpack in n steps. During i-th step he wants to move the book number bi into his backpack. If the book with number bi is in the stack, he takes this book and all the books above the book bi, and puts them into the backpack; otherwise he does nothing and begins the next step. For example, if books are arranged in the order [1,2,3] (book 1 is the topmost), and Vasya moves the books in the order [2,1,3], then during the first step he will move two books (1 and 2), during the second step he will do nothing (since book 1 is already in the backpack), and during the third step — one book (the book number 3). Note that b1,b2,…,bn are distinct.

Help Vasya! Tell him the number of books he will put into his backpack during each step.
根据题意模拟一下即可，已经出栈的书不可能在进入，所以时间复杂度为O（n）

#include <bits/stdc++.h>
using namespace std;
#define maxn 200005
#define ll long long
int num[maxn],a[maxn],b[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),num[i]=1;
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    int now=1;
    for(int i=1;i<=n;i++)
    {
        if(num[b[i]]==0)
            printf("0");
        else
        {
            int sum=0;
            while(1)
            {
                sum++;
                num[a[now]]=0;
                now++;
                if(a[now-1]==b[i])
                    break;
            }
            printf("%d",sum);
        }
        if(i!=n)
            cout<<" ";
    }
    return 0;
}

C题：

C. Vasya and Robot

Vasya has got a robot which is situated on an infinite Cartesian plane, initially in the cell (0,0). Robot can perform the following four kinds of operations:

U — move from (x,y) to (x,y+1);
D — move from (x,y) to (x,y−1);
L — move from (x,y) to (x−1,y);
R — move from (x,y) to (x+1,y).
Vasya also has got a sequence of n operations. Vasya wants to modify this sequence so after performing it the robot will end up in (x,y).

Vasya wants to change the sequence so the length of changed subsegment is minimum possible. This length can be calculated as follows: maxID−minID+1, where maxID is the maximum index of a changed operation, and minID is the minimum index of a changed operation. For example, if Vasya changes RRRRRRR to RLRRLRL, then the operations with indices 2, 5 and 7 are changed, so the length of changed subsegment is 7−2+1=6. Another example: if Vasya changes DDDD to DDRD, then the length of changed subsegment is 1.

If there are no changes, then the length of changed subsegment is 0. Changing an operation means replacing it with some operation (possibly the same); Vasya can’t insert new operations into the sequence or remove them.

Help Vasya! Tell him the minimum length of subsegment that he needs to change so that the robot will go from (0,0) to (x,y), or tell him that it’s impossible.

二分好题，因为题目未限制改变的个数，而显然，对于原序列来说，改变个数越多越容易满足题意，所以对于每个长为L的区间我完全可以全部改变去看是否满足题意。注意到如果改变一段长为L的数列无法满足题意，那么改变L-1的长度也一定不可以满足题意，假设若存在L-1的区间使得题意满足，设可行区间为[l,r]，那么[l,r+1]一定也是可行区间，和题设矛盾，所以不存在这样长度为L-1的区间。于是二分枚举L即可。

另外judge函数根据x和y的值以及奇偶性去判断是否可行，可以自己画一画。
注意特判答案为-1和0的情况。

#include <bits/stdc++.h>
using namespace std;
#define maxn 200005
#define ll long long
char str[maxn];
int len,x,y,u[maxn],d[maxn],l[maxn],r[maxn];
bool judge(int key)
{
    for(int i=1;i+key-1<=len;i++)
    {
        int up=i+key-1;
        int L=l[len]-l[up]+l[i-1];
        int R=r[len]-r[up]+r[i-1];
        int U=u[len]-u[up]+u[i-1];
        int D=d[len]-d[up]+d[i-1];
        int sum=(abs(x-(R-L)))+(abs(y-(U-D)));
        if(sum>key)
            continue;
        if((key-sum)%2==0)//奇数的情况一定不可以
            return true;
    }
    return false;
}
int main()
{
    scanf("%d",&len);
    scanf("%s",str+1);
    for(int i=1;i<=len;i++)
    {
        r[i]=r[i-1];
        l[i]=l[i-1];
        d[i]=d[i-1];
        u[i]=u[i-1];
        if(str[i]=='R')
            r[i]++;
        else if(str[i]=='L')
            l[i]++;
        else if(str[i]=='U')
            u[i]++;
        else
            d[i]++;
    }
    scanf("%d%d",&x,&y);
    if(abs(x)+abs(y)>len)
    {
        printf("-1\n");
        return 0;
    }
    if((len-x-y)%2!=0)
    {
        printf("-1\n");
        return 0;
    }
    if(r[len]-l[len]==x&&u[len]-d[len]==y)
    {
        printf("0\n");
        return 0;
    }
    int l=1,r=len;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(judge(mid))
            r=mid-1;
        else
            l=mid+1;
    }
    printf("%d\n",r+1);
    return 0;
}

D. Berland Fair

XXI Berland Annual Fair is coming really soon! Traditionally fair consists of n booths, arranged in a circle. The booths are numbered 1 through n clockwise with n being adjacent to 1. The i-th booths sells some candies for the price of ai burles per item. Each booth has an unlimited supply of candies.

Polycarp has decided to spend at most T burles at the fair. However, he has some plan in mind for his path across the booths:

at first, he visits booth number 1;
if he has enough burles to buy exactly one candy from the current booth, then he buys it immediately;
then he proceeds to the next booth in the clockwise order (regardless of if he bought a candy or not).
Polycarp’s money is finite, thus the process will end once he can no longer buy candy at any booth.

Calculate the number of candies Polycarp will buy.

很纳闷为什么这题可以在D的位置上…首先暴力模拟不可取，会炸的妈都不认识，考虑到一圈一圈的购买有循环性，所以每次可以买一圈时，就买，发现买不了一圈了，就重新遍历一遍商店开始新一轮的购买，知道手中的钱＜商店最小值为止…

感觉这题比C题简单多了，就是个不那么暴力的暴力，感觉会tle，然而跑的还超快…

#include <bits/stdc++.h>
using namespace std;
#define maxn 200005
#define ll long long
int n;
ll num[maxn],sum,Min;
int main()
{
    scanf("%d%lld",&n,&sum);
    for(int i=1;i<=n;i++)
        scanf("%lld",&num[i]);
    Min=num[1];
    for(int i=1;i<=n;i++)
        Min=min(Min,num[i]);
    ll ans=0;
    while(sum>=Min)
    {
        ll key=0,p=0;
        for(int i=1;i<=n;i++)
        {
            if(sum>=num[i])
            {
                key++;
                sum-=num[i];
                p+=num[i];
            }
        }
        ans+=key;
        ans=ans+(sum/p)*key;
        sum%=p;
    }
    printf("%lld\n",ans);
    return 0;
}

E. Segment Sum

You are given two integers l and r (l≤r). Your task is to calculate the sum of numbers from l to r (including l and r) such that each number contains at most k different digits, and print this sum modulo 998244353.

For example, if k=1 then you have to calculate all numbers from l to r such that each number is formed using only one digit. For l=10,r=50 the answer is 11+22+33+44=110.

Input
The only line of the input contains three integers l, r and k (1≤l≤r<1018,1≤k≤10) — the borders of the segment and the maximum number of different digits.

Output
Print one integer — the sum of numbers from l to r such that each number contains at most k different digits, modulo 998244353.

数位dp+状压，dp数组要开结构体，保存数字个数和总和，dp[i][j][k]代表处理到第i位时现在已有的数字状态为j，j的值为1到1024-1，因为可能出现的数字只有0-9,2进制压一下就好，k代表最多出现k个数字，这一维可以去掉因为CF是单组数据。

处理数字总和时，枚举当前位为now，现在是第num位，那么这里的数字总和就是pow(10,now-1)*前面数字个数+前面数字总和，所以才要保存个数和总和。感觉还是挺套路的。

另外注意前导零不是真的0，不能状压到1那一位的，要处理一下。

#include <bits/stdc++.h>
using namespace std;
#define maxn 4096
#define ll long long
const ll mod=998244353;
int sum[maxn];//每一个数存在1的个数，也就是出现了多少个不同的数
ll ten[25];//处理10的幂
int ca(int now)
{
    int ans=0;
    while(now>0)
    {
        if(now&1)
            ans++;
        now>>=1;
    }
    return ans;
}
ll digit[20];
struct DP
{
    ll amount,fin;
}dp[25][maxn][15];
DP dfs(int now,int flag,int ds,ll k,int zero)//zero处理是否是前导0
{
    if(!flag&&dp[now][ds][k].amount!=-1&&dp[now][ds][k].fin!=-1)
        return dp[now][ds][k];
    if(now==0)
    {
        DP s;
        if(sum[ds]<=k)
        {
            s.amount=1;
            s.fin=0;
            return s;
        }
        s.amount=s.fin=0;
        return s;
    }
    int up;
    if(flag==1)
        up=digit[now];
    else
        up=9;
    ll A=0,F=0;
    for(ll i=0;i<=up;i++)
    {
        int nz=zero;
        if(i!=0)
           nz=1;
        int nds=ds;
        if(nz)
            nds=nds|(1<<i);
        DP next=dfs(now-1,flag&(i==up),nds,k,nz);
        A+=next.amount;
        A%=mod;
        F=(F+(i*ten[now-1]%mod*next.amount%mod)+next.fin)%mod;
    }
    if(!flag)
    {
        dp[now][ds][k].amount=A;
        dp[now][ds][k].fin=F;
    }
    DP re;
    re.amount=A;
    re.fin=F;
    return re;
}
ll cal(ll num,ll k)
{
    if(num==0)
        return 0;
    int cnt=0;
    while(num>0)
    {
        digit[++cnt]=num%10;
        num/=10;
    }
    return dfs(cnt,1,0,k,0).fin;
}
int main()
{
    for(int i=0;i<=2000;i++)
        sum[i]=ca(i);
    ten[0]=1;
    for(int i=1;i<=20;i++)
        ten[i]=ten[i-1]*10%mod;
    ll l,r,k;
    scanf("%lld%lld%lld",&l,&r,&k);
    for(int i=0;i<=20;i++)
    {
        for(int j=0;j<2000;j++)
        {
            for(int K=1;K<=k;K++)
                dp[i][j][k].amount=dp[i][j][k].fin=-1;
        }
    }
    printf("%lld\n",(cal(r,k)-cal(l-1,k)+mod)%mod);
    return 0;
}