Codeforces Round #528 (Div. 1)

发表于 分类于

https://codeforces.com/contest/1086

B. Minimum Diameter Tree

最优方案是把总和分摊到所有和叶子相邻的边上，因为否则我们可以每次把直径上边上的权值挪到所有叶子节点上均分一定更优。

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
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int cnt,d[maxn],n,s;
 
int main() {
    read(n),read(s);
    for(int i=1,x,y;i<n;i++) read(x),read(y),d[x]++,d[y]++;
    for(int i=1;i<=n;i++) if(d[i]==1) cnt++;
    printf("%.10lf\n",2.0*s/cnt);
    return 0;
}

C. Vasya and Templates

我是直接爆搜搜过去的。。。加几个剪枝跑的飞快。

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
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int n,k,tr[200],vis[200];
char s[maxn],a[maxn],b[maxn],t[maxn];
 
int dfs(int x,int dn,int up) { // dn,up分别表示前面有没有大于（小于）a (b)
    if((dn&&up)||x==n+1) return 1;int p;
    if(p=tr[s[x]]) {
        if((!dn&&p<a[x])||(!up&&p>b[x])) return 0;
        return dfs(x+1,dn|(p>a[x]),up|(p<b[x]));
    } else {
        for(int i=dn?1:a[x];i<=(up?k:b[x]);i++) {
            if(vis[i]) continue;
            tr[s[x]]=i;vis[i]=1;
            if(dfs(x+1,dn|(i>a[x]),up|(i<b[x]))) return 1;
            tr[s[x]]=0;vis[i]=0;
        }
    }return 0;
}
 
void solve() {
    read(k);scanf("%s%s%s",s+1,a+1,b+1);n=strlen(s+1);
    for(int i=0;i<=26;i++) tr[i]=vis[i]=0;
    for(int i=1;i<=n;i++) s[i]=s[i]-'a'+1,a[i]=a[i]-'a'+1,b[i]=b[i]-'a'+1;
    if(dfs(1,0,0)) {
        puts("YES");
        for(int i=1;i<=k;i++) {
            if(!tr[i]) for(int j=1;j<=k;j++) if(!vis[j]) {vis[j]=1,tr[i]=j;break;}
            putchar(tr[i]+'a'-1);
        }puts("");
    } else puts("NO");
}
 
int main() {
    int t;read(t);while(t--) solve();
    return 0;
}

D. Rock-Paper-Scissors Champion

假设我们现在要判断$x$能不能成为冠军，假设他要出$\rm S$，那么他不能成为冠军当且仅当他左边或右边所有可能成为冠军的人都可以打败他，也就是左边或右边不能出现$P$并且至少有一个$R$。其他的情况也等价。

那么用树状数组和$\rm set$维护一下就好了。

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
76
77
78
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int n,q;
char r[maxn];
 
struct BIT {
    int t[maxn];
    void modify(int x,int a) {for(;x<=n;x+=x&-x) t[x]+=a;}
    int query(int x,int res=0) {for(;x;x-=x&-x) res+=t[x];return res;}
}t[4];
 
set<int > s[4],w[4];
 
int trans(char c) {return c=='S'?1:(c=='P'?2:3);}
 
int calc() {
    int ans=n;
    for(int x=1;x<=3;x++) {
        int y=x-1;if(!y) y=3;int z=6-x-y;
        if(!s[z].size()) return s[y].size()?s[y].size():n;
    }
    for(int x=1;x<=3;x++) {
        int y=x-1;if(!y) y=3;
        int z=6-x-y;
        int p=*s[z].rbegin(),q=max(*s[y].rbegin(),*s[z].rbegin());
        if(q>p) ans-=t[x].query(q-1)-t[x].query(p);
        p=*s[z].begin(),q=min(*s[y].begin(),*s[z].begin());
        if(p>q) ans-=t[x].query(p)-t[x].query(q);
    }return ans;
}
 
int main() {
    read(n),read(q);scanf("%s",r+1);
    for(int i=1;i<=n;i++) r[i]=trans(r[i]);
    for(int i=1;i<=n;i++) {
        t[r[i]].modify(i,1),s[r[i]].insert(i);
        for(int x=1;x<=3;x++) if(x!=r[i]) w[x].insert(i);
    }write(calc());
    for(int i=1;i<=q;i++) {
        int x;char op;read(x),cin>>op;
        t[r[x]].modify(x,-1),s[r[x]].erase(x),w[r[x]].insert(x);
        r[x]=trans(op);
        t[r[x]].modify(x,1),s[r[x]].insert(x),w[r[x]].erase(x);
        write(calc());
    }
    return 0;
}

E. Beautiful Matrix

有毒这题。。我本来以为一眼就会写了，然后越写代码越多。。。最后写了好久才写完。

首先考虑一个这样的问题：有多少个长度为$n$的排列满足前$k$个$a_i\ne i$。

这个问题也可以说成有任意$k$个$a_i$满足$a_i\ne b_i$，其中$b_i$互不相同，也就是说有任意$k$个限制都等价，设这个问题的答案为$g_{n,k}$，我们考虑$\rm dp$。

我们先忽略第$k$个限制，那么前面的方案数$g_{n,k-1}$转移过来，然后我们在减去不满足第$k$个限制的方案数，也就是$g_{n-1,k-1}$，方程就是：

边界是$g_{n,0}=n!$。

然后我们按字典序的顺序枚举，每次求出前面都一样，这一位比给出来的矩阵少的方案数加起来就好了，也就是当前这一行剩下来的几位的方案数乘以下面几层的方案数。

若干层的方案数非常好算，设为$f_i$，那么乘以每次的方案就好了，也就是$f_i=f_{i-1}\cdot g_{n,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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 2000+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;
 
int n,fac[maxn],f[maxn],ifac[maxn],v[maxn],a[maxn][maxn],g[maxn][maxn],w[maxn];
 
struct BIT {
    int t[maxn];
    void clear() {memset(t,0,sizeof t);}
    void modify(int x,int v) {for(;x<=n;x+=x&-x) t[x]+=v;}
    int query(int x,int ans=0) {for(;x;x-=x&-x) ans+=t[x];return ans;}
}T,r;
 
int c(int aa,int b) {return 1ll*fac[aa]*ifac[b]%mod*ifac[aa-b]%mod;}
 
int qpow(int aa,int x) {
    int res=1;
    for(;x;x>>=1,aa=1ll*aa*aa%mod) if(x&1) res=1ll*res*aa%mod;
    return res;
}
 
void gen() {
    fac[0]=ifac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=1;i<=n;i++) ifac[i]=1ll*ifac[i-1]*qpow(i,mod-2)%mod;
 
    g[0][0]=1;
    for(int i=1;i<=n;i++) {
        g[i][0]=fac[i];//printf("%d ",fac[i]);
        for(int j=1;j<=i;j++)
            g[i][j]=(g[i][j-1]-g[i-1][j-1]+mod)%mod;//,printf("%d ",g[i][j]);
    }
 
    f[0]=1;
    for(int i=1;i<=n;i++) f[i]=1ll*g[n][n]*f[i-1]%mod;
    // for(int i=0;i<=n;i++) printf("f[%d] :: %d\n",i,f[i]);    
}
 
void del(int x) {if(v[x]) T.modify(x,-1),v[x]=0;}
 
void delr(int x) {
    if(w[x]) w[x]=0,r.modify(x,-1);
    // ,printf("delr :: %d\n",x);
}
 
int main() {
    read(n),gen();int ans=0;
    for(int i=1,x;i<=n;i++) {
        T.clear();r.clear();
        // puts("\n\n");
        for(int j=1;j<=n;j++) w[j]=v[j]=1,T.modify(j,1),r.modify(j,1);
        for(int j=1;j<=n;j++) {
            read(x),a[i][j]=x;
            if(i==1) {
                if(j>1) del(a[i][j-1]);
                ans=(ans+1ll*T.query(x-1)*f[n-i]%mod*g[n-j][0]%mod)%mod;
                continue;
            }
            if(j>1) del(a[i][j-1]),delr(a[i][j-1]);
            if(i>1) delr(a[i-1][j]);
            // int pre=ans;
            int p=r.query(x-1);if(a[i-1][j]<x&&w[a[i-1][j]]) p--;
            // write(p);
            ans=(ans+1ll*p*f[n-i]%mod*g[n-j][r.query(n)-1]%mod)%mod;
            
            p=T.query(x-1)-r.query(x-1);if(a[i-1][j]<x&&v[a[i-1][j]]&&!w[a[i-1][j]]) p--;
            ans=(ans+1ll*p*f[n-i]%mod*g[n-j][r.query(n)]%mod)%mod;
 
            // if(pre-ans) printf("%d %d %d\n",i,j,ans-pre);
        }
    }write(ans);
    return 0;
}