Atcoder 235

\(E.\) MST + 1

题意（唯一一次10分钟之内一次AC的E题，太菜了)

给定一个有\(N\)个点，\(M\)条边的无向连通图\(G\)，可能有重边和自环，现在有\(Q\)个询问，每次询问给定一个条边\((u_i,v_i,w_i)\)，问把条边加入\(G\)中，这条边是否会出现在\(G^{'}\)的最小生成树中，保证\(w_i\)在原图的边权中没有出现过。

\(2\le N\le 2\times 10^5\) \(N-1\le M<\le 2\times 10^5\) \(1\le a_i,b_i\le N\) \(1\le c\le 10^9\) (\(c_i!=c_j\))

\(1\le Q \le 2\times 10^9\) \(1\le u_i,v_i\le N\) \(1\le w_i\le 10^9\)

思路

克鲁斯卡尔重构树+倍增

#include 
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;

template  void rd (T &x)
{
    x=0;int f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
    x*=f;
}
template  void chkMax(T &x, T y) { if (y > x) x = y; }
template  void chkMin(T &x, T y) { if (y < x) x = y; }

const int N=2e5+10;
int fa[N*2];
int var[N*2];
int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
struct edges
{
    int u,v,w;
    bool operator <(const edges &t)const
    {
        return wE[2*N];
int f[2*N][22],d[2*N];
void dfs(int u,int father,int depth)
{
    f[u][0]=father;
    d[u]=depth;
    for(int i=1;i<=20;i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(auto v:E[u])
    {
        if(v==father) continue;
        dfs(v,u,depth+1);
    }

}
int LCA(int u,int v)
{
    if(d[u]=0;i--)
        if(d[f[u][i]]>=d[v]) u=f[u][i];
    if(u==v) return u;
    for(int i=20;i>=0;i--)
    if(f[u][i]!=f[v][i])
    {
        u=f[u][i];
        v=f[v][i];
    }
    return f[u][0];
}
//重构树上跳一跳
int main()
{
    int n,m,q;
    rd(n),rd(m),rd(q); 
    for(int i=1;i<=2*n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        rd(u),rd(v),rd(w);
        e[i]={u,v,w};
    }
    int cnt=n;
    sort(e+1,e+1+m);
    for(int i=1;i<=m;i++)
    {
        int x=e[i].u,y=e[i].v,w=e[i].w;
        if(x==y) continue;
        int fx=find(x),fy=find(y);
        if(fx!=fy)
        {
           cnt++;
           E[cnt].pb(fx);
           E[cnt].pb(fy);
           fa[fx]=fa[fy]=cnt;
           var[cnt]=w;
        }
    }

    dfs(cnt,cnt,1);
    while(q--)
    {
        int u,v,w;
        rd(u),rd(v),rd(w);
        int lca=LCA(u,v);
        if(var[lca]>w) puts("Yes");
        else puts("No");
    }
    return 0;
}

\(F.\)Variety of Digits

题意

给定\(M\)个数字\(C_i\)，请求出从\(1\)到\(N\)中包含所有\(C_1,C_2,...,C_M\)的数字的和，答案对\(998244353\)取模

\(1\le N\le 10^{10^4}\) \(1\le M\le 10\) \(0\le C_i\le 9\)

Sol

数位DP~~(一直不会，唉)~~

定义\(dp[2][1e4][2][(1<<10)+10]\)

1.第一维\(0\)表示计数，\(1\)表示求和

2.第二维表示当前是第几位

3.第三维\(0\)表示当前这位有前一位的限制，也就是前一位到了自身的最大数值，当前位的枚举上限变为\(N\)这位的数,\(1\)则表示没有前一位的限制

4.第4维表示当前所用到的数字的集合,由于最多10个数字，所以可以用二进制来描述哪些数字出现过，所以第\(4\)维是\(1<<10\)

由于每次转移只和前一位有关，所以可以用滚动数组优化掉第2维，这里采用新建一个数组的方式，所以最终的dp为\(dp[2][2][(1<<10)+10]\)

这里只讲和的转移

一般数位dp都是从高位开始转移

假设有3位数并且枚举到第3位

假设前2位出现的数字的集合是\(\{1,2\}\)

说明前两位是\(12\)和\(21\)，假设第\(3\)位枚举到了\(3\)且没有限制

\(123+213=(12+21)*10+2*3\)

那么第\(3\)位和的转移就是\(dp[1][1][111]+=(12+21)*10+2*3\)

乘\(10\)的部分就是集合为\(s=11\)的前一位的数字和，乘\(3\)前面的部分就是集合为\(s=11\)的前一位的数量

#include 
#define ll long long
#define inf 1e18
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;

template  void rd (T &x)
{
    x=0;int f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
    x*=f;
}
template  void chkMax(T &x, T y) { if (y > x) x = y; }
template  void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=1e5+10;
int v[N];
ll dp[2][2][(1<<10)+10],f[2][2][(1<<10)+10];
//第一维0表示计数，1表示求和
//第二维表示是否有limit,即是否有前一位是最大值的限制,0表示有，1表示没有
//第三位表示用了哪些数的集合
int main()
{

    string s;
    cin>>s;
    int n=s.size();
    for(int i=0;i=0;i--) //从高位开始枚举
    {
        //枚举当前位
        for(int x=1;x<=(i==n-1?v[i]:9);x++)
        {
            auto &f1=f[0][i


\(G.\)Gardens
题意
果农有\(A\)个苹果种子，有\(B\)个香蕉种子，有\(C\)个樱桃种子，他有\(N\)个花园
现在他要把这些种子种在花园里，但有一下条件

每个花园至少种1个种子
不允许有相同的种子种在同一个花园里
不必用完所有的种子

请求出所有可能的种植方案数
\(1\le N\le 5\times 10^5\)    \(\le A,B,C\le N\)
Sol
考虑容斥
假设允许花园为空并且用完所有的种子
那么方案数就是\(\sum_{i=0}^NC_n^iC_{n-i}^AC_{n-i}^BC_{n-i}^C\)，其中\(C_n^i\)为选择的空的花园方案
那么依据容斥原理，不允许花园为空就是\(\sum_{i=0}^N(-1)^iC_n^iC_{n-i}^AC_{n-i}^BC_{n-i}^C\)
考虑条件三，由于可以不必用完所用的种子，假设当前位苹果种子，那么选完\(i\)个空的花园后，苹果种子的方案应该为\(\sum_{k=0}^AC_{n-i}^j\)
同理其它两个也是，所以答案应该为\(\sum_{i=0}^N(-1)^iC_n^i\sum_{k=0}^AC_{n-i}^j\sum_{k=0}^BC_{n-i}^j\sum_{k=0}^CC_{n-i}^j\)
后面的和考虑用前缀和优化
由于\(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\)
所以有\(\sum_{i=0}^mC_{n+1}^i=\sum_{i=0}^{m-1}C_{n}^i+\sum_{i=0}^mC_{n}^i=2\sum_{i=0}^mC_{n}^i-C_n^m\)
可以令\(sa\)为苹果种子的前缀和，那么更新时\(sa=2*sa-C_{n-i}^A\)
#include 
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;

template  void rd (T &x)
{
    x=0;int f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
    x*=f;
}
template  void chkMax(T &x, T y) { if (y > x) x = y; }
template  void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=5e6+10;
int n,a,b,c;
ll fac[N],infac[N],inv[N];
ll qmi(ll x,int y)
{
    ll res=1;
    while(y)
    {
        if(y&1) res=res*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return res;
}
ll C(int x,int y)
{
    if(y<0||x=1;i--)
    infac[i-1]=infac[i]*i%mod;
    
    ll ans=0;
    ll sa=1,sb=1,sc=1;
    //C(n,m)=C(n-1,m-1)+C(n-1,m);
    //sumC(n+1,0....,m+1)=sumC(n,0.....,m)+sumC(n,0....,m+1)=2*sumC(n,0....m+1)-C(n,m+1)
    for(int i=0;i<=n;i++)
    {
        if((n-i)%2) ans=(ans-C(n,i)*sa%mod*sb%mod*sc%mod+mod)%mod;
        else ans=(ans+C(n,i)*sa%mod*sb%mod*sc%mod)%mod;
        sa=(sa*2%mod-C(i,a)+mod)%mod; 
        sb=(sb*2%mod-C(i,b)+mod)%mod;
        sc=(sc*2%mod-C(i,c)+mod)%mod;
    }
    cout<

\(Ex.\)Painting Weighted Graph
题意

Atcoder 235

Atcoder 235

相关

标签