[原创]Codeforces Round #402 (Div. 2)

2017-03-13 21:19:02 Tabris_ 阅读数:211


博客爬取于2020-06-14 22:41:14
以下为正文

版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/61929040


Virtual Contest 4AC GG E题根本读不懂啊…
这里写图片描述

读题太慢,傻逼题还错,难题还不会, 总结就是!!

A Pupils Redistribution

——————————————————————————————————
日常傻逼题:
给你两个只含有{1,2,3,4,5}序列,让你使其平衡,就是两边1的个数,2的个数…5的个数相同,

问你最少交换几次, 不能输出-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
# include <bits/stdc++.h>
# define abs(x) ((x)>0?(x):-(x))
using namespace std;

int a[10],b[10];
int main(){
int n;
scanf("%d",&n);
for(int i=0,x;i<n;i++) {
scanf("%d",&x);
a[x]++,b[x]++;
}
for(int i=0,x;i<n;i++) {
scanf("%d",&x);
a[x]++;
}
for(int i=1;i<=5;i++){
if(a[i]&1) return 0*puts("-1");
}
int sum = 0;
for(int i=1;i<=5;i++){
sum+=abs(a[i]/2-b[i]);
}
printf("%d\n",sum/2);
return 0;
}

B Weird Rounding

————————————————————————————————————————————
日常傻逼题2:给你一个数,问你最少删除几位使得这个数能被10k10^k整除

字符串模拟做即可 ,注意 如果是 100 要被1010010^{100}整除,那么只能变成0,那么删除的是2位,而不仅仅是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
# include <bits/stdc++.h>
# define abs(x) ((x)>0?(x):-(x))
using namespace std;

int main(){

string s;
int k;
cin>>s>>k;
// cout<<s<<" "<<k;
int mx = s.size();
for(int i=s.size()-1;i>=0;i--){
if(s[i]=='0') {mx --;break;}
}
int m = 0,mm=0;
for(int i=s.size()-1;i>=0;i--){
if(s[i]=='0')m++;
else mm++;
if(m>=k) {break;}
if(!i) {mm=10000;}
}
// printf("%d %d\n",mx,mm);
printf("%d\n",min(mx,mm));

return 0;
}

C Dishonest Sellers

————————————————————————————————————————————
贪心题:
给你n个商品的两种价格,一种是现在的价格,一种是过几天的价格,今天最少买k个,问你最后每个商品买一次,最少的总花费。

排序,先买现在的价格-过几天价格的差大的。现在买的话 至少买k个或者买现在便宜的 剩下的都过几天买就好了

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
# include <bits/stdc++.h>
# define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 2e5+7;

struct node {
int now,week;
}a[N];

bool cmp(node A,node B){
return A.week-A.now>B.week-B.now;
}

int main(){
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i].now);
for(int i=1;i<=n;i++)scanf("%d",&a[i].week);

sort(a+1,a+n+1,cmp);

int sum = 0;
for(int i=1;i<=n;i++){
if(i<=k||a[i].week>a[i].now)sum+=a[i].now;
else sum+=a[i].week;
}
printf("%d\n",sum);
return 0;
}

D String Game

————————————————————————————————————————————
就是在tt字符串上按顺序依次删除第aia_i个字符串,问你最多删除几次,能保证在省下的字符串中能找到字符串pp

很明显t,p[1,2e5]|t|,|p|\in [1,2e5]是不能O(n2)O(n^2)

但是我们可以发现,在答案位置左边,一定是不能找到字符串pp得,右边一定是找到字符串pp得,

那么根据这个 我们可以对答案进行二分,最后复杂度O(nlogn)O(n\log n)

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 <bits/stdc++.h>
# define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 2e5+7;

int a[N],tz,pz;
string p,t;

bool check(int x){
string tt="",ttt;
ttt=t;
for(int u=1;u<=x;u++) ttt[a[u]-1]='0';
for(int u=0;u<tz;u++){
if(ttt[u]=='0')continue;
tt+=ttt[u];
}
int i,j;
for(i=0,j=0;i<tt.size()&&j<pz;i++){
if(p[j]==tt[i])j++;
}

// cout<<x <<" "<<t<<" "<<tt<<" "<<ttt<<endl;
// cout<<ans<<endl;
if(j==p.size()) return true;
return false;
}

int main(){
cin>>t>>p;
tz=t.size();
pz=p.size();
for(int i=1;i<=tz;i++) cin>>a[i];

int l=1,r=tz,mid,ans = 0;;
while(l<=r){
mid = (r+l)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans<<endl;

return 0;
}

E. Bitwise Formula

————————————————————————————————————————————
待补

F. Peterson Polyglot

————————————————————————————————————————————
待补