Sakana~
0%

【专题】Codeforces1500的构造题

发表于 更新于 分类于

Codeforces1500的构造题

暂时每天两道吧

【专题】Codeforces1500的构造题

C. Valera and Tubes

https://codeforces.com/problemset/problem/441/C

按照每段两格，这样蛇形摆放，最后留下一条长的填满即可。

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>

using namespace std;
int n, m, k;

void change (int &x, int &y) {
    cout << x << ' ' << y << ' ';
    if (x & 1) {
            if (y < m)  y++;
            else    x++;
        }
        else {
            if (y > 1)  y--;
            else    x++;
        }
}

int main () {
    cin >> n >> m >> k;
    if (k == 1) {
        cout << n*m << ' ';
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i & 1)  cout << i << ' ' << j << ' ';
                else    cout << i << ' ' << m-j+1 << ' ';
            }
        }
        return 0;
    }

    int x = 1, y = 1;
    for (int _ = 1; _ < k; _++) {
        cout << "2 ";
        change (x, y), change(x, y);    
        cout << endl;
    }

    int res = n*m - (k-1)*2;
    cout << res << ' ';
    while (res --)  change (x, y);
    
}

//按照蛇形，两个一分配，最后多出来连一条长的

C. Swap Letters

https://codeforces.com/problemset/problem/1215/C

题意：每次可以交换st中的任意一个字符，问把st变得相同最少需要多少次。

观察不难发现，可以分别存下 ”s[i]=a,t[i]=b; s[i]=b,t[i]=a” 这样的 i，然后两两交换。如果ab多出一个或者ba多出一个，那么最终将无法完成配对。如果两者都多出一个，就可以通过样例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
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

using namespace std;

int main () {
    int n, m;
    cin >> n;
    string s, t;
    cin >> s >> t;

    vector <int> v1, v2; //ab,ba
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'a' && t[i] == 'b')     v1.push_back (i);
        else if (s[i] == 'b' && t[i] == 'a')     v2.push_back (i);
    }
    n = v1.size(), m = v2.size();
    if (n + m == 0)     cout << 0;
    else if ((n + m) & 1)   cout << -1;
    else {
        int cnt = n / 2 + m / 2;
        if (n & 1)  cnt += 2;
        cout << cnt << endl;
        for (int i = 0; i < n - 1; i += 2)  cout << v1[i]+1 << ' ' << v1[i+1]+1 << endl;
        for (int i = 0; i < m - 1; i += 2)  cout << v2[i]+1 << ' ' << v2[i+1]+1 << endl;
        if (n & 1) {
            cout << v1[n-1]+1 << ' ' << v1[n-1]+1 << endl;
            cout << v1[n-1]+1 << ' ' << v2[m-1]+1 << endl;
        }
    }
}


//每次可以交换st中的任意一个字符

//每两队baba,abab换

A. Mashmokh and Numbers

https://codeforces.com/problemset/problem/414/A

题意：安排n不同的个数字，使得(按顺序)两两gcd之和为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>

using namespace std;

int main () {
    int n, k;
    cin >> n >> k;
    if (k < n/2 || (n == 1 && k))    cout << -1;
    else if (k == n/2)      for (int i = 1; i <= n; i++)    cout << i << ' ';
    else {
        int res = k - (n-2)/2, x = 1;
        cout << res << ' ' << res*2 << ' ';
        n -= 2;

        for (int i = 1; i < n; i += 2) {
            while (x == res || x+1 == res || x == res*2 || x+1 == res*2)   x ++;
            cout << x << ' ' << ++x << ' ';
            x++;
        }
        
        if (n & 1) {
            while (x == res || x == res*2)  x ++;
            cout << x;
        }
    }
}

//安排n不同的个数字，使得(按顺序)两两gcd之和为k

//构造一个数的两倍，然后直接后面都相邻来摆

A1. Binary Table (Easy Version)

https://codeforces.com/problemset/problem/1439/A1

直接暴力操作，对于每个1都能通过把这个小四方格改变三次从而变成全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
#include <bits/stdc++.h>

using namespace std;
const int N = 105;
int n, m, a[N][N];

void solve () {
    memset (a, 0, sizeof a);
    int ans = 0;
    cin >> n >> m;
    //intput string
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            if (s[j] == '1')    ans += 3, a[i][j+1] = 1;
        }
    }

    cout << ans << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 0)   continue;
            int dx = 1, dy = 1;
            if (i == 1)     dx = -1;
            if (j == 1)     dy = -1;
            cout << i << ' ' << j << ' ' << i-dx << ' ' << j << ' ' << i-dx << ' ' << j-dy << endl;
            cout << i << ' ' << j << ' ' << i << ' ' << j-dy << ' ' << i-dx << ' ' << j  << endl;
            cout << i << ' ' << j << ' ' << i << ' ' << j-dy << ' ' << i-dx << ' ' << j-dy  << endl;                           
        }
    }
}

int main () {
    int t;
    cin >> t;
    while (t --)    solve ();
}


//暴力操作，对于每个1都能通过操作3次使得这个格子变为全0

B. Yet Another Array Partitioning Task

https://codeforces.com/problemset/problem/1114/B

贪心选了前 k*m 大的数字，但是没想到要怎么切割，其实只要记录一下在里面的数，然后统计数量即可，每达到m就切割

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
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 2e5 + 5;
int n, m, k, sum, b[N];
pair<int, int> a[N];

signed main () {
    cin >> n >> m >> k;
    set <int> s;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        a[i] = {b[i], i};
    }    
    sort (a + 1, a + n + 1, greater<>());
    for (int i = 1; i <= k*m; i++)      sum += a[i].first, s.insert (a[i].second);
    
    cout << sum << endl;
    k --;
    vector <int> v;
    int cnt = 0;
    for (int i = 1; i <= n && k; i ++) {
        if (s.count (i))        cnt ++;
        if (cnt == m)           cout << i << ' ', k--, cnt = 0;
    }
}


//分成k段，每一段的前m大之和最大
//输出这个和以及分界点

//sum=最大的m*k个
//记录这些数，如果不是就不要在此划分

//排序然后记录m的倍数

C. Divan and bitwise operations

https://codeforces.com/problemset/problem/1614/C

重要性质：假设序列中有一个数在该位为 1， 那么则有1/2的子序列在该位的异或结果是1

需要判断所有数在该位上是否有 1 存在，就可以知道将他们全部异或后的结果是多少。这就是他给出的或运算的作用 -> 将所有数字或运算的结果就可以判断哪些位置上存在 1。

子序列个数：2^n^

即答案为：二分之一的子序列个数*异或和ans

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
#include <bits/stdc++.h>

using namespace std;
const int p = 1e9 + 7;

int qmi(int a,int k) {
	int ans = 1;
	while (k) {
		if (k & 1)//末位1取出
			ans = (long long)ans * a % p;
		k >>= 1;//次末位
		a = (long long)a * a % p;
	}
	return ans;
}

void solve () {
    int n, m;
    cin >> n >> m;
    int ans = 0;
    while (m --) {
        int x;
        cin >> x >> x >> x; //l,r无用
        ans |= x;
    }
    cout << 1ll * ans * qmi (2, n-1) % p << endl;
}

int main () {
    int t;
    cin >> t;
    while (t --)    solve ();
}

//重要性质：假设序列中有一个数在该位为 1,
//那么则有1/2的子序列在该位的异或结果是1。

//二分之一的子序列个数*异或和ans

C. Meaningless Operations

https://codeforces.com/problemset/problem/1110/C

如果 n 的二进制表示不是全1的话，可以通过对 n 按位取反，构造 m，这样 n&m=0, n ^ m=2^k^ –1, k=log(n)，则此时 gcd=n^m，最大。

如果 n 的二进制表示全是1的话，多写几项之后，不难发现 n&m 和 n^m 每一位上一定是 01交错的（即一个是0另一个就一定是1），令 a = n&m, b = n^m 则问题转化为

又因为：a％b=0 充要 a+b％b=0，所以 b 就是 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
#include <bits/stdc++.h>

using namespace std;

int find_prime (int x) {
    for (int i = 2; i*i <= x; i++) {
        if (x % i == 0)     return x / i;
    }
    return 1;
}

void solve () {
    int n, i;
    cin >> n;
    
    bool all_one = true;
    for (i = 0; (1 << i) <= n; i++) {
        if ((n >> i) & 1)   continue; //1
        all_one = false;
    }
    //cout << "sz=" << i << endl;

    if (all_one) cout << find_prime (n) << endl;
    else    cout << (1 << i) - 1 << endl;
}

int main () {
    int t;
    cin >> t;
    while (t --)    solve ();
}

//如果是全1,构造01交错的两个数a,b,满足a+b=n,且max(a,b)%min(a,b)==0
//否则就2的位次 (构造出0和2^k)

//转化为问题gcd(x,n-x)最大

//找n的最大因子

D. Vus the Cossack and Numbers

https://codeforces.com/problemset/problem/1186/D

把小的那个数全部加起来，然后看和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
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int sum, a[N], b[N]; //b[i]>a[i]

int main () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        double x;
        cin >> x;
        a[i] = (int)x;
        if (x == a[i])      b[i] = a[i];   
        else if (x >= 0)     b[i] = a[i] + 1;
        else    b[i] = a[i] - 1;

        if (a[i] > b[i])    swap (a[i], b[i]);
        sum += a[i];
    }

    if (sum == 0) {
        for (int i = 1; i <= n; i++)    cout << a[i] << endl;
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        if (sum < 0 && a[i] != b[i])    sum ++, cout << b[i] << endl;
        else    cout << a[i] << endl;
    }
}


//把小的那个数全部加起来，然后看和0相差多少，然后用大的那个数去修正偏移

C. XOR and OR

https://codeforces.com/problemset/problem/282/C

把x, y的所有情况列出来之后不难发现，本操作的实质就是 11，01，10 之间的互化。

所以a只要有一个1就能化成一个全1串，全1串又能转化成任意（含至少一个1）的01串

注：1是没办法被消掉的

即：看ab的是否都有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
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>

using namespace std;

int main () {
    string a, b;
    cin >> a >> b;
    if (a == b) {
        puts ("YES");
        return 0;
    }
    if (a.size() != b.size()) {
        puts ("NO");
        return 0;
    }

    int cnta = 0, cntb = 0; //1的个数
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == '1')    cnta ++;
    }
    for (int i = 0; i < b.size(); i++) {
        if (b[i] == '1')    cntb ++;
    }

    if (cnta && !cntb || !cnta && cntb)  puts ("NO");
    else    puts ("YES");
}

//11/10/01互化

//先全变1再化0?
//a中要变成1的0旁边必选挨着1

//只要有1个1就一定能变成全1

D. Weights Assignment For Tree Edges

https://codeforces.com/problemset/problem/1611/D

不难发现就是要满足拓扑序

然后直接按顺序增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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int n, p[N], b[N], d[N], root;

void solve () {
    memset (d, -1, sizeof d);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        if (i == b[i])  root = i;
    } 
    for (int i = 1; i <= n; i++)    cin >> p[i];

    if (p[1] != root) {
        cout << "-1\n";
        return ;
    }

    d[root] = 0;
    for (int i = 2; i <= n; i++) {
        if (d[b[p[i]]] == -1) { //祖先比他还小
            cout << "-1\n";
            return ;
        }
        d[p[i]] = d[p[i-1]] + 1;
    }

    for (int i = 1; i <= n; i++) {
        if (i == root)  cout << "0 ";
        else    cout << d[i] - d[b[i]] << ' ';
    }
    cout << endl;
}

int main () {
    int t;
    cin >> t;
    while (t --) {
        solve ();
    }
}
//如果a到root的路径上经过的点的dis>a，则-1

A. 24 Game

https://codeforces.com/problemset/problem/468/A

感觉这题还是蛮easy的

多写几项就能构造规律了

1
2
3
4
5
6
7
NO;  //n = 1,2,3
1*2*3*4 = 24; //n = 4
(5+1)*(3-2)*4 = 24; //n = 5
1*2*3*4*(6-5) = 24; //n = 6
(5+1)*(3-2)*4*(7-6) = 24; //n=7
...
//观察易得，此后对于奇数可以按照5-base来构造, >5的数直接邻项相减; 偶数按照4-base同理
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>

using namespace std;

void print_odd () { //5base
    printf ("1 + 5 = 6\n");
    printf ("3 - 2 = 1\n");
    printf ("4 * 6 = 24\n");
    printf ("1 * 24 = 24\n");    
}

void print_even () { //4base
    printf ("1 * 2 = 2\n");
    printf ("3 * 4 = 12\n");
    printf ("2 * 12 = 24\n");
}

int main () {
    int n;
    cin >> n;
    if (n < 4) {
        printf ("NO\n");
        return 0;
    }
    printf ("YES\n");
    if (n & 1) {
        print_odd();
        for (int i = 6; i < n; i += 2) {
            printf ("%d - %d = 1\n", i + 1, i);
        }
        for (int i = 1; i <= (n - 5)/2; i++) {
            printf ("1 * 24 = 24\n");
        }
    }
    else {
        print_even ();
        for (int i = 5; i < n; i += 2) {
            printf ("%d - %d = 1\n", i + 1, i);
        }
        for (int i = 1; i <= (n - 4)/2; i++) {
            printf ("1 * 24 = 24\n");
        }
    }
}

C. Removing Columns

https://codeforces.com/problemset/problem/496/C

贪心去比较，不符合升序的就要删掉，删掉之后会影响前面的顺序，所以判100次就可以每次都从头再来

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
#include <bits/stdc++.h>

using namespace std;
const int N = 105;
char a[N][N];
bool change[N];

int main () {
    int n, m, ans = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    for (int t = 1; t <= 100; t++) {
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (change[j])  continue;
                if (a[i-1][j] < a[i][j])    break;
                if (a[i-1][j] > a[i][j])    change[j] = true;
            }
        }
    }
    
    for (int i = 0; i < m; i++) {
        if (change[i])  ans ++;
    }
    cout << ans;
}

//判100次就可以每次都从头再来

C. Nastya Is Transposing Matrices

https://codeforces.com/problemset/problem/1136/C

只需要看所有副对角线（形如 ‘ / ’）上的点排序后是否相等即可

用map即可

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
#include <bits/stdc++.h>

using namespace std;
const int N = 505;
int a[N][N], b[N][N];

int main () {
    int n, m;
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf ("%d", &a[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf ("%d", &b[i][j]);
        }
    }

    bool suc = true;
    for (int k = 1; k <= m; k++) { //(1, j),(2, j+1-2),...
        map<int, int>c, d; 
        for (int i = 1, j = k; i <= n && j >= 1; i++, j--) {
            int x = a[i][j], y = b[i][j];
            c[x] ++, d[y] ++;
        }
        if (c != d) {
            suc = false;
            break;
        }
    }

    if (!suc) {
        puts ("NO");
        return 0;
    }

    for (int k = 2; k <= n; k++) { 
        map<int, int>c, d; 
        for (int i = k, j = m; i <= n && j >= 1; i++, j--) {
            int x = a[i][j], y = b[i][j];
            c[x] ++, d[y] ++;
        }
        if (c != d) {
            suc = false;
            break;
        }
    }    
    
    if (suc)    puts ("YES");
    else    puts ("NO");
}

//主相等，其余对称
//只要在一条/线上就一定ok

//每一条副对角线都盘一下
//sort然后比较?

H. A + B Strikes Back

https://codeforces.com/problemset/problem/409/H

愚人节乐子题，就是a+b problem，交6次就能过了

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>

using namespace std;

int main () {
    int a, b;
    cin >> a >> b;
    cout << a + b;
}

//6

楽

B. Pasha and Tea

https://codeforces.com/problemset/problem/557/B

大贪心，sort之后，1 ~ n为女生，n+1 ~ 2n 为男生，只看最低（因为男/女全部要一样）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 2e5 + 5;
int a[N];

signed main () {
    int n, w;
    cin >> n >> w;
    for (int i = 0; i < 2*n; i++)   cin >> a[i];
    sort (a, a + 2*n);

    double ans = min (1.0 * a[0], a[n] / 2.0) * n * 3;
    cout << fixed << setprecision (7) << min (ans, 1.0*w);
}

//直接贪心

B. Dreamoon and WiFi

https://codeforces.com/contest/476/problem/B

1300，但是不会。

二进制枚举

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
#include <bits/stdc++.h>

using namespace std;

int main () {
    string a, b;
    cin >> a >> b;
    int n = a.size();

    int ed = 0, st = 0, cnt = 0; //cnt=?的个数
    for (int i = 0; i < n; i++) {
        if (a[i] == '+')    ed ++;
        else    ed --;
    }
    for (int i = 0; i < n; i++) {
        if (b[i] == '?')    cnt ++;
        else if (b[i] == '+')   st ++;
        else    st --;
    }

    //二进制枚举
    int tot = 0, m = (1 << cnt);
    for (int i = 0; i < m; i++) {
        int dx = 0; //b的偏移
        for (int j = 0; j < cnt; j++) {
            if (i >> j & 1)     dx ++;
            else    dx --;
        }
        if (st + dx == ed)  tot ++;
    }
    double ans = 1.0*tot/m;

    cout << fixed << setprecision (10) << ans;
}


//二进制枚举

C. Paint the Digits

https://codeforces.com/problemset/problem/1209/C

很贪

首先运用单点栈，找到串中的单调不递减序列
临时当成第一部分，剩下的为第二部分
记第二部分最小的为 x，把第一部分里大于x的添加到第二部分，

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
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int n, b[N];
pii a[N];
string s;
bool in_stk[N];

void solve () {
    memset (in_stk, false, sizeof in_stk);
    cin >> n >> s;
    for (int i = 0; i < n; i++)     a[i+1] = {s[i] - '0', i+1};
    
    stack<pii> stk;
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && stk.top().first > a[i].first)    in_stk[stk.top().second] = false, stk.pop();
        stk.push (a[i]), in_stk[i] = true;
    }
    
    int x = 10;
    for (int i = 1; i <= n; i++) {
        if (!in_stk[i]) x = min (x, a[i].first);
    }

    //cout << "x = " << x << endl;
    // while (!stk.empty()) {
    //     cout << stk.top() << ' ';
    //     stk.pop();
    // }
    // cout << endl;

    vector <int> v1, v2;
    for (int i = 1; i <= n; i++) {
        if (!in_stk[i])     v2.push_back (a[i].first), b[i] = 2;
        else {
            if (a[i].first > x)  v2.push_back (a[i].first), b[i] = 2;
            else    v1.push_back (a[i].first), b[i] = 1;
        }
    }

    if (!is_sorted (v2.begin(), v2.end())) {
        cout << "-\n";
        return ;
    }
    for (int i = 1; i <= n; i++)    cout << b[i];
    cout << endl;
}

int main () {
    int t;
    cin >> t;
    while (t --) {
        solve ();
    }
}

//<=2段最长上升子序列
//下降序列长度<3

//先用单调栈存一段不减序列放到1
//>x的放2,最后判断一下第二部分是否单调

//首先运用单点栈，找到串中的单调不递减序列
//临时当成第一部分，剩下的为第二部分
//记第二部分最小的为 x，把第一部分里大于x的添加到第二部分，

D. Prime Graph

https://codeforces.com/problemset/problem/1178/D

连成环再加边
找到下一个质数然后加边直至该质数值

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
#include <bits/stdc++.h>

using namespace std;

bool is_prime (int x) {
    for (int i = 2; i*i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

int main () {
    int n;
    cin >> n;
    if (is_prime (n)) {
        cout << n << endl;
        for (int i = 1; i < n; i++) cout << i << ' ' << i + 1 << endl;
        cout << n << " 1\n";
    }
    else {
        int dx = 0;
        while (!is_prime(n + dx))   dx ++;
        cout << n + dx << endl;
        for (int i = 1; i < n; i++) cout << i << ' ' << i + 1 << endl;
        cout << n << " 1\n";   
        for (int i = 1; i <= dx; i++)   cout << i << ' ' << n - i << endl;    
    }
}

//构造一个无重边无自环的无向图
//n个点,m条边，m为素数，且所有的点的度数都为素数

//连成环再加边
//找到下一个质数然后加边直至质数

C. Smallest Word

https://codeforces.com/problemset/problem/1043/C

这题代码很短，核心思路就在于使得s[i]挪到最前面且其余元素不动的方法是：翻s[i-1]和s[i]

没做出来，属于是ct了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;
const int N = 1005;
int a[N];

int main () {
    string s;
    cin >> s;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] == 'a')    a[i] ++, a[i-1] ++;
    }
    for (int i = 0; i < s.size(); i++) {
        if (a[i] & 1)   cout << "1 ";
        else    cout << "0 ";
    }
}

//使得s[i]挪到最前面且其余元素不动:翻s[i-1]和s[i]

C. Ramesses and Corner Inversion

来自题解：十分的巧妙！！

考虑每次选择(1,1),(1,y),(x,1),(x,y)这样的四个点，那么我们就能够让所有除开第一行第一列的值都与第二个矩阵相等。

现在就只剩下第一行第一列了，如果每行、每列的奇偶性两个矩阵相等，那么剩下的第一行第一列必然也与第二个矩阵相等的。所以就这么判断一下就好了。

https://codeforces.com/problemset/problem/1119/C

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
#include <bits/stdc++.h>

using namespace std;
const int N = 505;
int n, m, a[N][N], b[N][N];

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> b[i][j];
        }
    }
    
    for (int i = 1; i <= n; i++) {
        int cnt1 = 0, cnt2 = 0;
        for (int j = 1; j <= m; j++) {
            if (a[i][j])    cnt1 ++;
            if (b[i][j])    cnt2 ++;
        }
        if (cnt1 % 2 != cnt2 % 2) {
            puts ("No");
            return 0;
        }
    }

    for (int j = 1; j <= m; j++) {
        int cnt1 = 0, cnt2 = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i][j])    cnt1 ++;
            if (b[i][j])    cnt2 ++;
        }
        if (cnt1 % 2 != cnt2 % 2) {
            puts ("No");
            return 0;
        }
    }

    puts ("Yes");
}

//每次可以改变翻转边角的四个，问A能否变为B

//每个与(1,1)删，然后判行列的奇偶性是否相等

D. Bicolored RBS

https://codeforces.com/problemset/problem/1167/D

更换另一种匹配方式，先进先匹配即可

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
#include <bits/stdc++.h>

using namespace std;
typedef pair<char, int> pii;
const int N = 2e5 + 5;
int a[N];

int main () {
    int n;
    cin >> n;
    string s;
    cin >> s;

    queue <pii> q;
    //q.push ({s[0], 0}), a[0] = 0;
    int tot = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(')    q.push  ({s[i], i});
        else {
            auto t = q.front();
            q.pop ();
            if (tot & 1)    a[i] = a[t.second] = 1;
            else    a[i] = a[t.second] = 0;
            tot ++;
        }
    }

    for (int i = 0; i < n; i++)     cout << a[i];
}


//queue
//先进先匹配

B. Bear and Different Names

倒着构造，先把后k-1个弄成各不相同
倒着每碰到一个NO就把第i个和第i+k-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
27
28
29
30
31
#include <bits/stdc++.h>

using namespace std;
const int N = 55;
string s[] = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "Aa", "Bb", "Cc", "Dd", "Ee", "Ff", "Gg", "Hh", "Ii", "Jj", "Kk", "Ll", "Mm", "Nn", "Oo", "Pp", "Qq", "Rr", "Ss", "Tt", "Uu", "Vv", "Ww", "Xx", "Yy", "Zz"};
string ans[N];
bool check[N];

int main () {
    int n, k, tot = -1;
    cin >> n >> k;
    
    for (int i = n; i > n-k; i--) {
        ans[i] = s[++tot];
    }
    for (int i = 1; i <= n-k+1; i++) {
        string ss;
        cin >> ss;
        if (ss[0] == 'Y')   check[i] = true;
    }

    for (int i = n-k+1; i >= 1; i--) {
        if (check[i])   ans[i] = s[++tot];
        else    ans[i] = ans[i+k-1];
    }

    for (int i = 1; i <= n; i++)    cout << ans[i] << ' ';
}

//倒着构造，先把后k-1个弄成各不相同
//倒着每碰到一个NO就把第i个和第i+k-1个弄成相同的，否则弄成不同的。

G. Even-Odd XOR

https://codeforces.com/problemset/problem/1722/G

感觉很困难，我已经忘了咋做的了

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
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 2e5 + 5;
int a[N], n;

void solve () {
    cin >> n;
    if (n == 3) {
        cout << "2 1 3\n";
        return ;
    }
    if (n % 4 == 0) {
        int x = 0;
        for (int i = 1; i <= n; i += 2)     a[i] = x++;
        for (int i = 2; i <= n; i += 2)     a[i] = x++;
    }
    else if (n % 4 == 3) {
        a[1] = 1, a[2] = 2, a[3] = 3;
        int x = 4;
        for (int i = 4; i <= n; i += 2)     a[i] = x++;
        for (int i = 5; i <= n; i += 2)     a[i] = x++;
    }

    else if (n % 4 == 2) {
        for (int i = 16; i < n + 9; i += 4)
            cout << i << ' ' << i+1 << ' ' << i+3 << ' ' << i+2 << ' ';
        cout << "12 8 2 4 1 3\n";
        return ;
    }

    else {
        int x = 4;
        for (int i = 1; i < n; i += 2)     a[i] = x++;
        for (int i = 2; i <= n; i += 2)     a[i] = x++;
        a[n] = 0;
    }

    for (int i = 1; i <= n; i++)    cout << a[i] << ' ';
    cout << "\n";
}

signed main () {
    ios::sync_with_stdio (0);cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while (t --) {
        solve ();
    }
}

//even: 相邻着放

A. The Party and Sweets

这题要考虑的细节还挺多

画个表，贪心构造

具体细节可看代码及下面的注释

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
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e5 + 5;
int ans, sumb;
int b[N], g[N];

signed main () {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        sumb += b[i];
    }
    ans += sumb * m;
    sort (b + 1, b + n + 1, greater <int> ());

    bool suc = true, add = false;
    for (int i = 1; i <= m; i++) {
        cin >> g[i];
        if (b[1] > g[i])    suc = false;
        if (b[1] == g[i])   add = true;
    }

    if (!suc) {
        cout << -1;
        return 0;
    }

    sort (g + 1, g + m + 1);
    if (add)    ans += g[1] - b[1];
    else    ans += g[1] - b[2]; //
    for (int i = 2; i <= m; i++)    ans += g[i] - b[1];

    cout << ans;
}

//先取每一格的最低限度，然后选取每列最大的->gmax
//sumb*m + \sum_{gj-b[1]}
//bi > gj  ->  -1
//b[1] > ming


//但是要保证行的最小值不变
//拿最小的gj与bmax_减，其余的都和最大的减
//但是如果有一行已经是最大的就不用拿第二大的去减了

B. Secret Combination

就是暴力枚举要加多少次（最多10次，含不加）以及哪个放首位

只需要加一个小优化，即观察样例不难发现，首位一定是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
#include <bits/stdc++.h>

using namespace std;
const int N = 1005;
int a[N];

int main () {
    int n;
    string s;
    cin >> n >> s;
    if (n == 1) {
        cout << 0;
        return 0;
    }

    string ans;
    for (int i = 0; i < n; i++)     ans += '9', a[i] = s[i] - '0';
    
    for (int dx = 0; dx < 10; dx++) {
        for (int i = 0; i < n; i++) {
            if (dx)    a[i] = (a[i] + 1) % 10, s[i] = (char) (a[i] + '0');
        }
        for (int i = 0; i < n; i++) {
            if (s[i] != '0')    continue;
            //s[i]放第一个
            string t;
            for (int j = i; j < n; j++) t = t + s[j];
            for (int j = 0; j < i; j++) t = t + s[j];
            ans = min (ans, t);
        }
    }
    cout << ans;
}

//相对差值不变
//首位必为0

//先把最小的放到前面
//O(10*n^2)
//枚举加的数

C. Phone Numbers

  1. k大于n，前n个放一样的，后面放k-n个现有最小字符

  2. k小于等于n，前k-1个放一样的，最后一个放最大的，如果放完之后和当前相同，则弹出第k-1个，找到大于第一个大于第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
31
32
33
#include <bits/stdc++.h>

using namespace std;

int main () {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    set<char> ss;
    for (int i = 0; i < n; i++)     ss.insert (s[i]);

    if (k <= n) {
        // stack <char> stk;
        // for (int i = 0; i < n-1; i++)   stk.push (s[i]);
        int tot = k-1;
        while (tot >= 0) {
            auto pos = upper_bound (ss.begin (), ss.end (), s[tot]);
            if (pos != ss.end ()) {
                s[tot] = *pos;
                for (int i = tot + 1; i < n; i++)   s[i] = *ss.begin ();
                for (int i = 0; i < k; i++)     cout << s[i];
                return 0;
            }
            tot --;
        }
    }
    else {
        cout << s;
        for (int i = 1; i <= k-n; i++)  cout << *ss.begin ();
    }
}

C. Mahmoud and Ehab and the wrong algorithm

https://codeforces.com/problemset/problem/959/C

对于能满足的很好构造，就是1连上其它所有结点。

对于不满足的，其实画出前10个之后大概就能构造出来了，不难发现可以按照第一层一个，第二层234， 第三层其余的全连到2上这样来构造，按照结论应该选3个点，然而实际上选1 和 2 两个点就足够了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>

using namespace std;

int main () {
    int n;
    cin >> n;
    //不符合——链
    if (n < 6)     cout << "-1\n";
    else {
        for (int i = 2; i <= 4; i++)    cout << "1 " << i << endl;
        for (int i = 5; i <= n; i++)    cout << "2 " << i << endl;
    }
    //符合——1连所有点
    for (int i = 2; i <= n; i++)    cout << "1 " << i << endl;
}

//第一层一个
//第二层234
//第三层其余的全连到2上

C. Misha and Forest

https://codeforces.com/problemset/problem/501/C

如果度数为1就相当于直接确定了连接的点。从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
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

int main () {
    int n;
    cin >> n;
    vector <int> d(n), s(n);
    vector <pii> v;
    queue <int> q;
    for (int i = 0; i < n; i++) {
        cin >> d[i] >> s[i];
        if (d[i] == 1)  q.push (i);
    }

    while (!q.empty ()) {
        int t = q.front ();
        q.pop ();
        if (d[t] != 1)  continue;
        v.push_back ({t, s[t]});

        if (d[t] == 0 || d[s[t]] == 0)  continue;
        d[s[t]] --, s[s[t]] ^= t;
        if (d[s[t]] == 1)   q.push (s[t]);
    }
    
    
    cout << v.size () << endl;
    for (auto i : v)    cout << i.first << ' ' << i.second << endl;
}



//知道该点度数以及连接该点的点的异或和
//构造简单图

//如果d<=1,就能直接确定
//把1的放进去

C. Searching for Graph

https://codeforces.com/problemset/problem/402/C

丁真题，观察样例找规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;

void solve () {
    int n, p;
    cin >> n >> p;
    for (int i = 0, j = 1, cnt = 1; i < 2*n + p; i++) {
        if (cnt > n - j)   cnt = 1, j ++;
        cout << j << ' ' << j + cnt << endl;
        cnt  ++;
    }
}

int main () {
    int t;
    cin >> t;
    while (t --)    solve ();
}