A.Maximize?
总共 t 组测试数据,每组测试数据给定一个 x ,已知 y∈[1,x) ,求出最大的 gcd(x,y)+y 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| #include<bits/stdc++.h> using namespace std; const int N=105; int n; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int main(){ int t; cin>>t; while(t--){ int x; cin>>x; int ans=0,y; for(int i=1;i<x;i++){ if(ans<=gcd(x,i)+i){ ans=gcd(x,i)+i; y=i; } } cout<<y<<endl; } return 0; }
|
B.Prefiquence
总共 t 组测试数据,每组测试数据给定 n 和 m ,和长度分别为 n 和 m 的 两个字符串 a 和 b ,a 可以由 b 删除几个元素得到,求字符串 a 的前缀是字符串 b 的子序列的最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int main(){ int t; cin>>t; while(t--){ int n,m; string a,b; cin>>n>>m>>a>>b; int p=0,ans=0; for(int i=0;i<a.length();i++){ p=b.find(a[i],p); if(p<m && p>=0 && i!=n-1){ p+=1; ans++; } } if(p<m && p>=0){ p+=1; ans++; } cout<<ans<<endl; } return 0; }
|