vp的 写出4道 C感觉目前不是能力范围 以后有机会留下来打比赛的话再说
A - Prefix and Suffix Array
给出字符串的前缀和后缀 问是不是回文
我采用枚举 长度为n-1和1的拼凑 但是这并不奏效 一直wa3 后来改用拼两个n/2的 就过了 如果有大佬看到了 希望能解答一下qwq
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; int lowbit(int x){ return x&-x; } int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;} ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;} void solve(){ int n;cin>>n; string s; int flag=0,cnt=0; string str; for(int i=1;i<=(n-1)*2;i++){ cin>>s; if(s.length()==n/2) str=str+s; } string ss=str; reverse(str.begin(),str.end()); if(ss==str) flag=1; if(flag) cout<<"YES\n"; else cout<<"NO\n"; } int main(){ close; int t;cin>>t; while(t--) solve(); }View Code
B - Not Dividing
给出一串数字 长度为n 最多2*n次操作 让后一个数不能被前一个数整除
首先 1肯定不合格 要变成2
如果 b能被a整除 说明b是a的倍数 那么当a不是1的时候 b+1/a肯定会余一个1 肯定不是倍数了
因此 从2遍历到n 如果这个数能被前面整除 直接+1、
注: 不能加前面的 因为无法证明是正确的
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; int a[MAXN]; int lowbit(int x){ return x&-x; } int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;} ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;} void solve(){ int n;cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; if(a[i]==1) a[i]++; } for(int i=2;i<=n;i++){ if(a[i]%a[i-1]==0) a[i]++; } for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<"\n"; } int main(){ int t;cin>>t; while(t--) solve(); }View Code
C - Scoring Subsequences
给一串递增的数字 在第i轮可以选前i个数字 你可以自由选择个数 每个数相乘 每选择一个 就会/当前个数 求最终结果最大的数的个数的最大值
因此 当给出 1 1 2 时 显然只选2 是最大的 如果给出 2 4 6 显然只选 6 4 是最大的 再选一个2 会/3 是亏的
因此 我们对每一次进行一个二分 2 4 6 对应的代价是 3 2 1 我们需要通过二分寻找该数字/代价>=1的情况 然后求数字的最大数量 这个是符合二分的 因为数字/代价一定是递增的
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; int n; int a[MAXN]; void solve(){ cin>>n; // set<int> sz; vector<int> sz; for(int i=1;i<=n;i++) cin>>a[i]; int ans=1; for(int i=1;i<=n;i++){ if(i==1) cout<<1<<" "; else{ int l=1,r=sz.size(); while(l<=r){ int mid=l+r>>1; if(sz[mid-1]<sz.size()+2-mid) l=mid+1; else r=mid-1; } cout<<sz.size()+1-r<<" "; } sz.push_back(a[i]); } cout<<"\n"; } int main(){ int t;cin>>t; while(t--) solve(); }View Code
我的二分写的比较丑
标签:std,856,const,int,ll,cf,long,str,div2 From: https://www.cnblogs.com/xishuiw/p/17300609.html