感觉edu的题目都比较有新意；
A.Prime Deletion
题意：给定长度为9的数，且1-9每个数字出现一次，求按照原定顺序选几个数组成的质数（起码选择两个）；
下意识写了一个dfs，过了；
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 char ch=getchar();int x=0,f=1; 5 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 6 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 7 return x*f; 8 } 9 int T,num; 10 int A[20],ans; 11 12 bool pd(int x){ 13 if(x<10)return false; 14 for(int i=2;i*i<=x;i++){ 15 if(x%i==0)return false; 16 } 17 return true; 18 } 19 void dfs(int x,int now){ 20 if(x==10){ 21 if(pd(now))ans=now; 22 return ; 23 } 24 dfs(x+1,now*10+A[x]); 25 dfs(x+1,now); 26 } 27 int main(){ 28 T=read(); 29 while(T--){ 30 num=read(); 31 for(int i=9;i>=1;i--){ 32 A[i]=num%10;num=num/10; 33 } 34 ans=0; 35 dfs(1,0); 36 if(ans==0){ 37 cout<<"-1"<<endl;continue; 38 } 39 cout<<ans<<endl; 40 } 41 return 0; 42 }
但是注意到特殊的性质：1-9每个数都会出现一次，那么对于一个数，我们一定能从里面选出13或者31（37和73等同理），这两个数都是质数，故我们只需判断1和3出现的相对顺序；
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 char ch=getchar();int x=0,f=1; 5 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 6 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 7 return x*f; 8 } 9 int T,num; 10 int ans; 11 int main(){ 12 T=read(); 13 while(T--){ 14 num=read(); 15 while(num){ 16 if(num%10==1){ 17 cout<<"31"<<endl;break; 18 } 19 if(num%10==3){ 20 cout<<"13"<<endl;break; 21 } 22 num=num/10; 23 } 24 } 25 return 0; 26 } 27
B.Two Binary Strings
题意：给定两个长度相同的01串（一定是0开头1结尾） a 和 b ，可以任选 a [ i ] = a [ j ]，使得 a [ x ] = a [ i ] = a [ j ] ，i <= x <= j ；或 b [ i ] = b [ j ]，使得 b [ x ] = b [ i ] = b [ j ] ，i <= x <= j ；问经过若干次变化能不能让 a 和 b 相等；
对于 a [ x ] ！= b [ x ]，需要找到 i <= x <= j，使得 a [ i ] = a [ j ] = b [ i ] = b [ j ]，就能使得这一段都相同；那么我们不妨找到相邻的01，就可以直接将 a 和 b 转换成相同的01串（前面全是0后面全是1）；
当然，注意不一定要修改，可能只有第一个是0或只有最后一个是1；
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 char ch=getchar();int x=0,f=1; 5 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 6 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 7 return x*f; 8 } 9 const int maxn=5005; 10 int T,len,l,r; 11 int A[maxn],B[maxn]; 12 bool ans; 13 string a,b; 14 int main(){ 15 T=read(); 16 while(T--){ 17 cin>>a>>b; 18 len=a.size();ans=false; 19 for(int i=1;i<=len;i++){ 20 A[i]=a[i-1]-'0';B[i]=b[i-1]-'0'; 21 } 22 for(int i=1;i<=len;i++){ 23 if(A[i]==B[i]&&A[i+1]==B[i+1]&&A[i]==0&&A[i+1]==1)ans=true; 24 } 25 for(int i=1;i<=len;i++)A[i]=B[i]=0; 26 if(ans==true)cout<<"YES"<<endl; 27 if(ans==false)cout<<"NO"<<endl; 28 } 29 return 0; 30 }
C.Queries for the Array
题意：给定一个字符串，包含+，-，0，1；+代表末尾插入一个数，-代表删去末尾的数，0表示数列不是递增的，1表示数列是递增的，给定你一个字符串，让你判断是否合理；
看了四五个好友的提交，一个都看不懂，于是嗯写，wa了三发，然后过了；
因为增加和删去都是从末尾进行，所以我们不妨用b [ len ] 代表长度为len时数列的单调性；
b [ len ] = 1代表数列时递增的；b [ len ] = -1代表数列是递减的；b [ len ] = 0代表数列长度为len时没有要求；
注意到只有+，-的操作会改变数列的单调性；
加入一个数，原本有单调性的数列不一定有单调性，原本无单调性的数列一定还是没有单调性；
删去一个数，原本有单调性的数列一定还是有单调性，原本无单调性的数列可能有单调性；
且长度小于等于1的数列一定有单调性，数列的长度不能小于0；
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 char ch=getchar();int x=0,f=1; 5 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 6 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 7 return x*f; 8 } 9 const int maxn=2e5+5; 10 int T,N,len; 11 bool ans; 12 int b[maxn]; 13 string a; 14 15 int main(){ 16 T=read(); 17 while(T--){ 18 cin>>a; 19 N=a.size();len=0;ans=true; 20 b[0]=1;b[1]=1; 21 for(int i=1;i<=N;i++){ 22 if(a[i-1]=='+'){ 23 if(b[len]==-1)b[len+1]=-1; 24 len++; 25 } 26 if(a[i-1]=='-'){ 27 if(b[len]==1&&len>=2){ 28 b[len]=0;b[len-1]=1; 29 } 30 if(b[len]==-1){ 31 b[len]=0; 32 } 33 len--; 34 if(len<0){ 35 ans=false;break; 36 } 37 } 38 if(a[i-1]=='1'){ 39 if(b[len]==-1){ 40 ans=false;break; 41 } 42 b[len]=1; 43 } 44 if(a[i-1]=='0'){ 45 if(len<2){ 46 ans=false;break; 47 } 48 if(b[len]==1){ 49 ans=false;break; 50 } 51 b[len]=-1; 52 } 53 } 54 for(int i=0;i<=N;i++)b[i]=0; 55 if(ans==true){ 56 cout<<"YES"<<endl; 57 } 58 if(ans==false){ 59 cout<<"NO"<<endl; 60 } 61 } 62 return 0; 63 } 64
D.Sorting By Multiplication
题意：对于给定的数列，每一次给定三个数 l , r , x ；对于 l <= i <= r ，所有的 A [ i ] = A [ i ] * x（x可以小于0）；问最少操作多少次可以让原数列严格单调递增；
如果要把连续 len 个数变成单调递增的，那么如果存在 A [ i ] >= A [ i + 1 ]就需要把 A [ i+1 ] 到 A [ len ] 全部乘上一个很大的数 ；
由于 x 可以小于 0 ，我们可以用类似的方法乘正数使得其递减；我们可以把数列分成两个部分，前面的部分递减（乘上 -1 后递增），后面的部分递增，然后枚举分界点取最小值；
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 ll read(){ 5 char ch=getchar();ll x=0,f=1; 6 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 8 return x*f; 9 } 10 const int maxn=2e5+5; 11 ll T,N,ans; 12 ll A[maxn],l[maxn],r[maxn]; 13 int main(){ 14 T=read(); 15 while(T--){ 16 N=read(); 17 for(int i=1;i<=N;i++){ 18 A[i]=read(); 19 } 20 for(int i=2;i<=N;i++){ 21 l[i]=l[i-1]; 22 if(A[i-1]<=A[i])l[i]++; 23 } 24 for(int i=N-1;i>=1;i--){ 25 r[i]=r[i+1]; 26 if(A[i]>=A[i+1])r[i]++; 27 } 28 ans=min(r[1],l[N]+1); 29 for(int i=1;i<N;i++){ 30 ans=min(ans,l[i]+r[i+1]+1); 31 } 32 cout<<ans<<endl; 33 for(int i=0;i<=N+1;i++){ 34 A[i]=0; 35 l[i]=0;r[i]=0; 36 } 37 } 38 return 0; 39 } 40
- Educational Codeforces Round Rated 154educational codeforces round rated round codeforces rated based educational codeforces round 151 construction educational codeforces round educational codeforces round 147 cf-educational educational codeforces round educational codeforces round 158 educational codeforces contest round educational codeforces monsters round educational codeforces balance round