NOIP2022模拟赛 9

这场好水，但是T3CE了（乐

T1

从大到小枚举因数，类似于埃式筛。

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
#include<bits/stdc++.h>
#define maxn 1000005
#define ll long long
#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;
int fa[maxn];
ll ans;
inline int gcd(int x,int y) {return y==0?x:gcd(y,x%y);}
inline int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
inline void merge(int x,int y) {
	int fx,fy;
    fx=getfa(x);fy=getfa(y);
    if (fx^fy) fa[fx]=fy,ans+=gcd(x,y);
}
signed main(void){
//	freopen("1.in","r",stdin);
	int i,j;
	read(n);
	for (i=1;i<=n;i++) fa[i]=i;
	for (i=n;i>=1;i--) 
		for (j=i*2;j<=n;j+=i)
		    merge(i,j);
	printf("%lld",ans);
 	return 0;
}

T2

记录下每个连通块是不是已经是基环树。

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
#include<bits/stdc++.h>
#define maxn 200005
#define int long long
#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,m;
int head=1,h[maxn];
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];
struct node{
	int x,y,z;
}g[maxn];
int cnt;
inline bool cmp(node x,node y) {
	return x.z>y.z;
}
int fa[maxn],vis[maxn];
inline int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
signed main(void){
//	freopen("1.in","r",stdin);
	int i,j,x,y,z,ans=0,las,fx,fy;
	read(n);read(m);
	for (i=1;i<=m;i++) {
		read(x);read(y);read(z);hjk  
		a[++head].add(x,y,z);
		a[++head].add(y,x,z); 
		g[i].x=x;g[i].y=y;g[i].z=z;
	}
	sort(g+1,g+1+m,cmp);
	for (i=1;i<=n;i++) fa[i]=i;
	for (i=1;i<=m;i++) {
		fx=getfa(g[i].x);fy=getfa(g[i].y);
		if (fx==fy&&vis[fx]==0) vis[fx]=1,ans+=g[i].z;
		else if (fx!=fy&&(vis[fx]==0||vis[fy]==0)) vis[fy]|=vis[fx],fa[fx]=fy,ans+=g[i].z;
	}
	printf("%lld",ans);
	return 0;
}

T3

排序后两个指针。或者扔到 multiset 里好像也可以。

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
#include<bits/stdc++.h>
#define maxn 500005
#define int long long
#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,m;
int a[maxn];
signed main(void){
//	freopen("1.in","r",stdin);
	int i,ans=0;
	read(n);read(m);
	for (i=1;i<=n;i++) read(a[i]);
	sort(a+1,a+1+n);
	int l=1,r=n;
	for (l=1;l<=n;l++) {
		if (l>=r) break;
		if (a[l]+a[r]>=m) r--,ans++;
		else continue;
	}
	printf("%lld",ans);
	return 0;
}