Codeforces Round #641 (Div. 2)
只写了A~D
题意：f(n)就是n的第二小因数，问执行k次 n=f(n)+n 后的结果。
题解：如果一直找第二小的因子的话,1e9肯定得t。看下边样例解释就会惊奇的发现，执行次数多了，n一定会变成2的倍数，然后就可以剪枝了。如果n不是2的倍数，那么就执行 n=f(n)+n，k-- 直到n是2的倍数（当然k得>0），最后再加上k*2。
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 int main() 6 { 7 ios::sync_with_stdio(false); 8 cin.tie(0); 9 cout.tie(0); 10 int t; 11 cin>>t; 12 while(t--){ 13 ll n,k; 14 cin>>n>>k; 15 while(k){ 16 if(n%2==0) break; 17 for(ll i=2;i<=n;i++){ 18 if(n%i==0){ 19 n+=i; 20 break; 21 } 22 } 23 k--; 24 } 25 n=n+k*2; 26 cout<<n<<endl; 27 } 28 return 0; 29 }
题意：让你找出一个序列使得他在原序列满足一下条件 i%j==0&&a[i]>a[j]; 问最长的序列长度
题解：找1~n每个数当因子时最长的符合条件的序列。
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 ll a[100100]; 6 ll dp[100100]; 7 8 int main() 9 { 10 ios::sync_with_stdio(false); 11 cin.tie(0); 12 cout.tie(0); 13 ll t; 14 cin>>t; 15 while(t--){ 16 ll n; 17 cin>>n; 18 for(ll i=1;i<=n;i++) cin>>a[i]; 19 ll ans=0 ; 20 for (ll i=n;i>=1;i--){ 21 dp[i]=1; 22 for (ll j=i;j<=n;j+=i){ 23 if(a[j]>a[i]) 24 dp[i]=max(dp[i],dp[j]+1); 25 } 26 ans = max(dp[i],ans); 27 } 28 cout<<ans<<endl; 29 } 30 return 0; 31 }
题意：求这个序列所有数两两之间的 lcm 的 gcd。
题解：和a1 lcm 后的所有数的 gcd 就是lcm(a1,gcd(a2,a3, ......))，a2就是lcm(a2,gcd(a3,a4, ......)).....，然后再把这些数就行gcd
证明结论：
gcd( lcm (a,b), lcm(a,c) )
= gcd( a*b/gcd(a,b), a*c/gcd(a,c) )
= a*gcd( b/gcd(a,b), c/gcd(a,c) )；
lcm( a, gcd(b, c) )=a*gcd(b, c) / gcd(a,gcd(b, c))；
最大公约数的百度百科的性质那一栏也能找到这个结论。
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 ll a[100100]; 6 ll p[200100]; 7 8 int main() 9 { 10 ios::sync_with_stdio(false); 11 cin.tie(0); 12 cout.tie(0); 13 ll n; 14 cin>>n; 15 for(ll i=1;i<=n;i++) cin>>a[i]; 16 ll ans; 17 p[n]=a[n]; 18 for(ll i=n-1;i>0;i--){ 19 p[i]=__gcd(p[i+1],a[i]); 20 } 21 ans=a[1]*p[2]/__gcd(a[1],p[2]); 22 for(ll i=2;i<=n;i++){ 23 ans=__gcd(ans,p[i+1]*a[i]/__gcd(a[i],p[i+1])); 24 } 25 cout<<ans<<endl; 26 return 0; 27 }
题意：数组里一段数可以都变成他的中位数，问整个序列能不能变成k。
题解：
①判断一下序列里是否有k这个数，没有的话就直接输出no；
②如果整个序列 >=k 的个数比 <k 的个数多，就输出yes；
③判断一下序列里是否有一段长度>2的连续子序列使得 >=k 的个数比 <k 的个数多，有的话就输出yes，没有就输出no；（代码略丑）
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 int a[100100]; 6 int p[100100]; 7 8 int main() 9 { 10 ios::sync_with_stdio(false); 11 cin.tie(0); 12 cout.tie(0); 13 int t; 14 cin>>t; 15 while(t--){ 16 int n,k; 17 cin>>n>>k; 18 for(int i=1;i<=n;i++) cin>>a[i],p[i]=0; 19 int flag=0; 20 for(int i=1;i<=n;i++){ 21 if(a[i]==k) flag=1; 22 if(a[i]>=k) p[i]=1; 23 else p[i]=-1; 24 } 25 if(!flag) {cout<<"no"<<endl;continue;} 26 flag=0; 27 for(int i=1;i<=n;i++){ 28 p[i]+=p[i-1]; 29 } 30 if(p[n]>0) flag=1; 31 int minn=p[0]; 32 for(int i=2;i<=n;i++){ 33 if(p[i]>minn){ 34 flag=1; 35 break; 36 } 37 if(p[i-1]<minn){ 38 minn=p[i-1]; 39 } 40 } 41 if(!flag) {cout<<"no"<<endl;continue;} 42 cout<<"yes"<<endl; 43 } 44 return 0; 45 }
