NOIP2022模拟赛by Jtz1

T1

CF1311D

枚举 $a$，$b$ 是 $a$ 的倍数，$c$ 是 $b$ 的倍数，复杂度 $O(n\ln ^2n)$

事实上，$c$ 可以通过 $b$ $O(1)$ 算出来。

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn
#define put() putchar('\n')
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;
}
int A,B,C,ans=1e9;
const int base=2e5;
signed main(void){
    //freopen("1.in","r",stdin);
	int i,j;
	read(A);read(B);read(C);
	for (i=1;i<=base;i++){
		int sum=abs(B-i);
		int sum1=1e9,sum2=1e9;
		for (j=1;j*j<=i;j++)
			if (i%j==0) sum1=min(sum1,min(abs(A-j),abs(A-i/j)));
		for (j=i;j<=base;j+=i) 
			sum2=min(sum2,abs(C-j));
		ans=min(ans,sum+sum1+sum2);
	}
	printf("%d",ans);
    return 0;
}

T2

CCC2011S5

线性dp，大力分类讨论

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
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;
}
int n,a[maxn],len[maxn],cnt;
int f[maxn],sum[maxn];
signed main(void){
	int i,j,k,x;
	memset(f,0x3f,sizeof(f));
	read(n);
	a[0]=-1;len[0]=0;
	for (i=1;i<=n;i++) {
		read(x);
		if (x!=a[cnt]) a[++cnt]=x,len[cnt]=1;
		else len[cnt]++;
	}
	a[0]=0,len[0]=0;
	f[0]=0;if (a[1]==1) f[1]=4-len[1];
	for (i=1;i<=cnt;i++) sum[i]=sum[i-1]+len[i];
	for (i=1;i<=cnt;i++){
		if (a[i]==0) {f[i]=f[i-1];continue;} 
		f[i]=f[i-2]+4-len[i];
		if (i>=3&&len[i]+len[i-1]+len[i-2]>=4&&len[i-1]<=7-len[i]-len[i-2]) f[i]=min(f[i],f[i-3]+len[i-1]);
		if (i>=3&&sum[i]-sum[i-3]==3) f[i]=min(f[i],f[i-3]+2);
		if (i>=5&&sum[i]-sum[i-3]==3&&len[i-4]+len[i-3]-1<=4) f[i]=min(f[i],f[i-5]+len[i-1]+len[i-3]);
		if (i>=5&&sum[i-2]-sum[i-5]==3&&len[i]+len[i-1]-1<=4) f[i]=min(f[i],f[i-5]+len[i-1]+len[i-3]);
		if (i>=7&&sum[i]-sum[i-7]==7) f[i]=min(f[i],f[i-7]+3);
	}
//	for (i=1;i<=cnt;i++) printf("%d ",f[i]);put();
	printf("%d",f[cnt]);
    return 0;
}

T3

CF1407E

因为颜色只和 $(u,v)$ 中的 $u$ 有关。考虑倒着搜。

根据 bfs 的最优性，如果这条边被搜到而且还没有赋权值，那么赋为与 $c[u]$ 相反的颜色，停止当前搜索。否则继续搜。

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
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;
}
int ans,c[maxn],n,m;
int h[maxn],head=1;
queue<int>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[500005];
int dis[maxn];
signed main(void){
    //freopen("1.in","r",stdin);
	int i,x,y,z;
	read(n);read(m);
	for (i=1;i<=m;i++) {
		read(x),read(y),read(z);
		a[++head].add(y,x,z);
	}
	memset(dis,0x3f,sizeof(dis));
	memset(c,-1,sizeof(c));
	q.push(n);dis[n]=0;
	while (!q.empty()) {
		x=q.front();q.pop();
		for (i=h[x];i;i=a[i].z)
			if (c[a[i].to]==-1) c[a[i].to]=1-a[i].w;
			else if (c[a[i].to]==a[i].w&&dis[a[i].to]>dis[x]+1) q.push(a[i].to),dis[a[i].to]=dis[x]+1;
	}
	printf("%d\n",dis[1]>n?-1:dis[1]);
	for (i=1;i<=n;i++) printf("%d ",c[i]==-1?0:c[i]);
    return 0;
}

T4

屑 ds

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
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;
}
int cnt,root;
struct yyy{
	int lazy,ls,rs,size;
}a[maxn*20];
inline void Pushup(int k) {a[k].size=a[a[k].ls].size+a[a[k].rs].size;}
inline void Pushdown(int l,int r,int k) {
	if (a[k].lazy==1) {
		int mid=l+r>>1;
		if (!a[k].ls) a[k].ls=++cnt;if (!a[k].rs) a[k].rs=++cnt;
		a[a[k].ls].lazy=a[a[k].rs].lazy=1;
		a[a[k].ls].size=mid-l+1,a[a[k].rs].size=r-mid;
		a[k].lazy=0;
	}
	if (a[k].lazy==-1) {
		int mid=l+r>>1;
		if (!a[k].ls) a[k].ls=++cnt;if (!a[k].rs) a[k].rs=++cnt;
		a[a[k].ls].lazy=a[a[k].rs].lazy=-1;
		a[a[k].ls].size=0,a[a[k].rs].size=0;
		a[k].lazy=0;
	}
}
inline void insert(int l,int r,int &k,int head,int tail) {
	if (!k) k=++cnt;
	if (head<=l&&r<=tail) return a[k].size=r-l+1,a[k].lazy=1,void();
	Pushdown(l,r,k);
	int mid=l+r>>1;
	if (head<=mid) insert(l,mid,a[k].ls,head,tail);
	if (tail>mid)  insert(mid+1,r,a[k].rs,head,tail);
	Pushup(k);
}
inline void del(int l,int r,int &k,int head,int tail) {
	if (!k) k=++cnt;
	if (head<=l&&r<=tail) return a[k].size=0,a[k].lazy=-1,void();
	Pushdown(l,r,k);
	int mid=l+r>>1;
	if (head<=mid) del(l,mid,a[k].ls,head,tail);
	if (tail>mid)  del(mid+1,r,a[k].rs,head,tail);
	Pushup(k);
}
inline int rk(int l,int r,int &k,int head) {
	if (!k) return 0;
	if (l==r) return a[k].size;
	int mid=l+r>>1;Pushdown(l,r,k);
	if (head<=mid) return rk(l,mid,a[k].ls,head);
	else return a[a[k].ls].size+rk(mid+1,r,a[k].rs,head);
}
inline int query(int l,int r,int deep,int &k,int x) {
	if (!k) return 0;
	if (l==r) return 0;
	int mid=l+r>>1;Pushdown(l,r,k);
//	printf("query %d %d  %d %d %d ls=%d rs=%d\n",x,(x>>deep)&1,l,r,a[k].ls,a[a[k].ls].size,a[a[k].rs].size);
	if ((x>>deep)&1) {
		if (a[a[k].ls].size) return query(l,mid,deep-1,a[k].ls,x)+(1<<deep);
		else return query(mid+1,r,deep-1,a[k].rs,x);
	}
	else {
		if (a[a[k].rs].size) return query(mid+1,r,deep-1,a[k].rs,x)+(1<<deep);
		else return query(l,mid,deep-1,a[k].ls,x);
	}
}
const int maxdeep=29,MASK=(1<<30)-1;
signed main(void){
	int T,op,x,l,r;
	read(T);
	while (T--) {
		read(op);
		if (op==1) read(l),read(r),insert(0,MASK,root,l,r);
		else if (op==2) read(l),read(r),del(0,MASK,root,l,r);
		else if (op==3) read(x),printf("%d\n",rk(0,MASK,root,x)-rk(0,MASK,root,x-1));
		else if (op==4) read(x),printf("%d\n",(x==0?1:rk(0,MASK,root,x-1)+1));
		else read(x),printf("%d\n",query(0,MASK,maxdeep,root,x));
		
	}
    return 0;
}