好久没刷51nod了，又听说topcoder有很多好题。那么就来51nod上刷吧。（那个客户端搞得有点烦（看不懂））
当图不连通的时候，答案为无穷大。
当图连通时，两个点之间的最大差值就是最短路长度乘上 $d$，跑floyd再看最短路的最大值即可。
#include <bits/stdc++.h> const int N = ;
const int INF = 0x3f3f3f3f; char s[N];
int mp[N][N], fa[N], n; int getfa(int x) {
return x == fa[x] ? x : fa[x] = getfa(fa[x]);
} void unit(int x, int y) {
x = getfa(x), y = getfa(y);
fa[x] = y;
} void floyd() {
for (int k = ; k <= n; k++)
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
mp[i][j] = std::min(mp[i][j], mp[i][k] + mp[k][j]);
} int main() {
int T;
scanf("%d", &T);
while (T--) {
int d;
scanf("%d%d", &n, &d);
for (int i = ; i <= n; i++) fa[i] = i;
for (int i = ; i <= n; i++) {
scanf("%s", s + );
for (int j = ; j <= n; j++) {
if (s[j] == 'Y' && i != j)
mp[i][j] = d, unit(i, j);
else if (i != j)
mp[i][j] = INF;
else
mp[i][j] = ;
}
}
int cnt = ;
for (int i = ; i <= n; i++)
if (getfa(i) == i) cnt++;
if (cnt > ) {
puts("-1");
continue;
}
floyd();
int ans = ;
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
if (mp[i][j] < INF)
ans = std::max(ans, mp[i][j]);
printf("%d\n", ans);
}
return ;
}
可以发现当限制比数字的位置还大时，这个限制就没用了。
然后有时候到不了极限数据，因为被前面的卡住了或者被后面的卡住了。
即 $t_i – t_{i – 1} > x_i – x_{i – 1}$，$t_i – t_{i + 1} > x_{i + 1} – x_i$ 这两种情况。暴力更新即可。
然后最大值就在每两个限制之间得到。
#include <bits/stdc++.h>const int N = ;int x[N], t[N];int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
int cnt = ;
x[cnt] = , t[cnt] = ;
for (int i = ; i <= m; i++) {
int a, b;
scanf("%d%d", &a, &b);
if (b < a - )
x[++cnt] = a, t[cnt] = b;
}
if (!cnt) {
printf("%d\n", n - );
continue;
}
for (int i = ; i <= cnt; i++) {
if (i > && t[i] - t[i - ] > x[i] - x[i - ])
t[i] = t[i - ] + x[i] - x[i - ];
if (i < cnt && t[i] - t[i + ] > x[i + ] - x[i]) {
t[i] = t[i + ] + x[i + ] - x[i];
i = ;
}
}
int ans = ;
for (int i = ; i < cnt; i++)
ans = std::max(ans, (t[i] + t[i + ] - x[i] + x[i + ]) / );
ans = std::max(ans, t[cnt] + n - x[cnt]);
printf("%d\n", ans);
}
}
一种球的贡献最多为 $2$，那么统计球的个数即可。
#include <bits/stdc++.h>const int N = ;
char s[N];
int cnt[];inline int getid(char ch) {
if (ch == 'R') return ;
if (ch == 'G') return ;
return ;
} int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%s", s + );
int n = strlen(s + );
if (n == ) {
puts("");
continue;
}
if (n == ) {
puts("");
continue;
}
for (int i = ; i < ; i++)
cnt[i] = ;
for (int i = ; i <= ; i++)
cnt[getid(s[i])]++;
int ans = ;
for (int i = ; i <= n; i++) {
for (int j = ; j < ; j++)
ans += std::min(cnt[j], );
cnt[getid(s[i])]++;
}
printf("%d\n", ans);
}
return ;
}
和一个点会有交集的点最多只有 $k^2$ 个，特判这些点，再去其他点中最大的那个即可。
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se secondconst int N = ;
const int M = 1e4 + ;
int dx[], dy[];
char s[N];
int mp[N][N];
std::vector<int> belong[M];
std::pii p[M];
std::map<std::pii, int> gong;int main() {
freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
while (T--) {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = ; i <= n; i++) {
scanf("%s", s + );
for (int j = ; j <= m; j++)
mp[i][j] = s[j] - '';
}
for (int i = ; i <= k; i++)
scanf("%d%d", &dx[i], &dy[i]);
for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++) {
int pos = (i - ) * m + j;
p[pos].se = pos;
p[pos].fi = ;
for (int z = ; z <= k; z++) {
int x = i + dx[z], y = j + dy[z];
if (x <= || x > n || y <= || y > m) continue;
belong[(x - ) * m + y].push_back(pos);
p[pos].fi += mp[x][y];
}
}
int ans = ;
std::sort(p + , p + n * m + , std::greater<std::pii>());
for (int cnt = ; cnt <= n * m; cnt++) {
gong.clear();
int pos = p[cnt].se;
int i = pos / m, j = pos % m;
if (!j) j = m;
else i++;
if (p[cnt].fi + p[].fi <= ans) continue;
for (int z = ; z <= k; z++) {
int x = i + dx[z], y = j + dy[z];
if (x <= || x > n || y <= || y > m) continue;
int ne = (x - ) * m + y;
for (int tong: belong[ne]) {
if (pos == tong) continue;
gong[std::pii(std::min(pos, tong), std::max(pos, tong))] -= mp[x][y];
}
}
for (int z = ; z <= k * k + ; z++) {
if (z == cnt) continue;
int id = p[z].se;
ans = std::max(ans, gong[std::pii(std::min(pos, id), std::max(pos, id))] + p[cnt].fi + p[z].fi);
if (!gong.count(std::pii(std::min(pos, id), std::max(pos, id)))) break;
}
}
for (int i = ; i <= n * m; i++)
belong[i].clear(), p[i].fi = p[i].se = ;
printf("%d\n", ans);
}
return ;
}
唉，这都想不出来，好菜啊…
$i$ 到 $j$ 的代价就等于第 $i$ 行 $0$ 到 $j – 1$ 有多少个 ‘Y’。要优先走这条边就要付出这么多代价，然后floyd就好了
#include <bits/stdc++.h>const int N = ;
const int INF = 0x3f3f3f3f;
int mp[N][N];
char s[N];int main() {
int T;
scanf("%d", &T);
while (T--) {
memset(mp, 0x3f, sizeof mp);
int n;
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%s", s + );
int cost = ;
for (int j = ; j <= n; j++)
if (s[j] == 'Y')
mp[i][j] = cost++;
}
for (int i = ; i <= n; i++)
mp[i][i] = ;
for (int k = ; k <= n; k++)
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
mp[i][j] = std::min(mp[i][j], mp[i][k] + mp[k][j]);
printf("%d\n", mp[][n] == INF ? - : mp[][n]);
}
return ;
}
当取的 $low$ 值之和不小于 $x$ 时，为一个方案
当不取的 $high$ 值之和不大于 $c – x$ 时，为一个方案
这两种情况可以独立来算，对 $low$ 和 $high$ 分别排个序就ok了。
#include <bits/stdc++.h>const int N = ;int low[N], high[N];int main() {
//freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
while (T--) {
int n, c, x;
scanf("%d%d%d", &n, &c, &x);
for (int i = ; i <= n; i++)
scanf("%d%d", low + i, high + i);
int ans = n;
std::sort(low + , low + + n);
std::sort(high + , high + + n);
for (int i = n, sum = ; i; i--) {
sum += low[i];
if (sum >= x) {
ans = std::min(n - i + , ans);
break;
}
}
for (int i = , sum = ; i <= n; i++) {
sum += high[i];
if (c - sum < x) {
ans = std::min(ans, n - i + );
break;
}
}
printf("%d\n", ans);
}
return ;
}/***
34
32
28
***/
当不出现问号时，该开时开，该关时关就OK了。
当出现了问号时，如果上一轮的该位置状态为 ‘-‘ 且这一轮有开灯的操作，那么这一位就可以是 ‘?’，或者该位置状态为 ‘+’ 且这一轮有关灯的操作，同理也是 ‘?’
多一个 ‘?’ 就可以让之后尽量少操作。
#include <bits/stdc++.h>const int N = ;
char mp[N][N], s[N];int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++)
scanf("%s", mp[i] + );
for (int i = ; i <= m; i++)
s[i] = '-';
int ans = ;
for (int i = ; i <= n; i++) {
bool open = , close = ;
for (int j = ; j <= m; j++) {
if (s[j] == '-' && mp[i][j] == '+')
open = ;
if (s[j] == '+' && mp[i][j] == '-')
close = ;
}
if (open) ans++;
if (close) ans++;
ans++;
for (int j = ; j <= m; j++) {
if (mp[i][j] == '?') {
if (close && s[j] == '+')
s[j] = '?';
if (open && s[j] == '-')
s[j] = '?';
} else {
s[j] = mp[i][j];
}
}
}
printf("%d\n", ans);
}
return ;
}
答案最多为 3，为 3 时即存在奇环，bfs判一下即可。
#include <bits/stdc++.h>const int N = ;
const int dir[][] = {{-, }, {-, }, {, }, {, }, {, -}, {, -}};
char s[N][N];
int n, dis[N][N];bool bfs(int dx, int dy) {
std::queue< std::pair<int, int> > que;
que.push(std::pair<int, int>(dx, dy));
while (!que.empty()) {
std::pair<int, int> p = que.front(); que.pop();
int i = p.first, j = p.second;
for (int k = ; k < ; k++) {
int x = i + dir[k][], y = j + dir[k][];
if (x < || y < || x > n || y > n || s[x][y] == '-') continue;
if (dis[x][y]) {
if (dis[x][y] % == dis[i][j] % ) return true;
continue;
}
que.push(std::pair<int, int>(x, y));
dis[x][y] = dis[i][j] + ;
}
}
return false;
}int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
int ans = ;
for (int i = ; i <= n; i++) {
scanf("%s", s[i] + );
for (int j = ; j <= n; j++)
if (s[i][j] == 'X') ans = ;
}
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++) if (s[i][j] == 'X') {
for (int k = ; k < ; k++) {
int x = i + dir[k][], y = j + dir[k][];
if (x < || y < || x > n || y > n || s[x][y] == '-') continue;
ans = ;
}
}
memset(dis, , sizeof(dis));
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
if (s[i][j] == 'X' && dis[i][j] == )
if (bfs(i, j)) ans = ;
printf("%d\n", ans);
}
return ;
}
