ZROI 2022NOIP10联测 Round 6 解题报告
100 + 20 + 25 + 0, rk 90.
评价是昨天上的分今天全吐出去了。
虽然但是,思维好场!
A
一个偏难的签到题。
我们考虑,先把这个图建出来,那么我们分类考虑一下:
对于直接走来说,我们只需要判断周围六格有没有空格即可,实现较为容易。
对于跳来说,我们考虑先根据每个有棋子的店把边建出来,那么我们每次需要查询的就是周围可达的联通块大小总和。这部分可以用并查集实现。并且注意去重,即我们不能访问到任意一个已经访问过的联通块。所以代码实现的时候注意一下细节即可。
时间复杂度理论上是
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cassert>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
#define ll long long
#define int long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair
char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
int v = getchar();T f = 1;t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
read(t);read(args...);
}
const ll mod = 998244353;
const double eps = 1e-10;
const int N = 1e6 + 10;
vector <int> G[N],G2[N];
vector <pii> poi;
map <pii,int> pos;
int n,vis[N],tot,ans[N][10],chk[N],siz[N];
pii rev[N];
void addedge(int x,int y) {
if (!pos.count(mp(x,y))) pos[mp(x,y)] = ++tot,rev[tot] = mp(x,y);
if (!pos.count(mp(x-1,y-1))) pos[mp(x-1,y-1)] = ++tot,rev[tot] = mp(x-1,y-1);
if (!pos.count(mp(x-1,y))) pos[mp(x-1,y)] = ++tot,rev[tot] = mp(x-1,y);
if (!pos.count(mp(x,y-1))) pos[mp(x,y-1)] = ++tot,rev[tot] = mp(x,y-1);
if (!pos.count(mp(x+1,y+1))) pos[mp(x+1,y+1)] = ++tot,rev[tot] = mp(x+1,y+1);
if (!pos.count(mp(x+1,y))) pos[mp(x+1,y)] = ++tot,rev[tot] = mp(x+1,y);
if (!pos.count(mp(x,y+1))) pos[mp(x,y+1)] = ++tot,rev[tot] = mp(x,y+1);
G[pos[mp(x-1,y-1)]].push_back(pos[mp(x+1,y+1)]);
G[pos[mp(x+1,y+1)]].push_back(pos[mp(x-1,y-1)]);
G[pos[mp(x,y-1)]].push_back(pos[mp(x,y+1)]);
G[pos[mp(x,y+1)]].push_back(pos[mp(x,y-1)]);
G[pos[mp(x+1,y)]].push_back(pos[mp(x-1,y)]);
G[pos[mp(x-1,y)]].push_back(pos[mp(x+1,y)]);
}
int check(pii p) {
int tmp =0;
int x = p.first,y = p.second;
if (!chk[pos[mp(x-1,y-1)]]) ++tmp;
if (!chk[pos[mp(x-1,y)]]) ++tmp;
if (!chk[pos[mp(x,y-1)]]) ++tmp;
if (!chk[pos[mp(x+1,y+1)]]) ++tmp;
if (!chk[pos[mp(x+1,y)]]) ++tmp;
if (!chk[pos[mp(x,y+1)]]) ++tmp;
return tmp;
}
int f[N];
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
void merge(int x,int y) {
int fx = find(x),fy = find(y);
if (fx == fy) return ;
if (siz[fy] > siz[fx]) swap(fx,fy);
f[fy] = fx;siz[fx] += siz[fy];
}
signed main() {
//FO(ex_checkers2)
read(n);
for (int i = 1;i <= n;++i) {
int x,y;read(x,y);
addedge(x,y);
poi.push_back(mp(x,y));chk[pos[mp(x,y)]] = 1;
}
for (int i = 1;i <= tot;++i) f[i] = i,siz[i] = 1;
for (int i = 1;i <= tot;++i) {
if (!chk[i]) {
for (auto y : G[i]) {
if (!chk[y])merge(y,i);
}
}
}
//for (int i = 1;i <= tot;++i) printf("%d %d\n",siz[i],find(i));
//printf("%d\n",pos.size());
for (auto x : poi) {
int num = pos[x],tmp = 0;
vector <int> used;
tmp += check(x);
for (auto y : G[num]) {
if (!chk[y]) {
int nxt = find(y);
if (vis[nxt]) continue;
vis[nxt] = 1;used.push_back(nxt);
tmp += siz[nxt];
}
}
printf("%d\n",tmp);
for (auto x : used) vis[x] = 0;
}
return 0;
}
B
字符串嘿嘿我的字符串嘿嘿
首先我们先观察一下这个题的本质,发现直接处理
考虑构造一个
接下来我们考虑对于形如答案串的两个字符串,如何比较他们的的字典序大小?这实际上是一个可以用 二分 + Hash 在单次
- 如果
len_{lcp} < \min\{len_1,len_2\} 那么我们可以直接比较b_{len_{lcp} + 1} 这一位来判断。 - 如果
len_{lcp} = \min\{len_1,len_2\} 那么我们需要接着比较剩下在a 中的那段,这个实现相对复杂。
可以参考代码:
int hsh1(int l, int r) {
return (h1[r] + (M1 - h1[l - 1]) * 1ll * pw1[r - l + 1]) % M1;
}
int hsh2(int l, int r) {
return (h2[r] + (M2 - h2[l - 1]) * 1ll * pw2[r - l + 1]) % M2;
}
int lcp(int x, int y) {
int l = 0, r = min(n * 2 - x + 1, n * 2 - y + 1), md;
for (; l < r;) {
md = (l + r >> 1) + 1;
if (hsh1(x, x + md - 1) == hsh1(y, y + md - 1) && hsh2(x, x + md - 1) == hsh2(y, y + md - 1))
l = md;
else
r = md - 1;
}
return l;
}
bool cmp(int bg, int x, int y) {
int l = lcp(n * 2 - x + 1, n * 2 - y + 1);
if (y - l >= bg)
return s[x - l] > s[y - l];
x -= y - bg + 1;
l = lcp(n * 2 - x + 1, y + 1);
return l <= x - bg && 5 - s[x - l] < s[y + l + 1];
}
如此,我们对于每个左端点做一遍,时间复杂度达到了
接下来则是最重要的观察:左端点一定是翻转后能变小的第一个字符。
这实际是一个基于贪心的考虑,我们考虑如果最开始的那个字符可以变小,那么我们如果更改接下来的字符实际上在字典序方面是不会更优的。
如果翻转后都不能变小,那么就翻转最后一个。如果翻转后左端点相等,那么把区间左右往里各缩一步,是没有区别的。 翻转后能变小,要么是本身就是 G 或 T, 要么本身是 C 并且后面有 T.
这样我们就把我们需要考虑的点缩小到了仅剩一个,那么时间复杂度就变成了
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define mp make_pair
#define fi first
#define se second
const int N = 1e5 + 5, mod = 1e9 + 7;
const pi base = mp(131, 13331);
int add(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }
pi operator + (pi x, pi y) { return mp(add(x.fi, y.fi), add(x.se, y.se)); }
pi operator - (pi x, pi y) { return mp(del(x.fi, y.fi), del(x.se, y.se)); }
pi operator * (pi x, pi y) { return mp(1ll * x.fi * y.fi % mod, 1ll * x.se * y.se % mod); }
pi operator * (pi x, int y) { return mp(1ll * x.fi * y % mod, 1ll * x.se * y % mod); }
int n, c[5]; char s[N];
pi h[2][N], w[N];
const char ch[] = {0, 'A', 'C', 'G', 'T'};
int trans(char x) {
if (x == 'A') return 1;
if (x == 'C') return 2;
if (x == 'G') return 3;
return 4;
}
pi H(int ty, int l, int r) { return (h[ty][r] - h[ty][l - 1]) * w[n - r]; }
int cmp(int l1, int r1, int r2) {
if (!r1) return r2;
int l = 1, r = r1 - l1 + 1, L = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (H(1, n - r1 + 1, n - (r1 - mid + 1) + 1) == H(1, n - r2 + 1, n - (r2 - mid + 1) + 1)) l = mid + 1, L = mid;
else r = mid - 1;
}
if (L <= r1 - l1) return s[r1 - L] > s[r2 - L] ? r1 : r2;
l = r + 1, r = r2 - l1 + 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (H(0, r1 + 1, l1 + mid - 1) == H(1, n - (r2 - (r1 - l1 + 1)) + 1, n - (r2 - mid + 1) + 1)) l = mid + 1, L = mid;
else r = mid - 1;
}
if (L <= r2 - l1) return s[l1 + L] < 5 - s[r2 - L] ? r1 : r2;
return r1;
}
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; i++) s[i] = trans(s[i]), c[s[i]]++;
w[0] = mp(1, 1);
for (int i = 1; i <= n; i++) w[i] = w[i - 1] * base;
for (int i = 1; i <= n; i++) h[0][i] = h[0][i - 1] + w[i - 1] * (int)s[i];
for (int i = n; i >= 1; i--) h[1][n - i + 1] = h[1][n - i] + w[n - i] * (int)(5 - s[i]);
for (int i = 1; i <= n; i++) {
int _c = 0;
for (int j = 4; j > 5 - s[i]; j--) if (c[j]) { _c = j; break; }
if (_c) {
int r = 0;
for (int j = i; j <= n; j++) if (s[j] == _c) r = cmp(i, r, j);
for (int j = 1; j < i; j++) putchar(ch[s[j]]);
for (int j = r; j >= i; j--) putchar(ch[5 - s[j]]);
for (int j = r + 1; j <= n; j++) putchar(ch[s[j]]);
return 0;
}
c[s[i]]--;
}
for (int i = 1; i < n; i++) putchar(ch[s[i]]);
putchar(ch[5 - s[n]]);
return 0;
}
D
我们考虑从区间角度解决这个问题。
首先我们考虑对于花费为
接下来我们考虑对于花费为
那么接下来我们的问题就变成了每次查询
时间复杂度
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int n, q, L[N][20], R[N][20]; char s[N];
int stk[N], tp, to[N];
int main() {
scanf("%s", s + 1), n = strlen(s + 1);
for (int i = 1; i <= n; i++) {
if (s[i] == '(') stk[++tp] = i;
else to[i] = stk[tp], to[stk[tp--]] = i;
}
for (int i = 1; i <= n; i++) {
L[i][0] = max(1, min(i - 1, to[i]));
R[i][0] = min(n, max(i + 1, to[i]));
}
for (int j = 1; j <= 19; j++)
for (int i = 1; i <= n; i++) {
L[i][j] = min(L[L[i][j - 1]][j - 1], L[R[i][j - 1]][j - 1]);
R[i][j] = max(R[R[i][j - 1]][j - 1], R[L[i][j - 1]][j - 1]);
}
scanf("%d", &q);
for (int i = 1, x, y; i <= q; i++) {
scanf("%d %d", &x, &y);
if (x > y) swap(x, y);
if (x == y) {
puts("0"); continue;
}
int ans = 1, l = x, r = x;
for (int j = 19; ~j; j--) {
int tl = min(L[l][j], L[r][j]), tr = max(R[l][j], R[r][j]);
if (tr < y) l = tl, r = tr, ans += (1 << j);
}
x = r, l = r = y;
for (int j = 19; ~j; j--) {
int tl = min(L[l][j], L[r][j]), tr = max(R[l][j], R[r][j]);
if (tl > x) l = tl, r = tr, ans += (1 << j);
}
printf("%d\n", ans);
}
return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。