比赛链接
E.小L的井字棋
题目描述
小L和炸鸡在下井字棋。
对于给定的
行
列的棋盘，一共有
个位置可以落子。双方可能已经进行了若干次行动，即你拿到的是一个残局局面。我们使用
表示棋盘中从上往下数第
行和从左往右数第
列的单元格，使用
表示这个单元格中现在的状态，状态有且仅有三种：
，表示第
行第
列的格子内小L下了一个子；
，表示第
行第
列的格子内炸鸡下了一个子；
，表示第
行第
列的格子内还没有落子。
谁先让自己的棋子三个连成一线，谁就获胜。三个连成一线指某一行、或者某一列、或者某一对角线棋子都一样。
保证此时棋盘上双方落子数量相同，且还未分出胜负。现在，轮到小L行动了，由于小L是新手，炸鸡自大地给予了小L一个特权：在接下去的某一次行动中可以连续走两步。
在双方都足够聪明的情况下，小L能否必胜？
输入描述
代表数据组数，每组测试数据描述如下：
行输入三个字符
，表示当前棋盘中第
输出描述
，否则输出
。
解题思路
没有技巧，全是暴力。
当双方棋子数均时，小L必胜。
当双方棋子数均为4时，只剩一个空，下棋并判断即可。
当双方棋子数均为3时，剩3个位置，由于特权，小L可选择其中任意两个，故存在3种可选下法，枚举判断即可。
完整代码
#include<bits/stdc++.h>
//#define int long long
using namespace std;
int check(int mp[3][3]) {
for (int i = 0; i < 3; i++) {
if (mp[i][0] == 1)
if (mp[i][1] == 1)
if (mp[i][2] == 1)
return 1;
if (mp[0][i] == 1)
if (mp[1][i] == 1)
if (mp[2][i] == 1)
return 1;
}
if (mp[0][0] == 1)
if (mp[1][1] == 1)
if (mp[2][2] == 1)
return 1;
if (mp[0][2] == 1)
if (mp[1][1] == 1)
if (mp[2][0] == 1)
return 1;
return 0;
}
static string solve() {
char c;
int mp[3][3];
int cntx = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cin >> c;
if (c == 'X') {
mp[i][j] = 1;
cntx++;
}
else if (c == 'O') mp[i][j] = -1;
else mp[i][j] = 0;
}
}
if (cntx <= 2) return "Yes";
else if (cntx == 4) {
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (mp[i][j] == 0)mp[i][j] = 1;
if (check(mp) == 1)return "Yes";
else return "No";
}
else {
int space[3][2];
int cnt = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
{
if (mp[i][j] == 0) {
space[cnt][0] = i;
space[cnt][1] = j;
cnt++;
}
}
mp[space[0][0]][space[0][1]] = -1;
mp[space[1][0]][space[1][1]] = 1;
mp[space[2][0]][space[2][1]] = 1;
if (check(mp) == 1) return "Yes";
mp[space[0][0]][space[0][1]] = 1;
mp[space[1][0]][space[1][1]] = -1;
mp[space[2][0]][space[2][1]] = 1;
if (check(mp) == 1) return "Yes";
mp[space[0][0]][space[0][1]] = 1;
mp[space[1][0]][space[1][1]] = 1;
mp[space[2][0]][space[2][1]] = -1;
if (check(mp) == 1) return "Yes";
return "No";
}
}
signed main() {
int T = 1;
cin >> T;
while (T--) {
cout << solve() << endl;
}
return 0;
}
C.小L的位运算
题目描述
小L有三个二进制数
，三个数字的位数均为
位。每一轮，他可以从以下四种操作中任选一个进行：
花费
元，反置二进制数
的任意一位；
花费
元，反置二进制数
的任意一位；
花费
元，交换二进制数
的任意两个数位；
花费
元，交换二进制数
的任意两个数位。
请你帮小红判断，若能进行任意多轮操作（也可以不进行操作），使得
的最小花费是多少。我们可以证明，一定存在一种操作方案，使得该式子成立。
在二进制表示中，数字
反置后得到
；数字
反置后得到
。
其中，
表示按位异或运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节。
输入描述
代表给定的二进制数的位数、操作一二的代价、操作三四的代价。
的二进制数
。
。
。
输出描述
解题思路
不难发现，错误的位有四种类型：
- 当
时，
；
- 当
；
- 当
时，
；
- 当
。
我们依次按 的顺序表示为
。
对于其中任意一种错误类型，都可以与其他三种错误类型通过交换操作来同时合法化，如 与
交换
中对应的位，变成
与
，从而合法。
我们统计这四种错误类型的数量，分别存入数组 ，而
为所有错误数量之和。
由于交换操作本质是同时对两个位进行反置操作，如果反置两个位的代价小于等于交换操作的代价（即 ），则所有的交换操作均可被反置操作取代。此时答案即为
。
否则，假设变量 为这四个数中最大的那个，如果
大于
的一半，则
可与除自己外所有的类型通过交换操作来合法化，多余的部分仅能反置；否则，可以证明，一定存在一种匹配方式，使得四种类型可以全部使用交换操作合法化（
为偶数的情况），或仅剩余 1 个位无法交换（
为奇数的情况）。
完整代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, x, y, ans, sum, mx;
string a, b, c;
int w[4];
signed main() {
cin >> n >> x >> y >> a >> b >> c;
for (int i = 0; i < n; i++) {
if (c[i] == '0') {
if (a[i] == '0' && b[i] == '1') w[0]++;
else if (a[i] == '1' && b[i] == '0') w[1]++;
}
else {
if (a[i] == '0' && b[i] == '0') w[2]++;
else if (a[i] == '1' && b[i] == '1') w[3]++;
}
}
sum = w[0] + w[1] + w[2] + w[3];
mx = max({ w[0],w[1],w[2],w[3] });
if (x * 2 <= y)
ans = sum * x;
else
if (mx > sum / 2) ans = (sum - mx) * y + (mx * 2 - sum) * x;
else ans = sum / 2 * y + sum % 2 * x;
cout << ans << endl;
}
京公网安备 11010502036488号