Codeforces Round #564 (Div. 1)-蒲公英云

Codeforces Round #564 (Div. 1)

太难了，一半时间刚这题还没做出来，简直自闭了。实际上分两种情况，一种很简单直接放，另一种就是要0,0,…,0,1,2,…,n，然后直接贪心，显然我是把情况判断错误一直没调出来。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int n,p,ans,a[N],b[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)if(b[i]==1)p=i;
    if(p)
    {
        bool flag=1;
        for(int i=p+1;i<=n;i++)if(b[i-1]+1!=b[i]){flag=0;break;}
        if(flag)
        {
            for(int i=1;i<p;i++)if(b[i]&&b[i]<n+2+i-p){flag=0;break;}
            if(flag){printf("%d",p-1);return 0;}
        }
    }
    for(int i=1;i<=n;i++)if(b[i])ans=max(ans,i-b[i]+1);
    printf("%d",n+ans);
}

签到。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7,mod=998244353;
int n,f[N],fac[N];
vector<int>G[N];
void dfs(int u,int fa)
{
    f[u]=fac[G[u].size()];
    for(int i=0;i<G[u].size();i++)if(G[u][i]!=fa)dfs(G[u][i],u),f[u]=1ll*f[u]*f[G[u][i]]%mod;
}
int main()
{
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);
    fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
    dfs(1,0);
    f[1]=1ll*f[1]*n%mod;
    printf("%d",f[1]);
}

C1很简单，很容易想到一个O(nm3)的做法，被A搞崩了心态于是写了一年，就是直接大力DP，f[T][i][j][k]表示T次操作后第i个物品重量为j总重量变化量为k的概率，直接推即可，记得滚动数组。

C2其实是找到一个结论，就是概率这块的结论，我没想到自然就没写出。a[i]相同的物品，最后的重量期望是成原比例的，这个大概是我高中数学没学好。f[i][j]表示加i次减j次的概率，也是大力转移即可，复杂度O(m2logm+nlogn)很可能会被卡常，怎么办？预处理逆元可以优化到O(m2+n)或者O(m2+nlogn)，仅需预处理临近的2m个即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7,M=3003,mod=998244353;
int n,m,sum,s[2],p[2],a[N],w[N],f[M][M],inv[M*2];
int qpow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)ret=1ll*ret*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]),sum+=w[i],s[a[i]]+=w[i];
    for(int i=0;i<=2*m;i++)if(sum+i-m>=0)inv[i]=qpow(sum+i-m,mod-2);
    f[0][0]=1;
    for(int i=0;i<m;i++)
    for(int j=0;i+j<m;j++)
    if(f[i][j])
    {
        int add=1ll*(s[1]+i)*inv[m+i-j]%mod,dec=1ll*(s[0]-j)*inv[m+i-j]%mod;
        f[i+1][j]=(f[i+1][j]+1ll*f[i][j]*add)%mod;
        f[i][j+1]=(f[i][j+1]+1ll*f[i][j]*dec)%mod;
    }
    for(int i=0;i<=m;i++)if(f[i][m-i])
    p[1]=(p[1]+1ll*(s[1]+i)*f[i][m-i])%mod,p[0]=(p[0]+1ll*(s[0]-m+i)*f[i][m-i])%mod;
    for(int i=1;i<=n;i++)
    printf("%d\n",1ll*w[i]*qpow(s[a[i]],mod-2)%mod*p[a[i]]%mod);
}

考虑把n*n的网格变成(n-1)*(n-1)的网格，如果满足条件则不要判断，否则找到最后一行中应该放在最后一列哪个和最后一列中应该放在最后一行哪个，这两个位置各放一个传送门即可。其实可以做到O(n)，但是数据范围小，我就是暴力O(n2)找的。

#include<bits/stdc++.h>
using namespace std;
const int N=1019;
int n,m,a[N],b[N],a1[N],b1[N],a2[N],b2[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=n;i;i--)
    if(a[i]!=i||b[i]!=i)
    {
        for(int j=1;j<=i;j++)if(a[j]==i)a[j]=a[i];
        for(int j=1;j<=i;j++)if(b[j]==i)b[j]=b[i];
        a1[++m]=a[i],b1[m]=i,a2[m]=i,b2[m]=b[i];
    }
    printf("%d\n",m);
    for(int i=1;i<=m;i++)printf("%d %d %d %d\n",a1[i],b1[i],a2[i],b2[i]);
}