【题解】CSP 2020 简要题解

游记和题解分开了 >_<

T1

出题人出题前就没想过自己马的安全么？

考虑二分年份，然后暴力确定几月几日。二分年份的话按照 $mid\leq 1582$ 和 $mid>1582$ 两种情况讨论一下就好了。

$mid\leq 1582$ 的，因为公元前 $4713$ 年是闰年，所以直接看看有多少年即可。对于 $mid>1582$ 的，先将 $1582$ 年以前的贡献加上，剩下的瞎搞搞就好了。

然后就没了。

ll N;

inline bool check(ll year) {
    if(year<1582) return (year%4==0);
    else if(year==1582) return false;
    else return (year%400==0||(year%4==0&&year%100!=0));
}
inline ll calc(ll year) {
    if(year<=1582) {
        year+=4712;
        return 1ll*year*365+year/4+(year%4!=0);
    } else {
        ll tmp=1ll*6294*365+6294/4+(6294%4!=0)+355;
        if(year==1583) return tmp;
        year-=1584,tmp+=365;
        return tmp+1ll*year*365+(year/4+(year%4!=0))-((year-17)/100)+((year-17)/400);
    }
}

inline int lim(int u,bool nmsl) {
    if(u==2) return nmsl?29:28;
    if(u==1||u==3||u==5||u==7||u==8||u==10||u==12) return 31;
    return 30;
}
inline void solve() {
    IN(N);

    ll l=-4712,r=1000000000,ans,mid;
    while(l<=r) {
        mid=l+r>>1;
        (calc(mid+1)>N)?ans=mid,r=mid-1:l=mid+1;
    }
    N-=calc(ans);

    int m=1,d=1;
    while(N) {
        if(d==lim(m,check(ans))) ++m,d=0;
        if(ans==1582) {
            if(m==10&&d==4) d=15;
            else ++d;
        } else ++d;
        --N;
    }
    printf("%d %d ",d,m);
    if(ans<=0) printf("%lld BC\n",-ans+1);
    else printf("%lld\n",ans);
}

T2

看看最后有多少个可用的二进制位即可。

注意一下 $n=0,k=64$ 的数据就好了。

const int N=1e6+5;

int n,m,c,k,p[N],q[N],god[N];
ull a[N],all;

int main() {
    IN(n),IN(m),IN(c),IN(k);
    lep(i,1,n) IN(a[i]),all|=a[i];

    lep(i,0,k-1) god[i]=true;
    lep(i,1,m) IN(p[i]),IN(q[i]),god[p[i]]=false;

    lep(i,1,m) if((all>>p[i])&1) god[p[i]]=true;

    int tot=0;
    lep(i,0,k-1) tot+=god[i];

    if(n==0&&tot==64) printf("18446744073709551616\n");
    else {
        ull ans=0;
        lep(i,0,tot-1) ans+=(1ull<<i);
        printf("%llu\n",ans-n+1);
    }
    return 0;
}

T3

一个加法操作的贡献取决于其后面有多少个乘法。

所以倒着做。假设现在要处理第 $i$ 个操作。显然第 $i$ 个操作中的所有加法操作都可以吃到 $i$ 后面的所有操作中的乘法操作的贡献。因此只需要考虑第 $i$ 个操作中，后面的乘法对前面的加法的贡献。

那么直接打个标记在 $i$ 这个点上，然后按照儿子的执行顺序下传即可。

const int N=1e5+5;
const int M=2e6+5;

int n,a[N],du[N],m,cnt,head[N];
struct Node {int T,P,V;} seq[N];
struct Edge {int nxt,to;} G[M];

inline void addedge(int u,int v) {
    G[++cnt]=(Edge){head[u],v},head[u]=cnt,++du[v];
}

int vis[N],sum[N]; /*prod*/
int dfs(int u) {
    if(vis[u]) return sum[u];
    vis[u]=true;

    int now=(seq[u].T==2)?seq[u].V:1;
    for(int i=head[u];i;i=G[i].nxt) now=mul(now,dfs(G[i].to));
    return sum[u]=now;
}

int tag[N],ans[N];
queue <int> q;
inline void solve_topsort() {
    lep(i,1,m) if(!du[i]) q.push(i);

    while(!q.empty()) {
        int u=q.front(); q.pop();
        if(seq[u].T==1) pls(ans[seq[u].P],mul(tag[u],seq[u].V));

        int now=tag[u];
        for(int i=head[u];i;i=G[i].nxt) {
            int v=G[i].to;
            pls(tag[v],now),now=mul(now,sum[v]);    
            if(--du[v],!du[v]) q.push(v);
        }
    }
}

int Q,f[N];
int main() {
    IN(n);
    lep(i,1,n) IN(a[i]);

    IN(m);
    lep(i,1,m) {
        IN(seq[i].T);

        if(seq[i].T==1) IN(seq[i].P),IN(seq[i].V);
        if(seq[i].T==2) IN(seq[i].V);
        if(seq[i].T==3) {
            int C,g; IN(C);
            lep(j,1,C) IN(g),addedge(i,g);
        }
    }
    lep(i,1,m) sum[i]=dfs(i);

    IN(Q);
    int now=1;
    lep(i,1,Q) IN(f[i]);
    rep(i,Q,1) pls(tag[f[i]],now),now=mul(now,sum[f[i]]);

    solve_topsort();
    lep(i,1,n) pls(ans[i],mul(a[i],now)),printf("%d ",ans[i]);
    puts("");
    return 0;
}

T4

Waring :: 这个做法假了

改题的时候与其他人的做法不同。如果这个做法是对的的话，那么真的是十分简洁了。

首先考虑暴力做法。当前剩下了一些蛇，然后找出最大的 $x$ 和最小的 $y$，假定 $x$ 吃了 $y$ ，然后递归下去，看看返回来的答案里面是否包含 $x$（即 $x$ 是否存活），存活的话就可以吃，否则一定不吃。

容易发现这个状态只有 $n$ 种。直接 $O(n^2)$ 可以拿到 $55$ 分。

考虑 $70$ 分做法，用 $set$ 模拟一遍整个过程，并记录 $die_i$ 表示 $i$ 在第几轮被吃，$top_i$ 表示第 $i$ 轮的最大蛇的编号。接着依旧使用上述递归方法。对于第 $i$ 轮来说，递归下去，如果第 $i+1$ 轮的答案为第 $k$ 轮，那么只需要检查第 $i$ 轮到第 $k$ 轮中，$top_i$ 是否被吃即可。

int dfs(int dep) {
    if(dep==1) return 1;
    int ans=dfs(dep-1);
    return (die[top[dep]]>ans)?dep:ans;
}

inline void solve() {
    lep(i,1,n) s.insert(mkp(b[i]=a[i],i));

    rep(i,n,2) {
        int y=(it=s.begin())->se,x=(it=s.end(),--it)->se;
        s.erase(mkp(b[x],x)),s.erase(mkp(b[y],y)),s.insert(mkp(b[x]-=b[y],x));
        top[i]=x,die[y]=i;
    }
    die[(it=s.begin())->se]=-1,s.clear();
    printf("%d\n",dfs(n));
}

接着考虑满分做法。

容易发现复杂度瓶颈在于求 $top$ 和 $die$ 。有没有办法优化呢？

考虑当前局面 $a_1\leq a_2\leq a_3\leq \cdots \leq a_n$ ，这个时候 $a_n$ 吃掉 $a_1$ ，分两种情况：

• $a_n$ 吃掉 $a_1$ 后不是最小蛇。

那么接下来的一轮，最大值一定不比原来大，最小值一定不比原来小，因此接下来的” 最大蛇吃掉最小蛇后剩下的长度”，一定不比 $a_n-a_1$ 大。

考虑用两个双端队列维护，$q1$ 维护没进行操作的蛇，$q2$ 维护进行了操作的蛇。此处规定两个双端队列中蛇的大小都是自队尾至队头单调递增的。

每一轮的最大值取出 $q1,q2$ 的队头最大值，最小值同理。这个时候容易发现将 $a_n-a_1$ 直接丢到 $q2$ 的队尾一定是没问题的，因为编号为 $n$ ，长度为 $a_n-a_1$ 的这条蛇，一定比上一个 $q2$ 的队尾要小。

但是还有一种情况。

• $a_n$ 吃掉 $a_1$ 后成为最小蛇。

容易发现，接下来的” 最大蛇吃掉最小蛇后剩下的长度” 有可能比 $a_n-a_1$ 要大，如果依旧强行插入至 $q2$ 队尾的话，不会破坏单调性么？

显然不会，因为上一个插入的 $a_n-a_1$ 已经被取出来了。可能这下连续的几次都满足” 最大蛇吃掉最小蛇后，成为了最小蛇”，但每一次都是将上一次放到 $q2$ 队尾中的元素取出来了。所以不会破坏单调性。

因此，每一次直接将 剩下的长度 插入至 $q2$ ，是不会破坏单调性的。

按照这样直接维护，单次时间复杂度是 $O(n)$ 的。

const int N=1e6+5;

int n,a[N],b[N],die[N],top[N];
deque <pii> q1,q2,tmp;

#define pp pop_back
#define po pop_front
#define pb push_back
#define pf push_front

int dfs(int dep) {
    if(dep==1) return 1;
    int ans=dfs(dep-1);
    return (die[top[dep]]>ans)?dep:ans;
}

inline pii _min(deque <pii> &q) {return q.empty()?mkp(inf,0):q.back();}
inline pii _max(deque <pii> &q) {return q.empty()?mkp(-1,0):q.front();}

inline void solve() {
    while(!q1.empty()) q1.pp();
    while(!q2.empty()) q2.pp();
    lep(i,1,n) q1.pf(mkp(b[i]=a[i],i)),die[i]=-1;

    int x,y;
    rep(i,n,2) {
        (_max(q1)>_max(q2))?(x=q1.fro().se,q1.po()):(x=q2.fro().se,q2.po());
        (_min(q1)<_min(q2))?(y=q1.bac().se,q1.pp()):(y=q2.bac().se,q2.pp());
        q2.pb(mkp(b[x]-=b[y],x)),top[i]=x,die[y]=i;
    }

    printf("%d\n",dfs(n));
}

上面这个做法其实是有问题的。我们不能保证 $q2$ 里面蛇的编号也是正确的。

考虑另一种做法，依然将第 $i$ 次的” 大蛇吃小蛇” 分成下列两种情况：

• 吃了之后，大蛇变成最小的蛇。
• 吃了之后，大蛇不变成最小的蛇。

对于第二种情况显然大蛇一定会选择吃，因为第 $i+1$ 次的大蛇吃掉小蛇后一定比这只蛇要小。

第一种情况的话，只需要考虑奇偶性即可。

容易发现，只要出现了第一种情况，那么结束的局面一定在这一段第一种情况之中了。所以尽管之前的队列做法有问题，在这里也绝对不会出问题了。

const int N=1e6+5;
const int inf=1e9+7;

int n,ans,a[N],b[N];
deque <pii> q1,q2;

inline pii _min(deque <pii> &q) {return q.empty()?mkp(inf,0):q.back();}
inline pii _max(deque <pii> &q) {return q.empty()?mkp(-1,0):q.front();}

inline void solve() {
    while(!q1.empty()) q1.pp();
    while(!q2.empty()) q2.pp();
    lep(i,1,n) q1.pf(mkp(b[i]=a[i],i));

    int x,y,cur=-1; ans=0;
    for(int i=n;i>=2;--i) {
        (_max(q1)>_max(q2))?(x=q1.fro().se,q1.po()):(x=q2.fro().se,q2.po());
        (_min(q1)<_min(q2))?(y=q1.bac().se,q1.pp()):(y=q2.bac().se,q2.pp());
        pii now=mkp(b[x]-=b[y],x);

        if(i>2&&now<min(_min(q1),_min(q2))) {(~cur)?(cur^=1):(cur=0);}
        else {if(~cur) return ans+=cur,printf("%d\n",n-ans),void(); ++ans;}
        q2.pb(now);
    }
    printf("%d\n",n-ans);
}

总结：

这一次 T4 只拿到了 $40$ 分是十分的遗憾，考试的时候应当一直都要专心，时间是十分宝贵的。按照常理来说，剩下一个半小时只打了一个爆搜是十分不应该的。找我看来正常发挥的话其实是可以拿到 $70$ 的。就可以避免被一些人踩了。

不过好的是，前三题思路都较为清晰，代码也十分整洁，因此暂时没有 fst 。愿以后都可以做到这一点，减少 fst 的次数嗷 >_< 。