Skip to content

AGC002 做题记录

A

略。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#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 main(){
    int a=read(),b=read();
    if(a<=0&&b>=0)puts("Zero");
    else if(b<0&&(b-a+1)%2==1)puts("Negative");
    else puts("Positive");
    return 0;
}

B

我们维护每个盒子里面的球数以及当前是否有红球，转移是显然的。

 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;
}
const int N=1e5+5;
int num[N];
bool vis[N];
int main(){
    int n=read(),m=read(),ans=0;
    vis[1]=1;rep(i,1,n)num[i]=1;
    rep(i,1,m){
        int x=read(),y=read();
        if(vis[x])vis[y]=1;
        num[x]--;num[y]++;
        if(num[x]==0)vis[x]=0;
    }
    rep(i,1,n)if(vis[i])ans++;
    cout<<ans<<endl;
    return 0;
}

C

先考虑什么时候无解。发现如果最长的两段合并成的一段都无法剪开的话，那么最后至少会有两段无法剪开，无解。

反之我们发现一个包含可剪开子段的一段绳子一定也是可剪开的，我们保留最长的 \(a_i+a_{i+1}\) 就可以了。

 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
#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=1e5+5;
int a[N];
int main(){
    int n=read(),l=read(),len=0,pos;
    rep(i,1,n)a[i]=read();
    rep(i,1,n-1){
        if(a[i]+a[i+1]>len){
            len=a[i]+a[i+1];pos=i;
        }
    }
    if(len<l)return puts("Impossible"),0;
    puts("Possible");
    rep(i,1,pos-1)printf("%d ",i);
    for(int i=n-1;i>=pos;i--)printf("%d ",i);
    puts("");
    return 0;
}

D

题目开始有意思了起来

最大值最小和单调性提示了我们二分答案 \(k\) 。于是我们可以把 \(id\le k\) 的边全部连上，并把当前 \(x,y\) 所在的连通块的大小加起来。如果 \(\ge z\) 则答案不大于 \(k\) ，反之大于 \(k\) 。

这样的暴力时间复杂度是 \(O(QN\log M)\) ，考虑优化。因为询问全部是离线的，可以用整体二分算法，时间复杂度为 \(O((N+M+Q)\log M)\) 。

 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
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
#define fi first
#define se second
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=1e5+5;
struct Edge{int x,y;}e[N];
struct Query{int x,y,z;}q[N];
struct Bin{int fi,se,mid;}p[N];
vector<int> v[N];
int n,m,Q,ans[N],fa[N],sz[N];
inline int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
inline void merge(int u,int v){
    int fu=find(u),fv=find(v);
    if(fu==fv)return;
    fa[fu]=fv,sz[fv]+=sz[fu];
}
int main(){
    n=read(),m=read();
    rep(i,1,m)e[i].x=read(),e[i].y=read();
    Q=read();
    rep(i,1,Q){
        q[i].x=read(),q[i].y=read(),q[i].z=read();
        p[i].fi=1,p[i].se=m;
    }
    rep(t,1,20){
        rep(i,1,m)v[i].clear();
        rep(i,1,Q)if (p[i].fi != p[i].se) v[p[i].mid = (p[i].fi + p[i].se) >> 1].push_back(i);
        rep(i,1,n) fa[i] = i, sz[i] = 1;
        rep(i,1,m){
            merge(e[i].x, e[i].y);
            for (auto k : v[i]) {
                int x = q[k].x, y = q[k].y, fx = find(x), fy = find(y);
                if (fx != fy)
                    ans[k] = sz[fx] + sz[fy];
                else
                    ans[k] = sz[fx];
            }
        }
        rep(i,1,Q)if (p[i].fi != p[i].se) {
            if (ans[i] >= q[i].z)
                p[i].se = p[i].mid;
            else
                p[i].fi = p[i].mid + 1;
        }
    }
    rep(i,1,Q)printf("%d\n",p[i].fi);
    return 0;
}

E

博弈论经典题目。

可以发现将数组降序排列后看成一堆方块，每次操作相当于把最左边的一列或者最底下一行的方块消除，消除最后一个方块的人输掉游戏。下面用 \((x,y)\) 表示消掉了前 \(x\) 列 和前 \(y\) 行的所有方块。

（这里就不再赘述必胜态和必败态的定义了）

引理：若 \((x+1,y+1)\) 没有消除全部方块，那么 \((x,y)\) 和 \((x+1,y+1)\) 的状态相同。

证：

  • 若 \((x+1,y+1)\) 是必败态，则先手从 \((x,y)\) 无论怎么走，后手都可以转移到 \((x+1,y+1)\) 这个状态。

  • 若 \((x+1,y+1)\) 是必胜态，由定义知道 \((x+2,y+1)\) 和 \((x+1,y+2)\) 至少有一个必败态（消除全部方块后先手必胜，所以必败态必然满足假设）。不妨设 \((x+2,y+1)\) 是必败态，那么由上一种情况推出 \((x+1,y)\) 是必败态，它与 \((x,y)\) 相邻。所以 \((x,y)\) 是必胜态。

这样就证明了初始状态 \((0,0)\) 等价于最大的 \((x,x)\) 。而最大化 \(x\) 意味着这个点之后只能沿单方向 \(+1\) ，判断是否存在一个方向需要奇数次操作消除即可。

 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
#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=1e5+5;
int a[N],n;
bool cmp(int x,int y){return x>y;}
int main(){
    n=read();
    rep(i,1,n)a[i]=read();
    sort(a+1,a+n+1,cmp);
    rep(i,1,n){
        if(i+1>a[i+1]){
            int ans=0;
            for(int j=i+1;a[j]==i;++j)ans^=1;
            ans|=(a[i]-i)&1;
            puts(ans?"First":"Second");
            break;
        }
    }
    return 0;
}

F

不难发现对于满足条件的序列，任何前缀中白色球的个数都要超过其他颜色的种类数。于是我们考虑依次填入白色球或者一个种类的所有球。

令 \(dp[i][j]\) 为填入了前 \(i\) 个白色球，以及 \(j\) 种出现最靠前的彩色球时的方案数，此时显然有 \(i\ge j\) 。

考虑转移，

  • 放入一个白色球。任何情况都可以在第一个未填入的地方填上白球，于是有
\[ dp[i+1][j]+=dp[i][j] \]
  • 放入一种彩色球。我们从 \(dp[i][j]\) 转移到 \(dp[i][j+1]\) ，这时需要满足 \(i \ge j+1\) 否则无法合法放入。有 \((n-j)\) 种未出现的颜色可以给我们选择，而填入了最靠前的空位之后，我们还有 \(k-2\) 个彩色球未放置。这些彩色球有 \((nk-i-j(k-1)-1)\) 个空位可选，于是转移为
\[ dp[i][j+1]+=dp[i][j]\times (n-j)\times\binom{nk-i-j(k-1)-1}{k-2} \]

时间复杂度 \(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=2005,P=1e9+7;
ll fpow(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1)res=res*x%P;
        y>>=1;x=x*x%P;
    }
    return res;
}
int n,k,fac[N*N],ifac[N*N];
ll dp[N][N];
ll C(ll n,ll m){return 1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}
int main(){
    n=read(),k=read();
    if(k==1)return puts("1"),0;
    fac[0]=1;
    rep(i,1,n*k)fac[i]=1ll*fac[i-1]*i%P;
    ifac[n*k]=fpow(fac[n*k],P-2);
    for(int i=n*k;i>=1;i--)ifac[i-1]=1ll*ifac[i]*i%P;
    dp[0][0]=1;
    rep(i,1,n){
        rep(j,0,i){
            dp[i][j]=dp[i-1][j];
            if(!j)continue;
            dp[i][j]=(dp[i][j]+(n-j+1)*dp[i][j-1]%P*C(n-i+(n-j+1)*(k-1)-1,k-2)%P)%P;
        }
    }
    printf("%lld\n",dp[n][n]);
    return 0;
}

Comments