Featured image of post Codeforces Round #789 (Div. 2)

Codeforces Round #789 (Div. 2)

小号,RANK450,+47

https://codeforces.com/contest/1678

A.Tokitsukaze and All Zero Sequence

 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
int n;
int a[MAXN];

inline void work(signed CASE=1,bool FINAL_CASE=false) {
    n=read();
    int zero=0;
    set<int> s;
    for(int i=1;i<=n;i++) {
        int x=read();
        zero+=(x==0);
        s.insert(x);
    }
    if(zero) {
        printf("%d\n",n-zero);
        return;
    }
    int k=n-sz(s);
    if(k==0) {
        printf("%d\n",n+1);
    } else {
        printf("%d\n",n);
    }
    return;
}

signed main() {
    // ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen(".in", "r", stdin);//freopen(".out", "w", stdout);
    signed T=(signed)read();//scanf("%d",&T);//cin>>T;
    for(signed CASE=1; CASE<=T; CASE++) { //
        //printf("Case #%d: ",CASE); //printf("Case %d: ",CASE); //printf("Case #%d: \n",CASE); //printf("Case %d: \n",CASE);
        work(CASE,CASE==T);
        if(CASE!=T) {}
    }
    return 0;
}

B1.Tokitsukaze and Good 01-String (easy version)

 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
int n,ans;
bool flag;
char lst=0;

inline void work(signed CASE=1,bool FINAL_CASE=false) {
    n=read(); vector<int> v;
    for(int i=1;i<=n;i++) {
        char c=nc();
        if(c==lst) {
            v.back()++;
        } else {
            v.pb(1);
            lst=c;
        }
    }
    for(auto x:v) {
        if(x&1) {
            flag=!flag;
        }
        ans+=flag;
    }
    printf("%lld\n",ans);
    return;
}

signed main() {
    // ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen(".in", "r", stdin);//freopen(".out", "w", stdout);
    signed T=(signed)read();//scanf("%d",&T);//cin>>T;
    for(signed CASE=1; CASE<=T; CASE++) { //
        //printf("Case #%d: ",CASE); //printf("Case %d: ",CASE); //printf("Case #%d: \n",CASE); //printf("Case %d: \n",CASE);
        work(CASE,CASE==T);
        if(CASE!=T) {
            ans=0;
            flag=false;
            lst=0;
        }
    }
    return 0;
}

B2.Tokitsukaze and Good 01-String (hard version)

一开始没找出B2规律,然后被带飞

 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
int n,ans,ls=-1,cnt;
bool flag;
char lst=0;

inline void work(signed CASE=1,bool FINAL_CASE=false) {
    n=read(); vector<int> v;
    for(int i=1;i<=n;i++) {
        char c=nc();
        if(c==lst) {
            v.back()++;
        } else {
            v.pb(1);
            lst=c;
        }
    }
    for(auto &x:v) {
        if(x&1) {
            flag=!flag;
            x=(x==1)?0:x;
        } else if(flag) {
            x=(x==2)?0:x;
        }
        ans+=flag;
    }
    for(int i=0;i<sz(v);i++) {
        if(0!=v[i] && ls!=(i&1)) {
            ls=i&1;
            cnt++;
        }
    }
    printf("%lld %lld\n",ans,cnt>1?cnt:1);
    return;
}

signed main() {
    // ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen(".in", "r", stdin);//freopen(".out", "w", stdout);
    signed T=(signed)read();//scanf("%d",&T);//cin>>T;
    for(signed CASE=1; CASE<=T; CASE++) { //
        //printf("Case #%d: ",CASE); //printf("Case %d: ",CASE); //printf("Case #%d: \n",CASE); //printf("Case %d: \n",CASE);
        work(CASE,CASE==T);
        if(CASE!=T) {
            lst=cnt=ans=0;
            flag=false;
            ls=-1;
        }
    }
    return 0;
}

C.Tokitsukaze and Strange Inequality

 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
int n,ans;
int a[MAXN];
int f[5009][5009];

inline void work(signed CASE=1,bool FINAL_CASE=false) {
    n=read();
    for(int i = 1; i <= n; i++) {
        a[i]=read();
    }
    for(int i = 1; i <= n; i++) {
        f[i][n] = a[n] < a[i];
        for(int j = n - 1; j >= i + 1; j--) {
            f[i][j] = f[i][j + 1] + (a[j] < a[i]);
        }
    }
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            f[i][j] += f[i - 1][j];
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++) {
            if(a[j]>a[i]) {
                int l=i+1,r=j-1;
                if(l<=r && r<n-1) {
                    ans+=(f[r][r + 2] - f[l - 1][r + 2]);
                }
            }
        }
    }
    printf("%lld\n",ans);
    return;
}

signed main() {
    // ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen(".in", "r", stdin);//freopen(".out", "w", stdout);
    signed T=(signed)read();//scanf("%d",&T);//cin>>T;
    for(signed CASE=1; CASE<=T; CASE++) { //
        //printf("Case #%d: ",CASE); //printf("Case %d: ",CASE); //printf("Case #%d: \n",CASE); //printf("Case %d: \n",CASE);
        work(CASE,CASE==T);
        if(CASE!=T) {
            ans=0;
        }
    }
    return 0;
}
Built with Hugo
主题 StackJimmy 设计