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字符串
输出
对每个样例，输出最小花费
样例
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;
} B. Sum of Medians
题面
一个长度为 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$
输出
对每个样例，子数组中位数之和的最大可能值。
样例
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)。
代码
#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$ ，表示每次转换的元素下标
样例
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$ ，表示每次转换的元素下标
样例
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
样例
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
样例
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://hyouka.club/index.php/archives/81/
转载时须注明出处及本声明