A. Dice Rolling

读题比写代码久系列

输出n/7+1就过了

有很多种方法，随便弄就完事了(雾

#include <bits/stdc++.h>
#define il inline
#define Max 100005
#define inf 0x3f3f3f3f
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,a[Max];
int main()
{
    m=read();
    while(m--)
    n=read(),cout<<n/7+1<<endl;
}

B. Letters Rearranging

特判全是一个字符的输出-1

其他的弄个桶排输出就完事了

#include <bits/stdc++.h>
#define il inline
#define Max 10005
#define inf 0x3f3f3f3f
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char c[Max];
int n,len,m,vst[Max];
int main()
{
    m=read();
    while(m--)
    {
        scanf("%s",c+1);
        n=strlen(c+1);
        int flag=0;
        memset(vst,0,sizeof(vst));
        if(n==1)
        {
            puts("-1");
            continue;
        }
        for(int i=1;i<n;i++)
        {
            if(c[i]!=c[i+1])
            {
                flag=1;
            }
            vst[c[i]]++;
        }
        vst[c[n]]++;
        if(!flag)
        {
            puts("-1");
            continue;
        }
        for(int i=1;i<=300;i++)
        {
            if(vst[i])
            for(int j=1;j<=vst[i];j++)
            {
                putchar(i);
            }
        }
        puts("");
    }
}

C. Mishka and the Last Exam

贪心乱搞，每次取满足要求最小的就好

#include <bits/stdc++.h>
#define il inline
#define Max 400005
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
il int read()
{
    char c=getchar();
    int x=0;
    while(c>'9'||c<'0')
    {
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int a[Max],b[Max],n;
signed main()
{
    n=read();
    for(int i=1;i<=n/2;i++)
    {
        b[i]=read();
    }
    a[1]=0,a[n]=b[1];
    for(int i=2;i<=n/2;i++)
    {
        int nw=max(a[i-1],b[i]-a[n-(i-1)+1]);
        a[i]=nw,a[n-i+1]=b[i]-nw;
    }
    for(int i=1;i<=n;i++)
        printf("%I64d ",a[i]);
}

以上为比赛25min写完的题

rating极其惨烈(

1545056000773

赛后↓

D. Beautiful Graph

二分图判定

把图分为二分图，左边为奇数，右边偶数

如果图为二分图,那么一定满足要求

设左边为a,右边为b

答案为2^a+2^b

注意每个联通块跑出来的答案乘起来

一定要用ll，一定要用循环清零数组！！！

这题我就是这样就调完了整个比赛还没调出来的（

惨痛代码↓

#include <bits/stdc++.h>
#define il inline
#define Max 300005
#define int long long//注意这里！！！
#define ll long long
#define inf 0x3f3f3f3f
#define Mod 998244353
#define rg register
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node
{
    int t,nt;
}e[Max<<1];
int T,head[Max],vst[Max],tot,cnt,to[Max],c[5];
ll ans=1;
il void add(int u,int v)
{
    e[++tot].t=v;
    e[tot].nt=head[u];
    head[u]=tot;
}
il ll qpw(int a,int b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%Mod;
        a=a*a%Mod;
        b>>=1;
    }
    return res%Mod;
}
il bool dfs(int u,int cl)
{
    vst[u]=cl;
    c[cl]++;
    int res=1;
    for(rg int i=head[u];i;i=e[i].nt)
    {
        int v=e[i].t;
        if(vst[v]==cl) return false;
        if(!vst[v])
            res&=dfs(v,cl^1);
    }
    return res;
}
signed main()
{
    T=read();
    while(T--)
    {
        int n=read(),m=read();
        for(int i=1;i<=max(n,m);i++) e[i].t=e[i].nt=head[i]=vst[i]=0;//注意这里！
        cnt=tot=0;
        vst[0]=2;
        ans=1;
        for(rg int i=1;i<=m;i++)
        {
            rg int u=read(),v=read();
            add(u,v),add(v,u);
        }
        for(rg int i=1;i<=n;i++)
        {
            if(vst[i]) continue;
            c[2]=c[3]=0;
            if(!dfs(i,2))
            {
                ans=0;
                break;
            }
            else ans=ans*((qpw(2,c[2])+qpw(2,c[3]))%Mod)%Mod;
        }
        printf("%I64d\n",ans);
    }
}

E. Intersection of Permutations

EFG至今没写

E据说是树套树

以下为paidy原话

我首先考虑对a的排列进行重排成1..n，b相应重排

然后考虑一个二维点阵(i,b[i])的值是1，其它的都是0

1操作相当于对横坐标lb..rb纵坐标la..ra的矩阵做一个求和

2操作相当于 (x,b[x])-- (y,b[y])-- (x,b[y])++ (y,b[x])++

所以随便拉个能维护二维区间和的数据结构就好

我只会树套树

二维区间和什么的，二维树状数组不就完事了吗(

F. Vasya and Array

F是这次比赛最难的题

以下为paidy原话

哦F题大概是这样

1545056916746

那个括号里要不要减是要判断能不能做到连续的len个相同，这个可以预处理

最后做的时候由于你只要一个总答案所以f是不必算的，只要算g和h就行了

paidy爷爷代码

#include <bits/stdc++.h>
#define mo 998244353
using namespace std;

inline int read(){
    int x=0,f=1;char cc=getchar();
    while(cc<'0' || cc>'9') {if(cc=='-') f=-1;cc=getchar();}
    while(cc>='0' && cc<='9') {x=x*10+cc-'0';cc=getchar();}
    return x*f;
}

int n,m,k,a[100010],num[110],v[100010];
int g[100010][110],h[100010];

int main(){
    n=read();k=read();m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<m;i++) if(a[i]>0) num[a[i]]++;
    for(int i=m;i<=n;i++){
        if(a[i]>0)num[a[i]]++;if(a[i-m]>0)num[a[i-m]]--;
        int flag=0;
        for(int j=1;j<=k;j++) if(num[j]>0) flag++;
        if(flag==1){
            for(int j=1;j<=k;j++) if(num[j]>0) v[i]=j;
        }
        if(flag==0) v[i]=-1;
    }
    g[0][0]=1;h[0]=1;
    for(int i=1;i<=n;i++){
        if(a[i]==-1){
            for(int j=1;j<=k;j++){
                g[i][j]=h[i-1];
                if((v[i]>0 && v[i]==j) || v[i]==-1) g[i][j]=(g[i][j]-h[i-m]+g[i-m][j])%mo;
                if(g[i][j]<0) g[i][j]+=mo;
                h[i]=(h[i]+g[i][j])%mo;
            }
        }
        else{
            for(int j=a[i];j<=a[i];j++){
                g[i][j]=h[i-1];
                if(v[i]) g[i][j]=(g[i][j]-h[i-m]+g[i-m][j])%mo;
                if(g[i][j]<0) g[i][j]+=mo;
                h[i]=(h[i]+g[i][j])%mo;
            }
        }
    }
    //for(int i=1;i<=n;i++){
    //  for(int j=1;j<=k;j++) printf("%d ",g[i][j]);
    //  printf("\n");
    //}
    printf("%d",h[n]);
}

于是我就这样跪在了paidy爷爷面前

G. Multidimensional Queries

paidy爷爷原话：

G题我考虑把绝对值展开，每个点有2^k种可能性，然后维护每种可能性的区间最大值，相反的一加就好

那这么说起来G题比E题容易

F题代码超容易，难想

代码就没了,自己找吧qwq

rating changes:

1545057563870

（离rating上升只差一个循环清空数组