Codeforces Round #704 (Div. 2)（E待补）_codeforces round #704 (div. 2)e

A. Three swimmers

题意：三个人走一个来回的时间分别是a,b,c。问当到达起点时间为t时，最少要等多久，会有人回到起点。

思路：取模判断

AC代码：

#include <iostream>
#include <bits/stdc++.h>
#include <unordered_map>
#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 10007;
const int N = 2e5+7;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
int c;
int sum[N];
int nxt[N];
 
signed main(){
    cin>>t;
    while(t--){
        int p,x,y,z;
        cin>>p>>x>>y>>z;
        int x1 = p%(x);
        int x2 = p%(y);
        int x3 = p%(z);
        if(x1 == 0) x1 = x;
        if(x2 == 0) x2 = y;
        if(x3 == 0) x3 = z;
        cout<<min(x-x1,min(y-x2,z-x3))<<endl;;
    }
    return 0;
}
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

B. Card Deck

题意：桌子上有一叠排。给出他们的点数（从底下到上面）。然后要把他们移动到一叠新的牌去。规则是只能选择这堆牌顶部的任意张，然后叠到新堆的顶上。直到全拿完。使得 ${\sum }_{i=1}^n{n}^{n-i}\cdot p_i$最大。求新的牌堆。

思路：这显然是一个贪心问题了。$n^{n-i}$相当于是每张牌的权重。越底下权重越大。所以每次选牌时，把当前最大值和他上面的牌，一起拿走，放到另一堆。这样就保证了每次当前最大值，在新牌堆的位置都是尽量低的。那么最后算出来的值就是尽量大的。代码模拟这个过程就好了。

AC代码：

#include <iostream>
#include <bits/stdc++.h>
#include <unordered_map>
#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 10007;
const int N = 2e5+7;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
int c;
int sum[N];
int nxt[N];
int maxx[N];
 
signed main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i = 0 ; i < n ; i ++){
            cin>>a[i];
        }
        maxx[0] = a[0];
        for(int i = 0 ; i < n ; i ++){
            maxx[i] = max(maxx[i-1],a[i]);
        }
        int pos = 0 ;
        int r = n;
        for(int i = n-1 ; i >= 0 ; i --){
            if(a[i] == maxx[i]){
                for(int j = i ; j < r ; j ++){
                    b[pos++] = a[j];
                }
                r = i;
            }
        }
        for(int i = 0 ; i < n ; i ++){
            cout<<b[i]<<" ";
        }
        cout<<endl;
 
    }
    return 0;
}
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
45
46

C. Maximum width

题意：给定两个串，s和t。t是由s的一个子序列组成的（可能有很多种方案）。然后要求的是，在所有可行方案（子序列）中，p_i-p_i-1的最大值。

思路：求两遍t，一次是从前往后，让所有元素都尽可能靠前，一次从后往前，让所有元素都尽可能靠后。然后用这两次的做差，最大值就是答案了。

AC代码：

#include <iostream>
#include <bits/stdc++.h>
#include <unordered_map>
#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 10007;
const int N = 2e5+7;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
int c;
 
signed main(){
    //cin>>t;
    while(t--){
        string s1,s2;
        cin>>n>>m;
        cin>>s1>>s2;
        int pre = 0;
        int pos = 0;
        int res = 0;
        for(int i = 0; i < m ; i ++){
            while(s1[pos] != s2[i]) pos++;
            a[i] = pos;
            pos ++;
        }
        pos = n-1;
        for(int i = m-1 ; i >= 0 ; i --){
            while(s1[pos] != s2[i]) pos--;
            b[i] = pos;
            pos --;
        }
        for(int i = 1 ; i < m ; i ++){
            res = max(res,b[i]-a[i-1]);
        }
        cout<<res<<endl;
    }
    return 0;
}
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

D. Genius’s Gambit

题意：给定a,b,k。找到两个二进制数，含有a个1和b个0。相减得到一个二进制数，含有k个1。求任意两个可能的二进制数。

思路：观察。贪心。假设这两个数为x和y。x和y位数是相同的。而又不能有前导零。那么很容易想到首位必须是1。再看什么样的情况下，做减法会产生1。 10 - 01 = 01 ，100 - 001 = 011，110 - 011 = 011，其实通过观察这三组，就已经可以找到思路。a个1和b个0。至多可以产生 a+b-1 个1，只要把1放在前面，0放在后面。那么答案就出来了。 答案要k个1，那么只需要选择 01 加起来等于k就好了。 然后注意一些显然易见的约束。 首位必须是1。 剩下的部分也必须要有0和1。选出k个之后，多出来的数 让他们相等就好了。 一减就是0了，不会产生1。所以代码就是模拟。

AC代码：

#include <iostream>
#include <bits/stdc++.h>
#include <unordered_map>
#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 10007;
const int N = 2e5+7;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
int c;
 
signed main(){
    //cin>>t;
    while(t--){
        int x,y;
        cin>>x>>y>>k;
        if(k == 0){
            cout<<"Yes"<<endl;
            for(int i = 0 ; i < y ; i ++)
                cout<<1;
            for(int i = 0 ; i < x ; i ++)
                cout<<0;
            cout<<endl;
            for(int i = 0 ; i < y ; i ++)
                cout<<1;
            for(int i = 0 ; i < x ; i ++)
                cout<<0;
            cout<<endl;
        }else{
            if(y >= 2 && x > 0 && y+x-2 >= k){
                cout<<"Yes"<<endl;
                if(y-1 >= k){
                    cout<<1;
                    for(int i = 0 ; i < k ; i ++) cout<<1;
                    cout<<0;
                    for(int i = 0 ; i < y-1-k ; i ++) cout<<1;
                    for(int i = 0 ; i < x-1 ; i ++) cout<<0;
                    cout<<endl;
 
                    cout<<1;
                    cout<<0;
                    for(int i = 0 ; i < k ; i ++) cout<<1;
                    for(int i = 0 ; i < y-1-k ; i ++) cout<<1;
                    for(int i = 0 ; i < x-1 ; i ++) cout<<0;
                    cout<<endl;
                }else{
                    int z = k-y+1;
                    cout<<1;
                    for(int i = 0 ; i < y-1 ; i ++) cout<<1;
                    for(int i = 0 ; i < z ; i ++) cout<<0;
                    cout<<0;
                    for(int i = 0 ; i < x-z-1 ; i ++) cout<<0;
                    cout<<endl;
 
                    cout<<1;
                    cout<<0;
                    for(int i = 0 ; i < y-2 ; i ++) cout<<1;
                    for(int i = 0 ; i < z ; i ++) cout<<0;
                    cout<<1;
                    for(int i = 0 ; i < x-z-1 ; i ++) cout<<0;
                    cout<<endl;
                }
            }else{
                cout<<"No"<<endl;
            }
        }
    }
    return 0;
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72