5406 CRB and Apple
1.排序之后费用流
spfa用stack才能过
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 2e3+7;
const int MAXE = 2e6+7;
const int INF = 0x3f3f3f3f;
#define S 0
#define SS MAXN - 2
#define T MAXN - 1
int dist[MAXN],pre[MAXN],preid[MAXN],flow[MAXN],vis[MAXN],n;
int tot,head[MAXN],nxt[MAXE],to[MAXE],fee[MAXE],cap[MAXE];
pair<int,int> pr[MAXN];
void ADDEDGE(int u, int v, int _cap, int _fee){
nxt[tot] = head[u]; to[tot] = v; cap[tot] = _cap; fee[tot] = _fee;
head[u] = tot++;
nxt[tot] = head[v]; to[tot] = u; cap[tot] = 0; fee[tot] = -_fee;
head[v] = tot++;
}
bool spfa(){
memset(dist,0x3f,sizeof(dist));
dist[S] = 0;
flow[S] = INF;
memset(vis,0,sizeof(vis));
stack<int> que;
que.push(S);
while(!que.empty()){
int u = que.top();
que.pop();
vis[u] = 0;
for(int i = head[u]; i; i = nxt[i]){
if(!cap[i] or dist[to[i]]<=dist[u]+fee[i]) continue;
dist[to[i]] = dist[u] + fee[i];
flow[to[i]] = min(cap[i],flow[u]);
pre[to[i]] = u; preid[to[i]] = i;
if(!vis[to[i]]){
vis[to[i]] = 1;
que.push(to[i]);
}
}
}
return dist[T]!=INF;
}
int mcmf(){
int cost = 0;
while(spfa()){
int u = T;
cost += dist[T] * flow[T];
while(u!=S){
int p = pre[u], id = preid[u];
cap[id] -= flow[T];
cap[id^1] += flow[T];
u = pre[u];
}
}
return cost;
}
void solve(){
scanf("%d",&n);
tot = 2;
for(int i = 1; i <= n; i++) scanf("%d %d",&pr[i].first,&pr[i].second);
sort(pr+1,pr+1+n,[](const pair<int,int> &A, const pair<int,int> &B){
return A.first==B.first ? A.second<B.second : A.first>B.first;
});
memset(head,0,sizeof(head));
ADDEDGE(S,SS,2,0);
for(int i = 1; i <= n; i++) ADDEDGE(SS,i,1,0);
for(int i = 1; i <= n; i++) ADDEDGE(i+n,T,1,0);
for(int i = 1; i <= n; i++) ADDEDGE(i,i+n,1,-1);
for(int i = 1; i <= n; i++) for(int j = i + 1; j <= n; j++) if(pr[i].second<=pr[j].second){
ADDEDGE(i+n,j,1,0);
}
printf("%d\n",-mcmf());
}
int main(){
int t;
for(scanf("%d",&t); t; t--) solve();
return 0;
}
2.排序之后问题变成找两个LIS且长度和最大
树状数组优化\(DP\)
\(dp[i][j]\)表示两个LIS最后位置的价值分别为\(i\)和\(j\)的答案最大值
先把所有\(delicious\)离散化
然后按高度排序\(apple\)
枚举每个\(apple\)
假设当前枚举的\(delicious\)为\(v\)
枚举\(i\)
状态转移为\(dp[v][i] = dp[i][v] = max\{d[i][j]\}(j\le v)\)
可以用树状数组来维护区间最大值
复杂度\(O(n^2\log n)\)
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1111;
#define lowbit(x) (x & -x)
int n,f[MAXN][MAXN];
pair<int,int> pr[MAXN];
vector<int> vec;
void update(int *f, int pos, int x){
while(pos<=n){
f[pos] = max(f[pos],x);
pos += lowbit(pos);
}
}
int query(int *f, int pos){
int ret = 0;
while(pos){
ret = max(ret,f[pos]);
pos -= lowbit(pos);
}
return ret;
}
int tmp[MAXN];
void solve(){
scanf("%d",&n);
vec.clear();
for(int i = 1; i <= n; i++) scanf("%d %d",&pr[i].first,&pr[i].second);
for(int i = 1; i <= n; i++) pr[i].first *= -1, vec.push_back(pr[i].second);
sort(pr+1,pr+1+n);
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(int i = 1; i <= n; i++) pr[i].second = lower_bound(vec.begin(),vec.end(),pr[i].second) - vec.begin() + 1;
memset(f,0,sizeof(f));
int ret = 0;
for(int i = 1; i <= n; i++){
int val = pr[i].second;
for(int j = 0; j <= n; j++) tmp[j+1] = query(f[j+1],val+1) + 1;
for(int j = 0; j <= n; j++){
ret = max(ret,tmp[j+1]);
update(f[j+1],val+1,tmp[j+1]);
update(f[val+1],j+1,tmp[j+1]);
}
}
printf("%d\n",ret);
}
int main(){
int T;
for(scanf("%d",&T); T; T--) solve();
return 0;
}
5407 CRB and Candies
显然要求的是\(LCM(C(n,0),C(n,1),C(n,2),\cdots ,C(n,n-1),C(n,n))\)显然\(LCM(C(n,0),C(n,1),C(n,2),\cdots ,C(n,n-1),C(n,n)) = \frac{LCM(1,2,3,\cdots,n-1,n,n+1)}{n+1}\)
接下来就是要计算\(LCM(1,2,3,\cdots,n-1,n,n+1)\)
令\(f(n)=LCM(1,2,3,\cdots,n-1,n)\)
\(f(n) = \begin{cases} f(n-1)*p & n=p^k \\ f(n-1) & otherwise \end{cases}\)
递推计算就好了
复杂度\(O(n\log n)\)
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
typedef long long int LL;
const int MAXN = 1e6+7;
const int MOD = 1e9+7;
LL f[MAXN],inv[MAXN],p[MAXN];
bool npm[MAXN];
vector<LL> prime;
void preprocess(){
for(int i = 2; i < MAXN; i++){
if(!npm[i]) prime.push_back(i);
for(int j = 0; j < (int)prime.size(); j++){
if(i*prime[j]>=MAXN) break;
npm[i*prime[j]] = true;
if(i%prime[j]==0) break;
}
}
fill(begin(p),end(p),1);
inv[1] = 1;
for(int i = 2; i < MAXN; i++) inv[i] = (MOD-MOD/i) * inv[MOD%i] % MOD;
for(LL pm : prime) for(LL x = pm; x < MAXN; x *= pm) p[x] = pm;
f[1] = 1;
for(int i = 2; i < MAXN; i++) f[i] = f[i-1] * p[i] % MOD;
}
int main(){
preprocess();
int T;
for(scanf("%d",&T); T; T--){
int n; scanf("%d",&n);
printf("%I64d\n",f[n+1]*inv[n+1]%MOD);
}
return 0;
}
5408 CRB and Farm
5409 CRB and Graph
tarjan缩点之后变成树上的问题
对于树上的每一条边，要求这条边把树分成的两部分中分别一个点\(u,v\)且\(u<v\)并最大化\(u\)，最小化\(v\)
可以发现如果确定了\(u\)，那么\(v\)必然是\(u+1\)
先把缩点后的每个点标记为连通块内点标号的最大和最小值
然后把标号离散化
接下来对于每条边分割成的两部分，把一部分的点染黑，另一部分染白
接下来就是找最大的黑白交界处的点
这个可以用树上启发式合并配合set维护线段来做
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e5+7;
const int INF = 0x3f3f3f3f;
int n,m,bccid[MAXN],dfn[MAXN],low[MAXN],num,idx,minnode[MAXN],maxnode[MAXN],nn;
int sz[MAXN],son[MAXN],st[MAXN],ed[MAXN],rdfn[MAXN],sonid[MAXN];
pair<int,int> ret[MAXN];
set<pair<int,int> > seg;
vector<int> vec;
struct Graph{
int head[MAXN],to[MAXN<<1],nxt[MAXN<<1],id[MAXN<<1],tot;
void clear(){ memset(head,255,sizeof(head)); tot = 0; }
void ADDEDGE(int u, int v, int eid){
to[tot] = v; nxt[tot] = head[u]; id[tot] = eid;
head[u] = tot++;
}
}GG,G;
void init(){
num = idx = 0;
GG.clear(); G.clear();
memset(dfn,0,sizeof(dfn));
memset(maxnode,0,sizeof(maxnode));
memset(minnode,INF,sizeof(minnode));
memset(ret,0,sizeof(ret));
vec.clear(); seg.clear();
}
stack<int> stk;
void tarjan(int u, int par){
dfn[u] = low[u] = ++idx;
stk.push(u);
for(int i = GG.head[u]; ~i; i = GG.nxt[i]){
int v = GG.to[i];
if(v==par) continue;
if(dfn[v]) low[u] = min(low[u],dfn[v]);
else{
tarjan(v,u);
low[u] = min(low[u],low[v]);
}
}
if(low[u]==dfn[u]){
int tp;
num++;
do{
tp = stk.top();
stk.pop();
bccid[tp] = num;
minnode[num] = min(minnode[num],tp);
maxnode[num] = max(maxnode[num],tp);
}while(tp!=u);
}
}
void rebuild(){
for(int u = 1; u <= n; u++){
for(int i = GG.head[u]; ~i; i = GG.nxt[i]){
int v = GG.to[i];
if(bccid[u]==bccid[v]) continue;
G.ADDEDGE(bccid[u],bccid[v],GG.id[i]);
}
}
}
void dfs(int u, int par){
sz[u] = 1; son[u] = 0;
st[u] = ++idx; rdfn[idx] = u;
for(int i = G.head[u]; ~i; i = G.nxt[i]){
int v = G.to[i];
if(v==par) continue;
dfs(v,u);
sz[u] += sz[v];
if(sz[v]>sz[son[u]]) son[u] = v, sonid[u] = G.id[i];
}
ed[u] = idx;
}
void insert(int x){
if(seg.empty()){
seg.insert(make_pair(x,x));
return;
}
auto p = seg.lower_bound(make_pair(x,x));
if(p==seg.end()){
advance(p,-1);
if(p->second!=x-1) seg.insert(make_pair(x,x));
else{
auto curseg = *p;
seg.erase(p);
curseg.second++;
seg.insert(curseg);
}
}
else if(p==seg.begin()){
if(p->first!=x+1) seg.insert(make_pair(x,x));
else{
auto curseg = *p;
seg.erase(p);
curseg.first--;
seg.insert(curseg);
}
}
else{
pair<int,int> curseg = make_pair(x,x);
if(p->first==x+1) curseg.second = p->second;
advance(p,-1);
if(p->second==x-1) curseg.first = p->first;
if(curseg.second!=x) seg.erase(make_pair(x+1,curseg.second));
if(curseg.first!=x) seg.erase(make_pair(curseg.first,x-1));
seg.insert(curseg);
}
}
void erase(int x){
auto p = seg.lower_bound(make_pair(x,x));
if(p!=seg.end() and p->first==x){
if(p->second==x) seg.erase(p);
else{
auto curseg = *p;
seg.erase(p);
curseg.first++;
seg.insert(curseg);
}
}
else{
advance(p,-1);
if(p->second==x){
auto curseg = *p;
seg.erase(p);
curseg.second--;
seg.insert(curseg);
}
else{
auto curseg = *p;
seg.insert(make_pair(curseg.first,x-1));
seg.insert(make_pair(x+1,curseg.second));
seg.erase(curseg);
}
}
}
pair<int,int> query(){
auto curseg = *seg.rbegin();
int ans = curseg.second==nn ? curseg.first - 1 : curseg.second;
return make_pair(vec[ans-1],vec[ans-1]+1);
}
void modify(int u, int x){
for(int i = st[u]; i <= ed[u]; i++){
if(x==1){
insert(minnode[rdfn[i]]);
if(minnode[rdfn[i]]!=maxnode[rdfn[i]]) insert(maxnode[rdfn[i]]);
}
else{
erase(minnode[rdfn[i]]);
if(minnode[rdfn[i]]!=maxnode[rdfn[i]]) erase(maxnode[rdfn[i]]);
}
}
}
void rua(int u, int par, int eid, bool clear){
for(int i = G.head[u]; ~i; i = G.nxt[i]){
int v = G.to[i];
if(v==par or v==son[u]) continue;
rua(v,u,G.id[i],true);
}
if(son[u]) rua(son[u],u,sonid[u],false);
for(int i = G.head[u]; ~i; i = G.nxt[i]){
int v = G.to[i];
if(v==par or v==son[u]) continue;
modify(v,1);
}
insert(minnode[u]);
if(minnode[u]!=maxnode[u]) insert(maxnode[u]);
if(!par) return;
ret[eid] = query();
if(clear) modify(u,-1);
}
void solve(){
scanf("%d %d",&n,&m);
init();
for(int i = 1; i <= m; i++){
int u, v;
scanf("%d %d",&u,&v);
GG.ADDEDGE(u,v,i); GG.ADDEDGE(v,u,i);
}
tarjan(1,0);
rebuild();
for(int i = 1; i <= num; i++) vec.push_back(minnode[i]), vec.push_back(maxnode[i]);
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
nn = vec.size();
for(int i = 1; i <= num; i++){
minnode[i] = lower_bound(vec.begin(),vec.end(),minnode[i]) - vec.begin() + 1;
maxnode[i] = lower_bound(vec.begin(),vec.end(),maxnode[i]) - vec.begin() + 1;
}
idx = 0; dfs(1,0);
rua(1,0,0,false);
for(int i = 1; i <= m; i++) printf("%d %d\n",ret[i].first,ret[i].second);
}
int main(){
int T; for(scanf("%d",&T); T; T--) solve();
return 0;
}
/*
test1:
6 6
1 2
2 5
2 3
1 4
4 6
6 1
ans:
5 6
5 6
3 4
0 0
0 0
0 0
test2:
9 10
1 2
1 4
1 5
2 6
2 3
3 5
6 7
7 8
7 9
8 9
ans:
0 0
4 5
0 0
5 6
0 0
0 0
6 7
0 0
0 0
0 0
*/
5410 CRB and His Birthday
二进制分组背包
每个物品第一次拿可以有额外的\(B[i]\)的价值
把第一次拿分成一种，后面拿的二进制分组即可
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 2222;
const int INF = 0x3f3f3f3f;
int m,n,A[MAXN],B[MAXN],w[MAXN],f[MAXN];
void solve(){
scanf("%d %d",&m,&n);
for(int i = 1; i <= n; i++) scanf("%d %d %d",&w[i],&A[i],&B[i]);
vector<pair<int,int>> vec;
for(int i = 1; i <= n; i++){
if(w[i]>m) continue;
vec.push_back(make_pair(A[i]+B[i],w[i]));
for(int bit = 1; bit * w[i] <= m; bit <<= 1) vec.push_back(make_pair(A[i]*bit,w[i]*bit));
}
memset(f,0,sizeof(f));
for(int i = 0; i < (int)vec.size(); i++){
for(int j = m; j >= vec[i].second; j--) f[j] = max(f[j],f[j-vec[i].second] + vec[i].first);
}
printf("%d\n",f[m]);
}
int main(){
int T;
for(scanf("%d",&T); T; T--) solve();
return 0;
}
5411 CRB and Puzzle
矩阵快速幂优化DP
并且在快速幂中记录对答案的贡献
复杂度\(O(n^3\log m)\)
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 55;
const int MOD = 2015;
int n,m;
struct Matrix{
int mat[MAXN][MAXN];
Matrix(int tag = 0){
for(int i = 0; i < MAXN; i++) for(int j = 0; j < MAXN; j++){
if(i==j) mat[i][j] = tag;
else mat[i][j] = 0;
}
}
Matrix operator*(const Matrix rhs){
Matrix ret(0);
for(int i = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
for(int k = 0; k <= n; k++)
ret.mat[i][j] = (ret.mat[i][j] + mat[i][k] * rhs.mat[k][j]) % MOD;
return ret;
}
};
Matrix qpow(Matrix A, int b){
Matrix ret(1);
while(b){
if(b&1) ret = ret * A;
b >>= 1;
A = A * A;
}
return ret;
}
bool vis[MAXN][MAXN];
void solve(){
memset(vis,0,sizeof(vis));
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++){
int num; scanf("%d",&num);
while(num--){
int x; scanf("%d",&x);
vis[i][x] = true;
}
}
Matrix M(0);
for(int i = 0; i <= n; i++) M.mat[i][0] = 1;
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) M.mat[i][j] = vis[i][j] ? 1 : 0;
Matrix ret = qpow(M,m);
int ans = 0;
for(int i = 0; i <= n; i++) ans += ret.mat[i][0];
printf("%d\n",ans%MOD);
}
int main(){
int T;
for(scanf("%d",&T); T; T--) solve();
return 0;
}
5412 CRB and Queries
动态区间第K大
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 3e5+7;
#define lowbit(x) (x&-x)
int n,q,A[MAXN];
struct Qeury{
int op,l,r,k,pos,x;
}Q[MAXN];
vector<int> vec;
struct PersistentSegmentTree{
int root[MAXN],ls[MAXN*40],rs[MAXN*40],sum[MAXN*40],tot;
stack<int> stk;
vector<int> vl,vr;
void clear(){ memset(root,0,sizeof(root)); tot = 0; }
int newnode(){
int node;
if(!stk.empty()) node = stk.top(), stk.pop();
else node = ++tot;
ls[node] = rs[node] = 0;
sum[node] = 0;
return node;
}
void upd(int L, int R, int &rt, int x){
if(!rt) rt = newnode();
sum[rt] += x / abs(x);
if(L+1==R) return;
int mid = (L+R) >> 1;
if(abs(x)<mid) upd(L,mid,ls[rt],x);
else upd(mid,R,rs[rt],x);
if(!sum[rt]) stk.push(rt), rt = 0;
}
void update(int pos, int x){
for(int i = pos; i <= n; i += lowbit(i)){
upd(1,vec.size()+1,root[i],x);
}
}
int cal(){
int ret = 0;
for(int rt : vl) ret -= sum[ls[rt]];
for(int rt : vr) ret += sum[ls[rt]];
return ret;
}
int _query(int L, int R, int k){
if(L+1==R) return L;
int suml = cal();
if(k<=suml){
for(int &rt : vl) rt = ls[rt];
for(int &rt : vr) rt = ls[rt];
return _query(L,(L+R)>>1,k);
}
else{
for(int &rt : vl) rt = rs[rt];
for(int &rt : vr) rt = rs[rt];
return _query((L+R)>>1,R,k-suml);
}
}
int query(int L, int R, int k){
vl.clear(); vr.clear();
for(int i = L - 1; i; i -= lowbit(i)) vl.push_back(root[i]);
for(int i = R; i; i -= lowbit(i)) vr.push_back(root[i]);
return _query(1,vec.size()+1,k);
}
}PST;
void solve(){
PST.clear();
vec.clear();
for(int i = 1; i <= n; i++) scanf("%d",&A[i]), vec.push_back(A[i]);
scanf("%d",&q);
for(int i = 1; i <= q; i++){
scanf("%d",&Q[i].op);
if(Q[i].op==1) scanf("%d %d",&Q[i].pos,&Q[i].x), vec.push_back(Q[i].x);
else scanf("%d %d %d",&Q[i].l,&Q[i].r,&Q[i].k);
}
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(int i = 1; i <= n; i++) A[i] = lower_bound(vec.begin(),vec.end(),A[i]) - vec.begin() + 1;
for(int i = 1; i <= q; i++){
if(Q[i].op==1) Q[i].x = lower_bound(vec.begin(),vec.end(),Q[i].x) - vec.begin() + 1;
}
for(int i = 1; i <= n; i++) PST.update(i,A[i]);
for(int i = 1; i <= q; i++){
if(Q[i].op==1){
PST.update(Q[i].pos,-A[Q[i].pos]);
PST.update(Q[i].pos,A[Q[i].pos] = Q[i].x);
}
else printf("%d\n",vec[PST.query(Q[i].l,Q[i].r,Q[i].k)-1]);
}
}
int main(){
while(scanf("%d",&n)!=EOF) solve();
return 0;
}
5413 CRB and Roads
因为是个\(DAG\)，所以可以先拓扑排序
能删去的\(u\)所连出去的边（到\(v\)），必然是\(u\)能通过其他点间接到达\(v\)
我们只要通过拓扑序维护\(u\)能间接到达的点即可
复杂度是\(O(n^2)\)
\(bitset\)优化之后复杂度为\(O(\frac{n^2}{32})\)
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 2e4+7;
const int MAXM = 1e5+7;
bitset<MAXN> A[MAXN];
int n,m,deg[MAXN];
vector<int> rG[MAXN],G[MAXN];
void solve(){
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++){
A[i].reset();
G[i].clear(); rG[i].clear();
}
for(int i = 1; i <= m; i++){
int u, v;
scanf("%d %d",&u,&v);
rG[v].push_back(u);
G[u].push_back(v);
deg[u]++;
}
queue<int> que;
for(int i = 1; i <= n; i++) if(!deg[i]) que.push(i);
int ret = 0;
while(!que.empty()){
int u = que.front();
que.pop();
for(int v : G[u]) if(A[u].test(v)) ret++;
for(int v : G[u]) A[u].set(v,1);
for(int v : rG[u]){
if(!--deg[v]) que.push(v);
A[v] |= A[u];
}
}
printf("%d\n",ret);
}
int main(){
int T; for(scanf("%d",&T); T; T--) solve();
return 0;
}
5414 CRB and String
思维+子序列自动机
先判断首字母是否相同，不相同则No
然后判断\(s\)和\(t\)头部最长相同字符长度,如果\(t\)的长度比\(s\)长则No
然后去掉开头\(s\)和\(t\)的匹配部分，判断剩下部分的\(s\)是否是剩下部分的\(t\)的子序列即可
复杂度\(O(Length)\)
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 2e5+7;
const int INF = 0x3f3f3f3f;
char s[MAXN],t[MAXN];
int ls,lt,f[MAXN][26];
void solve(){
scanf("%s %s",s,t);
ls = strlen(s); lt = strlen(t);
int match = 0;
int ms = 1, mt = 1;
while(s[ms-1]==s[ms]) ms++;
while(t[mt-1]==t[mt]) mt++;
if(s[0]!=t[0] or mt>ms){ puts("No"); return; }
match = mt;
memset(f[lt-1],0x3f,sizeof(f[lt-1]));
for(int i = lt - 2; i >= 0; i--){
for(int ch = 0; ch < 26; ch++) f[i][ch] = f[i+1][ch];
f[i][t[i+1]-'a'] = i + 1;
}
// check if s_match...s_ls-1 is a subsequence of t_match...t_lt-1
// subsequence automaton
int pos = match - 1;
bool ok = true;
for(int i = match; i < ls; i++){
if(f[pos][s[i]-'a']==INF){
ok = false;
break;
}
pos = f[pos][s[i]-'a'];
}
puts(ok?"Yes":"No");
}
int main(){
int T;
for(scanf("%d",&T); T; T--) solve();
return 0;
}
5415 CRB and Substrings
5416 CRB and Tree
可以把两点之间路径权值异或和转化为从根到两点的路径的权值异或和的异或和
复杂度\(O(TQN)\)
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 4e5+7;
typedef long long int LL;
int n,d[MAXN],cnt[MAXN];
vector<pair<int,int>> G[MAXN];
void dfs(int u, int f){
for(auto e : G[u]){
if(e.first==f) continue;
d[e.first] = d[u] ^ e.second;
dfs(e.first,u);
}
}
void solve(){
scanf("%d",&n);
for(int i = 1; i <= n; i++) G[i].clear();
for(int i = 1; i < n; i++){
int u, v, w;
scanf("%d %d %d",&u,&v,&w);
G[u].push_back(make_pair(v,w));
G[v].push_back(make_pair(u,w));
}
dfs(1,0);
memset(cnt,0,sizeof(cnt));
for(int i = 1; i <= n; i++) cnt[d[i]]++;
int q; scanf("%d",&q);
while(q--){
int x; scanf("%d",&x);
LL ret = 0;
for(int i = 1; i <= n; i++) ret += cnt[x^d[i]];
if(!x) ret += n;
printf("%I64d\n",ret>>1);
}
}
int main(){
int T;
for(scanf("%d",&T); T; T--) solve();
return 0;
}