前言

今年考 CSP 状态奇差,本来期望得分 40+100+60+0=200,实际 40+0+70+0=110(T2 MLE 惨案)。考 NOIP 之前决定来颓一颓题解

T1 儒略历

先咕着

T2 动物园

先读入所有的动物编号,记录下所有已经被占用的二进制位。然后考虑每条要求,如果发现了 p_i 没有被已有动物占用但却要购买没买过的 q_i 饲料,则这一位是铁定不能有的,记录一下。不难发现由乘法原理并去重,我们的答案就是 2^s-ns 表示可以使用的二进制位。

注意如果 n=0k=64 的话答案为 2^{64},而 1ull<<64 是 UB,所以需要特判输出

代码:

#include <cstdio>
#include <cctype>
#define FOR(i,j,k) for(int i=j;i<=k;++i)

typedef unsigned long long ll;
const int maxn=1e6+5,maxc=1e8+5;

inline ll read()
{...}

ll n,m,c,k,a[maxn],p[maxn],q[maxn];
bool vis[maxc],affected[65];
ll tmp=0;

int main()
{
    n=read(),m=read(),c=read(),k=read()-1;
    FOR(i,1,n)
        a[i]=read(),tmp|=a[i];
    FOR(i,1,m)
    {
        p[i]=read(),q[i]=read();
        if(tmp&(1ull<<p[i]))
            vis[q[i]]=1;
    }
    FOR(i,1,m)
    {
        if(!(tmp&(1ull<<p[i])))
            if(!vis[q[i]])
                affected[p[i]]=1;
    }
    ll nafed=0;
    if(k==63 && n==0)
    {
        printf("18446744073709551616");
        return 0;
    }
    FOR(i,0,k)
        if(!affected[i])
            ++nafed;
    printf("%llu\n",(1ull<<nafed)-n);
    return 0;
}

T3 函数调用

不难发现所有的函数调用关系是一个 DAG,然后其实我们可以考虑一个加法操作被乘法影响了几次。

首先所有的数是肯定要乘上所有调用的 2 号函数的操作值之积的,所以可以开一个 mul[i] 数组表示调用函数 i 后数列会乘上多少。对于所有的 2 号函数,它的 mul[i] 就是 v_i,1 号函数则为 1,对于所有的 3 号函数,可以 dfs 一遍之后找出答案。

void dfs(int id)
{
    vis[id]=true;
    mul[id]=(type[id]==2?val[id]:1);
    VEC(it,c[id])//遍历3号函数的所有子函数
    {
        int i=*it;
        if(!vis[i])dfs(i);
        mul[id]=mul[id]*mul[i]%mod;
    }
    return;
}

之后定义一个变量 mu,记录一共要乘多少,在处理函数调用序列的时候可以一并处理,这里先考虑怎么处理加法。

定义一个数组 add[i] 表示 a[i] 最终在乘上 mu 之后还要加上多少,于是考虑如何处理 add[i]

先这样想:如果一个 1 号函数被调用之后所有的数被乘上了 t,则这个 1 号函数就会产生 t 倍的贡献,不妨定义 f_i 表示函数 i其调用的 1 号函数产生了 f_i 倍贡献。

倒序处理函数调用序列:首先 mu=1,然后:

  • 对于 1 号函数,f_i\leftarrow f_i+mu
  • 对于 2 号函数,mu\leftarrow mu\times v_i
  • 对于 3 号函数,f_i\leftarrow f_i+mumu\leftarrow mu\times mul_i

最后通过在调用关系的 DAG 上拓扑排序来把 3 号函数真正的 f_i 求出来:

  • 对于 1 号函数:add_{p_i}\leftarrow add_{p_i}+v_i\times f_i
  • 2 号函数不做处理
  • 对于 3 号函数,倒序处理它调用的函数,对于每个被调用的函数 jf_j\leftarrow f_j+f_i,而 j 对之前被调用的函数 pre 放大了 mul_j 倍贡献,所以 f_i\leftarrow f_i\times mul_j,然而 f_i 会被覆盖,所以需要单独开一个变量
#include <cstdio>
#include <cctype>
#include <queue>
#include <algorithm>
#define FOR(i,j,k) for(int i=j;i<=k;++i)
#define DEC(i,j,k) for(int i=j;i>=k;--i)
#define VEC(it,c) for(std::vector<int>::iterator it=c.begin();it!=c.end();++it)

typedef long long ll;
const ll mod=998244353,maxn=1e5+5;

inline ll read()
{...}

int n,m,Q,type[maxn],pos[maxn],cal[maxn],deg[maxn];
bool vis[maxn];
ll a[maxn],val[maxn],mu=1,mul[maxn],f[maxn],add[maxn];
std::vector<int> c[maxn];
std::queue<int> q;

void dfs(int id)
{
    vis[id]=true;
    mul[id]=(type[id]==2?val[id]:1);
    VEC(it,c[id])
    {
        int i=*it;
        if(!vis[i])dfs(i);
        mul[id]=mul[id]*mul[i]%mod;
    }
    return;
}

int main()
{
    n=read();
    FOR(i,1,n)a[i]=read();
    m=read();
    FOR(i,1,m)
    {
        type[i]=read();
        if(type[i]==1)pos[i]=read(),val[i]=read();
        else if(type[i]==2)val[i]=read();
        else
        {
            int ci=read();
            while(ci--)
            {
                int tmp=read();
                c[i].push_back(tmp);
                ++deg[tmp];
            }
        }
    }
    FOR(i,1,m)
        if(!vis[i] && !deg[i])
            dfs(i);
    Q=read();
    FOR(i,1,Q)cal[i]=read();
    DEC(i,Q,1)
    {
        if(type[cal[i]]==1)
            f[cal[i]]+=mu;
        else if(type[cal[i]]==2)
            mu=mu*val[cal[i]]%mod;
        else f[cal[i]]+=mu,mu=mu*mul[cal[i]]%mod;
    }
    FOR(i,1,m)
        if(!deg[i])q.push(i);
    while(!q.empty())
    {
        int i=q.front();q.pop();
        if(type[i]==1)
            add[pos[i]]=(add[pos[i]]+f[i]*val[i])%mod;
        ll tmp=f[i];
        std::reverse(c[i].begin(),c[i].end());
        VEC(it,c[i])
        {
            int g=*it;
            if(!--deg[g])
                q.push(g);
            f[g]=(f[g]+tmp)%mod,tmp=tmp*mul[g]%mod;
        }
    }
    FOR(i,1,n)
        printf("%lld ",(a[i]*mu+add[i])%mod);
    return 0;
}

T4 贪吃蛇

太难了先咕咕咕

最后修改日期:2020年11月30日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。