题解
T1 小埋的最大差值
额，就是 钱瑞和 前缀和遍历一下就好了
#include <bits/stdc++.h>
#define int long long
using namespace std;
int t, n, a[1000005], s[1000005];
int check (int k) {
int x = LLONG_MIN, y = LLONG_MAX;
for (int i = k; i <= n; i += k) {
x = max(abs(s[i] - s[i - k]), x);
y = min(abs(s[i] - s[i - k]), y);
}
return x - y;
}
signed main (void) {
cin >> t;
int sum = 0;
while (t--) {
sum = 0;
memset(s, 0, sizeof(s));
cin >> n;
int l = LLONG_MAX, r = LLONG_MIN;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
l = min(l, a[i]);
r = max(r, a[i]);
}
sum = max(sum, r - l);
for (int i = 1; i <= 2 * sqrt(n); i++) {
if (n % i == 0) {
sum = max(sum, check(i));
sum = max(sum, check(n / i));
}
}
cout << sum << endl;
}
return 0;
}用define int long long 蔡老师应该不会说我吧
T2 白令海峡
思路：二分加搜索，二分两座大陆会分隔开来的时间，搜索能否从上面走到下面
自己的代码没写出来
把余帅的部分代码粘上来
void dfs(int xx,int yy){
vis[xx][yy]=1;
for(int i=0;i<4;i++){
int tx=xx+dx[i],ty=yy+dy[i];
if(tx<0||tx>n-1||ty<0||ty>m-1){
continue;
}
if(mp[tx][ty]=='1'||vis[tx][ty]!=0){
continue;
}
dfs(tx,ty);
}
}
int check(int s){
memset(vis,0,sizeof(vis));
for(int i=1;i<=s;i++){
vis[x[i]][y[i]]=2;
}
for(int i=0;i<m;i++){
if(mp[0][i]=='0'&&vis[0][i]==0){
dfs(0,i);
}
}
for(int i=0;i<m;i++){
if(vis[n-1][i]==1){
return 1;
}
}
return 0;
}呜呜呜，写出来了
#include <bits/stdc++.h>
#define int long long
using namespace std;
int t, n, m, q, sx, sy;
char a[505][505], b[505][505];
bool vis[505][505], flag = false;
int x[250005], y[250005], dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
struct node {
int x, y;
};
void dfs(int x, int y) {
if (x == n) {
flag = true;
return;
}
if (flag) return ;
for (int i = 0; i < 4; i++) {
int tx = dx[i] + x, ty = dy[i] + y;
if (tx < 1 || ty < 1 || tx > n || ty > m || vis[tx][ty] || b[tx][ty] == '1') continue;
vis[tx][ty] = true;
dfs(tx, ty);
}
}
bool check(int mid) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
vis[i][j] = false;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
b[i][j] = a[i][j];
}
}
for (int i = 1; i <= mid; i++) b[x[i]][y[i]] = '1';
flag = false;for (int i = 1; i <= m; i++)if (b[1][i] == '0') dfs(1, i);return flag;
}
signed main() {
cin >> t;
while (t--) {
int year,cnt=0,num=0;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
vis[i][j] = false;
}
}
cin >> q;
for (int i = 1; i <= q; i++) cin >> x[i] >> y[i], x[i]++, y[i]++;
if (check(q)) {
cout << -1 << endl;
continue;
}
int l = 0, r = q, mid;
while (l < r) {
mid = l + r >> 1;
check(mid) ? l = mid + 1 : r = mid;
}
cout << r << endl;
}
return 0;
}T3
可以 bfs 预处理出每个点到点 1、s1、s2 的距离，然后枚举每一个点作为分叉点，如果满足条件就更新答案。
#include <bits/stdc++.h>
#define maxn 3005
#define inf 0x3f
using namespace std;
inline int read() {
int x = 0, w = 1;
char ch = getchar();
while (ch > '9' || ch < '0') {
if (ch == '-')w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();
return x * w;
}
struct node {
int nxt, to;
} edge[maxn << 1];
int dis[3][maxn], head[maxn];
int s1, s2, t1, t2, tot, n, m;
queue<int> q;
inline void add(int u, int v) {
edge[++tot].nxt = head[u];
edge[tot].to = v;
head[u] = tot;
}
inline void addedge(int u, int v) {
add(u, v), add(v, u);
}
void bfs(int st, int *dis) {
q.push(st);
dis[st] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (dis[v] > dis[u] + 1)
dis[v] = dis[u] + 1, q.push(v);
}
}
}
int main(void) {
n = read(), m = read();
for (int i = 1; i <= m; i++) {
int u = read(), v = read();
addedge(u, v);
}
memset(dis, inf, sizeof(dis));
s1 = read(), t1 = read(), s2 = read(), t2 = read();
bfs(1, dis[0]), bfs(s1, dis[1]), bfs(s2, dis[2]);
int ans = inf;
for (int i = 1; i <= n; i++)
if (dis[0][i] + dis[1][i] <= t1 && dis[0][i] + dis[2][i] <= t2)
ans = min(ans, dis[0][i] + dis[1][i] + dis[2][i]);
if (ans == inf) puts("-1");
else printf("%d\n", m - ans);
return 0;
}