Educational Codeforces Round 81 (Rated for Div. 2)
A. Display The Number
题意：
告诉你摆出每个数字需要的火柴数，现在给你n跟火柴问能摆出的最大数字是多少
思路：
①当n为奇数：7111..
②当n为偶数：1111..
#include<iostream> #include<algorithm> #include<cstring> using namespace std; int main() { int t,n; scanf("%d",&t); while(t--){ scanf("%d",&n); if(n%2==0){ for(int i=1;i<=n/2;i++) cout<<1; cout<<endl; continue; } else{ cout<<7; for(int i=1;i<=(n-3)/2;i++) cout<<1; cout<<endl; continue; } } return 0; }
B. Infinite Prefixes
题意：
给出一个字符串01串s，s可以无限次重复（例如s=010，可以重复为010010..），给出一个x，求出满足cnt0(串中0的个数)-cnt1(串中1的个数)=x的串的个数，如果有无限个，输出-1
思路:
记cnt[i]=cnt0(i)-cnt1(i)（从0-i位置中，0的个数与1的个数的差值）
①首先考虑无限的情况：如果cnt[n-1]=0并且子串中有cnt[i]=x的情况，则为无限次
②没有无限的情况下，遍历整个串，如果(x-cnt[i])%cnt[n-1]==0&&(x-cnt[i])/x>=0(判断是否同号，注意x为负数的情况),则ans++
③还要考虑x=0的情况，ans要再加上1
#include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int maxn=1e5+10; char s[maxn]; int t,n,x,a[maxn]; int main() { scanf("%d",&t); while(t--){ int cnt=0; scanf("%d%d%s",&n,&x,s); for(int i=0;i<n;i++){ if(s[i]=='0') cnt++; else cnt--; a[i]=cnt; } int ans=0,temp; if(!x) ans++; if(cnt==0){ int flag=0; for(int i=0;i<n;i++){ if(a[i]==x){ flag=1; ans=-1; } } } else{ int k=a[n-1]; for(int i=0;i<n;i++){ temp=x-a[i]; if(temp%k==0&&temp/k>=0) ans++; } } cout<<ans<<endl; } return 0; }
C. Obtain The String
题意：
给出两个字符串s与t，每次可以从s中取出一个字序列(注意不是子串)加到一个字符串的末尾，问最少执行多少次取出操作能构成t，不能组成t输出-1
思路：
定义nx[i][j]为在位置i下一个j的位置在哪，可以通过last数组用dp得到(last[i]为i字符上一次出现的位置，初始化为n+1)
之后只需要通过循环利用nxt数组将t数组遍历一遍即可，不能组成t数组的条件为last[i]=n-1
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int maxn=1e5+10; int nxt[maxn][26],last[26],n,T,h; char s[maxn],t[maxn]; int main() { scanf("%d",&T); while(T--){ cin>>s+1>>t+1; int len1=strlen(s+1),len2=strlen(t+1); for(int i=0;i<26;i++) last[i]=len1+1; for(int i=len1;i>=0;i--){ for(int j=0;j<26;j++) nxt[i][j]=last[j]; last[s[i]-'a']=i; } int pos=0,ans=0,now=1; while(now<=len2){ if(last[t[now]-'a']==len1+1){ ans=-1; break; } pos=0; while(nxt[pos][t[now]-'a']<=len1&&now<=len2){ pos=nxt[pos][t[now]-'a']; now++; } ans++; } cout<<ans<<endl; } return 0; }
查看10道真题和解析
