题解：
https://files.cnblogs.com/files/clrs97/HarbinEditorialV2.zip
Code：
A. Artful Paintings
/*
let x=f[n]
f[i-1]-f[i]<=0 i -> i-1 0
f[i]-f[i-1]<=1 i-1 -> i 1
f[l-1]-f[r]<=-k r -> l-1 -k
f[r]-f[l-1]<=-k+x l-1 -> r -k+x
f[n]-f[0]<=x 0 -> n x
f[0]-f[n]<=-x n -> 0 -x
for each cycle whose cost is A+Bx, we have A+Bx>=0 -> x>=(-A/B)
so find a cycle with minimum average cost
*/
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int>P;
const int N=3010,M=3010,inf=1000000000;
int Case,n,m1,m2,i,j,k,x,y,z,f[N][N],h[N],ans,nu,nd,tu,td,cnt[N<<1];
vector<P>g[N];
struct E{int u,v,w;}e[M];
inline void up(int&a,int b){a>b?(a=b):0;}
inline void cal(int u,int d){
if(u>=0)return;
u=-u;
u=u/d+((u%d)>0);
if(u>ans)ans=u;
}
inline void solve(){
int i,j,x,y,base;
for(i=n;i>1;i--)up(h[i-1],h[i]);
for(i=1;i<n;i++)up(h[i+1],h[i]+1);
base=h[n];
//h[n] is stable now
//h[i]=h[i+1] or h[i+1]-1
//h[n]-h[i] in [0..n]
//h[n]-h[i]+i in [0..2n]
for(i=1;i<=n;i++)cnt[base-h[i]+i]++;
for(i=n;i;i--){
cnt[base-h[i]+i]--;
if(i<n){
up(h[i],h[i+1]);
if(cnt[base-h[i+1]+i+1])h[i]=h[i+1]-1;
}
for(j=0;j<g[i].size();j++){
x=g[i][j].first;
y=h[i]+g[i][j].second;
if(h[x]>y){
cnt[base-h[x]+x]--;
h[x]=y;
cnt[base-h[x]+x]++;
}
}
}
}
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d%d%d",&n,&m1,&m2);n++;
for(i=1;i<=n;i++)g[i].clear();
while(m1--)scanf("%d%d%d",&x,&y,&z),g[y+1].push_back(P(x,-z));
for(i=1;i<=m2;i++){
scanf("%d%d%d",&x,&y,&z);
e[i].u=x;
e[i].v=y+1;
e[i].w=-z;
}
e[++m2].u=1;
e[m2].v=n;
e[m2].w=0;
ans=0;
//case 1: not passed the edge n -> 0 -x
for(i=0;i<=n;i++)for(j=1;j<=n;j++)f[i][j]=inf;
f[0][1]=0;
for(i=0;i<=n;i++){
for(j=1;j<=n;j++)h[j]=f[i][j];
solve();
for(j=1;j<=n;j++)f[i][j]=h[j];
if(i<n)for(j=1;j<=m2;j++)up(f[i+1][e[j].v],f[i][e[j].u]+e[j].w);
}
for(i=1;i<=n;i++){
nu=-inf,nd=1;
for(j=0;j<n;j++){
tu=f[n][i]-f[j][i],td=n-j;
if(1LL*nu*td<1LL*tu*nd)nu=tu,nd=td;
}
cal(nu,nd);
}
//case 2: passed the edge n -> 0 -x
for(i=2;i<=n;i++)cal(f[i][n],i-1);
printf("%d
",ans);
}
}
B. Binary Numbers
/*
lcp(a[i],l[i])>=lcp(a[i-1],l[i])
lcp(a[i],r[i])>=lcp(a[i+1],r[i])
f[i][lcp(a[i],l[i+1])][lcp(a[i],r[i])]
*/
#include<cstdio>
const int N=131100,K=20,P=100000007;
int Case,m,n,i,j,k,l[N],r[N],A,B,C,D,f[K][K],g[K][K];
inline int cal(int a,int b){
int ret=0;
for(int i=m-1;~i;i--)if((a>>i&1)==(b>>i&1))ret++;else break;
return ret;
}
inline void up(int&a,int b){a=a+b<P?a+b:a+b-P;}
inline void clr(){for(j=0;j<=m;j++)for(k=0;k<=m;k++)g[j][k]=0;}
inline void nxt(){
for(j=0;j<=m;j++)for(k=0;k<=m;k++){
f[j][k]=g[j][k];
if(j)up(f[j][k],f[j-1][k]);
}
for(j=0;j<=m;j++)for(k=m-1;~k;k--)up(f[j][k],f[j][k+1]);
}
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
clr();
g[0][m]=1;
nxt();
for(i=1;i<=n;i++){
clr();
for(j=l[i];j<=r[i];j++){
A=cal(j,l[i]);
B=cal(j,r[i]);
C=i<n?cal(j,l[i+1]):0;
D=i>1?cal(j,r[i-1]):0;
g[C][B]=(1LL*f[A][D]*j+g[C][B])%P;
}
nxt();
}
printf("%d
",f[m][0]);
}
}
C. Competition in Swiss-system
#include<cstdio>
typedef long long ll;
const int N=10010,M=20;
int Case,n,m,i,j,a[N],g[N][M],cg[N];bool v[N];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
struct P{
ll u,d;
P(){}
P(ll _u,ll _d){u=_u,d=_d;}
void operator+=(const P&b){
ll x=gcd(d,b.d);
u=u*(b.d/x)+(d/x)*b.u;
d=d/x*b.d;
}
P fix()const{
if(u*3<d)return P(1,3);
return P(u,d);
}
void write(){
if(!u)printf("0/1");
else{
ll x=gcd(u,d);
u/=x,d/=x;
printf("%lld/%lld",u,d);
}
}
}mw[N],gw[N];
inline void calomw(int x){
if(!cg[x]){
printf("1/3");
return;
}
P now(0,1);
for(int i=0;i<cg[x];i++)now+=mw[g[x][i]].fix();
now.d*=cg[x];
now.write();
}
inline void calogw(int x){
if(!cg[x]){
printf("1/3");
return;
}
P now(0,1);
for(int i=0;i<cg[x];i++)now+=gw[g[x][i]].fix();
now.d*=cg[x];
now.write();
}
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++){
mw[i]=P(0,0);
gw[i]=P(0,0);
}
for(i=1;i<=n;i++)cg[i]=0;
for(i=1;i<=m;i++){
printf("Round %d
",i);
for(j=1;j<=n;j++)v[j]=0;
for(j=1;j<=a[i];j++){
int p1,p2,w1,w2,d;
scanf("%d%d%d%d%d",&p1,&p2,&w1,&w2,&d);
if(w1>w2)mw[p1].u+=3;
else if(w1<w2)mw[p2].u+=3;
else{
mw[p1].u++;
mw[p2].u++;
}
mw[p1].d+=3;
mw[p2].d+=3;
gw[p1].u+=3*w1+d;
gw[p2].u+=3*w2+d;
gw[p1].d+=3*(w1+w2+d);
gw[p2].d+=3*(w1+w2+d);
g[p1][cg[p1]++]=p2;
g[p2][cg[p2]++]=p1;
v[p1]=v[p2]=1;
}
for(j=1;j<=n;j++)if(!v[j]){
mw[j].u+=3;
mw[j].d+=3;
gw[j].u+=6;
gw[j].d+=6;
}
for(j=1;j<=n;j++){
printf("%lld ",mw[j].u);
calomw(j);
putchar(' ');
gw[j].fix().write();
putchar(' ');
calogw(j);
puts("");
}
}
}
}
D. Driverless Car
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long double ld;
const ld eps=1e-9;
const int N=10000;
inline int sgn(ld x){
if(x>eps)return 1;
if(x<-eps)return -1;
return 0;
}
struct P{
ld x,y;
P(){x=y=0;}
P(ld _x,ld _y){x=_x,y=_y;}
P operator+(const P&b)const{return P(x+b.x,y+b.y);}
P operator-(const P&b)const{return P(x-b.x,y-b.y);}
void operator-=(const P&b){*this=*this-b;}
P operator*(const ld&b)const{return P(x*b,y*b);}
ld len()const{return hypot(x,y);}
P rotate(ld c)const{return P(x*cos(c)-y*sin(c),x*sin(c)+y*cos(c));}
P rot90()const{return P(-y,x);}
P rot270()const{return P(y,-x);}
void flip(){x=-x,y=-y;}
void read(){
double _x,_y;
scanf("%lf%lf",&_x,&_y);
x=_x,y=_y;
}
}a[4],A,B,C,D,f[2][2];
ld ans;
struct E{
P A,B;//A->B left hand
E(){}
E(const P&_A,const P&_B){A=_A,B=_B;}
}e[N];
int cnt,tp[2];ld pool[N],v[N];
inline ld cross(const P&a,const P&b){return a.x*b.y-a.y*b.x;}
inline int line_intersection(const P&a,const P&b,const P&p,const P&q,P&o,ld&t){
ld U=cross(p-a,q-p),D=cross(b-a,q-p);
if(sgn(D)==0)return sgn(U)==0?2:0;
o=a+(b-a)*(U/D);
t=U/D;
return 1;
}
inline void work(const P&A,const P&B,int S,int o){
if(S==0){
//closer to A
e[++cnt]=E(A,A+((B-A).rot90()));
f[o][0]=A;
tp[o]=0;
}
if(S==1){
//closer to B
e[++cnt]=E(B,B+((A-B).rot90()));
f[o][0]=B;
tp[o]=0;
}
if(S==2){
//the line
e[++cnt]=E(A,A+((B-A).rot270()));
e[++cnt]=E(B,B+((A-B).rot270()));
f[o][0]=A;
f[o][1]=B;
tp[o]=1;
}
}
inline bool check(const P&X){
for(int i=1;i<=cnt;i++)if(sgn(cross(X-e[i].A,e[i].B-e[i].A))>0)return 0;
return 1;
}
inline void calline(const P&A,const P&B){
int i,m=0;
for(i=1;i<=cnt;i++){
P o;ld t;
int tmp=line_intersection(A,B,e[i].A,e[i].B,o,t);
if(tmp==2)return;
if(tmp==1)pool[++m]=t;
}
sort(pool+1,pool+m+1);
ld ret=0;
for(i=2;i<=m;i++)if(check(A+(B-A)*(pool[i]+pool[i-1])*0.5))ret+=pool[i]-pool[i-1];
ans+=ret*((B-A).len());
}
inline ld mysqrt(ld x){
if(sgn(x)<=0)return 0;
return sqrt(x);
}
inline bool getroot(ld A,ld B,ld C,ld&x,ld&y){
ld D=B*B-4*A*C;
if(sgn(D)<0)return 0;
D=mysqrt(D);
x=(-B-D)/(A*2);
y=(-B+D)/(A*2);
return 1;
}
inline ld integrate(ld A,ld x){
return (mysqrt(A*x*x+1)*x+log(fabs(2*A*x+2*mysqrt(A*(A*x*x+1))))/mysqrt(A))/2;
}
inline void solve(){
if(tp[0]>tp[1]){
swap(tp[0],tp[1]);
swap(f[0][0],f[1][0]);
swap(f[0][1],f[1][1]);
}
P A=f[0][0],B=f[0][1],C=f[1][0],D=f[1][1];
if(tp[0]==0&&tp[1]==0){
//point A and point C
P E=(A+C)*0.5;
calline(((A-E).rot90())+E,E);
}else if(tp[0]==1&&tp[1]==1){
//line AB and line CD
P o;
ld t;
int res=line_intersection(A,B,C,D,o,t);
if(res==0){
o=(A+C)*0.5;
calline(o,o+D-C);
}else{
if((A-o).len()<(B-o).len())swap(A,B);
if((C-o).len()<(D-o).len())swap(C,D);
ld w=(atan2(A.y-o.y,A.x-o.x)+atan2(C.y-o.y,C.x-o.x))*0.5;
P E(cos(w),sin(w));
calline(o,o+E);
calline(o,o+(E.rot90()));
}
}else{
//point A and line CD
//x^2=py
D=D-C;
A=A-C;
int i;
for(i=1;i<=cnt;i++)e[i].A-=C,e[i].B-=C;
ld w=atan2(D.y,D.x);
A=A.rotate(-w);
for(i=1;i<=cnt;i++)e[i].A=e[i].A.rotate(-w),e[i].B=e[i].B.rotate(-w);
if(A.y<0){
A.flip();
for(i=1;i<=cnt;i++)e[i].A.flip(),e[i].B.flip();
}
C=P(A.x,A.y*0.5);
ld p=A.y*2;
if(!sgn(p))return;
int m=0;
for(i=1;i<=cnt;i++){
e[i].A-=C,e[i].B-=C;
ld dx=e[i].A.x-e[i].B.x;
if(!sgn(dx)){
pool[++m]=e[i].A.x;
continue;
}
//y=kx+b
ld k=(e[i].A.y-e[i].B.y)/dx,b=e[i].A.y-k*e[i].A.x;
//x^2-pkx-pb=0
ld x,y;
if(getroot(1,-p*k,-p*b,x,y)){
pool[++m]=x;
pool[++m]=y;
}
}
sort(pool+1,pool+m+1);
for(i=1;i<=m;i++){
v[i]=integrate(4/p/p,pool[i]);
if(i>1){
ld x=(pool[i-1]+pool[i])*0.5;
if(check(P(x,x*x/p)))ans+=v[i]-v[i-1];
}
}
}
}
int main(){
int Case,i,j,k;
scanf("%d",&Case);
while(Case--){
int xl,yl,xr,yr;
scanf("%d%d%d%d",&xl,&yl,&xr,&yr);
a[0]=P(xl,yl);
a[1]=P(xr,yl);
a[2]=P(xr,yr);
a[3]=P(xl,yr);
A.read();
B.read();
C.read();
D.read();
ans=0;
for(i=0;i<3;i++)for(j=0;j<3;j++){
cnt=0;
for(k=0;k<4;k++)e[++cnt]=E(a[k],a[(k+1)%4]);
work(A,B,i,0);
work(C,D,j,1);
solve();
}
printf("%.15f
",(double)ans);
}
}
E. Exchanging Gifts
#include<cstdio>
typedef long long ll;
const int N=1000010;
int Case,n,i,j,x,y,z,ans,type[N],a[N],b[N],st[N],en[N],pool[N],cnt;ll g[N],len[N];
struct Info{
int x;ll v;
Info(){}
Info(int _x,ll _v){x=_x,v=_v;}
Info operator+(const Info&b)const{
if(x==b.x)return Info(x,v+b.v);
if(v>b.v)return Info(x,v-b.v);
return Info(b.x,b.v-v);
}
}f[N];
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d",&n);
cnt=0;
for(i=1;i<=n;i++){
scanf("%d",&type[i]);
if(type[i]==2)scanf("%d%d",&a[i],&b[i]);
else{
scanf("%d",&x);
st[i]=cnt+1;
while(x--){
scanf("%d",&y);
pool[++cnt]=y;
}
en[i]=cnt;
}
}
for(i=1;i<=n;i++)if(type[i]==2){
f[i]=f[a[i]]+f[b[i]];
len[i]=len[a[i]]+len[b[i]];
}else{
x=y=0;
len[i]=en[i]-st[i]+1;
for(j=st[i];j<=en[i];j++){
z=pool[j];
if(!y)x=z,y++;
else if(x==z)y++;
else y--;
}
f[i]=Info(x,y);
}
ans=f[n].x;
for(i=1;i<=n;i++)if(type[i]==2)g[i]=g[a[i]]+g[b[i]];
else{
x=0;
for(j=st[i];j<=en[i];j++)if(pool[j]==ans)x++;
g[i]=x;
}
ll t=g[n]*2-len[n];
if(t<0)t=0;
t=len[n]-t;
printf("%lld
",t);
}
}
F. Fixing Banners
#include<cstdio>
#include<cstring>
#include<string>
const int N=6;
int Case,i,j,k,len,S,f[1<<N],g[1<<N];char b[2000010];std::string a="harbin";
int main(){
scanf("%d",&Case);
while(Case--){
for(i=0;i<1<<N;i++)f[i]=0;
f[0]=1;
for(i=0;i<N;i++){
scanf("%s",b);
len=strlen(b);
S=0;
for(j=0;j<len;j++)for(k=0;k<N;k++)if(b[j]==a[k])S|=1<<k;
for(j=0;j<1<<N;j++)g[j]=0;
for(j=0;j<1<<N;j++)for(k=0;k<N;k++)if(S>>k&1)g[j|(1<<k)]|=f[j];
for(j=0;j<1<<N;j++)f[j]=g[j];
}
puts(f[(1<<N)-1]?"Yes":"No");
}
}
G. Game Store
#include<cstdio>
typedef long long ll;
typedef unsigned long long ull;
const int K=60;
int n;ll x,y,ans,w[K];ull a[K][2];bool v[K];
inline void ins(ull x,ull y,ll z){
for(int i=0;i<K;i++)if((x>>i&1)||(y>>i&1)){
if(!v[i]){
v[i]=1;
a[i][0]=x;
a[i][1]=y;
w[i]=z;
ans+=z;
return;
}
if(w[i]<z){
ull A=a[i][0],B=a[i][1];ll C=w[i];
a[i][0]=x;
a[i][1]=y;
w[i]=z;
ans+=z-C;
x=A;
y=B;
z=C;
}
ull C=a[i][0],D=a[i][1];
while((x>>i&1)||(y>>i&1)){
ull t=((x|y)&(C|D))^(y&D);
x^=C^(y&D)^((y^D)&t);
y^=D^t;
}
}
}
int main(){
scanf("%d",&n);
while(n--){
ll x,y;
scanf("%lld%lld",&x,&y);//1<=x<=1e18 1<=y<=1e9
x^=ans,y^=ans;
ins(0,x,y);
printf("%lld
",ans);
}
}
H. Highway Buses
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;
const int N=200010,M=N*20,K=55;
const ll inf=1LL<<60;
int n,m,day,i,x,y,a[N],b[N],lim[N],cost[N],g[N],v[N<<1],nxt[N<<1],ok[N<<1],ed;
int f[N],son[N],all,now;
int _st[N],st[N],en[N],cur,q[M][2],vis[N];
int G[N],V[M],W[M],NXT[M],ED;
priority_queue<P,vector<P>,greater<P> >Q;
ll dis[N],fin[N];
int dsu[N];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;ok[ed]=1;}
inline void ADD(int x,int y,int z){V[++ED]=y;W[ED]=z;NXT[ED]=G[x];G[x]=ED;}
void findroot(int x,int y){
son[x]=1;f[x]=0;
for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y){
findroot(v[i],x);
son[x]+=son[v[i]];
if(son[v[i]]>f[x])f[x]=son[v[i]];
}
if(all-son[x]>f[x])f[x]=all-son[x];
if(f[x]<f[now])now=x;
}
inline void bfs(int S){
vis[S]=S;
q[++cur][0]=S;
q[cur][1]=0;
int h=cur;
while(h<=cur){
int x=q[h][0],y=q[h++][1]+1;
for(int i=g[x];i;i=nxt[i])if(ok[i]&&vis[v[i]]!=S){
vis[v[i]]=S;
q[++cur][0]=v[i];
q[cur][1]=y;
}
}
}
void solve(int x){
st[x]=cur+1;
bfs(x);
en[x]=cur;
for(int i=st[x];i<=cur;i++)ADD(q[i][0],x,q[i][1]);
for(int i=g[x];i;i=nxt[i])if(ok[i]){
ok[i^1]=0;
f[0]=all=son[v[i]];
findroot(v[i],now=0);
solve(now);
}
}
inline void extend(int x,ll y){
if(vis[x])return;
vis[x]=1;
dis[x]=y;
Q.push(P(y+cost[x],x));
}
inline void go(int x,int lim,ll y){
int&h=st[x],t=en[x];
while(h<=t){
if(q[h][1]>lim)break;
extend(q[h++][0],y);
}
}
int DSU(int x){return dsu[x]==x?x:dsu[x]=DSU(dsu[x]);}
namespace VIP{
bool is[N],vis[N];
int pool[K],cp,q[K][N],d[K][N],st[K];
int i,j,k,h,t,x,y,g[N],v[(N+K)<<1],nxt[(N+K)<<1],ed;
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline void set(int x){
if(is[x])return;
is[x]=1;
pool[cp++]=x;
}
inline void ext(int x){
if(vis[x])return;
vis[x]=1;
q[i][++t]=x;
d[i][x]=y;
}
inline void init(){
for(i=0;i<cp;i++){
for(j=1;j<=n;j++)vis[j]=0;
y=0;
h=1,t=0;
ext(pool[i]);
while(h<=t){
x=q[i][h++];
y=d[i][x]+1;
for(k=g[x];k;k=nxt[k])ext(v[k]);
}
}
}
inline void go(int x,ll y,int lim){
int&h=st[x];
while(h<=n){
if(d[x][q[x][h]]>lim)break;
extend(q[x][h++],y);
}
}
}
inline void work(int day){
for(i=1;i<=n;i++){
vis[i]=0;
st[i]=_st[i];
cost[i]=a[i]+1LL*b[i]*(day-1);
}
for(i=0;i<VIP::cp;i++)VIP::st[i]=1;
extend(1,0);
while(!Q.empty()){
P t=Q.top();Q.pop();
for(i=G[t.second];i;i=NXT[i])go(V[i],lim[t.second]-W[i],t.first);
for(i=0;i<VIP::cp;i++)VIP::go(i,t.first,lim[t.second]-VIP::d[i][t.second]);
}
for(i=1;i<=n;i++)fin[i]=min(fin[i],dis[i]);
}
int main(){
scanf("%d%d%d",&n,&m,&day);
for(i=1;i<=n;i++)scanf("%d%d%d",&lim[i],&a[i],&b[i]);
for(i=1;i<=n;i++)dsu[i]=i;
ed=1;
while(m--){
scanf("%d%d",&x,&y);
VIP::add(x,y);
VIP::add(y,x);
if(DSU(x)==DSU(y)){
VIP::set(x);
}else{
dsu[dsu[x]]=dsu[y];
add(x,y);
add(y,x);
}
}
f[0]=all=n;findroot(1,now=0);solve(now);
VIP::init();
for(i=1;i<=n;i++)fin[i]=inf,_st[i]=st[i];
work(1);
work(day);
for(i=1;i<=n;i++)printf("%lld
",fin[i]);
}
I. Interesting Permutation
#include<cstdio>
const int P=1000000007;
int Case,n,i,a[100010];
inline int solve(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
if(a[1])return 0;
int gap=a[1],slot=0,ans=1;
for(i=2;i<=n;i++){
if(a[i]<gap)return 0;
if(a[i]>=n)return 0;
if(a[i]==gap){
if(!slot)return 0;
ans=1LL*ans*slot%P;
slot--;
}else{
ans=2LL*ans%P;
slot+=a[i]-gap-1;
gap=a[i];
}
}
return ans;
}
int main(){
scanf("%d",&Case);
while(Case--)printf("%d
",solve());
}
J. Justifying the Conjecture
#include<cstdio>
int Case,n;
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d",&n);
if(n<=5){
puts("-1");
continue;
}
if(n&1)printf("3 %d
",n-3);
else printf("2 %d
",n-2);
}
}
K. Keeping Rabbits
#include<cstdio>
#include<cstdlib>
using namespace std;
int Case,n,k,i;double a[100010],s;
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d%d",&n,&k);
s=0;
for(i=1;i<=n;i++)scanf("%lf",&a[i]),s+=a[i];
for(i=1;i<=n;i++)printf("%.15f%c",a[i]+a[i]*k/s,i<n?' ':'
');
}
}
L. LRU Algorithm
#include<cstdio>
typedef unsigned long long ull;
const int N=5010,M=200010;
int Case,n,q,m,i,j,a[N],b[N],len[M],ans[M];ull goal[M],f[N];
inline void cal(int n){for(int i=1;i<=n;i++)f[i]=f[i-1]*13331+b[i]+19260817;}
inline void ext(int x){
int i;
for(i=1;i<=n;i++)if(b[i]==x)break;
for(;i<n;i++)b[i]=b[i+1];
for(i=n;i>1;i--)b[i]=b[i-1];
b[1]=x;
}
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=q;i++){
scanf("%d",&m);
len[i]=m;
for(j=1;j<=m;j++)scanf("%d",&b[j]);
cal(m);
goal[i]=f[m];
ans[i]=0;
}
for(i=1;i<=n;i++)b[i]=0;
for(i=0;i<=n;i++){
if(i)ext(a[i]);
cal(n);
for(j=1;j<=q;j++)if(f[len[j]]==goal[j])ans[j]=1;
}
for(i=1;i<=q;i++)puts(ans[i]?"Yes":"No");
}
}