Codeforces Global Round 4 题解

时间：2024-08-09 23:34:02

技不如人，肝败吓疯……

开场差点被 A 题意杀了，幸好仔细再仔细看，终于在第 7 分钟过掉了。

跟榜。wtf 怎么一群人跳题/倒序开题？

立刻紧张，把 BC 迅速切掉，翻到了 100+。

开 D。感觉有点吓人……感觉有点可做？

的确挺可做。再切掉 D，但是此时已经到 300+ 了。

没事，还能翻。

开 E。这……什么玩意？

瞄了一眼 F1，……

盯着这两题盯到自闭。

最后 rk 1000 左右。我的名字颜色真的是对的吗……

A

看懂题了就是水题。选上所有小于等于第一个党派一半人数的党派，如果不行就不行，否则就可以。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

    char ch=getchar();ll x=,f=;

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int n,a[maxn],s,s2,cnt;

int main(){

    n=read();

    FOR(i,,n) s+=a[i]=read();

    s2=a[];cnt=;

    FOR(i,,n) if(a[]>=*a[i]) s2+=a[i],cnt++;

    if(s2*<=s) puts("");

    else{

        printf("%d\n",cnt);

        printf("1 ");

        FOR(i,,n) if(a[]>=*a[i]) printf("%d ",i);

    }

}

B

枚举中间的 o，然后看看两边能选出多少个 vv，简单前缀/后缀和解决。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

    char ch=getchar();ll x=,f=;

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int n,pre[maxn],suf[maxn];

ll ans;

char s[maxn];

int main(){

    scanf("%s",s+);

    n=strlen(s+);

    FOR(i,,n){

        pre[i]=pre[i-];

        if(s[i]=='v' && s[i-]=='v') pre[i]++;

    }

    ROF(i,n-,){

        suf[i]=suf[i+];

        if(s[i]=='v' && s[i+]=='v') suf[i]++;

    }

    FOR(i,,n) if(s[i]=='o') ans+=1ll*pre[i-]*suf[i+];

    cout<<ans<<endl;

}

C

最左上角的可以随便选。

第一行的在左边那个已经确定后，可以发现可以选两种。

第一列的同理，每个可以选两种。

不在第一行也不在第一列的，发现只能选固定的一种。

答案就是 $2^{n+m}$。

（为什么一群人盯样例盯出来了……）

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=,mod=;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

    char ch=getchar();ll x=,f=;

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int n,m;

int qpow(int a,int b){

    int ans=;

    for(;b;b>>=,a=1ll*a*a%mod) if(b&) ans=1ll*ans*a%mod;

    return ans;

}

int main(){

    n=read();m=read();

    printf("%d\n",qpow(,n+m));

}

D

每个点度数不小于 $2$，所以边数最小为 $n$。

不妨找到第一个大于等于 $n$ 的质数作为边数。

根据一些%*#(!^定理（猜想？），$n\ge 3$ 时，$[n,\frac{3}{2}n]$ 中至少有一个质数。

可以通过下面这个方法构造出一个有 $2n-m$ 个度数为 $2$ 的点，$m-n$ 个度数为 $3$ 的点的图。

首先 $i$ 向 $i+1$ 连边（$n$ 向 $1$ 连边），此时用了 $n$ 条边，所有点度数为 $2$。

剩下的 $m-n$ 条边随便连，只要没有重边并且这 $m-n$ 条边不重复用点就好了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

    char ch=getchar();ll x=,f=;

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int n,m,cnt;

bool use[maxn];

bool check(int x){

    if(x==) return false;

    for(int i=;i*i<=x;i++) if(x%i==) return false;

    return true;

}

int main(){

    n=m=read();

    while(!check(m)) m++;

    cnt=m-n;

    printf("%d\n",m);

    FOR(i,,n){

        printf("%d %d\n",i,i%n+);

        if(cnt && !use[i]){

            int to=i%n+;

            to=to%n+;

            while(use[to]) to=to%n+;

            use[i]=use[to]=true;

            printf("%d %d\n",i,to);

            cnt--;

        }

    }

}

E

这也太神了吧……

对于长度 $\le 3$ 的字符串，可以任意选其中一个字符。

对于长度 $\ge 4$ 的字符串，取出前两个字符和后两个字符，由于相邻字符不相等，所以一定可以从前两个中选出一个，后两个中选出一个，使得它们相等。删掉这四个字符，然后重复操作。

可以发现这样求出的一定是回文串而且合法。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

    char ch=getchar();ll x=,f=;

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int n,m,l,r;

char s[maxn],t[maxn];

int main(){

    scanf("%s",s+);

    n=strlen(s+);

    l=;r=n;

    while(r-l+>=){

        if(s[l]==s[r] || s[l]==s[r-]) t[++m]=s[l];

        else t[++m]=s[l+];

        l+=;r-=;

    }

    FOR(i,,m) putchar(t[i]);

    if(l<=r) t[++m]=s[l];

    ROF(i,m,) putchar(t[i]);

}

F1/F2

点这里。

相关文章