Codeforces Round #641 (Div. 2)（数论）数据结构与算法CDreamy的博客-

A. Orac and Factors

比赛的时候用预处理死活过不了（现在也没发现错误）

错误代码 ：

     #include <bits/stdc++.h>     #define rush() int T;cin>>T;while(T--)     #define go(a) while(cin>>a)     #define ms(a,b) memset(a,b,sizeof a)     #define E 1e-8     using namespace std;     typedef long long ll;     const int N=9e6+5;          int n,m,t,_;         int i,j,k;         int vis[N];         string s;      int main()     {         cin.tie(0);         iostream::sync_with_stdio(false);          /*for(i=2;i<=3e3;i++){             if(!vis[i]){                 for(j=2*i;j<N;j+=i){                     vis[j]=i;                 }             }         }*/         for(i=2;i<N;i++){             if(!vis[i]){                 for(j=i;j<N;j+=i){                     if(!vis[j]) vis[j]=i;//必须加判断，保证最小质因数                 }             }         }          rush()         {             ll n,k,i;             cin>>n>>k;             for(i=1;;i++){                 if(i>k) break;                 if(n & 1){                     if(!vis[n]) n<<=1;                     else n+=vis[n];                     i++;                     break;                 }                 else break;             }             if(i!=k+1){                 ll num=k-i+1;                 n+=(num<<1);             }             cout<<n<<endl;         }         return 0;     }

 正确（暴力）代码：

 #include <bits/stdc++.h> #define rush() int T;cin>>T;while(T--) #define go(a) while(cin>>a) #define ms(a,b) memset(a,b,sizeof a) #define E 1e-8 using namespace std; typedef long long ll; const int N=1e5+5;      int n,m,t,_;     int i,j,k;     int a[N];     string s;  int main() {     cin.tie(0);     iostream::sync_with_stdio(false);     rush()     {         ll n,k,ans=0;         cin>>n>>k;         for(i=2;i<=(int)sqrt(n+0.5);i++){             if(n%i==0){                 ans=i;                 break;             }         }         if(ans==0) ans=n;         n+=ans;         n+=((k-1)<<1);         cout<<n<<endl;     }     return 0; }

B. Orac and Model

题目大意：（dp）

求下标单调递增且互为倍数，且满足若i>j,且  si>sj  的最长子序列

 #pragma GCC optimize(2) #include <bits/stdc++.h> #define rush() int T;cin>>T;while(T--) #define go(a) while(cin>>a) #define ms(a,b) memset(a,b,sizeof a) #define E 1e-8 using namespace std; typedef long long ll; const int N=1e5+5;      int n,m,t,_;     int i,j,k;     ll a[N];     ll dp[N];//坐标以 i 为结尾满足条件的最大个数     vector<int>v[N];     string s;  int main() {     cin.tie(0);     iostream::sync_with_stdio(false);     rush()     {         cin>>n;         for(i=1;i<=n;i++) v[i].clear();         for(i=1;i<=n;i++) cin>>a[i];         for(i=1;i<=n;i++){             for(j=i*2;j<=n;j+=i){  //下标为倍数                 if(a[j]>a[i]){  //值要大                     v[j].push_back(i);                 }             }         }          ll maxx=0;         for(i=1;i<=n;i++){             dp[i]=1;             for(int j:v[i]){                 dp[i]=max(dp[i],dp[j]+1);             }             maxx=max(maxx,dp[i]);         }         cout<<maxx<<endl;     }     return 0; }

D. Orac and Medians

题目大意： （思维）

你可以使任意一个子区间的数变为该子区间的中位数，问可不可以使得序列最后都变为k

题解：如果不存在k，显然不成立。

若存在，则在其任意两个单位前后若有   a[i]>=k,则成立

证明：我们取  a[i]==k 的右区间，若 a[i+1]>=k 则 i—-i+1 可以变成k，然后扩散

若a[i+2]>=k,讨论  a[i+1] ,当他小于k时，三个数中 中位数为k，当其>=k时，满足a[i+1]>=k的上述条件，成立

但这样还是差一点，当存在三个数的区间内有两个数或更多的数满足  有两个数 >k 的条件时，这个区间便可以扩散，直至遇到k

证毕

 #pragma GCC optimize(2) #include <bits/stdc++.h> #define rush() int T;cin>>T;while(T--) #define go(a) while(cin>>a) #define ms(a,b) memset(a,b,sizeof a) #define E 1e-8 using namespace std; typedef long long ll; const int N=1e5+5;      int n,m,t,_;     int i,j,k;     ll a[N];     string s;  int main() {     cin.tie(0);     iostream::sync_with_stdio(false);     rush()     {         ll n,k;         bool f=0,f1=0;         cin>>n>>k;         for(i=1;i<=n;i++){             cin>>a[i];             if(a[i]==k){                 f=1;             }         }         if(n==1&&f){//特判             cout<<"yes"<<endl;             continue;         }         if(f==0){             cout<<"no"<<endl;             continue;         }          for(i=1;i<=n;i++){             if(a[i]>=k){                 if((i+2<=n&&a[i+2]>=k) || (i+1<=n&&a[i+1]>=k)) f1=1;             }         }         if(f1){             cout<<"yes"<<endl;         }         else{             cout<<"no"<<endl;         }     }     return 0; }