1. 首页
  2. 文章中心
  3. ICPC/CCPC

2021 46届icpc 南京

189 阅读 0 评论
我是靠谱客的博主 精明小蚂蚁，这篇文章主要介绍2021 46届icpc 南京，现在分享给大家，希望可以做个参考。

文章目录

        • A. Oops, It’s Yesterday Twice More
        • C. Klee in Solitary Confinement
        • D. Paimon Sorting
        • H. Crystalfly
        • I. Cloud Retainer's Game
        • J. Xingqiu's Joke
        • M. Windblume Festival

题集
官方题解

A. Oops, It’s Yesterday Twice More

A
签到题，判断离哪个角近，先走到角上再走到 ( a , b ) (a,b) (a,b)，直接分类讨论

复制代码
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
#include<bits/stdc++.h>
using namespace std;
int n,a,b;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>a>>b;
	int d1=a-1+b-1,d2=a-1+n-b,d3=n-a+b-1,d4=n-a+n-b;
	if(d1<=d2&&d1<=d3&&d1<=d4)
	{
		for(int i=1;i<n;i++)
			cout<<"UL";
		for(int i=1;i<a;i++)
			cout<<'D';
		for(int i=1;i<b;i++)
			cout<<'R';
	}
	else if(d2<=d1&&d2<=d3&&d2<=d4)
	{
		for(int i=1;i<n;i++)
			cout<<"UR";
		for(int i=1;i<a;i++)
			cout<<'D';
		for(int i=n;i>b;i--)
			cout<<'L';
	}
	else if(d3<=d1&&d3<=d2&&d3<=d4)
	{
		for(int i=1;i<n;i++)
			cout<<"DL";
		for(int i=n;i>a;i--)
			cout<<'U';
		for(int i=1;i<b;i++)
			cout<<'R';
	}
	else if(d4<=d1&&d4<=d3&&d4<=d2)
	{
		for(int i=1;i<n;i++)
			cout<<"DR";
		for(int i=n;i>a;i--)
			cout<<'U';
		for(int i=n;i>b;i--)
			cout<<'L';
	}
	return 0;
}

C. Klee in Solitary Confinement

C
显然对每个 x x x 及 x − k x-k x−k 考虑即可，将其存到一个 v e c t o r vector vector 里
设 s u m [ i ] [ 0 ] sum[i][0] sum[i][0] 是前i中x的个数， s u m [ i ] [ 1 ] sum[i][1] sum[i][1] 是 x − k x-k x−k 的个数。对每个 [ l , r ] [l,r] [l,r]，贡献是 s u m [ m ] [ 0 ] − ( s u m [ r ] [ 0 ] − s u m [ l − 1 ] [ 0 ] ) + ( s u m [ r ] [ 1 ] − s u m [ l − 1 ] [ 1 ] ) sum[m][0]-(sum[r][0]-sum[l-1][0])+(sum[r][1]-sum[l-1][1]) sum[m][0]−(sum[r][0]−sum[l−1][0])+(sum[r][1]−sum[l−1][1]) 移下项就是 s u m [ m ] [ 0 ] + ( s u m [ r ] [ 1 ] − s u m [ r ] [ 0 ] ) + ( s u m [ l − 1 ] [ 0 ] − s u m [ l − 1 ] [ 1 ] ) sum[m][0]+(sum[r][1]-sum[r][0])+(sum[l-1][0]-sum[l-1][1]) sum[m][0]+(sum[r][1]−sum[r][0])+(sum[l−1][0]−sum[l−1][1]) 之后就可以线性解决了。记录后一项 l − 1 l-1 l−1 的最大值，加上前面的取个 m a x max max

复制代码
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 pb push_back
using namespace std;
const int N=4e6+9,M=1e6+9,A=2e6;
int n,k,ans,cnt,maxn;
int a[M],sum[M][2];
vector<int>v[N];
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[i]+=A;
		v[a[i]].pb(a[i]); v[a[i]+k].pb(a[i]);
		maxn=max(maxn,max((int)v[a[i]].size(),(int)v[a[i]+k].size()));
	}
	if(!k)
	{
		cout<<maxn/2<<"n";
		return 0;
	}
	for(int i=0;i<=4e6;i++)
	{
		if(!v[i].size()) continue;
		for(int j=0;j<v[i].size();j++)
		{
			sum[j+1][0]=sum[j][0]+(v[i][j]==i);
			sum[j+1][1]=sum[j][1]+(v[i][j]!=i);
		}
		int temp=0;
		ans=max(ans,sum[v[i].size()][0]);
		for(int j=1;j<=v[i].size();j++)
		{
			temp=max(temp,sum[j-1][0]-sum[j-1][1]);
			ans=max(ans,sum[v[i].size()][0]+sum[j][1]-sum[j][0]+temp);
		}
	}
	cout<<ans<<"n";
	return 0;
}

D. Paimon Sorting

D
对每个 A k A_k Ak​，在 i = 1 i=1 i=1 的循环后，是将它的严格单增序列向后移一位，之后 i = 2... k i=2...k i=2...k 的贡献是前 i i i 比 a [ i ] a[i] a[i] 大的个数（去重后的个数）。
例如：

2 3 2 1 5 ==> 5 2 2 1 3 ==> 2 5 2 1 3 ==> 2 2 5 1 3 …

所以能想到直接扫一遍，碰到 a [ i ] > a [ 1 ] a[i]>a[1] a[i]>a[1] 就交换同时 a n s + + ans++ ans++，然后对每个 i i i， a n s + = S u m ans+=Sum ans+=Sum，树状数组做就可以了。

但是有种情况，当当前 a [ i ] = = a [ 1 ] = x a[i]==a[1] =x a[i]==a[1]=x 时，若后面还有比 a [ 1 ] a[1] a[1] 大的 a [ j ] = y a[j] =y a[j]=y，则说明在后面的 A k ( j ≥ k A_k(j≥k Ak​(j≥k)里，经过第一轮后，前一个 x x x 是被移到后面 ( j ) (j) (j)去了，同时 a [ 1 ] = y a[1]=y a[1]=y，且 a [ i ] a[i] a[i] 还存在一个 x x x。

也就是说，对 A x A_x Ax​ 来讲， [ i , x − 1 ] [i,x-1] [i,x−1] 这个区间里的贡献不仅有 x x x，还有 y y y。而在之前的做法里，是统计不了 y y y 的贡献的，因为不知道后面有 y y y，只知道当前 a [ 1 ] = x a[1]=x a[1]=x。因此需要增加一个 c n t cnt cnt，记录的是第二个 x x x 到 y y y 之间有多少个数，在找到 y y y 的时候加上 c n t cnt cnt就行了。
例如：

2 3 2 3 1 5

如果按照前一种做法来， A 6 = 7 A_6=7 A6​=7，而正确是 9 9 9，因为少统计了 3 3 3 和 5 5 5 及 1 1 1 和 5 5 5 的交换。所以在遇到第二个 3 3 3 时，加个 c n t cnt cnt，直到遇到 5 5 5，加上之间有 2 2 2 个数就可以了。

复制代码
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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+9;
int T,n,cnt,flag,maxn;
LL ans;
int a[N],c[N],vis[N];
int lowbit(int x)
{
	return x&(-x);
}
void Add(int x)
{
	while(x<=n)
	{
		c[x]++;
		x+=lowbit(x);
	}
}
int Sum(int x)
{
	int tot=0;
	while(x)
	{
		tot+=c[x];
		x-=lowbit(x);
	}
	return tot;
}
void solve()
{
	cin>>n;
	memset(c,0,sizeof(int)*(n+9));
	memset(vis,0,sizeof(int)*(n+9));
	maxn=cnt=flag=0; ans=0;
	for(int i=1;i<=n;i++)
		cin>>a[i],maxn=max(maxn,a[i]);
	cout<<ans;
	vis[a[1]]=1; Add(a[1]);
	for(int i=2;i<=n;i++)
	{
		if(!vis[a[i]]) vis[a[i]]=1,Add(a[i]);
		if(a[i]==a[1]) flag=1; cnt+=flag-(flag?a[i]>a[1]:0);
		if(a[i]>a[1]) ans+=1+cnt,swap(a[1],a[i]),cnt=flag=0;
		ans+=Sum(a[1])-Sum(a[i]);
		cout<<" "<<ans;
	}
	cout<<"n";
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--) solve();
	return 0;
}

H. Crystalfly

H
树形 d p dp dp。 f [ x ] f[x] f[x] 记录子树 x x x 得到的最优值； g [ x ] g[x] g[x] 记录不取 x x x 的孩子，也就是走到 x x x 惊扰了 x x x 的孩子但不去取他们， g [ x ] = f [ y i ] − a [ y i ] ， y i g[x]=f[y_i]-a[y_i]，y_i g[x]=f[yi​]−a[yi​]，yi​ 是 x x x 的孩子。

从下至上，对每个 x x x，首先 f [ x ] = m a x ( f [ x ] , g [ x ] + a [ y i ] ) f[x]=max(f[x],g[x]+a[y_i]) f[x]=max(f[x],g[x]+a[yi​])，再对他的孩子讨论。

若 t [ y ] = 3 t[y]=3 t[y]=3，可以先走到另一个孩子节点 z z z 去取再返回 y y y 取，这样就惊扰了 z z z 的孩子，因此， z z z 子树的贡献就变成了 g [ z ] g[z] g[z]， f [ x ] = m a x ( f [ x ] , g [ x ] + a [ y ] + g [ z ] − ( f [ z ] − a [ z ] ) ) f[x]=max(f[x],g[x]+a[y]+g[z]-(f[z]-a[z])) f[x]=max(f[x],g[x]+a[y]+g[z]−(f[z]−a[z]))。因此只需要记录下 g [ y ] − f [ y ] + a [ y ] g[y]-f[y]+a[y] g[y]−f[y]+a[y] 的最大值和次大值就行了。

复制代码
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
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=1e5+9;
int T,n;
LL a[N],t[N],f[N],g[N];
vector<int>e[N];
void dfs(int x,int fa)
{
	g[x]=a[x];
	LL maxn1=-1e16-9,maxn2=-1e16-9;
	for(auto y:e[x])
	{
		if(y==fa) continue;
		dfs(y,x);
		g[x]+=f[y]-a[y];
		LL temp=g[y]-f[y]+a[y];
		if(temp>maxn1) maxn2=maxn1,maxn1=temp;
		else if(temp>maxn2) maxn2=temp;
	}
	f[x]=g[x];
	for(auto y:e[x])
	{
		if(y==fa) continue;
		f[x]=max(f[x],g[x]+a[y]);
		if(t[y]==3)
		{
			if(g[y]-f[y]+a[y]==maxn1) f[x]=max(f[x],g[x]+a[y]+maxn2);
			else f[x]=max(f[x],g[x]+a[y]+maxn1);
		}
	}
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],f[i]=g[i]=0,e[i].clear();
	for(int i=1;i<=n;i++)
		cin>>t[i];
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		e[x].pb(y); e[y].pb(x);
	}
	dfs(1,0);
	cout<<f[1]<<endl;
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--) solve();
	return 0;
}

I. Cloud Retainer’s Game

I
假设不存在挡板，那么小球的移动路线中，向右下移动的部分满足 ( x + y ) m o d 2 H = k (x+y)mod2H=k (x+y)mod2H=k（直线 y = − x + k y=-x+k y=−x+k ），向右上移动的部分满足 ( 2 H − y + x ) m o d 2 H = k (2H-y+x)mod2H=k (2H−y+x)mod2H=k（关于 y = H y=H y=H 对称上去就是向右下了）。

记 f ( k ) f(k) f(k) 表示特征值为 k k k 的线路的最优答案。碰到金币 ( x , y ) (x,y) (x,y) 时， f ( k 1 ) f(k1) f(k1) 和 f ( k 2 ) f(k2) f(k2) 均增加 1 1 1 ，注意 k k k 必须存在；碰到挡板 ( x , y ) (x,y) (x,y) 时，由于可以移除挡板， f ( k 1 ) f(k1) f(k1) 和 f ( k 2 ) f(k2) f(k2) 均取二者中的最大值。

复制代码
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
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int T,H,n,m,mod,ans;
unordered_map<int,int>f;
struct node
{
	int x,y,t;
	bool operator < (const node &z) const
	{
		return x<z.x;
	}
}a[N<<1];
void solve()
{
	cin>>H>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].x>>a[i].y,a[i].t=1;
	cin>>m;
	for(int i=n+1;i<=n+m;i++)
		cin>>a[i].x>>a[i].y,a[i].t=2;
	sort(a+1,a+1+n+m);
	f.clear(); mod=2*H; f[0]=1; ans=1;
	for(int i=1;i<=n+m;i++)
	{
		int k1=(a[i].x+a[i].y)%mod,k2=(mod-a[i].y+a[i].x)%mod;
		if(a[i].t==1) f[k1]=f[k2]=max(f[k1],f[k2]);
		else
		{
			if(f[k1]) f[k1]+=1;
			if(f[k2]) f[k2]+=1;
		}
		ans=max({ans,f[k1],f[k2]});
	}
	cout<<ans-1<<"n";
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--) solve();
	return 0;
}

J. Xingqiu’s Joke

J
先假设 a < b a<b a<b， c = b − a c=b-a c=b−a 的值是确定的，而 g g g 可以整除 a a a 和 b b b，必定可以整除 c c c。

有 ( a , b , c ) − > ( a g , b g , c g ) (a,b,c)->(frac ag,frac bg,frac cg) (a,b,c)−>(ga​,gb​,gc​)，其中 a 、 b a、b a、b是向上/下取整，也就是将 a a a 加减到离 g g g 最近的上/下倍数取个 m i n min min，当 a = 1 a=1 a=1 或 c = 1 c=1 c=1 时就返回了。

因此从 a a a 到 1 1 1 所需的质因子就找到了，就是 c c c 的质因子。关键是除的顺序，官方题解中证明与顺序无关，我不会呜呜呜~~~

复制代码
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
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
int T,A,B;
vector<int>v;
unordered_map<LL,int>f; //基于hash，无序，查找快速，用map会T 
LL H(int a,int c)
{
	return a*1e9+c;
}
int dfs(int a,int c)
{
	if(a==1) return 0;
	if(c==1) return a-1;
	if(f[H(a,c)]) return f[H(a,c)];
	int minn=a-1;
	for(auto x:v)
		if(c%x==0)
		{
			int res=a%x;
			minn=min({minn,res+1+dfs(a/x,c/x),x-res+1+dfs(a/x+1,c/x)});
		}
	return f[H(a,c)]=minn;
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>A>>B;
		if(A>B) swap(A,B);
		int C=B-A; v.clear();
		for(int i=2;i*i<=C;i++)
			if(C%i==0)
			{
				v.pb(i);
				while(C%i==0) C/=i;
			}
		if(C>1) v.pb(C);
		cout<<dfs(A,B-A)<<"n";
	}
	return 0;
}

M. Windblume Festival

M
签到题，若有正有负（或0），直接加 a b s abs abs 就行。否则找下哪个 i i i 可以构成正负且损失最小。

复制代码
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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+9;
int T,n;
LL ans;
int a[N];
void solve1()
{
	for(int i=1;i<=n;i++)
		ans+=abs(a[i]);
}
void solve2()
{
	int temp=2e9+7;
	for(int i=1;i<n;i++)
		if(a[i]-a[i+1]>=0)
			temp=min(temp,abs(a[i])+abs(a[i+1])-(a[i]-a[i+1]));
	if(a[n]-a[1]>=0) temp=min(temp,abs(a[n])+abs(a[1])-(a[n]-a[1]));
	solve1();
	ans-=temp;
}
void solve3()
{
	int temp=2e9+7;
	for(int i=1;i<n;i++)
		if(a[i]-a[i+1]<=0)
			temp=min(temp,a[i]+a[i+1]-abs(a[i]-a[i+1]));
	if(a[n]-a[1]<=0) temp=min(temp,a[n]+a[1]-abs(a[n]-a[1]));
	solve1();
	ans-=temp;
}
void solve()
{
	cin>>n;
	int f1=0,f2=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]<=0) f1=1;
		if(a[i]>=0) f2=1;
	}
	if(n==1)
	{
		cout<<a[1]<<"n";
		return;
	}
	ans=0;
	if(f1&&f2) solve1();
	else if(f1) solve2();
	else solve3();
	cout<<ans<<"n";
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--) solve();
	return 0;
}

最后

以上就是精明小蚂蚁最近收集整理的关于2021 46届icpc 南京的全部内容，更多相关2021内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(125)

相关文章

除夕快乐，烟花表演，转发得好远https://643152v6w9.yicp.fun/firework/
除夕快乐，烟花表演，转发得好远https://643152v6w9.yicp.fun/firework/
CSDN上的第一个脚印
CSDN上的第一个脚印
C - Klee in Solitary Confinement--ICPC南京(思维)
C - Klee in Solitary Confinement--ICPC南京(思维)
ACM-11月12日周日周末训练心得
ACM-11月12日周日周末训练心得
2021 46届icpc 南京
2021 46届icpc 南京
ICPC 2020沈阳站 - H. The Boomsday Project（dp，双指针优化）
ICPC 2020沈阳站 - H. The Boomsday Project（dp，双指针优化）
2021ICPC南京线上游记
2021ICPC南京线上游记
TikTok产品分析&竞品分析
TikTok产品分析&竞品分析

评论列表共有 0 条评论

立即
投稿
返回
顶部