湖南集训DAY2

水题统计0的前缀和

枚举一个位置i 判断i之前1的个数和i后面0的个数的和

取小

 1 #include <cstdio>
 2 #include <cctype>
 3 #include <cstring>
 4 
 5 const int MAXN=100010;
 6 
 7 int n,cnt,ans;
 8 
 9 int sum[MAXN];
10 
11 char s[MAXN];
12 
13 int hh() {
14 //    freopen("reverse.in","r",stdin);
15 //    freopen("reverse.out","w",stdout);
16     
17     scanf("%s",s+1);
18     n=strlen(s+1);
19     
20     for(int i=1;i<=n;++i) {
21         if(s[i]=='0') ++cnt,sum[i]=sum[i-1]+1;
22         else sum[i]=sum[i-1];
23     }
24     
25     ans=1e9;
26     for(int i=1;i<=n;++i) {
27         int t=0;
28         t+=i-1-sum[i-1];
29         t+=sum[n]-sum[i];
30         ans=ans>t?t:ans;
31     }
32     printf("%d
",ans);
33 
34     return 0;
35 }
36 
37 int sb=hh();
38 int main(int argc,char**argv) {;}

代码

10^7只能用O(n)的做法

枚举每一个数求一个相当于哈希值的数

若x,y的数码种类相同则这个哈希值也相同

一个哈希值的个数为C(sum,2);

 1 #include <cstdio>
 2 #include <cctype>
 3 #include <iostream>
 4 
 5 typedef long long LL;
 6 
 7 const int MAXN=10000010;
 8 
 9 LL ans;
10 
11 int n;
12 
13 int prime[10]={2,3,5,7,11,13,19,17,23,29};
14 
15 int prim[10]={101,103,107,109,113,127,131,137,233,151};
16 
17 LL cnt[MAXN];
18 
19 bool vis[MAXN][10];
20 
21 int hh() {
22 //    freopen("number.in","r",stdin);
23 //    freopen("number.out","w",stdout);
24     
25     scanf("%d",&n);
26 
27     int t,l,p=0;
28     for(int i=1;i<=n;++i) {
29         t=i;p=0;
30         while(t) {
31             l=t%10;
32             if(!vis[i][l]) p+=prim[l]*prime[l]+l*prime[l];
33             vis[i][l]=true;
34             t/=10;
35         }
36         ++cnt[p];
37     }
38     for(int i=1;i<=1000000;++i) 
39       if(cnt[i]>1) ans+=(LL)(cnt[i]-1)*(LL)cnt[i]/2;
40     
41     std::cout<<ans;
42     return 0;
43 }
44 
45 int sb=hh();
46 int main(int argc,char**argv) {;}

代码

贪心使偶数项上的数尽量大，使奇数项上的数尽量小

 1 #include <cstdio>
 2 #include <cctype>
 3 #define max(a,b) a<b?b:a
 4 #define min(a,b) a>b?b:a
 5 
 6 const int MAXN=2000010;
 7 
 8 int n,k,ans;
 9 
10 int a[MAXN];
11 
12 inline void read(int&x) {
13     int f=1;register char c=getchar();
14     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
15     for(;isdigit(c);x=x*10+c-48,c=getchar());
16     x=x*f;
17 }
18 
19 int hh() {
20     freopen("wave.in","r",stdin);
21     freopen("wave.out","w",stdout);
22 
23     read(n);read(k);
24     for(int i=1;i<=n;++i) read(a[i]);
25     
26     int last=a[1],flag=1,ans=1;
27     for(int i=2;i<=n;++i) {
28         if(flag) {
29             if(a[i]>=last+k) flag^=1,last=a[i],++ans;
30             else last=min(last,a[i]);
31         }
32         else {
33             if(last>=a[i]+k) flag^=1,last=a[i],++ans;
34             else last=max(last,a[i]);
35         }
36     }
37     printf("%d
",ans);
38     
39     return 0;
40 }
41 
42 int sb=hh();
43 int main(int argc,char**argv) {;}

代码