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 }

B - Orac and Models

题意：让你找出一个序列使得他在原序列满足一下条件 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 }

C - Orac and LCM

题意：求这个序列所有数两两之间的 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 }

D - Orac and Medians

题意：数组里一段数可以都变成他的中位数，问整个序列能不能变成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 }

巴特西

Codeforces Round #641 (Div. 2)

最新文章

热门文章