花了三天断断续续地补完了QAQ
Combo
Statement
有一个只由$A,B,X,Y$构成的母串$S$，保证首字母在整个母串里只会出现一次
现在你需要交互不超过$n+2$次，每次可以询问一个字符串（长度不超过$4N$），交互端会返回在你询问的串中出现的母串的最长前缀。
$N\leq 1000$
Solution
考虑首字母可以花$2$次来确定：询问$AB$然后在询问$A$或者$X$。
那么现在假设首字母是$A$，怎么才能一次性确定某位的字母呢？
不难想到，利用返回值来判断字母，我们可以考虑用$S+B+S+XY+S+XX+S+XB$来询问
那么如果返回值是$|S|$，答案显然是$Y$，如果是$|S|+1$则是$B$，若是$|S|+2$则是$X$
注意最后一个字母要用和第一个字母一样的方法去判断。
这样总共会询问$N-2+4=N+2$次，最大长度为$4(N-2)+7=4N-1$，可以通过所有测试数据。
Code
#include <bits/stdc++.h>
#include "combo.h"
using namespace std;
#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;
string convert(int x)
{
if(x == 1) return "A";
else if(x == 2) return "B";
else if(x == 3) return "X";
else return "Y";
}
int candi[4];
string guess_sequence(int n)
{
int first;
string ret = "";
if(press("AB"))
{
if(press("A")) first = 1, ret = "A";
else first = 2, ret = "B";
}
else
{
if(press("X")) first = 3, ret = "X";
else first = 4, ret = "Y";
}
srand(time(NULL));
fo(i,1,4) if(i != first) candi[i] = i;
fo(i,2,n-1)
{
random_shuffle(candi+1,candi+3+1);
fo(a,1,3)
{
fo(b,1,3) if(a != b)
{
string tmp = ret + convert(candi[a]);
fo(c,1,3)
tmp = tmp + ret + convert(candi[b]) + convert(candi[c]);
int answer = press(tmp);
if(answer == i + 1) ret = ret + convert(candi[b]);
else if(answer == i) ret = ret + convert(candi[a]);
else fo(k,1,3) if(k != a && k != b) {ret = ret + convert(candi[k]); break;}
goto loop;
}
}
loop:;
}
if(n != 1)
{
random_shuffle(candi+1,candi+3+1);
string tmp = ret + convert(candi[1]) + ret + convert(candi[2]);
if(press(tmp) == n)
{
tmp = ret + convert(candi[1]);
if(press(tmp) == n) {ret = tmp; goto gg;}
ret = ret + convert(candi[2]); goto gg;
}
ret = ret + convert(candi[3]);
gg:;
}
return ret;
}Seats
Statement
给一个$N\times M$的矩阵，矩阵元素为$0...N\times M-1$的一个排列，现在需要支持交换矩阵中某两个元素，计算有多少个$good$子矩阵
$good$子矩阵定义为由$0...A\times B-1$构成的$A\times B$的子矩阵。
$N\times M\leq 10^{6}$
Solution
考虑$N=1$的情况
不难注意到，子矩阵放在整个矩阵中看起来像$-----+++++-----$一样 ($+$为$0...t-1$，我们正在考虑大小为$t$的子矩阵是否合法）
那么用线段树去维护是否正好有两个分界点即可。
同理，考虑编号$0...t-1$的格子染成黑色，其他格子染白色。
那么如果用$2\times 2$的小矩阵去覆盖整个矩阵的话，不难发现黑色格子形成一个矩形的充要条件：
1.恰好有$4$个小矩阵中包含正好$1$个黑格子【矩形的四角】 2.不存在有小矩形包含$3$个黑格子【保证是封闭且凸】
于是考虑用线段树去维护，维护最小值和最小值个数即可。
时间复杂度$O(HW\log HW)$
Code
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;
const int maxn = 1000050;
const int dx[] = {0,0,1,1};
const int dy[] = {1,0,0,1};
struct node{int l, r, cnt; pii v, tag;}t[maxn<<2];
int one[maxn], tri[maxn];
int h, w, r[maxn], c[maxn];
vector<vector<int> > A;
VI sur;
void build(int l, int r, int k)
{
t[k].l = l; t[k].r = r;
if(l == r)
{
t[k].v.fi = one[l];
t[k].v.se = tri[l];
t[k].tag = mp(0, 0);
t[k].cnt = 1;
return;
}
int mid = l + r >> 1;
build(l, mid, k<<1);
build(mid+1, r, k<<1|1);
t[k].v = min(t[k<<1].v, t[k<<1|1].v); t[k].cnt = 0;
if(t[k<<1].v == t[k].v) t[k].cnt += t[k<<1].cnt;
if(t[k<<1|1].v == t[k].v) t[k].cnt += t[k<<1|1].cnt;
}
void pd(int k)
{
t[k<<1].tag.fi += t[k].tag.fi;
t[k<<1].tag.se += t[k].tag.se;
t[k<<1].v.fi += t[k].tag.fi;
t[k<<1].v.se += t[k].tag.se;
t[k<<1|1].tag.fi += t[k].tag.fi;
t[k<<1|1].tag.se += t[k].tag.se;
t[k<<1|1].v.fi += t[k].tag.fi;
t[k<<1|1].v.se += t[k].tag.se;
t[k].tag = mp(0, 0);
}
void modify(int l, int r, pii x, int k)
{
if(l > r) return;
if(l <= t[k].l && t[k].r <= r)
{
t[k].v.fi += x.fi;
t[k].v.se += x.se;
t[k].tag.fi += x.fi;
t[k].tag.se += x.se;
return;
}
pd(k);
int mid = t[k].l + t[k].r >> 1;
if(r <= mid) modify(l, r, x, k<<1);
else if(l > mid) modify(l, r, x, k<<1|1);
else modify(l, mid, x, k<<1), modify(mid+1, r, x, k<<1|1);
t[k].v = min(t[k<<1].v, t[k<<1|1].v); t[k].cnt = 0;
if(t[k<<1].v == t[k].v) t[k].cnt += t[k<<1].cnt;
if(t[k<<1|1].v == t[k].v) t[k].cnt += t[k<<1|1].cnt;
}
void getx(int x, int y)
{
sur.clear();
fo(k,0,3) sur.pb(A[x+dx[k]][y+dy[k]]);
sort(sur.begin(), sur.end());
}
void update(int x, int y, int w)
{
getx(x, y);
modify(sur[0], sur[1]-1, mp(w, 0), 1);
modify(sur[2], sur[3]-1, mp(0, w), 1);
}
void upd(int x, int y, int val)
{
update(x, y-1, -1);
update(x-1, y, -1);
update(x, y, -1);
update(x-1, y-1, -1);
A[x][y] = val;
update(x, y-1, 1);
update(x-1, y, 1);
update(x, y, 1);
update(x-1, y-1, 1);
}
int ask()
{
return (t[1].v.fi == 4 && t[1].v.se == 0) ? t[1].cnt : 0;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
int n = R.size();
h = H; w = W;
fo(i,0,H+1)
{
vector<int> cur;
fo(j,0,W+1) cur.pb(H*W+1);
A.pb(cur);
cur.clear();
}
fo(i,0,n-1)
{
r[i+1] = R[i] + 1;
c[i+1] = C[i] + 1;
A[r[i+1]][c[i+1]] = i+1;
}
fo(i,0,H) fo(j,0,W)
{
getx(i, j);
++ one[sur[0]]; -- one[sur[1]];
++ tri[sur[2]]; -- tri[sur[3]];
}
fo(i,1,H*W) one[i] += one[i-1], tri[i] += tri[i-1];
build(1, H*W, 1);
}
int swap_seats(int a, int b)
{
++ a; ++ b;
int x = A[r[a]][c[a]], x2 = A[r[b]][c[b]];
swap(r[a], r[b]);
swap(c[a], c[b]);
upd(r[a], c[a], x);
upd(r[b], c[b], x2);
return ask();
}Werewolf
Statement
给定一张$N$个点，$M$条边的无向连通图，有$Q$个询问。
你从$S$出发，到达$E$，你初始是人形态，要求到达$E$的时候是狼人形态。
人形态的时候不能经过城市$0...L-1$， 狼人形态的时候不能经过城市$R+1..N-1$，你只能从人变到狼人。
问是否存在一种路径能让你到达$E$
$N,M,Q\leq 2\times 10^{5}$
Solution
不难发现题目等价于询问从$S$出发只走$\geq L$的点的路径，和从$E$出发只走$\leq R$的点的路径，是否会有交集。
考虑如果点都很连续，那么这道题就很好做
所以我们不如类似$kruskal$那样：
1.倒序加入新点$x$
2.枚举$>x$的邻接点$y$
3.找到$y$所在的连通块的根，把它的父亲设置为$x$
那么这样的话，我们发现在这棵树上，某个点的子树一定是这个点只经过不超过该点权值，所能到达的点。
同理，构造第二棵，要求是不小于而并非不超过。
这样的话我们只需要利用树上倍增（我个人更倾向于说是二分），就可以把所有可以要求的点锁定在一个子树里
问题等价于询问两个树的子树是否有交集。
以在两棵树的dfs序为坐标，那么问题就变为了一个二维数点，用主席树或者扫描线加线段树就可以了。
时间复杂度$O(Q\log N+M\log M)$。
Code
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;
const int maxn = 200050;
int fa[maxn];
struct KruskalT
{
VI adj[maxn];
int tot, anc[maxn][20], in[maxn], out[maxn];
void link(int u, int v)
{
adj[u].emplace_back(v);
anc[v][0] = u;
}
void init(int N)
{
fo(j,1,19)
for(int i = 0; i < N; ++ i)
if(anc[i][j-1] != -1)
anc[i][j] = anc[anc[i][j-1]][j-1];
}
int getsub(int u, int x, int oper) // oper = 0 => >= L[i], 1-> <=R[i]
{
if(oper == 0)
{
fd(i,19,0)
if(anc[u][i] != -1 && anc[u][i] >= x)
u = anc[u][i];
if(u >= x) return u;
else return -1;
}
else
{
fd(i,19,0)
if(anc[u][i] != -1 && anc[u][i] <= x)
u = anc[u][i];
if(u <= x) return u;
else return -1;
}
}
void dfs(int u)
{
in[u] = ++ tot;
for(auto p : adj[u]) dfs(p);
out[u] = tot;
}
}Tu, Tv, T;
int ls[maxn*20], rs[maxn*20], nd[maxn*20], tot;
int rt[maxn], bag[maxn];
int getfa(int x){return fa[x] == x ? x : fa[x] = getfa(fa[x]);}
void add(int &now, int pre, int p, int l, int r)
{
now = ++ tot;
nd[now] = nd[pre] + 1; ls[now] = ls[pre]; rs[now] = rs[pre];
if(l == r) return;
int mid = l + r >> 1;
if(p <= mid) add(ls[now], ls[pre], p, l, mid);
else add(rs[now], rs[pre], p, mid+1, r);
}
int ask(int now, int pre, int l, int r, int L, int R)
{
if(!now) return 0;
if(l <= L && R <= r) return nd[now] - nd[pre];
int mid = L + R >> 1;
if(r <= mid) return ask(ls[now], ls[pre], l, r, L, mid);
else if(l > mid) return ask(rs[now], rs[pre], l, r, mid+1, R);
else return ask(ls[now], ls[pre], l, mid, L, mid) +
ask(rs[now], rs[pre], mid+1, r, mid+1, R);
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int Q = S.size(), M = X.size();
std::vector<int> A(Q);
// construct two trees
for(int i = 0; i < N; ++ i) fa[i] = i;
memset(Tu.anc,0xff,sizeof(Tu.anc));
memset(Tv.anc,0xff,sizeof(Tv.anc));
for(int i = 0; i < M; ++ i) T.link(X[i], Y[i]), T.link(Y[i], X[i]);
for(int i = N-1; i >= 0; -- i)
{
for(auto p : T.adj[i]) if(p > i)
{
int fx = getfa(p);
if(fx != i) {fa[fx] = i; Tu.link(i, fx); D("%d %d\n",i,fx);}
}
}
D("~~~~~~~~~~\n");
for(int i = 0; i < N; ++ i) fa[i] = i;
for(int i = 0; i < N; ++ i)
{
for(auto p : T.adj[i]) if(p < i)
{
int fx = getfa(p);
if(fx != i) {fa[fx] = i; Tv.link(i, fx); D("%d %d\n",i,fx);}
}
}
D("~~~~~~~~~\n");
//build up binary lifting stuffs
Tu.init(N); Tv.init(N);
Tu.dfs(0); Tv.dfs(N-1);
//insert points into persistent rangetree
for(int i = 0; i < N; ++ i)
bag[Tu.in[i]] = Tv.in[i];
for(int i = 1; i <= Tu.tot; ++ i)
{
add(rt[i], rt[i-1], bag[i], 1, Tv.tot);
D("%d\n",ask(rt[i],rt[i-1],bag[i],bag[i],1,Tv.tot));
}
//now query
for(int i = 0; i < Q; ++ i)
{
int x = Tu.getsub(S[i], L[i], 0), y = Tv.getsub(E[i], R[i], 1);
if(x == -1 || y == -1) {A[i] = 0; continue;}
D("%d %d %d\n",i,x,y);
D("[%d,%d] [%d,%d]\n",Tu.in[x],Tu.out[x],Tv.in[y],Tv.out[y]);
A[i] = ask(rt[Tu.out[x]], rt[Tu.in[x]-1], Tv.in[y], Tv.out[y], 1, Tv.tot);
A[i] = (A[i] > 0);
}
return A;
}
鄂公网安备 42010202000505 号