NOIP2022模拟赛 2

, ,

T1

令 $n=\prod p_i^{q_i}$
$$
ans=8(\prod p_i^{\left\lfloor\frac{q_i}{2}\right\rfloor} -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
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
#define maxn 
#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;
}
inline int div(int x,int n) {
	
}
signed main(void){ 
	int i,n,x;
	read(n);
	while (n) {
		int ans=0,x=n,sum=1,tmp=1;
		for (i=2;i*i<=n;i++) {
			int tot=0;
			if (x%i==0) {
				while (x%i==0) {
					tot++;
					if (tot%2==1) sum*=i;
					x/=i;
				}
				if (tot==1) tmp*=i;
			} 
		}
		if (x) sum*=x,tmp*=x;
	//	printf("%lld\n",sum);
		for (i=sum;i<n;i+=sum) {
			int x=tmp*(i/sum)*(i/sum)+tmp*((n-i)/sum)*((n-i)/sum);
			if ((x+n)%2==0) ans++;
		}
		printf("%lld\n",ans*8);
		read(n);
	}
	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
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
#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 h[maxn],head=1,n,m,d[maxn];
int fa[maxn][21],deep[maxn],dis[maxn],lg[maxn],id[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];
__int128 ans,pus;
inline void ins(int x,int y,int z) {
	a[++head].add(x,y,z);
	a[++head].add(y,x,z);
}
inline void dfs(int x,int pre) {
	int i;deep[x]=deep[pre]+1;fa[x][0]=pre;
	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);
}
inline int lca(int x,int y) {
	int i;
	if (deep[x]<deep[y]) swap(x,y);
	while (deep[x]>deep[y]) x=fa[x][lg[deep[x]-deep[y]]];
	if (x==y) return x;
	for (i=lg[deep[x]];i>=0;i--) if (fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
inline int D(int x,int y) {
	return dis[x]+dis[y]-2*dis[lca(x,y)];
}
int f[maxn],u[maxn],v[maxn],w[maxn];
inline int getfa(int x) {
	return x==f[x]?x:f[x]=getfa(f[x]);
}
inline bool cmp(int x,int y) {
	return d[x]>d[y];
}
inline void merge(int x,int y,int k) {
	//printf("%lld %lld  ",x,y);
	x=getfa(x),y=getfa(y);f[x]=y;
	//printf("%lld %lld\n",x,y);
	int tmp1=D(u[x],u[y]),tmp2=D(v[x],u[y]),tmp3=D(u[x],v[y]),tmp4=D(v[x],v[y]);
	int Max=max(tmp1,max(tmp2,max(tmp3,max(tmp4,max(w[x],w[y])))));
	int ans1=0,ans2=0;
	if (w[y]==Max) ans1=u[y],ans2=v[y];
	else if (w[x]==Max) ans1=u[x],ans2=v[x];
	else if (tmp1==Max) ans1=u[x],ans2=u[y];
	else if (tmp2==Max) ans1=v[x],ans2=u[y];
	else if (tmp3==Max) ans1=u[x],ans2=v[y];
	else if (tmp4==Max) ans1=v[x],ans2=v[y]; 
	u[y]=ans1,v[y]=ans2;w[y]=Max;
	pus=k;pus=pus*Max;
	ans=max(ans,pus);
}
inline void write(__int128 x){
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}
signed main(void){
	int i,x,y,z,j;
	read(n);
	for (i=1;i<=n;i++) read(d[i]),id[i]=i;
	for (i=2;i<=n;i++) lg[i]=lg[i/2]+1;
	for (i=1;i<n;i++) {
		read(x);read(y);read(z);
		ins(x,y,z);
	}
	dfs(1,0);
	sort(id+1,id+1+n,cmp);
	for (i=1;i<=n;i++) f[i]=u[i]=v[i]=i;
	for (i=1;i<=n;i++) {
		int x=id[i];
		//printf("case %lld\n",id[i]);
		for (j=h[x];j;j=a[j].z) {
		//	printf("%lld %lld\n",a[j].to,d[a[j].to]);
			if (d[a[j].to]>=d[x]) merge(x,a[j].to,d[x]);
		}
	}
	write(ans);
	return 0;
}

T3

EJOI 2017 骆驼

不会