Reincarnation

正因为梦易碎，才格外美好。

长沙一中集训 模拟赛1

发表于 更新于 分类于 ，
本文字数： 11k 阅读时长 ≈ 10 分钟

场。

A. 树（tree）

题目简介

给定一棵有 个结点的无根树，定义度数为 的结点为叶结点，每次操作选择 个叶结点并删除其路径上所有的边，直到无法操作为止。

求出最少的操作次数。

数据范围：

贪心是坏文明。

考虑子树，那么能够向上传递的最多只有 个叶结点，所以我们按照叶结点个数 讨论：

  • 如果有 个叶结点的子树大于 个，那么其内部两两匹配。
  • 如果存在 棵及以上的有 个叶结点的子树，那么其内部自匹配。
  • 如果存在 个有 个叶结点的子树以及 棵有 个叶结点的子树，那么其匹配。

注意因为有第 种匹配方式，所以我们需要保留 棵有 个叶结点的子树。

时间复杂度 。

AC 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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=5e5+10;
int N;
struct G
{ int next,to; }Edge[MAXN<<1];
int Head[MAXN],Deg[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;++Deg[u];
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;++Deg[v];
}
int Fa[MAXN],Siz[MAXN],Son[MAXN],Dep[MAXN];
int Leafcnt[MAXN],Depmax[MAXN],ans;
bool Tar[MAXN],Leaf[MAXN];
void dfsTree(int x,int last)
{
	Fa[x]=last,Siz[x]=1,Son[x]=0,Dep[x]=Dep[last]+1;
	Leafcnt[x]=Depmax[x]=0,Leaf[x]=0;
	bool leaf=0;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		if(Tar[v]){ leaf=1;continue; }
		dfsTree(v,x);
		Siz[x]+=Siz[v],Leafcnt[x]+=Leafcnt[v];
		checkMax(Depmax[x],Depmax[v]);
		if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
	}
	if(!Son[x]&&!leaf) Leafcnt[x]=1,Depmax[x]=Dep[x],Leaf[x]=1;
}
int maxdis,fir,sec;
void getFar(int x,int last,int &tar,int dis)
{
	if(Leaf[x]&&checkMax(maxdis,dis)) tar=x;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last||Tar[v]) continue;
		getFar(v,x,tar,dis+1);
	}
}
inline void getTarget(int rt,int u,int v,std::vector<int>&vec)
{
	vec.clear();
	while(u!=rt) Tar[u]=1,vec.push_back(u),u=Fa[u];
	while(v!=rt) Tar[v]=1,vec.push_back(v),v=Fa[v];
	Tar[rt]=1;
}
void solve(int x)
{
	dfsTree(x,0);
	maxdis=-1;
	getFar(x,0,fir,0);
	maxdis=-1;
	getFar(fir,0,sec,0);
	if(fir==sec) return ;
	++ans;
	std::vector<int>leaf;
	getTarget(x,fir,sec,leaf);
	// write(x,'\n',fir,' ',sec,'\n');
	// for(int u:leaf) write(u,' ');
	// puts("");
	for(int u:leaf)
	{
		dfsTree(u,0);
		// write(u,' ',Son[u],' ',Leafcnt[u],' ',Depmax[u],'\n');
		if(!Son[u]) continue;
		if(Depmax[u]<=2)
		{
			ans+=Leafcnt[u]>>1;
			continue;
		}
		if(Leafcnt[u]>1) solve(u);
	}
}
int dpTree(int x,int last)
{
	int cnt1=0,cnt2=0;
	bool leaf=1;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		int v0=dpTree(v,x);leaf=0;
		if(v0==1) ++cnt1;
		else if(v0==2) ++cnt2;
	}
	if(leaf) return 1;
	if(cnt1>2)
	{
		ans+=cnt1>>1,cnt1&=1;
		if(!cnt1) cnt1+=2,--ans;
	}
	if(cnt2>1) ans+=cnt2>>1,cnt2&=1;
	if(!cnt1&&!cnt2) return 0;
	if(!cnt1) return 2;
	if(!cnt2) return cnt1;
	if(cnt1==1&&cnt2==1) return 2;
	++ans;
	return 1;
}
int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	read(N);
	for(int i=2,u,v;i<=N;++i) read(u,v),addEdge(u,v);
	for(int rt=1;rt<=N;++rt) if(Deg[rt]>1){ ans+=dpTree(rt,0)==2;break; }
	write(ans);
	return 0;
}
/*

*/

B. 最大公约数（gcd）

题目简介

原题链接：https://codeforces.com/problemset/problem/1305/F

给定一个长度为 的序列 ，每次操作可以选择 个 ，求最少的操作使得整个序列的 。

数据范围：

牛的题，可以的，总司令。出题人用 造数据。

首先考虑暴力，枚举一个质因数并 求解。时间复杂度 。

考虑答案上界一定是 （将所有数修改为 的倍数），于是输出 就可以切掉这道题。

然后考虑因为答案上界是 ，所以修改了 次的位置一定不超过 ，反过来讲就是只修改了 次的位置 个。所以最终的 一定是 之中一个的因数。

所以我们随机 个位置，然后分解 的质因数作为备选，然后对这些质因数求答案即可。由于上面的分析，这样做错误的概率为 ，所以 左右就可以了。

时间复杂度 。

AC 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
// ----- Eternally question-----
// Problem: F. Kuroni and the Punishment
// Contest: Codeforces - Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!)
// URL: https://codeforces.com/problemset/problem/1305/F
// Memory Limit: 256 MB
// Time Limit: 2500 ms
// Written by: Eternity
// Time: 2023-10-23 15:53:44
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
int N;
ll a[MAXN];
std::vector<ll>pri;
std::mt19937 rnd((ll)new char);
inline void apart(ll x)
{
	for(ll i=2;i*i<=x;++i)
		if(x%i==0)
		{
			pri.push_back(i);
			while(x%i==0) x/=i;
		}
	if(x>1) pri.push_back(x);
}
inline ll solve(ll x)
{
	ll sum=0;
	for(int i=1;i<=N;++i) sum+=a[i]<x?x-a[i]:std::min(((a[i]-x)%x+x)%x,((x-a[i])%x+x)%x);
	return sum;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(a[i]);
	for(int cnt=30;cnt--;)
	{
		int pos=rnd()%N+1;
		apart(a[pos]-1),apart(a[pos]),apart(a[pos]+1);
	}
	std::sort(pri.begin(),pri.end());
	pri.erase(std::unique(pri.begin(),pri.end()),pri.end());
	ll ans=N;
	for(ll x:pri) checkMin(ans,solve(x));
	write(ans);
	return 0;
}
/*

*/

博弈（game）

题目简介

原题链接：https://codeforces.com/problemset/problem/914/H

先后手博弈，先手首先构造一棵有 个结点的带标号树，要求任意结点度数不超过 ，后手选择其中两个结点 ，并将 的路径写作一个序列。记为 ，最后先手可以选择执行一次操作，二者取一：

  • 翻转 ，并全部加上 。
  • 取负 ，并全部加上 。

若最后序列 严格单调，则先手胜，否则后手胜。

求对于五元组 （ 表示树的形态， 表示操作类型），统计先手胜的方案数。对 取模。

数据范围：

还没改，别急。

D. 序列（sequence）

题目简介

给定 个可重数 ，构造其排列使得 最大。。

数据范围：

对 排序，分讨 的奇偶。

  • 若 为偶数，则形式一定类似 的形式，可以直接构造。
  • 若 为奇数，答案⼀定是先取⼀个连续段依次放在所有奇数位上，剩下的从连续段后⼀个开始，循环放置在偶数位上，那么最优答案应该是连续段⾸尾差值最小的那种放置⽅式，因为这个放置⽅式实际上是断开了连续段⾸尾项，那么任何⼀个⾮最优的放置⽅式，⼀定意味着其答案小于等于最优放置⽅式的⾸尾差值，明显不优。

太麻烦？长沙一中的老哥有更厉害的做法。

我们把整个序列分成 ，两部分内部匹配显然不优于相互匹配。相差较近匹配显然不优于较远匹配。

所以我们让左边最右匹配右边最右匹配，右边最右匹配左边第二右，以此类推即可。时间复杂度 。

保留了考场上模拟退火的代码。

AC 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
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
template<class T>
inline T abs(T x){ return x<0?-x:x; }
const int MAXN=2e5+10;
const int Inf=0x3f3f3f3f;
const double T0=1e4,TE=1e-4,Tk=0.997;
std::mt19937 rnd((ll)new char);
int N,a[MAXN],ans[MAXN],tmp[MAXN];
int res;
inline int calc()
{
	int sum=Inf;
	for(int i=1;i<N;++i) checkMin(sum,abs(tmp[i]-tmp[i+1]));
	return sum;
}
inline void copy()
{
	for(int i=1;i<=N;++i) tmp[i]=ans[i];
	return ;
}
inline void simulate()
{
    for(double T=T0;T>TE;T*=Tk)
    {
        if((double)clock()/CLOCKS_PER_SEC>=0.85)
        {
        	write(res,'\n');
        	for(int i=1;i<=N;++i) write(tmp[i],' ');
            exit(0);
        }
        int pos1=rand()%N+1,pos2=rand()%N+1;
        std::swap(ans[pos1],ans[pos2]);
        int nowres=calc();
        if(nowres>res) res=nowres,copy();
        else if(exp((double)(nowres-res)/T)*RAND_MAX<=rand()) std::swap(ans[pos1],ans[pos2]);
    }
}		
inline void solve()
{
	int mid=(N+1)>>1,tot=mid;
	for(int i=1;i<=N;i+=2) tmp[i]=a[tot--];
	tot=N;
	for(int i=2;i<=N;i+=2) tmp[i]=a[tot--];	
}
int main()
{
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	srand(time(NULL));
	for(int i=1;i<=10;++i) srand(rand());
	read(N);
	for(int i=1;i<=N;++i) read(a[i]);
	std::sort(a+1,a+N+1);
	solve();
	// write(calc(),'\n');
	for(int i=1;i<=N;++i) write(tmp[i],' ');
	return 0;
	int tot=0;
	for(int i=1;i<=N;i+=2) ans[i]=a[++tot];
	for(int i=2;i<=N;i+=2) ans[i]=a[++tot];
	res=calc(),copy();
	while((double)clock()/CLOCKS_PER_SEC<=0.80) simulate();
	write(res,'\n');
	for(int i=1;i<=N;++i) write(tmp[i],' ');
	return 0;
}
/*

*/
相关文章