test20191113

发表于

闲扯

今天的 $T1$ 是考英语的？？？

题面

题面

$T1$

Solution

打表，发现答案为 $\frac{n!}{2}$ ，其中 $n=1$ 时，是特例，答案为 $1$ .

但是由于需要输出序数词，然后我光荣暴毙。

分以下几种情况讨论：

  1. $n\%100\in[11,19]$ 跟 $th$ 。
  2. $n\%10=1$ 跟 $st$ 。
  3. $n\%10=2$ 跟 $nd$ 。
  4. $n\%10=3$ 跟 $rd$ 。
  5. 其余的都是 $th$ 。

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 1e5+5,mod = 1e9+7;
int n,ans=1;
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
it mul(int x,int y){return 1ll*x*y%mod;}
int main(){
	freopen("problem1.in","r",stdin);
	freopen("problem1.out","w",stdout);
	read(n);
	if(n==1) return puts("The 1st answer is 1."),0;
	if(n==2) return puts("The 2nd answer is 1."),0;
	for(ri i=3;i<=n;++i) ans=mul(ans,i);
	printf("The %d",n);
	if(n%100>=11&&n%100<=19) printf("th answer is %d.",ans);
	else if(n%10==1) printf("st answer id %d.",ans);
	else if(n%10==2) printf("nd answer is %d.",ans);
	else if(n%10==3) printf("rd answer is %d.",ans);
	else printf("th answer is %d.",ans);
	return 0;
}

$T2$

Solution

最开始我写了一个链表，然后发现写挂了，就改成了启发式合并，虽然多了一个 $\log$ ，但是常数不大，可以通过。

对于修改操作，我们维护一个全局的 $tag$ 。

在加入一个新元素时，我们加入的值为 $val-tag$ 。

查询时，答案为 $val+tag$ 。

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
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 1e6+5,mod = 1e9+7;
int n,m,opt,x,y,head[MAXN],tail[MAXN],cnt,tag[MAXN],sz[MAXN];
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
struct Node{
	int pre,next,val;
	Node(){}
	Node(int pre,int next,int val):pre(pre),next(next),val(val){}
}node[MAXN*20];
il Insert(int x,int y,int ty){
	++sz[x];
	if(ty==1){
		node[++cnt]=Node(0,0,add(y,mod-tag[x]));
		if(!head[x])
			head[x]=tail[x]=cnt;
		else
			node[cnt].next=head[x],node[head[x]].pre=cnt,head[x]=cnt;
	}
	else{
		node[++cnt]=Node(0,0,add(y,mod-tag[x]));
		if(!tail[x])
			head[x]=tail[x]=cnt;
		else
			node[tail[x]].next=cnt,node[cnt].pre=tail[x],tail[x]=cnt;
	}
}
il Delete(int x,int ty){
	--sz[x];
	if(ty==1){
		printf("%d\n",add(node[head[x]].val,tag[x]));
		if(node[head[x]].next)
			head[x]=node[head[x]].next,node[head[x]].pre=0;
		else
			head[x]=tail[x]=0;
	}
	else{
		printf("%d\n",add(node[tail[x]].val,tag[x]));
		if(node[tail[x]].pre)
			tail[x]=node[tail[x]].pre,node[tail[x]].next=0;
		else
			head[x]=tail[x]=0;
	}
}
il Updata(int x,int y){
	tag[x]=add(tag[x],y);
}
il Merge(int x,int y){
	if(!head[y]) return ;
	if(!head[x]){
		head[x]=head[y],tail[x]=tail[y],tag[x]=tag[y],sz[x]=sz[y];
		head[y]=tail[y]=0,sz[y]=0;
	}
	else{
		if(sz[x]<sz[y]){
			for(ri i=tail[x];i;i=node[i].pre)
				Insert(y,add(node[i].val,tag[x]),1);
			head[x]=head[y],tail[x]=tail[y],tag[x]=tag[y],sz[x]=sz[y];
			head[y]=tail[y]=0,sz[y]=0;
		}
		else{
			for(ri i=head[y];i;i=node[i].next)
				Insert(x,add(node[i].val,tag[y]),2);
			head[y]=tail[y]=0,sz[y]=0;
		}
	}
}
int main(){
	freopen("problem2.in","r",stdin);
	freopen("problem2.out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=m;++i){
		read(opt);
		if(opt==1) read(x),read(y),Insert(x,y,1);
		if(opt==2) read(x),Delete(x,1);
		if(opt==3) read(x),read(y),Insert(x,y,2);
		if(opt==4) read(x),Delete(x,2);
		if(opt==5) read(x),read(y),Updata(x,y);
		if(opt==6) read(x),read(y),Merge(x,y);
	}
	return 0;
}

$T3$

Solution

看到这道题，我们有一个显然的想法：求出点为根结点的答案，然后取一个 $\min$ 作为最终答案。

考虑换根。

设当前以 $u$ ，为根结点，要转移到 $v$ 这个节点上。

对于 $v$ 的子树中的点，它们的贡献由 $\sum dis^2$ 变为了 $\sum (dis-w)^2$ 。其中 $dis$ 表示到根结点的距离， $w$ 为这条边的权值。

可以发现答案增加了 $w^2\cdot sz_v-2w\cdot\sum dis$ 。

同理，对于其他点，答案增加了 $w^2\cdot(tot-sz_v)+2w\cdot (sum-\sum dis)$ 。

其中 $tot,sum$ 分别表示总的选手数和所有点到当前根结点的距离之和。

我们动态维护一下 $sum$ 即可 $O(n)$ 处理出所有点的答案。

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 2e5+5;
int n,val[MAXN],u,v,d,head[MAXN],num_edge,sz[MAXN],tot;
long double ans,now,dis[MAXN],sum[MAXN],sum1;
struct Edge{
	int next,to,dis;
	Edge(){}
	Edge(int next,int to,int dis):next(next),to(to),dis(dis){}
}edge[MAXN<<1];
il add_edge(int u,int v,int dis){
	edge[++num_edge]=Edge(head[u],v,dis),head[u]=num_edge;
	edge[++num_edge]=Edge(head[v],u,dis),head[v]=num_edge;
}
il DFS1(int u,int fa){
	sz[u]=val[u];
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==fa) continue;
		dis[edge[i].to]=dis[u]+edge[i].dis;
		DFS1(edge[i].to,u),sz[u]+=sz[edge[i].to];
	}
}
il DFS2(int u,int fa){
	sum[u]=dis[u]*val[u];
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==fa) continue;
		DFS2(edge[i].to,u),sum[u]+=sum[edge[i].to];
	}
}
il DFS(int u,int fa){
	ans=min(now,ans);
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==fa) continue;
		long double w=edge[i].dis,tmp=now;
		now+=pow(w,2)*sz[edge[i].to]-2*w*(sum[edge[i].to]-sz[edge[i].to]*dis[u]);
		now+=pow(w,2)*(tot-sz[edge[i].to])+2*w*(sum1-sum[edge[i].to]+sz[edge[i].to]*dis[u]);
		sum1+=1.*edge[i].dis*(tot-2*sz[edge[i].to]);
		DFS(edge[i].to,u),now=tmp;
		sum1-=1.*edge[i].dis*(tot-2*sz[edge[i].to]);
	}
}
int main(){
	freopen("problem3.in","r",stdin);
	freopen("problem3.out","w",stdout);
	read(n);
	for(ri i=1;i<=n;++i) read(val[i]),tot+=val[i];
	for(ri i=1;i<n;++i) read(u),read(v),read(d),add_edge(u,v,d);
	DFS1(1,0),DFS2(1,0);
	for(ri i=2;i<=n;++i)
		ans+=val[i]*pow(dis[i],2),sum1+=dis[i]*val[i];
	now=ans,DFS(1,0);
	printf("%.7Lf",ans);
	return 0;
}