T0
换一张经典图片，否则会腻的[doge]
T1
[1000/1000]
华哥喜欢让学长上操场跑圈圈.这个操场可以看作n个点,顺时针依次标号为1到n.相邻两点的距离为1.学长总是从1号点开始跑.
最近, 华哥觉得跑圈没意思, 于是他给出m个指令. 每当给出一个指令x, 学长必须跑到x点上,然后他才会继续给出下一个指令.
学长每次可以选择顺时针或逆时针跑步,他希望跑步的总距离最少.
看一眼应该就可以想出，CQR DALAO甚至可能3mins不到就秒了。
其实就是破环成链，逆时针跑时在普通基础上+n就可以了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m;
void work() {
int u = 1;
LL res = 0;
scanf("%d%d", &n, &m);
while (m--) {
int x;
scanf("%d", &x);
int cnt;
if (x < u)
cnt = x + n - u;
else
cnt = u + n - x;
res += min(abs(x - u), cnt);
u = x;
}
printf("%lld\n", res);
}
int main() {
int T;
scanf("%d", &T);
while (T--) work();
return 0;
}
T2
[1300/1300]
小C经过几个月的奋战，终于拿到了他的驾照！欣喜若狂的小C拿出他的积蓄，买了一辆怪物卡车。之所以叫做怪物卡车，不仅仅是因为它整整和4辆普通汽车一样大，也是因为它可以直接从普通汽车上碾压过去！小C发现，即使买了这样一辆怪物卡车，停车的问题还是很难解决，毕竟怪物卡车太大了。
他的朋友小T在镇上的停车系统公司上班。她会定期提供给小C一张城市停车位图，共R行C列。每一格可以有如下表示：‘#’表示建筑物（就算是怪物卡车也不能碾压建筑物）；‘X’表示已有普通汽车停在该格上面了；‘.’表示一个空的停车位。怪物卡车可以看做占地面积为2*2的正方形。
请你帮小C算一算，他停车后分别碾压0-4辆普通汽车的情况数。注意，我们在这里讨论的是停车后怪物卡车所在区域碾压的汽车数，而不是在它停车的过程中碾压的汽车数。
暴力出奇迹——枚举每一个位置分别计数就可以了
感觉可能今天出题人出水了，想想昨天的我还在遭受B题的拷打。
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int n, m, res[10];
char G[N][N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", G[i] + 1);
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (G[i][j] == '#' || G[i + 1][j] == '#' || G[i][j + 1] == '#' || G[i + 1][j + 1] == '#')
continue;
int cnt = 0;
if (G[i][j] == 'X')
cnt++;
if (G[i + 1][j] == 'X')
cnt++;
if (G[i][j + 1] == 'X')
cnt++;
if (G[i + 1][j + 1] == 'X')
cnt++;
res[cnt]++;
}
}
for (int i = 0; i < 5; i++) printf("%d\n", res[i]);
return 0;
}
T3
[1400/1400]
光头强又来啦。。这次他不是找熊大和熊二，他是去抓袋鼠，可怜的袋鼠们要面临麻烦了。。。
现在有n只袋鼠在草坪上玩，突然他们发现光头强正拿着枪对着它们。它们要想办法让袋鼠们尽可能少的暴露在外面，即把其他的袋鼠装在自己的袋子里，再逃跑。已知每次袋鼠只能装下一只袋鼠，且这只袋鼠的体积不能超过它的一半。现在请你帮它们算算，最多可以使多少袋鼠隐藏起来。
这题最开始打爆炸了——毫无疑问袋鼠并不会多次套娃，因此如果没有这个特判将会100->75。
剩下的就不是特别难了，普遍更受欢迎的方案是二分，当然也可以直接做。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
int n, res, a[N];
int check(int mid) {
if (mid < n - mid + 1) {
for (int i = 1, j = n - mid + 1; i <= mid; i++, j++) {
if (a[i] > a[j] / 2)
return 0;
}
return 1;
}
return 0;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + n + 1);
int l = 0, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid))
l = mid;
else
r = mid - 1;
}
printf("%d", l);
return 0;
}
T4
[1500/1500]
给定两个由1到n组成的排列A和B。现在要将A序列变成B序列，每次的操作可以将A序列的最后一位数，插入到前面的数之前。如排列1 2 3，操作一次之后可以变成3 1 2和1 3 2，即将3插入到一个数之前或者第二个数之前。现在请你算出，最少需要操作几次，使得排列A变成排列B。
不得不怀疑今天运气是不是有点好，第一次当场ACT4。
我的想法非常简单。
既然A->B，两个序列都不一样，而且也没有什么特殊性质，那就转换一下，把它写成下形式，用下标形式进行作答
然后你就会发现A序列虽然还是非常的混乱，但是B序列已经是一个完全排好的序列，因此，求出A序列的前端最长上升序列长度就可以了。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, a[N];
vector<int> A;
unordered_map<int, int> mp;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
mp[x] = i;
}
for (int i = 1; i <= n; i++) A.push_back(mp[a[i]]);
int cnt = 1;
for (int i = 1; i < A.size(); i++) {
if (A[i - 1] < A[i])
cnt++;
else
break;
}
printf("%d", n - cnt);
return 0;
}
T5
[1800/1800]
爱心企鹅游戏，两只企鹅要相遇！
每次游戏操作有4种：
如果按上或下，两只企鹅方向一致。
如果按左或右，右边的企鹅会朝相反的方向移动。
如果撞到墙或是边界，企鹅会原地踏步。
起初第一只企鹅的位置在左边地图的(20,20);目标是走到(1,20)
第二只企鹅的位置在右边地图的(20,1);目标是走到(1,1)
可以认为外面一层都是墙。
移动时，如果一个企鹅无法移动，另一个企鹅也可以朝目标移动。
没事，问题不大，不过是一个大的bfs嘛，就是这个细节有一点点多，不过还是可以勉强应付的。
#include <bits/stdc++.h>
using namespace std;
const int N = 25, M = 20;
char L[N][N], R[N][N];
struct node {
int Lx, Ly, Rx, Ry;
vector<char> res;
};
queue<node> q;
int print, d[N][N][N][N];
node Down(node u) {
if (u.Lx < M && L[u.Lx + 1][u.Ly] != '#')
u.Lx++;
if (u.Rx < M && R[u.Rx + 1][u.Ry] != '#')
u.Rx++;
u.res.push_back('D');
return u;
}
node Left(node u) {
if (u.Ly > 1 && L[u.Lx][u.Ly - 1] != '#')
u.Ly--;
if (u.Ry < M && R[u.Rx][u.Ry + 1] != '#')
u.Ry++;
u.res.push_back('L');
return u;
}
node Right(node u) {
if (u.Ly < M && L[u.Lx][u.Ly + 1] != '#')
u.Ly++;
if (u.Ry > 1 && R[u.Rx][u.Ry - 1] != '#')
u.Ry--;
u.res.push_back('R');
return u;
}
node Up(node u) {
if (u.Lx > 1 && L[u.Lx - 1][u.Ly] != '#')
u.Lx--;
if (u.Rx > 1 && R[u.Rx - 1][u.Ry] != '#')
u.Rx--;
u.res.push_back('U');
return u;
}
vector<char> bfs() {
q.push({ 20, 20, 20, 1 });
while (q.size()) {
node u = q.front();
if (u.Lx == 1 && u.Ly == 20 && u.Rx == 1 && u.Ry == 1)
return u.res;
q.pop();
if (d[u.Lx][u.Ly][u.Rx][u.Ry])
continue;
d[u.Lx][u.Ly][u.Rx][u.Ry] = 1;
q.push(Down(u));
q.push(Left(u));
q.push(Right(u));
q.push(Up(u));
}
vector<char> E;
E.clear();
return E;
}
int main() {
scanf("%d", &print);
for (int i = 1; i <= M; i++) scanf("%s %s", L[i] + 1, R[i] + 1);
vector<char> res = bfs();
if (!res.size()) {
printf("-1");
return 0;
}
printf("%d\n", res.size());
if (print) {
for (int i = 0; i < res.size(); i++) printf("%c", res[i]);
puts("");
node u = { 20, 20, 20, 1 };
L[u.Lx][u.Ly] = R[u.Rx][u.Ry] = 'A';
for (int i = 0; i < res.size(); i++) {
if (res[i] == 'D')
u = Down(u);
else if (res[i] == 'L')
u = Left(u);
else if (res[i] == 'R')
u = Right(u);
else
u = Up(u);
L[u.Lx][u.Ly] = R[u.Rx][u.Ry] = 'A';
}
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= M; j++) printf("%c", L[i][j]);
printf(" ");
for (int j = 1; j <= M; j++) printf("%c", R[i][j]);
puts("");
}
}
return 0;
}
T6
[0/2100]
七夕是个特殊的日子，CC和WW想去庆祝一下。他们打算找个浪漫的地方度过。他们所在的城市可以看作是由个点组成的，城市中的道路可以看成两点间的距离。由于到目的要花很长的时间，他们打算中途吃点东西，CC当然要表现一下，他打算在途中最贵的地方吃。从出发点到目的点路费可以看作是路径的长度和。CC想你帮他算算，如何选择选择路线，使得花费最少？（花费=路费+餐费）
原来出题人在这等我呢，打的爆搜挂了最后发现自己没有为边权赋值……
不过正解也很简单，枚举吃饭点，做单源最短路，注意不要让路上的cost超过源点的即可。
当然很感谢出题人鞭尸了我的最短路，赶紧回去复习。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 20005;
typedef long long LL;
typedef pair<LL, int> PLI;
int n, m, q;
LL cost[N], dist[N], res[N], w[M];
int h[N], e[M], ne[M], st[N], idx;
void add(int a, int b, LL c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }
void dijkstra(int S) {
for (int i = 1; i <= n; i++) {
dist[i] = 1e15;
st[i] = 0;
}
priority_queue<PLI, vector<PLI>, greater<PLI> > q;
q.push({ dist[S] = 0, S });
while (q.size()) {
pair<LL, int> u = q.top();
q.pop();
int ver = u.second;
LL dis = u.first;
if (st[ver])
continue;
st[ver] = 1;
for (int i = h[ver]; ~i; i = ne[i]) {
int j = e[i];
if (cost[j] <= cost[S]) {
if (dist[j] > dis + (LL)w[i]) {
dist[j] = dis + (LL)w[i];
q.push({ dist[j], j });
}
}
}
}
}
pair<int, int> query[N];
int main() {
memset(h, -1, sizeof h);
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++) scanf("%lld", &cost[i]);
while (m--) {
int a, b;
LL c;
scanf("%d%d%lld", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
for (int i = 1; i <= q; i++) {
scanf("%d%d", &query[i].first, &query[i].second);
res[i] = 2e18;
}
for (int i = 1; i <= n; i++) {
dijkstra(i);
for (int j = 1; j <= q; j++) {
if (dist[query[j].first] != 1e15 && dist[query[j].second] != 1e15)
res[j] = min(res[j], dist[query[j].first] + dist[query[j].second] + cost[i]);
}
}
for (int i = 1; i <= q; i++) printf("%lld\n", res[i] == 2e18 ? -1 : res[i]);
return 0;
}
T7
在双人对弈游戏”四子棋”中,棋盘为4×4大小,双方棋子以x,o表示,x先行.
双方轮流在棋盘中空的位置下一子.
当一方下子后,达成某一行,或某一列,或某一对角线上都是己方的4个棋子,则获胜.
若所有位置下完,无人获胜,则为平局.
华哥经常和女友下棋,他需要根据场合来把控棋局走向.
有时需要获胜以显示自己的智商,有时需要失败以哄女友开心,有时需要平局来拖时间.
现在他正面对一个残局,请判断他是否一定能达成自己的目标.
首先在开始前必须%CQR，实在是TQL，当场把这题过了。
然后我默默看着我约等于不会的博弈论发愁。
当然其实这题正解最主要还是DFS爆搜，博弈论只是用来优化搜索过程的。
#include <bits/stdc++.h>
using namespace std;
char s[10], Map[10][10], c[2];
int state;
int check() {
for (int i = 0; i < 4; i++) {
if (Map[i][0] == 'x' && Map[i][1] == 'x' && Map[i][2] == 'x' && Map[i][3] == 'x')
return (c[0] == 'x');
if (Map[i][0] == 'o' && Map[i][1] == 'o' && Map[i][2] == 'o' && Map[i][3] == 'o')
return (c[0] == 'o');
if (Map[0][i] == 'x' && Map[1][i] == 'x' && Map[2][i] == 'x' && Map[3][i] == 'x')
return (c[0] == 'x');
if (Map[0][i] == 'o' && Map[1][i] == 'o' && Map[2][i] == 'o' && Map[3][i] == 'o')
return (c[0] == 'o');
}
if (Map[0][0] == 'x' && Map[1][1] == 'x' && Map[2][2] == 'x' && Map[3][3] == 'x')
return (c[0] == 'x');
if (Map[0][0] == 'o' && Map[1][1] == 'o' && Map[2][2] == 'o' && Map[3][3] == 'o')
return (c[0] == 'o');
if (Map[3][0] == 'x' && Map[2][1] == 'x' && Map[1][2] == 'x' && Map[0][3] == 'x')
return (c[0] == 'x');
if (Map[3][0] == 'o' && Map[2][1] == 'o' && Map[1][2] == 'o' && Map[0][3] == 'o')
return (c[0] == 'o');
return -1;
}
bool dfs(int u, int now) {
int t = check();
if (!t)
return (bool)(state == 0);
else if (t == 1)
return (bool)(state == 1);
if (u == 16)
return (bool)(state == 2);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (Map[i][j] == '.') {
Map[i][j] = c[now];
t = dfs(u + 1, now ^ 1);
Map[i][j] = '.';
if (now ^ t)
return t;
}
}
}
return now;
}
void work() {
scanf("%s", s);
if (s[0] == 'W')
state = 1;
else if (s[0] == 'L')
state = 0;
else
state = 2;
int cntx = 0, cnto = 0;
for (int i = 0; i < 4; i++) {
scanf("%s", Map[i]);
for (int j = 0; j < 4; j++) {
if (Map[i][j] == 'x')
cntx++;
else if (Map[i][j] == 'o')
cnto++;
}
}
if (cntx == cnto) {
c[0] = 'x';
c[1] = 'o';
} else {
c[0] = 'o';
c[1] = 'x';
}
puts((dfs(cntx + cnto, 0)) ? "YES" : "NO");
}
int main() {
int T;
scanf("%d", &T);
while (T--) work();
return 0;
}