题目大意：
给出(8*8)的棋盘，给定起点和终点，输出从起点到达终点的最短步数以及路径。
思路：
必定会尽可能选择沿着两点连线前进，容易得到这样最多能够行走(max(abs(end[0] - start[0]), abs(end[1] - start[1])))步。
输出路径我们观察到方向都是由“左右/上下”组成，因此考虑将方向拆解成单个方向进行输出。
Code：
#include <bits/stdc++.h>
using namespace std;
int main() {
string st, ed; cin >> st >> ed;
int a = ed[0] - st[0];
int b = ed[1] - st[1];
char dirx = a > 0 ? 'R' : 'L';
char diry = b > 0 ? 'U' : 'D';
a = abs(a), b = abs(b);
cout << max(a, b) << endl;
for (; a || b; cout << endl) {
if (a) {
cout << dirx;
--a;
}
if (b) {
cout << diry;
--b;
}
}
return 0;
}
题目大意：
有一个体积为(v)的背包，一共有(n)件物品，没见物品的体积为(t_i)，价值为(p_i)，现要从中取出若干物品放入背包，使得背包中物品的价值最大。
思路：
根据题意一共由两类物品，每种物品我们肯定贪心选择价值更大的物品。由此我们将两类物品降序排列。
枚举体积为(1)的物品放入背包的数量，剩余容量用于放入体积为(2)的物品，更新最大值。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct Node
{
int p, id;
}ka1[N], ca2[N];
int n, v, cnt1, cnt2, pre[N], sum, ans, pos1, pos2;
bool cmp(Node a, Node b) {
return a.p > b.p; //按价值从大到小排序
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> v;
for (int i = 1; i <= n; i++) { //根据体积分成两类
int t, p; cin >> t >> p;
if (t == 1) {
ka1[++cnt1].p = p;
ka1[cnt1].id = i;
} else {
ca2[++cnt2].p = p;
ca2[cnt2].id = i;
}
}
sort(ka1 + 1, ka1 + cnt1 + 1, cmp);
sort(ca2 + 1, ca2 + cnt2 + 1, cmp);
for (int i = 1; i <= cnt2; i++) { //预处理出体积为2的物品价值的前缀和
pre[i] = pre[i - 1] + ca2[i].p;
}
for (int i = 0; i <= min(v, cnt1); i++) { //选了i个体积为1的物品
sum += ka1[i].p; //体积为1的物品价值和
if (sum + pre[min(cnt2, (v - i) / 2)] > ans) { //体积为2的物品选了 min(cnt2, (v - i) / 2) 个
ans = sum + pre[min(cnt2, (v - i) / 2)];
pos1 = i, pos2 = min(cnt2, (v - i) / 2); //记录该方案的位置
}
}
cout << ans << endl;
for (int i = 1; i <= pos1; i++) cout << ka1[i].id << " ";
for (int i = 1; i <= pos2; i++) cout << ca2[i].id << " ";
return 0;
}
题目大意：
给出井字棋的棋谱，要求判断其属于六种局势中的哪一种。
六种局势分别为非法，先手获胜，后手获胜，平局，轮到先手，轮到后手。
思路：
模拟题，需要考虑一些特殊棋谱，比如：
-
(test2)
0.X XX. 000 -
(test4)
XXX ... 000 -
(test9)
000 X.X X.X
我是按照illegal、获胜态、someone‘s turn、draw的顺序来进行判断。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 5;
char mp[N][N];
int cnt0, cnt1;
int Win = 0;
int main() {
for (int i = 1; i <= 3; i++) scanf("%s", mp[i] + 1);
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if (mp[i][j] == '0') cnt0++;
else if (mp[i][j] == 'X') cnt1++;
}
}
if (abs(cnt1 - cnt0) > 1 || cnt1 < cnt0) {
cout << "illegal" << endl;
} else {
if (mp[1][1] == 'X' && mp[1][2] == 'X' && mp[1][3] == 'X' ||
mp[2][1] == 'X' && mp[2][2] == 'X' && mp[2][3] == 'X' ||
mp[3][1] == 'X' && mp[3][2] == 'X' && mp[3][3] == 'X' ||
mp[1][1] == 'X' && mp[2][1] == 'X' && mp[3][1] == 'X' ||
mp[1][2] == 'X' && mp[2][2] == 'X' && mp[3][2] == 'X' ||
mp[1][3] == 'X' && mp[2][3] == 'X' && mp[3][3] == 'X' ||
mp[1][1] == 'X' && mp[2][2] == 'X' && mp[3][3] == 'X' ||
mp[3][1] == 'X' && mp[2][2] == 'X' && mp[1][3] == 'X'
) {
Win += 1;
}
if (mp[1][1] == '0' && mp[1][2] == '0' && mp[1][3] == '0' ||
mp[2][1] == '0' && mp[2][2] == '0' && mp[2][3] == '0' ||
mp[3][1] == '0' && mp[3][2] == '0' && mp[3][3] == '0' ||
mp[1][1] == '0' && mp[2][1] == '0' && mp[3][1] == '0' ||
mp[1][2] == '0' && mp[2][2] == '0' && mp[3][2] == '0' ||
mp[1][3] == '0' && mp[2][3] == '0' && mp[3][3] == '0' ||
mp[1][1] == '0' && mp[2][2] == '0' && mp[3][3] == '0' ||
mp[3][1] == '0' && mp[2][2] == '0' && mp[1][3] == '0'
) {
Win += 2;
}
if (Win == 3) {
cout << "illegal" << endl;
} else if (Win == 1&& cnt1 - cnt0 != 1) {
cout << "illegal" << endl;
} else if (Win == 2 && cnt1 != cnt0) {
cout << "illegal" << endl;
} else if (Win == 1) {
cout << "the first player won" << endl;
} else if (Win == 2) {
cout << "the second player won" << endl;
}
else if (cnt1 == cnt0 && cnt0 + cnt1 < 9) {
cout << "first" << endl;
} else if (cnt1 == cnt0 + 1 && cnt0 + cnt1 < 9) {
cout << "second" << endl;
} else {
cout << "draw" << endl;
}
}
return 0;
}
D. Least Cost Bracket Sequence
题目大意：
给定一个包含(()、())、(?)的序列，每一个?都要替换成左括号或右括号，每个替换都有相应的代价，需要替换后括号是匹配的，输出最小代价和替换后的序列，若括号不能匹配输出-1。
思路：
用(cnt)记录括号匹配情况，遇到(() 时(cnt+1)，遇到())时(cnt-1)。先假设所有的(?)都为())，如果当前(cnt<0)，说明没有足够的(()进行匹配，则从前面找到替换代价尽可能小的(?)（此时已经全被当成())）改替换为(()，并更新 (cnt= cnt + 2)。
这个类似反悔的过程我们可以使用优先队列进行优化，每次遇到(?)将其加入到队列中， 其值为(-b+a)，并记录其位置下标(id)。若(cnt<0)则弹出最小代价的节点。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 50010;
struct Node {
int delta, id;
bool operator<(const Node& t) const { return delta > t.delta; }
};
priority_queue<Node> q;
string s;
LL cost;
int cnt;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> s;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
++cnt;
} else {
--cnt;
if (s[i] == '?') {
int a, b; cin >> a >> b;
Node tmp;
tmp.delta = a - b, tmp.id = i;
q.push(tmp);
s[i] = ')';
cost += b;
}
}
if (cnt < 0) {
if (q.empty()) {
cost = -1; break;
}
cnt += 2;
Node tmp = q.top(); q.pop();
cost += tmp.delta;
s[tmp.id] = '(';
}
}
if (cnt || cost == -1) cout << -1 << endl;
else {
cout << cost << endl;
cout << s << endl;
}
return 0;
}