A. Orac and Factors
题意：每次 N 加上N的最小质因子，执行M次
题解：暴力模拟。先判断是不是质数，来减少时间，然后在M次执行中，N可能会成为偶数X，那么，接下来的质因子都为2，那么就是X+=2*T，T代表剩余多少次操作
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <vector> #include <map> #include <set> #include <list> #include <deque> #include <queue> #include <stack> #include <cstdlib> #include <cstdio> #include <cmath> #include <iomanip> #define ull unsigned long long #define ll long long #define pb push_back #define all(vc) vc.begin() , vc.end() #define rep(i,start,end) for(int i=start;i<=end;i++) #define per(i,end,start) for(int i=end;i>=start;i--) #define tle ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define lc now<<1 #define rc now<<1|1 ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } using namespace std; const int mod = 998244353; const int mxn = 1e6 +7; int _,n,m,t,k,u,v,ans,cnt,ok,lim,len,tmp; int pre[mxn] , head[mxn]; struct node {int u,v,w,nx;}e[mxn]; bool vis[mxn]; bool isPrime_3(int num) { if(num==1) return 0; if(num==2||num==3) return 1; if(num%6!=1&&num%6!=5) return 0; int tmp=sqrt(num); for(int i=5;i<=tmp;i+=6) if(num%i==0||num%(i+2)==0) return 0; return 1; } int main() { for(cin>>t;t;t--) { cin>>n>>m; if(n%2==0) cout<<n+(m*2)<<endl; else { if(isPrime_3(n)) n+=n , m--; for(int i=2;i<=n;i++) { if(n%i==0) { m--; n+=i; if(n%2==0){ n+=m*2; break; } } } cout<<n<<endl; } } }
B - Orac and Models
题意：在满足下标成倍数增长的情况下，找到最长的上升序列，
题解：DP的思想，每次更新下标X的倍数，n*logn，不会T，然后每次对第一个数进行特判
外引：Alyona and Spreadsheet ，思路的话可以看看这个题，最近做题遇见的，算思想类似题
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <vector> #include <map> #include <set> #include <list> #include <deque> #include <queue> #include <stack> #include <cstdlib> #include <cstdio> #include <cmath> #include <iomanip> #define ull unsigned long long #define ll long long #define pb push_back #define all(vc) vc.begin() , vc.end() #define rep(i,start,end) for(int i=start;i<=end;i++) #define per(i,end,start) for(int i=end;i>=start;i--) #define tle ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define lc now<<1 #define rc now<<1|1 ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } using namespace std; const int mod = 998244353; const int mxn = 2e5 +7; int _,n,m,t,k,u,v,ans,cnt,ok,lim,len,tmp; int a[mxn] , c[mxn] , b[mxn]; struct node {int u,v,w,nx;}e[mxn]; bool vis[mxn]; int main() { for(cin>>t;t;t--) { cin>>n; for(int i=1;i<=n;i++) cin>>a[i] ,b[i] = 1 ; for(int i=2;i<=n;i++) { int tmp = a[i]; if(a[i]>a[1]) b[i] = max(b[i],2); for(int j=2*i;j<=n;j+=i) { if(a[j]>tmp) b[j] = max(b[j] , b[i]+1 ); /// cout<<j<<" "<<b[j]<<endl; } } ans = 0 ; for(int i=1;i<=n;i++) ans = max(ans,b[i]); cout<<ans<<endl; } }
Orac and Medians
题意：能否将给定的序列全部变为K
题解：先判断是否存在K，然后，可以把一段序列变为K的条件是不是存在 K 的左边或者右边大于等于K就可以？对，这是一种方法
那么，如果是类似于7 8 1 2 6 2 3 7 8 这样的序列呢，我是不是可以先变成7 8 7 7 6 6 6 6 6 ？再逆向变成 6 6 6 6 6 6 6 6 6 ①
那么，也就是如果存在下标为 x x+1 x+2 中 arr【X】 ，arr【 x+2】 >=K就可以变成max （ arr【X】，arr【 x+2】），而 max 也大于等于K，那么最后就可以选择两个或者三个一组的去全部变成K，但我们只需要知道存在不存在这样的结构就可以，并不需要去管如何将序列全部变成 K
那么，也就是最终只需要判断是否存在K，以及是否存在（ arr【x】=K，arr【x+1】>=k 或者 arr【x-1】>= K） || （arr【x】>=K && arr【x+2】>=K）两个条件的任意一个就可以
代码的话上一位大佬的（我的代码四次遍历+条件的判断，以及2次特判，代码及其丑陋）
#include<cstdio> #include<algorithm> #include<vector> #include<map> using namespace std; int n, w[101000], K; void Solve(){ int i, ck=0; scanf("%d%d",&n,&K); for(i=1;i<=n;i++){ scanf("%d",&w[i]); if(w[i]==K)ck=1; } if(!ck){ puts("no"); return; } if(n==1){ puts("yes"); return; } for(i=1;i<n;i++){ if(w[i]>=K&&w[i+1]>=K){ puts("yes"); return; } } for(i=1;i<n-1;i++){ if(w[i]>=K&&w[i+2]>=K){ puts("yes"); return; } } puts("no"); } int main(){ int TC; scanf("%d",&TC); while(TC--){ Solve(); } }