[CF 1096] 题目分析

Posted on | Edited on | In , | Views:

链接

Educational Codeforces Round 57

A

由于题目保证有解，所以直接输出(l,2*l)就行了。

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
using namespace std;
int T,x,y; 
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
int main(){
    read(T);
    while (T--){
        read(x),read(y);
        printf("%d %d\n",x,2*x);
    }
    return 0;
}

B

由于删除的是一个子串，所以最后留下的一定是个前缀或者后缀，那么我们就先暴力算出前缀的前多少位一样，后缀的最后多少位是一样的，设为a1和a2。
由于题目保证整个串中至少出现两种字符，所以$a1+a2$一定$\le n$
再看一下整个串的第一位和最后一位是否一样，如果相等，那么答案就是$(a1+1)*(a2+1)+1$
否则输出$a1+a2+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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (200005)
using namespace std;
int n,a1,a2;
char s[N],pp;
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
int main(){
    read(n);
    scanf("%s",s+1);
    pp=s[1];
    a1=1;
    for (int i=2;i<=n;i++){
        if (s[i]==pp) a1++;
        else break;
    } 
    for (int i=n;i>=1;i--){
        if (s[i]==s[n]) a2++;
        else break;
    }
    if (s[n]==pp){
        printf("%d",1ll*(a1+1)*(a2+1)%998244353);
    }
    else{
        printf("%d",a1+a2+1);
    }
    return 0;
}

C

由于数据范围较小，我们考虑直接枚举正i边形是否可行。
判断的话要根据两个条件,
(1) $n*i%180==0$，我要是这个i边形内最小角的倍数
(2) $n*i<=(i-2)*180$，不能大于这个正i边形的最大内角

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
using namespace std;
int T,n; 
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
int gcd(int a,int b){
    while (a%b!=0){
        int tmp=b;
        b=a%b;
        a=tmp;
    }
    return b;
}
int main(){
    read(T);
    while (T--){
        read(n);
        bool flag=0;
        for (int i=3;i<=360;i++){
            if (n*i%180==0&&n*i<=(i-2)*180){
                flag=1;
                printf("%d\n",i);
                break; 
            }
        }
        if (!flag) puts("-1");
    }

    return 0;
}

D

考虑直接dp，f[i][j]表示到了第i个字符，hard这个结构只拥有前j个字符的最小代价，显然j的范围是$[0,3]$。
转移的话看下第i个是不是”h”,”a”,”r”,”d”中的一个，如果是的话要花这个代价删除，直接看代码吧。

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<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
using namespace std;
int n; 
int a[N];
LL f[N][5];
char c[N];
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
int main(){
    read(n);
    scanf("%s",c+1);
    for (int i=1;i<=n;i++) read(a[i]);
    for (int i=1;i<=n;i++){
        f[i][0]=f[i-1][0];
        for (int j=1;j<=3;j++) f[i][j]=min(f[i-1][j],f[i][j-1]);
        if (c[i]=='h') f[i][0]=f[i-1][0]+a[i];
        else if (c[i]=='a') f[i][1]=f[i-1][1]+a[i];
        else if (c[i]=='r') f[i][2]=f[i-1][2]+a[i];
        else if (c[i]=='d') f[i][3]=f[i-1][3]+a[i];
        //printf("%lld %lld %lld %lld\n",f[i][0],f[i][1],f[i][2],f[i][3]);
    } 
    LL minn=1e18;
    for (int j=0;j<=3;j++) minn=min(minn,f[n][j]);
    printf("%lld",minn);
    return 0;
}

E

考场上没来得及看，待更

F

由于期望的线性性，我们可以把整个期望的贡献分成三类，-1对-1，其他数字与其他数字，-1与其他数字。
对于第一类贡献，令$f[i]$表示$[1,i]$的排列，逆序对数量的期望，考虑加入第i+1个数，放在最前面会产生i的贡献，向后移一位贡献-1，一共有i+1个位置可以放，分别能产生i,i-1,i-2…0的贡献，所以$f[i+1]=f[i]+\frac{(i+1)*i}{2*(i+1)}$，化简为通项式可得$f[i]=\frac{i*(i-1)}{4}$
对于第二类贡献，直接树状数组求逆序对可得。
对于第三类贡献，我们实际上就是考虑每个-1填每个数贡献的和，注意这里的贡献不能直接加。
设-1的个数为tot，我们确定了这一位，贡献为x,剩下(tot-1)位不管怎么取对贡献没有影响，所以$x*((tot-1)!)$是最后的贡献，再除以$tot!$就是期望，即$\frac{x}{tot}$。
但是这个贡献并不好算，我们考虑每个已经确定的数对-1的贡献，显然是我前面-1的个数乘上比我大的没取的数的个数，加上我后面-1的个数乘上比我小的没取的数的个数，把每一位的这个贡献sigma起来，乘以一个总-1数tot的逆元加到最后答案里就好了。

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define int long long
#define N (200005)
using namespace std;
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
int n,tot,ans,jc=1,res,inv;
int a[N],T[N],sum[N];
bool vis[N];
const int P=998244353;
inline void add(int x){
    for (int i=x;i<=n;i+=i&-i) T[i]++;
}
inline int query(int x){
    int ret=0;
    for (int i=x;i;i-=i&-i) ret+=T[i];
    return ret; 
}
int ksm(int a,int b){
    if (b==0) return 1;
    int ret=1;
    while (b>1){
        if (b&1) ret=1ll*ret*a%P;
        b>>=1;
        a=1ll*a*a%P;
    }
    return 1ll*a*ret%P;
}
signed main(){
    read(n);
    for (int i=1;i<=n;i++){
        read(a[i]);
        if (a[i]==-1) tot++,jc=1ll*jc*tot%P;
        else vis[a[i]]=1;
    }
    ans=1ll*tot*(tot-1)%P*ksm(4,P-2)%P;
    res=tot;
    inv=ksm(tot,P-2);
    for (int i=n;i>=1;i--){
        if (a[i]!=-1) ans=(ans+query(a[i]-1))%P,add(a[i]);
    }
    for (int i=1;i<=n;i++){
        sum[i]=sum[i-1];
        if (!vis[i]) sum[i]++;
    }
    for (int i=1;i<=n;i++){
        if (a[i]==-1) res--;
        else{
            ans=(ans+(1ll*sum[a[i]]*res%P+1ll*(tot-sum[a[i]])*(tot-res)%P)%P*inv%P)%P;
        }
    }
    printf("%lld",ans);
    return 0;
}

G

第一感是dp，以f[i][j]表示已经确定了前i个数，前一半与后一半的差为j的方案数，但是这个差值可能会非常大，这个状态存不下。
考虑生成函数。
例如能去0,2,3,5,9，我们就用多项式$x^0+x^2+x^3+x^5+x^9$来表示，令这个多项式的n/2次幂为f，那么f中$x^k$的系数就可以表示组成k的方案数了。
至于多项式的幂次可以不用分治+NTT
考虑NTT第一步的本质，就是把系数表达式转化成点值表达式。众所周知点值是可以直接乘的，那么直接把NTT过的点值快速幂后NTT回来就行了。
最后的答案就是每一项系数的平方的和

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (6000005)
using namespace std;
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
const int P=998244353;
int n,k,x,ans,lim;
int f[N],R[N],b[N];
int ksm(int a,int b){
    int ret=1;
    while (b>1){
        if (b&1) ret=1ll*ret*a%P;
        b>>=1;
        a=1ll*a*a%P;
    }
    return 1ll*ret*a%P;
}
inline void NTT(int *f,int G){
    for (int i=0;i<lim;i++){
        if (i>R[i]) swap(f[i],f[R[i]]);
    }
    for (int i=1;i<lim;i<<=1){
        int w0=ksm(G,(P-1)/(i<<1));
        for (int j=0;j<lim;j+=(i<<1)){
            int w=1;
            for (int k=j;k<j+i;k++){
                int t=1ll*f[k+i]*w%P;
                f[k+i]=(f[k]-t+P)%P;
                f[k]=(f[k]+t)%P;
                w=1ll*w*w0%P;
            }
        }
    }
}
int main(){
    read(n),read(k);
    lim=4194304;
    for (int i=0;i<lim;i++) R[i]=(R[i>>1]>>1)|((i&1)*lim>>1);
    for (int i=1;i<=k;i++){
        read(x);
        f[x]=1;
    }
    NTT(f,3);
    for (int i=0;i<lim;i++){
        b[i]=ksm(f[i],n/2);
    }
    NTT(b,ksm(3,P-2));
    int inv=ksm(lim,P-2);
    for (int i=0;i<lim;i++) b[i]=1ll*b[i]*inv%P;
    for (int i=0;i<lim;i++){
        ans=(ans+1ll*b[i]*b[i]%P)%P;
    }
    printf("%d",ans);
    return 0;
}