【codeforces题解】Codeforces Round #684 (Div. 2)

博主： PCsky
发布时间：2020 年 11 月 21 日
9565次浏览
暂无评论
1370字数
分类：信息竞赛题解

A. Buy the String

题面
给你四个整数 $n, c_0, c_1 和 h$，以及一个长度为 n 的01字符串。你可以花费 h 把某个字符转换（0变1，1变0）。在若干次（也可能是0）转换后，你想买下字符串，0需要花费 $c_0$ ，1需要花费 $c_1$ ，问买下字符串的最小花费是？（time limit per test：1 second）

输入

第一行输入 t (1 ≤ T ≤ 10)，代表 t 个样例
每一个样例：
- 第一行输入 $n, c_0, c_1 , h$ $(1 ≤ n, c_0, c_1 , h ≤ 1000)$
- 第二行输入长度为 n 的01字符串

输出
对每个样例，输出最小花费

样例

Input
Output

6
3 1 1 1
100
5 10 100 1
01010
5 10 1 1
11111
5 1 10 1
11111
12 2 1 10
101110110101
2 100 1 10
00

3
52
5
10
16
22

思路
签到题，因为是最小花费，所以对于每个字符，要么就不换，要么就换一次之后买下，不存在一直换的情况。所以字符0的最小花费一定是min(c0,c1+h)，字符1的最小花费一定是min(c1,c0+h)，按新的价格遍历一遍字符串即可，复杂度O(n)。

代码

#include <bits/stdc++.h> 
#include <cstdio>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define debug(x) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6+5;

int n,c0,c1,h;
string s;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> c0 >> c1 >> h;
        cin >> s;
        int sum = 0;
        int nc0 = min(c0,c1+h);    // 字符0的最小花费 
        int nc1 = min(c1,c0+h);    // 字符1的最小花费 
        for(int i = 0; i < n; i++) {
            if(s[i] == '0') sum += nc0;
            else sum += nc1;
        }
        cout << sum << '\n';
    }
    return 0;
}

题面
一个长度为 n 的非递减整数数组，中位数是第 $\lceil \frac{n}{2} \rceil$ 个元素（编号从1开始）。现在给两个整数 n , k 以及一个长度为 nk 的非递减整数数组，我们可以把它随机分成 k 个长度为 n 的非递减子数组（每个数字只能属于一个子数组），一定有一种分法能让子数组的中位数之和最大，求出这个最大值。（time limit per test：1 second）

输入

第一行输入 t (1 ≤ T ≤ 100)，代表 t 个样例
每一个样例：
- 第一行输入 n, k (1 ≤ n, k ≤ 1000)
- 第二行输入 nk 个整数 $a_1,a_2,...,a_{nk}$ $(0 ≤ a_i ≤ 10^9)$
- 数组按非递减输入，nk 不会超过 $2*10^5$

输出
对每个样例，子数组中位数之和的最大可能值。

样例

Input
Output

6
2 4
0 24 34 58 62 64 69 78
2 2
27 61 81 91
4 3
2 4 16 18 21 27 36 53 82 91 92 95
3 4
3 11 12 22 33 35 38 67 69 71 94 99
2 1
11 41
3 3
1 1 1 1 1 1 1 1 1

165
108
145
234
11
3

思路
思维题，按定义中位数一定是数组第 $\lceil \frac{n}{2} \rceil$ 个元素，要凑最大中位数之和，则每个子数组的中位数一定要尽量大。最佳分配策略：每个子数组的中位数位置之前的元素从最小取起，中位数位置及以后的元素从最后面反着取，这样分割能保证所有子数组的中位数集中靠后。算法只需在原数组按规律倒着找k次即可，时间复杂度O(k)。
样例3示例图

代码

#include <bits/stdc++.h> 
#include <cstdio>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define debug(x) cout << "---->" << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6+5;

int n,k;
ll a[maxn];

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> k; 
        int len = n*k;
        for(int i = 1; i <= len; i++) cin >> a[i];
        int mid = ceil(n/2.0);
        int pos = len - (n-mid);
        ll sum = 0;
        while(k--) {
            // 从pos开始反过来选 
            sum += a[pos];
            // 每次往回跳
            pos = pos-(n-mid)-1;
        }
        cout << sum << '\n';
    }
    return 0;
}

C1. Binary Table (Easy Version)

题面
给定 n×m 的 01 矩阵，每次操作可以对它的某个 2×2 子矩阵中的三个元素取反，试寻找一个不超过 3nm 次操作的策略，使最终矩阵中所有元素全为 0。不需要求最小操作次数，且保证一定有可行解（time limit per test：1 second）

输入

第一行输入 t (1 ≤ T ≤ 5000)，代表 t 个样例
每一个样例：
- 第一行输入 $n, m$ $(2 ≤ n, m ≤ 100)$
- 接下去 n 行输入长度为 m 的字符串
- nm 不会超过20000

输出

对每个样例，首先输出操作次数 k (0 ≤ k ≤ 3nm)
接下来 k 行，输出六个整数 $x_1, y_1, x_2, y_2, x_3, y_3$ ，表示每次转换的元素下标

样例

Input
Output

5
2 2
10
11
3 3
011
101
110
4 4
1111
0110
0110
1111
5 5
01011
11001
00010
11011
10000
2 3
011
101

1
1 1 2 1 2 2
2
2 1 3 1 3 2
1 2 1 3 2 3
4
1 1 1 2 2 2
1 3 1 4 2 3
3 2 4 1 4 2
3 3 4 3 4 4
4
1 2 2 1 2 2
1 4 1 5 2 5
4 1 4 2 5 1
4 4 4 5 3 4
2
1 3 2 2 2 3
1 2 2 1 2 2

思路
待补

代码

#include <bits/stdc++.h> 
#include <cstdio>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define debug(x) cout << "---->" << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 105;
const int maxm = 105;

int t,n,m;
bool mp[maxn][maxm];
queue<int> qx1,qy1,qx2,qy2,qx3,qy3;

// 记录每次的转换 
void change(int x1,int y1,int x2,int y2,int x3,int y3)
{
    qx1.push(x1);
    qy1.push(y1);
    qx2.push(x2);
    qy2.push(y2);
    qx3.push(x3);
    qy3.push(y3);
    mp[x1][y1] = !mp[x1][y1];
    mp[x2][y2] = !mp[x2][y2];
    mp[x3][y3] = !mp[x3][y3];
}

int main()
{
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i = 1;i <= n;++i) {
            getchar(); // 消去换行 
            for(int j = 1;j <= m;++j) {
            mp[i][j] = getchar()-'0';
            }
        }
        for(int i = 2;i <= n;i += 2) {
            for(int j = 1;j < m;++j) {
                if(mp[i-1][j] && mp[i][j]) {
                    change(i-1,j,i,j,i,j+1);
                }
                else if(mp[i-1][j]) {
                    change(i-1,j,i-1,j+1,i,j+1);
                }
                else if(mp[i][j]) {
                    change(i,j,i-1,j+1,i,j+1);
                }
            }
        }
        for(int i = 1;i < n;++i){
            if(mp[i][m]){
                change(i,m,i,m-1,i+1,m-1);
                change(i,m-1,i+1,m-1,i+1,m);
            }
        }
        if(n % 2){
            for(int j = 1;j < m;++j){
                if(mp[n][j]){
                    change(n,j,n-1,j,n-1,j+1);
                    change(n-1,j,n-1,j+1,n,j+1);
                }
            }
        }
        if(mp[n][m]){
            change(n-1,m-1,n-1,m,n,m);
            change(n-1,m,n,m,n,m-1);
            change(n,m,n,m-1,n-1,m-1);
        }
        cout<<qx1.size()<<endl;
        while(!qx1.empty()){
            cout<<qx1.front()<<' '<<qy1.front()<<' ';
            cout<<qx2.front()<<' '<<qy2.front()<<' ';
            cout<<qx3.front()<<' '<<qy3.front()<<endl;
            qx1.pop(),qx2.pop(),qx3.pop();
            qy1.pop(),qy2.pop(),qy3.pop();
        }
    }
    return 0;
}

C2. Binary Table (Hard Version)

题面
给定 n×m 的 01 矩阵，每次操作可以对它的某个 2×2 子矩阵中的三个元素取反，试寻找一个不超过 nm 次操作的策略，使最终矩阵中所有元素全为 0。不需要求最小操作次数，且保证一定有可行解（time limit per test：1 second）

输入

第一行输入 t (1 ≤ T ≤ 5000)，代表 t 个样例
每一个样例：
- 第一行输入 $n, m$ $(2 ≤ n, m ≤ 100)$
- 接下去 n 行输入长度为 m 的字符串
- nm 不会超过20000

输出

对每个样例，首先输出操作次数 k (0 ≤ k ≤ nm)
接下来 k 行，输出六个整数 $x_1, y_1, x_2, y_2, x_3, y_3$ ，表示每次转换的元素下标

样例

Input
Output

5
2 2
10
11
3 3
011
101
110
4 4
1111
0110
0110
1111
5 5
01011
11001
00010
11011
10000
2 3
011
101

1
1 1 2 1 2 2
2
2 1 3 1 3 2
1 2 1 3 2 3
4
1 1 1 2 2 2
1 3 1 4 2 3
3 2 4 1 4 2
3 3 4 3 4 4
4
1 2 2 1 2 2
1 4 1 5 2 5
4 1 4 2 5 1
4 4 4 5 3 4
2
1 3 2 2 2 3
1 2 2 1 2 2

思路
待补

代码

#include <bits/stdc++.h> 
#include <cstdio>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define debug(x) cout << "---->" << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 105;
const int maxm = 105;

int t,n,m;
bool mp[maxn][maxm];
queue<int> qx1,qy1,qx2,qy2,qx3,qy3;

void change(int x1,int y1,int x2,int y2,int x3,int y3)
{
    qx1.push(x1);
    qy1.push(y1);
    qx2.push(x2);
    qy2.push(y2);
    qx3.push(x3);
    qy3.push(y3);
    mp[x1][y1] = !mp[x1][y1];
    mp[x2][y2] = !mp[x2][y2];
    mp[x3][y3] = !mp[x3][y3];
}

int main()
{
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i = 1;i <= n;++i) {
            getchar();
            for(int j = 1;j <= m;++j) {
                mp[i][j] = getchar()-'0';
            }
        }
        for(int i = n;i > 2;--i) {
            if(mp[i][1]) change(i,1,i-1,1,i-1,2);
            for(int j = 2;j <= m;++j) {
                if(mp[i][j])change(i,j,i-1,j,i-1,j-1);
            }
        }
        for(int j = m;j > 2;--j) {
            if(mp[1][j] && mp[2][j]) change(1,j,2,j,1,j-1);
            else if(mp[1][j]) change(1,j,1,j-1,2,j-1);
            else if(mp[2][j]) change(2,j,1,j-1,2,j-1);
        }
        while(1) {
            int cnt = mp[1][1]+mp[1][2]+mp[2][1]+mp[2][2];
            if(cnt == 0) break;
            if(cnt == 1) {
                if(mp[1][1] == mp[2][2])change(1,1,1,2,2,1);
                else change(1,1,1,2,2,2);
            }
            else if(cnt == 2){
                if(mp[1][1] == mp[2][2]) {
                    if(mp[1][1]) change(1,1,1,2,2,1);
                    else change(1,1,1,2,2,2);
                }
                else{
                    if(mp[1][1]) {
                        if(mp[1][2]) change(1,2,2,1,2,2);
                        else change(1,1,1,2,2,2);
                    }
                    else{
                        if(mp[1][2]) change(1,1,2,1,2,2);
                        else change(1,1,1,2,2,1);
                    }
                }
            }
            else if(cnt == 3){
                if(!mp[1][1]) change(1,2,2,1,2,2);
                else if(!mp[1][2]) change(1,1,2,1,2,2);
                else if(!mp[2][1]) change(1,1,1,2,2,2);
                else change(1,1,1,2,2,1);
            }
            else{
                change(1,1,1,2,2,1);
            }
        }
        cout << qx1.size() << endl;
        while(!qx1.empty()) {
            cout<<qx1.front()<<' '<<qy1.front()<<' ';
            cout<<qx2.front()<<' '<<qy2.front()<<' ';
            cout<<qx3.front()<<' '<<qy3.front()<<endl;
            qx1.pop(),qx2.pop(),qx3.pop();
            qy1.pop(),qy2.pop(),qy3.pop();
        }
    }
    return 0;
}

D. Graph Subset Problem

题面
待补（time limit per test：1 second）

输入

第一行输入 t (1 ≤ T ≤ 10)，代表 t 个样例
每一个样例：
- 第一行输入 $n, c_0, c_1 , h$ $(1 ≤ n, c_0, c_1 , h ≤ 1000)$
- 第二行输入长度为 n 的01字符串

输出
xxx

样例

Input
Output

3
5 9 4
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
10 15 3
1 2
2 3
3 4
4 5
5 1
1 7
2 8
3 9
4 10
5 6
7 10
10 8
8 6
6 9
9 7
4 5 4
1 2
2 3
3 4
4 1
1 3

2
4 1 2 3
1 10
1 2 3 4 5 6 7 8 9 10
-1

思路
待补

代码

// 待补

E. Greedy Shopping

题面
待补（time limit per test：3 second）

输入

第一行输入 t (1 ≤ T ≤ 10)，代表 t 个样例
每一个样例：
- 第一行输入 $n, c_0, c_1 , h$ $(1 ≤ n, c_0, c_1 , h ≤ 1000)$
- 第二行输入长度为 n 的01字符串

输出
xxx

样例

Input
Output

10 6
10 10 10 6 6 5 5 5 3 1
2 3 50
2 4 10
1 3 10
2 2 36
1 4 7
2 2 17

8
3
6
2

思路
待补

代码

// 待补

版权属于：PCsky
本文链接：http://www.hyouka.club/index.php/archives/81/
转载时须注明出处及本声明

最后修改：2022 年 01 月 27 日 12 : 50 PM

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

邮箱 *

地址

侯
安装软件或者卸载软甲出这个弹框什么意思，区域啥的也设置了nsi...
后浪
找到了，谢谢
后浪
这个主题挺好看的，有深色模式，是自己写的吗还是在哪里可以找到？
橘白猫
我单位的WIN10神州网信系统出现了一个奇葩的问题，不知道你有...
Acg
handsome.min.css的度盘链接有问题，打开是一个图片

【codeforces题解】Codeforces Round #684 (Div. 2)

PCsky • 2020 年 11 月 21 日

A. Buy the String

输入

第一行输入 t (1 ≤ T ≤ 10)，代表 t 个样例
每一个样例：
- 第一行输入 $n, c_0, c_1 , h$ $(1 ≤ n, c_0, c_1 , h ≤ 1000)$
- 第二行输入长度为 n 的01字符串

输出
对每个样例，输出最小花费

样例

Input
Output

6
3 1 1 1
100
5 10 100 1
01010
5 10 1 1
11111
5 1 10 1
11111
12 2 1 10
101110110101
2 100 1 10
00

3
52
5
10
16
22

代码

#include <bits/stdc++.h> 
#include <cstdio>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define debug(x) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6+5;

int n,c0,c1,h;
string s;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> c0 >> c1 >> h;
        cin >> s;
        int sum = 0;
        int nc0 = min(c0,c1+h);    // 字符0的最小花费 
        int nc1 = min(c1,c0+h);    // 字符1的最小花费 
        for(int i = 0; i < n; i++) {
            if(s[i] == '0') sum += nc0;
            else sum += nc1;
        }
        cout << sum << '\n';
    }
    return 0;
}

B. Sum of Medians

输入

第一行输入 t (1 ≤ T ≤ 100)，代表 t 个样例
每一个样例：
- 第一行输入 n, k (1 ≤ n, k ≤ 1000)
- 第二行输入 nk 个整数 $a_1,a_2,...,a_{nk}$ $(0 ≤ a_i ≤ 10^9)$
- 数组按非递减输入，nk 不会超过 $2*10^5$

输出
对每个样例，子数组中位数之和的最大可能值。

样例

Input
Output

6
2 4
0 24 34 58 62 64 69 78
2 2
27 61 81 91
4 3
2 4 16 18 21 27 36 53 82 91 92 95
3 4
3 11 12 22 33 35 38 67 69 71 94 99
2 1
11 41
3 3
1 1 1 1 1 1 1 1 1

165
108
145
234
11
3

代码

#include <bits/stdc++.h> 
#include <cstdio>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define debug(x) cout << "---->" << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6+5;

int n,k;
ll a[maxn];

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> k; 
        int len = n*k;
        for(int i = 1; i <= len; i++) cin >> a[i];
        int mid = ceil(n/2.0);
        int pos = len - (n-mid);
        ll sum = 0;
        while(k--) {
            // 从pos开始反过来选 
            sum += a[pos];
            // 每次往回跳
            pos = pos-(n-mid)-1;
        }
        cout << sum << '\n';
    }
    return 0;
}

C1. Binary Table (Easy Version)

输入

第一行输入 t (1 ≤ T ≤ 5000)，代表 t 个样例
每一个样例：
- 第一行输入 $n, m$ $(2 ≤ n, m ≤ 100)$
- 接下去 n 行输入长度为 m 的字符串
- nm 不会超过20000

输出

对每个样例，首先输出操作次数 k (0 ≤ k ≤ 3nm)
接下来 k 行，输出六个整数 $x_1, y_1, x_2, y_2, x_3, y_3$ ，表示每次转换的元素下标

样例

Input
Output

5
2 2
10
11
3 3
011
101
110
4 4
1111
0110
0110
1111
5 5
01011
11001
00010
11011
10000
2 3
011
101

1
1 1 2 1 2 2
2
2 1 3 1 3 2
1 2 1 3 2 3
4
1 1 1 2 2 2
1 3 1 4 2 3
3 2 4 1 4 2
3 3 4 3 4 4
4
1 2 2 1 2 2
1 4 1 5 2 5
4 1 4 2 5 1
4 4 4 5 3 4
2
1 3 2 2 2 3
1 2 2 1 2 2

思路
待补

代码

#include <bits/stdc++.h> 
#include <cstdio>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define debug(x) cout << "---->" << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 105;
const int maxm = 105;

int t,n,m;
bool mp[maxn][maxm];
queue<int> qx1,qy1,qx2,qy2,qx3,qy3;

// 记录每次的转换 
void change(int x1,int y1,int x2,int y2,int x3,int y3)
{
    qx1.push(x1);
    qy1.push(y1);
    qx2.push(x2);
    qy2.push(y2);
    qx3.push(x3);
    qy3.push(y3);
    mp[x1][y1] = !mp[x1][y1];
    mp[x2][y2] = !mp[x2][y2];
    mp[x3][y3] = !mp[x3][y3];
}

int main()
{
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i = 1;i <= n;++i) {
            getchar(); // 消去换行 
            for(int j = 1;j <= m;++j) {
            mp[i][j] = getchar()-'0';
            }
        }
        for(int i = 2;i <= n;i += 2) {
            for(int j = 1;j < m;++j) {
                if(mp[i-1][j] && mp[i][j]) {
                    change(i-1,j,i,j,i,j+1);
                }
                else if(mp[i-1][j]) {
                    change(i-1,j,i-1,j+1,i,j+1);
                }
                else if(mp[i][j]) {
                    change(i,j,i-1,j+1,i,j+1);
                }
            }
        }
        for(int i = 1;i < n;++i){
            if(mp[i][m]){
                change(i,m,i,m-1,i+1,m-1);
                change(i,m-1,i+1,m-1,i+1,m);
            }
        }
        if(n % 2){
            for(int j = 1;j < m;++j){
                if(mp[n][j]){
                    change(n,j,n-1,j,n-1,j+1);
                    change(n-1,j,n-1,j+1,n,j+1);
                }
            }
        }
        if(mp[n][m]){
            change(n-1,m-1,n-1,m,n,m);
            change(n-1,m,n,m,n,m-1);
            change(n,m,n,m-1,n-1,m-1);
        }
        cout<<qx1.size()<<endl;
        while(!qx1.empty()){
            cout<<qx1.front()<<' '<<qy1.front()<<' ';
            cout<<qx2.front()<<' '<<qy2.front()<<' ';
            cout<<qx3.front()<<' '<<qy3.front()<<endl;
            qx1.pop(),qx2.pop(),qx3.pop();
            qy1.pop(),qy2.pop(),qy3.pop();
        }
    }
    return 0;
}

C2. Binary Table (Hard Version)

输入

第一行输入 t (1 ≤ T ≤ 5000)，代表 t 个样例
每一个样例：
- 第一行输入 $n, m$ $(2 ≤ n, m ≤ 100)$
- 接下去 n 行输入长度为 m 的字符串
- nm 不会超过20000

输出

对每个样例，首先输出操作次数 k (0 ≤ k ≤ nm)
接下来 k 行，输出六个整数 $x_1, y_1, x_2, y_2, x_3, y_3$ ，表示每次转换的元素下标

样例

Input
Output

5
2 2
10
11
3 3
011
101
110
4 4
1111
0110
0110
1111
5 5
01011
11001
00010
11011
10000
2 3
011
101

1
1 1 2 1 2 2
2
2 1 3 1 3 2
1 2 1 3 2 3
4
1 1 1 2 2 2
1 3 1 4 2 3
3 2 4 1 4 2
3 3 4 3 4 4
4
1 2 2 1 2 2
1 4 1 5 2 5
4 1 4 2 5 1
4 4 4 5 3 4
2
1 3 2 2 2 3
1 2 2 1 2 2

思路
待补

代码

#include <bits/stdc++.h> 
#include <cstdio>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define debug(x) cout << "---->" << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 105;
const int maxm = 105;

int t,n,m;
bool mp[maxn][maxm];
queue<int> qx1,qy1,qx2,qy2,qx3,qy3;

void change(int x1,int y1,int x2,int y2,int x3,int y3)
{
    qx1.push(x1);
    qy1.push(y1);
    qx2.push(x2);
    qy2.push(y2);
    qx3.push(x3);
    qy3.push(y3);
    mp[x1][y1] = !mp[x1][y1];
    mp[x2][y2] = !mp[x2][y2];
    mp[x3][y3] = !mp[x3][y3];
}

int main()
{
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i = 1;i <= n;++i) {
            getchar();
            for(int j = 1;j <= m;++j) {
                mp[i][j] = getchar()-'0';
            }
        }
        for(int i = n;i > 2;--i) {
            if(mp[i][1]) change(i,1,i-1,1,i-1,2);
            for(int j = 2;j <= m;++j) {
                if(mp[i][j])change(i,j,i-1,j,i-1,j-1);
            }
        }
        for(int j = m;j > 2;--j) {
            if(mp[1][j] && mp[2][j]) change(1,j,2,j,1,j-1);
            else if(mp[1][j]) change(1,j,1,j-1,2,j-1);
            else if(mp[2][j]) change(2,j,1,j-1,2,j-1);
        }
        while(1) {
            int cnt = mp[1][1]+mp[1][2]+mp[2][1]+mp[2][2];
            if(cnt == 0) break;
            if(cnt == 1) {
                if(mp[1][1] == mp[2][2])change(1,1,1,2,2,1);
                else change(1,1,1,2,2,2);
            }
            else if(cnt == 2){
                if(mp[1][1] == mp[2][2]) {
                    if(mp[1][1]) change(1,1,1,2,2,1);
                    else change(1,1,1,2,2,2);
                }
                else{
                    if(mp[1][1]) {
                        if(mp[1][2]) change(1,2,2,1,2,2);
                        else change(1,1,1,2,2,2);
                    }
                    else{
                        if(mp[1][2]) change(1,1,2,1,2,2);
                        else change(1,1,1,2,2,1);
                    }
                }
            }
            else if(cnt == 3){
                if(!mp[1][1]) change(1,2,2,1,2,2);
                else if(!mp[1][2]) change(1,1,2,1,2,2);
                else if(!mp[2][1]) change(1,1,1,2,2,2);
                else change(1,1,1,2,2,1);
            }
            else{
                change(1,1,1,2,2,1);
            }
        }
        cout << qx1.size() << endl;
        while(!qx1.empty()) {
            cout<<qx1.front()<<' '<<qy1.front()<<' ';
            cout<<qx2.front()<<' '<<qy2.front()<<' ';
            cout<<qx3.front()<<' '<<qy3.front()<<endl;
            qx1.pop(),qx2.pop(),qx3.pop();
            qy1.pop(),qy2.pop(),qy3.pop();
        }
    }
    return 0;
}

D. Graph Subset Problem

题面
待补（time limit per test：1 second）

输入

第一行输入 t (1 ≤ T ≤ 10)，代表 t 个样例
每一个样例：
- 第一行输入 $n, c_0, c_1 , h$ $(1 ≤ n, c_0, c_1 , h ≤ 1000)$
- 第二行输入长度为 n 的01字符串

输出
xxx

样例

Input
Output

3
5 9 4
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
10 15 3
1 2
2 3
3 4
4 5
5 1
1 7
2 8
3 9
4 10
5 6
7 10
10 8
8 6
6 9
9 7
4 5 4
1 2
2 3
3 4
4 1
1 3

2
4 1 2 3
1 10
1 2 3 4 5 6 7 8 9 10
-1

思路
待补

代码

// 待补

E. Greedy Shopping

题面
待补（time limit per test：3 second）

输入

第一行输入 t (1 ≤ T ≤ 10)，代表 t 个样例
每一个样例：
- 第一行输入 $n, c_0, c_1 , h$ $(1 ≤ n, c_0, c_1 , h ≤ 1000)$
- 第二行输入长度为 n 的01字符串

输出
xxx

样例

Input
Output

10 6
10 10 10 6 6 5 5 5 3 1
2 3 50
2 4 10
1 3 10
2 2 36
1 4 7
2 2 17

8
3
6
2

思路
待补

代码

// 待补

版权属于：PCsky
本文链接：http://www.hyouka.club/index.php/archives/81/
转载时须注明出处及本声明

【codeforces题解】Codeforces Round #684 (Div. 2)

A. Buy the String

B. Sum of Medians

C1. Binary Table (Easy Version)

C2. Binary Table (Hard Version)

D. Graph Subset Problem

E. Greedy Shopping

发表评论取消回复

【Windows10技巧】Windows 10 神州网信政府版的奇妙操作

【私人博客】腾讯云+typecho 搭建简易的个人博客

【博客优化】Typecho博客使用MathJax显示数学公式

【博客优化】Typecho代码高亮插件Code Prettify

【入门基础】c++高精度运算模板v1.0

【Windows10技巧】win10家庭版系统打开组策略编辑器

日常随拍

【风光摄影】广州小蛮腰从什么角度拍好看

【数论】素数筛的四种方式

【TV动画推荐】2019年的TV动画佳作

【codeforces题解】Codeforces Round #684 (Div. 2)

A. Buy the String

B. Sum of Medians

C1. Binary Table (Easy Version)

C2. Binary Table (Hard Version)

D. Graph Subset Problem

E. Greedy Shopping

发表评论 取消回复

【codeforces题解】Codeforces Round #684 (Div. 2)

发表评论取消回复