Codeforces Round #582 (Div. 3)

给定n个数，每个数加减2不需要花费，加减1需要花费1个coin，求将这n个数变为同一个数的最小花费

只需要求偶数个数和奇数个数即可，取较小值

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 #define ls(rt) (rt<<1)
24 #define rs(rt) (rt<<1|1)
25 #define lowbit(x) (x&(-x))
26 using namespace std; 
27 int n,odd,even,t;
28 int read()
29 {
30     int s=1,x=0;
31     char ch=getchar();
32     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
33     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
34     return x*s;
35 }
36 int main()
37 {
38     n=read();
39     for(int i=1;i<=n;++i) 
40     {
41         t=read();
42         if(t&1) odd++;
43         else even++;
44     }
45     cout<<min(odd,even)<<endl;
46 }

View Code

B、Bad Prices

给定一个序列，定义一个元素为bad为存在比它小的元素在它后面，求bad元素的个数

逆序，树状数组求

记得离散化

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 #define ls(rt) (rt<<1)
24 #define rs(rt) (rt<<1|1)
25 #define lowbit(x) (x&(-x))
26 using namespace std;
27 const int MAXN=150000+5;
28 int T[MAXN],a[MAXN],b[MAXN]; 
29 int n,t;
30 int read()
31 {
32     int s=1,x=0;
33     char ch=getchar();
34     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
35     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
36     return x*s;
37 }
38 int getsum(int x)
39 {
40     int ans=0;
41     for(int i=x;i>=1;i-=lowbit(i))
42     ans+=T[i];
43     return ans;
44 }
45 void update(int x,int v)
46 {
47     for(int i=x;i<=n;i+=lowbit(i))
48     T[i]+=v;
49 }
50 int main()
51 {
52     t=read();
53     while(t--)
54     {
55         mem(T,0);
56         n=read();
57         for(int i=1;i<=n;++i)
58         a[i]=read(),b[i]=a[i];
59         sort(b+1,b+n+1);
60         int res=0;
61         for(int i=n;i>=1;--i)
62         {
63             a[i]=lower_bound(b+1,b+n+1,a[i])-b;
64             if(getsum(a[i]-1)) res++;
65             update(a[i],1);
66         }
67         cout<<res<<endl;
68     }
69 }

View Code

emmm，其实想复杂了，逆序求，维护最小值就行，O(n)复杂度

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 #define ls(rt) (rt<<1)
24 #define rs(rt) (rt<<1|1)
25 #define lowbit(x) (x&(-x))
26 using namespace std;
27 const int MAXN=150000+5;
28 int a[MAXN]; 
29 int n,t;
30 int read()
31 {
32     int s=1,x=0;
33     char ch=getchar();
34     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
35     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
36     return x*s;
37 }
38 int main()
39 {
40     t=read();
41     while(t--)
42     {
43         n=read();
44         for(int i=1;i<=n;++i)
45         a[i]=read();
46         int res=0,small=1<<30;
47         for(int i=n;i>=1;--i)
48         {
49             if(a[i]>small) res++;
50             small=min(small,a[i]);
51         }
52         cout<<res<<endl;
53     }
54 }

View Code

C、Book Reading

对于每个n和m，求[1,n]中除以0余数为0的数的末尾数的和。

找规律

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 #define ls(rt) (rt<<1)
24 #define rs(rt) (rt<<1|1)
25 #define lowbit(x) (x&(-x))
26 using namespace std;
27 ll read()
28 {
29     ll s=1,x=0;
30     char ch=getchar();
31     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
32     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
33     return x*s;
34 }
35 int main()
36 {
37     ll q=read();
38     ll T,ans;
39     while(q--)
40     {
41         ll n=read(),m=read();
42         if(m%10==5)
43         {
44             T=n/(2*m);
45             ans=T*5;
46             for(ll i=2*T*m;i<=n;i+=m)
47             if(i%m==0) ans+=i%10;
48         }
49         else if(m%10==0) ans=0;
50         else if(m%2==1)
51         {
52             T=n/(m*10);
53             ans=T*45;
54             for(ll i=10*T*m;i<=n;i+=m)
55             if(i%m==0) ans+=i%10;
56         }
57         else if(m%2==0)
58         {
59             T=n/(m*5);
60             ans=T*20;
61             for(ll i=5*T*m;i<=n;i+=m)
62             if(i%m==0) ans+=i%10;
63         }
64         cout<<ans<<endl;
65     } 
66 }

View Code

D、Equalizing by Division (hard version)