感觉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,ch,154,int,len,while,Rated,getchar,数列 From： https://www.cnblogs.com/burutaofan/p/17673069.html