传送门
C:
题意: 已知该人的旅游路线，编号的规则为 Ai, j = y(i - 1) + j，让你求是否存在某个矩阵的满足路线，不懂的可以看下样例1
思路: 对于相邻的两个数之间的间隔一定是1 或者 y, 所以我们只需要管y不用管x, 那么我们直接check所有的间隔是不是y就是了, 注意一个坑点就是如果y == 3, 那么3 4 是不符合题意的， 即我们算出y后还要for一遍check出这种情况….
AC Code
const int maxn = 2e5+5;
int a[maxn];
void solve()
{
int n;
while(cin >> n) {
int flag = 1, y = 1;
for (int i = 1 ; i <= n ; i ++) {
cin >> a[i];
if (i == 1) continue;
if (a[i] == a[i-1]) flag = 0;
if (abs(a[i] - a[i-1]) != 1) y = abs(a[i] - a[i-1]);
}
if (!flag) {
cout << "NO" << endl;
continue;
}
for (int i = 2 ; i <= n ; i ++) {
if (abs(a[i] - a[i-1]) != 1 && abs(a[i] - a[i-1]) != y) {
flag = 0;
break;
}
if (a[i] - a[i-1] == 1 && a[i] % y == 1) {
flag = 0;
break;
}
if (a[i] - a[i-1] == -1 && a[i] % y == 0 && y != 1) {
flag = 0;
break;
}
}
if (!flag) cout << "NO" << endl;
else {
cout << "YES" << endl;
cout << 1000000000 << ' ' << y << endl;
}
}
}D:
题意: 给定一幅(n, m)图, 边长都是1，给定s, t问对多能加多少条边使得s 和 t之间的距离不会变短?
思路：n只有1000, 所以一个n^2的算法自然就想到了，对于s, t分别进行一次bfs求出到其他点的最短距离, 然后n^2枚举任意两点之间, 是否可以加边, i,j 能加的条件是 d[s][i] + d[t][j] + 1 >= d[s][t], 注意就是因为枚举的顺序原因, 所以s, t与这两个点之间的最短距离要取min, 具体请看代码实现.
AC Code
const int maxn = 1e3+5;
int n, m;
int d[2][maxn], mapp[maxn][maxn];
bool vis[maxn];
vector<int>g[maxn];
void bfs(int st, int f) {
queue<pii>q; Fill(vis, 0);
q.push({st, 0}); vis[st] = 1;
while(!q.empty()) {
pii u = q.front();
q.pop();
for (int i = 0 ; i < sz(g[u.fi]) ; ++ i) {
int to = g[u.fi][i];
if (vis[to]) continue;
vis[to] = 1;
d[f][to] = u.se + 1;
q.push({to, u.se+1});
}
}
}
void solve()
{
int s, t;
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1 ; i <= m ; i ++) {
int u, v;
scanf("%d%d", &u, &v);
mapp[u][v] = mapp[v][u] = 1;
g[u].pb(v);
g[v].pb(u);
}
bfs(s, 0); bfs(t, 1); int ans = 0;
for (int i = 1 ; i <= n ; ++ i) {
for (int j = 1 ; j <= n ; ++ j) {
if (i == j || mapp[i][j]) continue;
if (min(d[0][j] + d[1][i], d[0][i] + d[1][j]) + 1 >= d[0][t]) {
++ ans;
}
}
}
printf("%d\n", ans/2);
}G:
题意：有n组墙, 墙上有弓箭手, 给出他们能射击到的范围， 然后有预备的k个弓箭手， 问这n组墙的最小防御值是多少, 防御值定义为墙上的弓箭手数量， 所有n组墙上的弓箭手取min就是这n组墙的最小防御值.
思路：当然就是二分答案啊, 那么难点就在于如何check, 出一个样例就知道主要解决的问题了,
3 1 1000
0 0 0
这个答案是1000，把1000个弓箭手全部放在第二个墙上, 所以通过这个例子我们可以发现, 我们要把添加的弓箭手尽量的放在边界的最右边, 所以我们要维护一个区间r的和，然后每次算我们二分的答案与当前墙上的弓箭手的数量关系， 然后判断需要到达二分的答案所需要的额外弓箭手, 然后判断下与k的关系就是了, 注意一个肯定就是这个数可能会很大, 会爆long long ，就会变负数，就会影响判断. 因为k最大1e18， 那么当额外的弓箭手数量超过了1e18时就和1e18+5取min即可, 表示不可能. 具体细节请看代码.
AC Code
const int maxn = 5e5+5;
ll a[maxn], tmp[maxn];
ll n, len, k;
ll ok(ll u) {
memcpy(tmp, a, sizeof(a));
ll now = 0, s = 0;
for (int i = 1 ; i <= len ; i ++) now += a[i];
for (int i = 1 ; i <= n ; i ++) {
now += i+len>n?0:tmp[i+len];
now -= i-len-1<0?0:tmp[i-len-1];
if (now < u) {
tmp[min(n, i+len)] += u - now;
s = min(s + u - now, INF+5);
now = u;
}
}
return s;
}
void solve()
{
while(~scanf("%lld%lld%lld", &n, &len, &k)) {
for (int i = 1 ; i <= n ; i ++) {
scanf("%lld", &a[i]);
}
ll l = 0, r = (1ll<<60), mid, ans = 0;
while(l <= r) {
mid = (l + r) >> 1;
if (ok(mid) <= k) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
printf("%lld\n", ans);
}
}