<span>Codeforces Round #641 (Div. 2) </span>

只写了A~D

A - Orac and Factors

题意: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 }

 

全部评论

相关推荐

06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
06-23 11:43
门头沟学院 Java
allin校招的烤冷...:我靠,今天中午我也是这个hr隔一个星期发消息给我。问的问题还是一模一样的😅
点赞 评论 收藏
分享
找到实习了&nbsp;给了150一天&nbsp;但是说是低代码&nbsp;值得去吗
码农索隆:是在没实习,可去,待个一两周,不行就润呗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务