2021 46届icpc 南京

A. Oops, It’s Yesterday Twice More

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

#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-k$ 考虑即可，将其存到一个 $vector$ 里
设 $sum[i][0]$ 是前i中x的个数，$sum[i][1]$ 是 $x-k$ 的个数。对每个 $[l,r]$，贡献是 $$sum[m][0]-(sum[r][0]-sum[l-1][0])+(sum[r][1]-sum[l-1][1])$$ 移下项就是 $$sum[m][0]+(sum[r][1]-sum[r][0])+(sum[l-1][0]-sum[l-1][1])$$ 之后就可以线性解决了。记录后一项 $l-1$ 的最大值，加上前面的取个 $max$

#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$，在 $i=1$ 的循环后，是将它的严格单增序列向后移一位，之后 $i=2...k$ 的贡献是前 $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]$ 就交换同时 $ans++$，然后对每个 $i$， $ans+=Sum$，树状数组做就可以了。

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

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

2 3 2 3 1 5

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

#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
树形 $dp$。$f[x]$ 记录子树 $x$ 得到的最优值；$g[x]$ 记录不取 $x$ 的孩子，也就是走到 $x$ 惊扰了 $x$ 的孩子但不去取他们，$g[x]=f[y_i]-a[y_i]，y_i$ 是 $x$ 的孩子。

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

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

#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)mod2H=k$（直线 $y=-x+k$ ），向右上移动的部分满足 $(2H-y+x)mod2H=k$（关于 $y=H$ 对称上去就是向右下了）。

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

#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$，$c=b-a$ 的值是确定的，而 $g$ 可以整除 $a$ 和 $b$，必定可以整除 $c$。

有 $(a,b,c)->(\frac{a}{g},\frac{b}{g},\frac{c}{g})$，其中 $a、b$是向上/下取整，也就是将 $a$ 加减到离 $g$ 最近的上/下倍数取个 $min$，当 $a=1$ 或 $c=1$ 时就返回了。

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

#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），直接加 $abs$ 就行。否则找下哪个 $i$ 可以构成正负且损失最小。

#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 46届icpc 南京所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。