Codeforces Round #833 (Div. 2)

新会陈皮茶业

A - The Ultimate Square

理解题意后 ， 观察样例 。（~~签到题~~）
我们发现规律 \left \lceil n/2 \right \rceil  即是答案 ！
#include<bits/stdc++.h>
using namespace std;
#define open(x) freopen(x ".in", "r", stdin);freopen(x ".out", "w", stdout);

inline int read(){int f=1;int x=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){f=-f;}c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x*f;}
inline void wr(int x){if(x<0){putchar('-');x=-x;}if(x>9){wr(x/10);}putchar(x%10+'0');}


int T;
int n;

signed main(){
        T=read();
        while(T--){
                n=read();
                if(n&1){
                        wr(n/2+1);
                        puts(" ");
                }
                else{
                        wr(n/2);
                        puts(" ");
                }
        }
}
<hr/>B - Diverse Substrings

暴力枚举 l,r , 并用前缀和优化 ，时间复杂度 O_{(n^2)} 。
因为 \sum n\le1e5 , 所以若时间复杂度为 O_{(n^2)} , 必定会 TLE ! ! ! 。
考虑优化剪枝 。考虑最劣情况 ， 因为数字 0\sim9 共有十种 ，
故最长的满足题意的子串长度 == 种类 \times 每种字符出现次数 \le 10 \times 10 ==100 。
据此 ， len_{max} = r-l+1 \le 100 。时间复杂度 O_{(100 \sum n)} 。
注：参考代码中是通过求　不满足条件的子串　反求出　满足条件的子串 ！！！
#include<bits/stdc++.h>
using namespace std;
#define open(x) freopen(x ".in", "r", stdin);freopen(x ".out", "w", stdout);

inline int read()
{
        int f=1;
        int x=0;
        char c=getchar();
        while(c<'0'||c>'9') {
                if(c=='-') {
                        f=-f;
                }
                c=getchar();
        }
        while(c>='0'&&c<='9') {
                x=(x<<1)+(x<<3)+(c^48);
                c=getchar();
        }
        return x*f;
}
inline void wr(int x)
{
        if(x<0) {
                putchar('-');
                x=-x;
        }
        if(x>9) {
                wr(x/10);
        }
        putchar(x%10+'0');
}


int T;
char a[1000050];
int sum[1000050][10];

signed main()
{
        T=read();
        while(T--) {
                int n;
                n=read();
                for(int i=1; i<=n; ++i) {
                        cin>>a;
                        for(int j=0; j<=9; ++j) {
                                sum[j]=sum[i-1][j];
                                if(j==a-'0'){
                                        sum[j]++;
                                }
                        }
                }
                int ans = 0;
                for(int i=1; i<=n; ++i) {
                        int cnt = 0;
                        int maxa=-1;
                        for(int j=i; j<=min(i+100-1,n); ++j) {
                                if(sum[j][a[j]-'0']-sum[i-1][a[j]-'0']==1){
                                        cnt++;
                                }       
                                if(sum[j][a[j]-'0']-sum[i-1][a[j]-'0']>maxa){
                                        maxa=sum[j][a[j]-'0']-sum[i-1][a[j]-'0'];
                                }
                                if(cnt>=maxa) {
                                        ans++;
                                }
                        }
                }
                wr(ans);
                puts(" ");
        }
}
<hr/>C - Zero-Sum Prefixes

根据题意 ，可以多次修改 a_i = 0 的值 ，使得数列前缀和为 0 的个数最多 ！
若 a_{i_1}=a_{i_2}=\ldots=a_{i_k}=0 ,
据此 ，我们可以将数列划分为：
\bullet [s_1,s_2,\ldots,s_{i_1-1}]
\bullet [s_{i_2},s_{i_2+1},\ldots,s_{i_3-1}]
\dots
\bullet [s_{i_k},s_{i_{k+1}},\ldots,s_n]
每一段之间实际上是相互独立的 。
(因为 , 修改上一次的值 , 但是对于后面数的相对值不变 !)
即只需要考虑每一段的最优情况 ， 而对于每一段的最优情况 ，既是出现次数最多的前缀和 !
故时间复杂度 O_{(nlogn)} 。( map 的时间复杂度为 O_{(nlogn)}) 。
#include<bits/stdc++.h>
using namespace std;
#define open(x) freopen(x ".in", "r", stdin);freopen(x ".out", "w", stdout);

#define int long long
inline int read(){int f=1;int x=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){f=-f;}c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x*f;}
inline void wr(int x){if(x<0){putchar('-');x=-x;}if(x>9){wr(x/10);}putchar(x%10+'0');}

int T;
int n;
int a[1000050];
map<int,int> f;

inline void ok(){
        int presum=0;
        f.clear();
        int ans=0;
        bool have = 0;
        int maxzero=0;
        int n=read();
        for(int i=1;i<=n;++i){
                a=read();
        }
        a[n+1]=0;
        for(int i=1;i<=n+1;++i){
                if(a==0){
                        if(!have) ans+=f[0],have=1;
                        else ans+=maxzero;
                        maxzero=0;
                        f.clear();
                }
                presum+=a;
                maxzero=max(maxzero,++f[presum]);
        }
        wr(ans);
        puts(" ");
}

signed main(){
        T=read();
        while(T--){
                ok();
        }
        return 0;
}
/*
5
5
2 0 1 -1 0
3
1000000000 1000000000 0
4
0 0 0 0
8
3 0 2 -10 10 -30 30 0
9
1 0 0 1 -1 0 1 0 -1

*/

丁涛

楼下的接上