526互联

练习记录-cf-div2-856(A-C)

发布时间 2023-04-09 17:13:08作者: xishuiw

vp的 写出4道 C感觉目前不是能力范围 以后有机会留下来打比赛的话再说

A - Prefix and Suffix Array

给出字符串的前缀和后缀 问是不是回文 

我采用枚举 长度为n-1和1的拼凑 但是这并不奏效 一直wa3 后来改用拼两个n/2的 就过了 如果有大佬看到了 希望能解答一下qwq

#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、

注： 不能加前面的 因为无法证明是正确的

#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的情况 然后求数字的最大数量 这个是符合二分的 因为数字/代价一定是递增的

#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

我的二分写的比较丑