Articles12
Tags2
Categories0

Codeforces Round 616(Div.2)


好久没更了,更一场上了大分的div2 赛时rk18 +168(呜呜当时怎么这么猛

传送门

整体难度 A<B<C<D<F<E

A. Even But Not Even

可能是全场写的最煎熬的题了(按题意模拟写的)

赛后知道只要输出两个奇数就好了 艹

我的sb代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
char ch[3030];
void solve(){
    int n;scanf("%d%s",&n,ch);int sum=0;int cnt=-1;
    for(int i=0;i<n;i++){
        sum+=ch[i]-'0';
        if((ch[i]-'0')%2) cnt=i;
    }if(sum%2==0&&(ch[n-1]-'0')%2){
        printf("%s\n",ch);return;
    }
    if(n==1||cnt==-1){
        printf("-1\n");
        return;
    }sum=0;int flag=-1;for(int i=0;i<=cnt;i++){
        sum+=ch[i]-'0';if((ch[i]-'0')%2&&i!=cnt) flag=i;
    }if(sum%2==0){
        for(int i=0;i<=cnt;i++) printf("%c",ch[i]);printf("\n");
    }else if(flag==-1){
        printf("-1\n");
    }else{
        for(int i=0;i<=cnt;i++) if(i!=flag) printf("%c",ch[i]);printf("\n");
    }
}
int main(){
    int t;scanf("%d",&t);while(t--) solve();
} 

实际上只需要这样

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(int)2e5+100;
int n;
char s[maxn];
int solve(){
    scanf("%d%s",&n,s+1); int cnt=0,ans=0;
    for(int i=1;i<=n;i++){
        if((s[i]-'0')%2) cnt++,ans=ans*10+s[i]-'0';
        if(cnt==2) return printf("%d\n",ans);
    }return puts("-1");
}
int main(){
    int T;cin>>T;while(T--) solve();
}

B. Array Sharpening

这把我是弱智A题,但是没关系,因为我就要开启王者模式,芜湖起飞,从现在开始我要起飞了~

不知道他们为啥写的这么慢

贪心想一想 满足最小的情况就行 正反dp一下 然后judge就好了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+50;
int a[maxn];
int ok1[maxn],ok2[maxn];
int solve(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),ok1[i]=ok2[i]=0;ok2[n+1]=1;
    for(int i=n;i>=1;i--){
        if(a[i]>=n-i) ok2[i]=1;
        else break;
    }for(int i=1;i<=n;i++){
        if(a[i]>=i-1) ok1[i]=1;
        else break;
    }for(int i=1;i<=n;i++){
        if(ok1[i]&&ok2[i]) return printf("Yes\n");
    }return printf("No\n");
}
int main(){
    int t;scanf("%d",&t);while(t--) solve();
} 

C.Mind Control

比较迷幻的一道题,看到3500就知道N2,然后既然要控制人,那我肯定一开始就要控制(但其实我也不知道为什么,单纯因为如果不是这样会非常难写,所以就开莽了),那么在这个基础上,枚举左边需要控制多少人,右边就是k-左边的人数,取最大值,这是第一重循环,然后的话再枚举左边随机的人,因为随机,所以肯定取最小值,这是第二重循环,那么答案其实已经出来了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int a[3550];
void solve(){
    int n,m,k;scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    k=min(k,m-1);int ans=0;
    for(int i=0;i<=k;i++){
        int l=i+1;int r=n-(k-i);int rem=m-k-1;int res=1e9;
        for(int j=0;j<=rem;j++){
            int l1=l+j;int r1=r-(rem-j);
            int tmp=max(a[l1],a[r1]);res=min(res,tmp);
        }ans=max(ans,res);
    }printf("%d\n",ans);
}
int main(){
    int t;scanf("%d",&t);while(t--) solve();
} 

D.Irreducible Anagrams

这波啊,这波是随便猜猜

给你一个串和q个询问,每个询问给定这个串中的子串,问你能否找出另一个串满足“at least one irreducible anagram.”

q既然是1e5,那询问复杂度肯定不高,我就直接开始猜结论。

那么有三种情况是判yes的,其余都是no:

1.len为1(很简单,不证了

2.子串开头结尾不相等:那么只要把开头和结尾调换一下,中间复制,就是符合要求的串

3.有三个及以上不同的字母:建立在首尾相同的情况下,假设开头结尾字母为A,剩下两个为BC,我们用B替换开头的A,用C替换结尾的A,注意不能用第二个出现的字母去替换开头。

如:ABCA->CAAB 而不能AB|CA->BA|AC

AAABCCCA->CAAAABCC

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
char ch[maxn];int cnt[maxn][30];
int solve(){
    int l,r;scanf("%d%d",&l,&r);
    int x=ch[r]-'a';
    if(ch[l]!=ch[r]||l==r) return printf("Yes\n");
    int ans=0;
    for(int i=0;i<26;i++)
        if(cnt[r][i]-cnt[l][i]) ans++;
    if(ans>=3) return printf("Yes\n");
    else return printf("No\n");
}
int main(){
    scanf("%s",ch+1);int q;scanf("%d",&q);int n=strlen(ch+1);
    for(int i=0;i<26;i++) cnt[0][i]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<26;j++) cnt[i][j]=cnt[i-1][j];
        cnt[i][ch[i]-'a']++;
    }while(q--) solve();
} 
Author:西瓜喵喵.
Link:https//:ForgGYLH.github.io/2020/03/11/cf616/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可