7.9 模拟赛

, , , ,

7.9 模拟赛

T1. six

Description

image-20230718141203887

1s 512MB

Solution

模拟。总状态只有 $2^8=256$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int dis[maxn];
queue<int>q;
int ch1[11],ch2[11];
int t[11],g[11],b[11];
inline int calc(int *a) {
	int i,sum=0;
	for (i=0;i<8;i++) sum+=a[i]*(1<<i);
	return sum;
}
inline bool check(int x) {
	int i;
	for (i=0;i<8;i++) b[i]=(x>>i)&1;
	for (i=0;i<4;i++) if (ch1[i]!=(b[i]|b[i+4])) return 0;
	if (ch2[0]!=(b[0]|b[1])) return 0;
	if (ch2[1]!=(b[4]|b[5])) return 0;
	if (ch2[2]!=(b[2]|b[3])) return 0;
	if (ch2[3]!=(b[6]|b[7])) return 0;
	return 1;
}
const int inf=1e9;
signed main(void){
    freopen("six.in","r",stdin);
	freopen("six.out","w",stdout); 
	char ch;int i,j,tmp;
	memset(dis,0x3f,sizeof(dis));
	int x=0;
	for (i=1;i<=8;i++) cin>>ch,x+=(ch=='1')*(1<<i-1);
	for (i=0;i<4;i++) cin>>ch,ch1[i]=(ch=='1');
	for (i=0;i<4;i++) cin>>ch,ch2[i]=(ch=='1');
	dis[x]=0;q.push(x);
	while (!q.empty()) {
		x=q.front();q.pop();
		for (i=0;i<8;i++) t[i]=(x>>i)&1;
		if (check(x)) return printf("%d",dis[x]),0;
		
		memcpy(g,t,sizeof(g));
		swap(g[0],g[1]),swap(g[1],g[3]),swap(g[3],g[2]);
		if (dis[tmp=calc(g)]>=inf) dis[tmp]=dis[x]+1,q.push(tmp);
		
		memcpy(g,t,sizeof(g));
		swap(g[2],g[3]),swap(g[3],g[1]),swap(g[1],g[0]);
		if (dis[tmp=calc(g)]>=inf) dis[tmp]=dis[x]+1,q.push(tmp);
		
		memcpy(g,t,sizeof(g));
		swap(g[4],g[5]),swap(g[5],g[7]),swap(g[7],g[6]);
		if (dis[tmp=calc(g)]>=inf) dis[tmp]=dis[x]+1,q.push(tmp);
		
		memcpy(g,t,sizeof(g));
		swap(g[6],g[7]),swap(g[7],g[5]),swap(g[5],g[4]);
		if (dis[tmp=calc(g)]>=inf) dis[tmp]=dis[x]+1,q.push(tmp);
		//
		memcpy(g,t,sizeof(g));
		swap(g[1],g[3]),swap(g[3],g[7]),swap(g[7],g[5]);
		if (dis[tmp=calc(g)]>=inf) dis[tmp]=dis[x]+1,q.push(tmp);
		
		memcpy(g,t,sizeof(g));
		swap(g[5],g[7]),swap(g[7],g[3]),swap(g[3],g[1]);
		if (dis[tmp=calc(g)]>=inf) dis[tmp]=dis[x]+1,q.push(tmp);
		
		memcpy(g,t,sizeof(g));
		swap(g[0],g[2]),swap(g[2],g[6]),swap(g[6],g[4]);
		if (dis[tmp=calc(g)]>=inf) dis[tmp]=dis[x]+1,q.push(tmp);
		
		memcpy(g,t,sizeof(g));
		swap(g[4],g[6]),swap(g[6],g[2]),swap(g[2],g[0]);
		if (dis[tmp=calc(g)]>=inf) dis[tmp]=dis[x]+1,q.push(tmp);
		//
		memcpy(g,t,sizeof(g));
		swap(g[0],g[1]),swap(g[1],g[5]),swap(g[5],g[4]);
		if (dis[tmp=calc(g)]>=inf) dis[tmp]=dis[x]+1,q.push(tmp);
		
		memcpy(g,t,sizeof(g));
		swap(g[4],g[5]),swap(g[5],g[1]),swap(g[1],g[0]);
		if (dis[tmp=calc(g)]>=inf) dis[tmp]=dis[x]+1,q.push(tmp);
		
		memcpy(g,t,sizeof(g));
		swap(g[2],g[3]),swap(g[3],g[7]),swap(g[7],g[6]);
		if (dis[tmp=calc(g)]>=inf) dis[tmp]=dis[x]+1,q.push(tmp);
		
		memcpy(g,t,sizeof(g));
		swap(g[6],g[7]),swap(g[7],g[3]),swap(g[3],g[2]);
		if (dis[tmp=calc(g)]>=inf) dis[tmp]=dis[x]+1,q.push(tmp);
	}
	return 0;
}

T2. march

Description

image-20230718152125824

$m\le |S|\le 10^6$

Solution

很好的线性 dp！

考虑令 $f[i][0/1],g[i][0/1],h[i][0/1]$ 表示到第 $i$ 个位置，结尾为 $0/1$，分别没找到 $[l1,r1]$，仅存在 $[l1,r1]$，存在 $[l1,r1],[l2,r2]$ 的方案数。

考虑 $f$ 向 $g$ 转移，如果在 $[i-m+1,i]$ 都没有 $0$，$g[i][1]\leftarrow f[i-m][0]$ ，同时为了防止 $f$ 算重（保持总数不变），$f[i][1]\leftarrow -f[i-m][0]$。

$g$ 向 $h$ 同理。

1s 512MB

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
const int mod=1e9+7,Inv=(mod+1)/2;
char ch[maxn];
int n,m;
int suf1[maxn],suf0[maxn],f[maxn][2],g[maxn][2],h[maxn][2]; 
inline void add(int &x,int y) {x=(x+y)%mod;}
signed main(void){
	int i;
	read(m);
	scanf("%s",ch+1);
	for (n=0;ch[n+1];n++);
	for (i=1;i<=n;i++) {
		suf1[i]=suf1[i-1];
		suf0[i]=suf0[i-1];
		if (ch[i]=='1') suf1[i]++;
		if (ch[i]=='0') suf0[i]++; 
	}
	f[0][0]=1;
	for (i=1;i<=n;i++) {
		if (ch[i]!='0') add(f[i][1],f[i-1][0]+f[i-1][1]);
		if (ch[i]!='1') add(f[i][0],f[i-1][0]+f[i-1][1]); 
		if (i>=m&&suf0[i]-suf0[i-m]==0) add(g[i][1],f[i-m][0]),add(f[i][1],mod-f[i-m][0]);
		
		if (ch[i]!='0') add(g[i][1],g[i-1][0]+g[i-1][1]);
		if (ch[i]!='1') add(g[i][0],g[i-1][0]+g[i-1][1]); 
		if (i>=m&&suf1[i]-suf1[i-m]==0) add(h[i][0],g[i-m][1]),add(g[i][0],mod-g[i-m][1]);
		
		if (ch[i]!='0') add(h[i][1],h[i-1][0]+h[i-1][1]);
		if (ch[i]!='1') add(h[i][0],h[i-1][0]+h[i-1][1]);
	}
	printf("%lld",(h[n][0]+h[n][1])%mod);
	return 0;
}

T3.planet

Description

image-20230718153023351

$n\le 1500$

1s 512MB

Solution

很好的题。

点边互换，考虑一个 $(n+1)\times (n+1)$ 的点阵，最外面一圈都已经相连。这个图显然是一平面图。如果两条边断开，则对应图上的两个点相连。两个点不再联通等价于图上多了一个面。

用平面图欧拉定理维护面的数量。具体实现上，判断两个点是否已经联通。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 2005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,q;
inline int id(int i,int j) {return (i-1)*(n+1)+j;}
int fa[maxn*maxn];
int dn,en,total;
inline int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
inline void merge(int x,int y) {
	x=getfa(x),y=getfa(y);
	if (x^y) fa[x]=y;
}
signed main(void){
	int x,y,xx,yy,c=0,q,i,j,fx,fy;
	read(n);read(q);gdb(n);
	for (i=1;i<=(n+1)*(n+1);i++) fa[i]=i;
	for (i=1;i<=n;i++) merge(id(1,i),id(1,i+1)),merge(id(n+1,i),id(n+1,i+1));
	for (i=1;i<=n;i++) merge(id(i,1),id(i+1,1)),merge(id(i,n+1),id(i+1,n+1));
	en=(n-1)*4,dn=n*n,total=(n-2)*(n-2)+1;
	while (q--) {
		read(x),read(y),read(xx),read(yy);
		x=(x+c)%n+1,y=(y+c)%n+1,xx=(xx+c)%n+1,yy=(yy+c)%n+1;
		if (x==xx) {
			if (y>yy) swap(y,yy);
			fx=getfa(id(x,yy));
			fy=getfa(id(x+1,yy));
		}
		else {
			if (x>xx) swap(x,xx);
			fx=getfa(id(xx,y));
			fy=getfa(id(xx,y+1));
		}
		if (fx^fy) puts("YES"),fa[fx]=fy,c++;
		else puts("NO");
	}
	return 0;
}

T4. dustbin

Description

image-20230718153902806

$n,q\le 5\times 10^5$

3s 512MB

原题 CF526G，强制在线方式略有不同。

Solution

先不考虑 $a$ 的限制。

如果 $c=1$ ，选择的是直径。否则再选择 $c-1$ 条最大以叶子节点为端点的线段交的最大值。

考虑以直径的一端为端点。则原题即为选择 $2c-1$ 条最长叶子到根的路径并起来。

但不一定是前 $2c-1$ 长的路径组成的。这里贪心一下即可预处理出来。

现在要加上 $a$ 的限制。

一种情况是直接替换第 $2c-1$ 小的路径。另一种情况是在 $2c-2$ 小的路径的基础上，再找一条最长的路径。

可能要特判 $c=1$ 的点。

Code

代码贴的是 CF 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 500005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int h[maxn],head=1,n,q;
struct yyy{
	int to,z,w;
	inline void add(int x,int y,int val) {
		to=y;z=h[x];h[x]=head;w=val;
	}
}a[maxn*2];
namespace TD{
	queue<int>q;
	int dis[maxn];
	inline int bfs(int x) {
		int i,ans=x;
		for (i=1;i<=n;i++) dis[i]=-1;
		dis[x]=0;
		q.push(x);
		while (!q.empty()) {
			x=q.front();q.pop();
			for (i=h[x];i;i=a[i].z) if (dis[a[i].to]==-1) {
				dis[a[i].to]=dis[x]+a[i].w,q.push(a[i].to);
				if (dis[ans]<dis[a[i].to]) ans=a[i].to;
			}
		}
		return ans;
	}
	inline void init(int &x,int &y) {
		x=bfs(1),y=bfs(x);
	} 
};
int lg[maxn];
struct node{
	int x,w;
};
inline bool cmp(node x,node y) {return x.w>y.w;}
struct tree{
	node e[maxn];
	int fa[maxn][21],deep[maxn],w[maxn],dis[maxn],cnt,rk[maxn],Ans[maxn],g[maxn];
	inline void dfs(int x,int pre) {
		deep[x]=deep[pre]+1;fa[x][0]=pre;int i;
		for (i=1;i<=lg[deep[x]];i++) fa[x][i]=fa[fa[x][i-1]][i-1];
		for (i=h[x];i;i=a[i].z) if (a[i].to^pre) {
			dis[a[i].to]=dis[x]+a[i].w;
			dfs(a[i].to,x);
			if (w[a[i].to]+a[i].w>w[x]) g[x]=a[i].to,w[x]=w[a[i].to]+a[i].w; 
		}
	}
	int top[maxn];
	inline void dfs2(int x,int u) {
		top[x]=u;
		if (x==u) e[++cnt]=(node){x,w[x]+dis[x]-dis[fa[x][0]]};
		if (g[x]) dfs2(g[x],u);
		for (int i=h[x];i;i=a[i].z) if (a[i].to^fa[x][0]&&a[i].to^g[x]) dfs2(a[i].to,a[i].to);
	} 
	inline void init(int rt) {
		int i;
		dfs(rt,rt);
		dfs2(rt,rt);
		sort(e+1,e+1+cnt,cmp);
		for (i=1;i<=cnt;i++) Ans[i]=Ans[i-1]+e[i].w,rk[e[i].x]=i;
		for (i=1;i<=n;i++) rk[i]=rk[top[i]]; 
	}
	inline int query(int x,int k) {
		if (rk[x]<=k) return Ans[min(k,cnt)];
		int u=x,v=x,i;
		for (i=lg[deep[v]];i>=0;i--) if (rk[fa[v][i]]>k) v=fa[v][i]; 
		for (i=lg[deep[u]];i>=0;i--) if (rk[fa[u][i]]>=k) u=fa[u][i];
		return max(Ans[k-1]+w[x]+dis[x]-dis[fa[u][0]],Ans[k]+w[x]+dis[x]-w[fa[v][0]]-dis[fa[v][0]]);
	}
}t1,t2;
signed main(void){
	int i,x,y,z,rt1=0,rt2=0,q;
	read(n);read(q);
	for (i=1;i<n;i++) {
		read(x),read(y),read(z);
		a[++head].add(x,y,z);
		a[++head].add(y,x,z);
	} 
	for (i=2;i<=n;i++) lg[i]=lg[i/2]+1;
	TD::init(rt1,rt2);
	t1.init(rt1);t2.init(rt2);
	int las=0;
	while (q--) {
		read(x),read(y);x=(x+las-1)%n+1;y=(y+las-1)%n+1;
		printf("%d\n",las=max(t1.query(x,2*y-1),t2.query(x,2*y-1)));
	}
	return 0;
}