Skip to content

AGC005 做题记录

A

用栈加入元素，如果当前是'T'且前面是'S'消掉即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2e5+5;
char s[N];
int st[N],top;
int main(){
    scanf("%s",s+1);
    for(int i=1;s[i];i++){
        if(s[i]=='S')st[++top]=1;
        if(s[i]=='T'){
            if(st[top])top--;
            else st[++top]=0;
        }
    }
    cout<<top<<endl;
    return 0;
}

B

直接暴力是 \(O(N^2)\) 的肯定不行，不妨考虑每个元素给答案的贡献。只需要对每个元素 \(a_i\) ，找出最小 \(l_i\) 和最大 \(r_i\) 使得 \([l_i,r_i]\) 区间中的最小值是 \(a_i\) ，可以用单调栈求出 \(l_i,r_i\) 。显然对于 \(l\in[l_i,i],r\in[i,r_i],[l,r]\) 区间中最小值也是 \(a_i\) 。于是 \(a_i\) 对答案的贡献就是 \((i-l_i+1)(r_i-i+1)a_i\) 。

时间复杂度： \(O(N)\) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2e5+5;
int n,a[N],l[N],r[N],st[N],top;
ll ans;
int main(){
    n=read();
    rep(i,1,n)a[i]=read();
    rep(i,1,n){
        while(top&&a[st[top]]>a[i]){
            r[st[top--]]=i-1;
        }
        st[++top]=i;
    }
    while(top)r[st[top--]]=n;
    per(i,n,1){
        while(top&&a[st[top]]>a[i]){
            l[st[top]]=i+1;top--;
        }
        st[++top]=i;
    }
    while(top)l[st[top--]]=1;
    rep(i,1,n){
        ans+=1ll*(r[i]-i+1)*(i-l[i]+1)*a[i];
    }
    printf("%lld\n",ans);
    return 0;
}

C

构造题。首先 \(M=\max a_i\) 为该树的直径。我们考虑直径上的点，它们在树上的最远距离显然是到直径的两个端点之一的距离，于是这些点的 \(a_i\) 取值应该为 \(M,M-1,M-2,\cdots,\lfloor M/2\rfloor+1,?,\lfloor M/2\rfloor +1,\dots,M\) 。当 \(M\) 为偶数时，\(?\) 处为两个 \(M/2\) ，为奇数时则不存在。因此，能构成树的必要条件是上述距离的边都要有足够数量。

接下来只用考虑这个条件是否充分，即考虑剩下多余的最远距离怎么与这条链关联。我们在链上除了头和尾的其他节点上继续挂节点就可以了，不难发现除了 \(\lceil M/2\rceil\) 这个距离（感性理解为树的半径）无法构造出来，其他距离都可以这么构造，于是这道题就解决了。因为 \(N\) 很小，实现过程中可以开桶记录距离 \(x\) 的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int n,c[110],mx;
int main(){
    n=read();
    rep(i,1,n){
        int x=read();++c[x];
        mx=max(mx,x);
    }
    int mid=(mx+1)>>1;
    for(int i=mx;i>mid;--i){
        if(c[i]<2)return puts("Impossible"),0;
        n-=c[i];
    }
    if(c[mid]!=1+(mx&1)||n!=c[mid])return puts("Impossible"),0;
    puts("Possible");
    return 0;
}

D

好dp计数题。

考虑 \(P_i=j\) 为 \((i,a_j)\) 之间连一条边，那么一个排列可以被转化成 \(n\) 个点与另 \(n\) 个点的一个匹配。再看 \(|P_i-i|\neq K\) 这个限制，正面不好做，我们考虑用容斥原理。即 \(f_i\) 为有 \(i\) 个地方与限制矛盾，答案就是 \(\sum_{i=1}^n (-1)^i\times f_i\) 。

具体地，我们把 \((i+K,a_i),(i-K,a_i)\) 连边，那么图上会形成若干条不相交的链，这些链上选了几条边作为匹配的边就会统计进 \(f_i\) 。不妨对这些不相交的链分别考虑，由于匹配中只用满足每个点只与另外一个点配对，我们可以记 \(dp[i][j][0/1]\) 为当前考虑到第 \(i\) 个点，连接了 \(j\) 条边，第 \(i-1\) 个点是否被匹配。于是有： 最终有 \(f_i=(n-i)!\times dp[2n][i]\) （剩下 \(n-i\) 个数可以随便排列 ）。

时间复杂度：\(O(N^2)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2010,P=924844033;
int n,k,tot;
ll fac[N],dp[N<<1][N][2],ans;
bool vis[N<<1];
inline ll Add(const ll x,const ll y){return (x+y>=P)?x+y-P:x+y;}
inline ll Del(const ll x,const ll y){return (x-y<0)?x-y+P:x-y;}
int main(){
    n=read(),k=read();
    fac[0]=1;
    rep(i,1,n)fac[i]=fac[i-1]*i%P;
    rep(i,1,k){
        rep(t,0,1){
            for(int j=i;j<=n;j+=k){
                tot++;
                if(i!=j)vis[tot]=1;
            }
        }
    }
    dp[0][0][0]=1;
    rep(i,1,n<<1)rep(j,0,n){
        dp[i][j][0]=Add(dp[i-1][j][0],dp[i-1][j][1]);
        if(vis[i]&&j)dp[i][j][1]=dp[i-1][j-1][0];
    }
    rep(i,0,n){
        if(i&1)ans=Del(ans,(dp[n<<1][i][0]+dp[n<<1][i][1])*fac[n-i]%P);
        else ans=Add(ans,(dp[n<<1][i][0]+dp[n<<1][i][1])*fac[n-i]%P);
    }
    printf("%lld\n",ans);
    return 0;
}

E

神仙题。

首先考虑先手如何一直苟下去。如果存在一条红边 \((u,v)\) ，而 \(u\) 和 \(v\) 在蓝树上的距离大于等于 \(3\) ，那么后手永远抓不到先手。因为先手可以等后手靠近其中一个节点后朝另一个节点跑，后手永远追不上先手。

下面我们开始考虑先手走到这样的边之前，游戏决策是怎样的。注意到这意味着先手经过的所有边在蓝树上距离不超过 \(2\) 。这可以进一步推出先手所在的点 \(v\) 在蓝树上一定在后手所在点 \(u\) 的子树上，可以通过归纳证明。没有操作时蓝树以后手节点为根，假设成立。而每一步操作先手的从 \(v\) 移动到 \(v'\) ，\((v,v')\) 在蓝树距离不超过 \(2\) ，这说明先手无法在蓝树中跨越后手所在的节点。如果跨越了则后手可以直接抓到它，不如不走。

从这个结论出发，对于点 \(u\) 在红树和蓝树上到各自根节点的距离 \(d_1,d_2\) ，如果有 \(d_1\ge d_2\) ，那么先手不会把棋子移动到这里。因为先手不跨过后手棋子，必然会比后手晚到这个节点。所以先手每次操作都要保证 \(d_1<d_2\) 。

最后可以搜索出是否能达到能无限操作的边，如果达到了答案就是 \(-1\) ；反之答案为最大的 \(d_2\) 的两倍，决策为先手走到这里原地等死。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2e5+5;
int n,x,y,dr[N],d[N],fa[N],mx;
bool flag;
vector <int> R[N],B[N];
void dfs1(int u,int f){
    for(int v:B[u])if(v!=f){
        fa[v]=u;d[v]=d[u]+1;
        dfs1(v,u);
    }
}
bool check(int u,int v){
    return u!=fa[v]&&v!=fa[u]&&u!=fa[fa[v]]&&v!=fa[fa[u]]&&fa[u]!=fa[v];
}
void dfs2(int u,int f,int dep){
    if(dep>=d[u])return;
    mx=max(mx,d[u]);
    for(int v:R[u])if(v!=f){
        if(check(u,v)){puts("-1");exit(0);}
        dfs2(v,u,dep+1);
    }
}
int main(){
    n=read(),x=read(),y=read();
    rep(i,1,n-1){
        int u=read(),v=read();
        R[u].push_back(v);R[v].push_back(u);
    }
    rep(i,1,n-1){
        int u=read(),v=read();
        B[u].push_back(v);B[v].push_back(u);
    }
    dfs1(y,0);dfs2(x,0,0);
    printf("%d\n",mx*2);
    return 0;
}

F

妙计数*2。

显然不能枚举子集，我们尝试算每个点对答案的贡献这种常见套路。不妨先考虑 \(u\) 对 \(f_k\) 的贡献，即有多少方案中的点集跨越 \(u\) ...还是有点不好求。

正难即反，观察发现容易求出对于 \(u\) 有多少方案不跨越它。如果一个点集的最小连通块不包含它，那么它一定在 \(u\) 的儿子的子树中 （树以 \(u\) 为根）。把大小为 \(s\) 的子树个数进行统计，拆开用组合数卷一卷就可以做到了，注意模数 \(924844033\) 的原根是 \(5\) 。

时间复杂度： \(O(n\log n)\) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
using namespace std;
const ll N=3e5+5,P=924844033,G=5,IG=554906420;
int n,lim,inv,head[N],tot;
ll A[N*10],B[N*10],fac[N],ifac[N];
struct Edge{int to,nxt;}e[N<<1];
inline void add(int u,int v){e[++tot]={v,head[u]};head[u]=tot;}
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
inline ll fpow(ll a,ll b){
    ll ret=1;
    while(b){
        if(b&1)ret=(ret*a)%P;
        b>>=1;a=(a*a)%P;
    }
    return ret;
}
int rev[N],cnt[N],sz[N];
ll C(int n,int m){return 1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}
inline void NTT(ll* A,int n,int op) {
    rep(i,0,n-1)if (i<rev[i]) swap(A[i],A[rev[i]]);
    for (int i=1;i<n;i<<=1) {
        ll rot=fpow(op==1?G:IG,(P-1)/(i<<1));
        for (int j=0;j<n;j+=i<<1)
            for (int k=0,w=1;k<i;++k,w=1ll*w*rot%P) {
                int x=A[j+k],y=1ll*w*A[j+k+i]%P;
                A[j+k]=(x+y)%P,A[j+k+i]=(x-y+P)%P;
            }
    }
    if (op==-1)rep(i,0,n-1)A[i]=1ll*A[i]*inv%P;
}
vector <int> E[N];
void dfs(int u,int fa) {
    sz[u] = 1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);sz[u]+=sz[v];++cnt[sz[v]];
    }
    ++cnt[n-sz[u]];
}
int main(){
    n=read();
    rep(i,1,n-1){
        int u=read(),v=read();
        add(u,v);add(v,u);
    }
    dfs(1,0);
    int lim=1,l=0;
    for (;lim<=n<<1;lim<<=1,++l);
    for (int i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
    inv=fpow(lim,P-2);
    fac[0]=1;
    rep(i,1,n)fac[i]=i*fac[i-1]%P;
    ifac[n]=fpow(fac[n],P-2);
    per(i,n,1)ifac[i-1]=ifac[i]*i%P;
    rep(i,1,n)A[i]=1ll*cnt[i]*fac[i]%P;
    reverse(A,A+n+1);
    rep(i,0,n)B[i]=ifac[i];
    NTT(A,lim,1);NTT(B,lim,1);
    rep(i,0,lim-1)A[i]=A[i]*B[i]%P;
    NTT(A,lim,-1);
    reverse(A,A+n+1);
    rep(i,1,n){
        printf("%lld\n",(n*C(n,i)%P-A[i]*ifac[i]%P+P)%P);
    }
    return 0;
}

Comments