[原创]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(nlog⁡n)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

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