2022中国大学生程序设计竞赛（CCPC）高职专场_ccpc真题

一，期望

题意：

• 初始时你有1−n这n个正整数和一个空的序列，你准备玩一个往序列中加数字的无聊游戏。
• 游戏进行n轮,在游戏的每一轮中你要向序列尾部加入一个还未被加入的数，最终的序列将会是一个长度为n的排列。
• 在某一轮游戏开始前，令此时所有未被加入的数的和是sum,那么这一轮加入一个未被加入的数x的概率是sumx​。
• 求最终序列逆序对个数的期望，答案对109+7取模。
• 对于一个序列a1​,a2​,...,an​,对于(i,j)满足,ai​>aj​且1≤i<j≤n,则称(ai​,aj​)是一对逆序对。

思路：

1. 考虑一对逆序对(i,j)在所有排列下出现的期望。发现显然i出现在j前面，与其他数无关，所以所有排列下i出现在j前面的期望都是
2. 所以答案就是所有逆序对的期望相加。观察出相加实际就是等差数组求和

#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define endl             "\n"
#define int              long long
const int N = 3e5 + 10;
const int mod=1e9+7;
 
ll fastmi(ll base, ll power)
{
	ll ans = 1;
	while (power)
		{
			if (power & 1)ans=ans*base%mod;
			base=base*base%mod;
			power >>=1;
		}
	return ans;
}
 
void mysolve()
{
	int n;
	cin>>n;
	int ans=0;
	for(int i=3; i<=2*n-1; ++i)
		ans=(ans+((min(i-1,n)+i/2+1)*(min(i-1,n)-i/2)/2)%mod*fastmi(i,mod-2)%mod)%mod;
	cout<<ans<<endl;
}
 
int32_t main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll t=1;
	//cin >> t;
	while (t--)
		{
			mysolve();
		}
	system("pause");
	return 0;
}

重排数组

题意

• 给定一个长度为n的数组a1​,a2​,...,an​,定义一个数组的权值为将数按照下标顺序拼接在一起
• 例如：一个长度为3的数组a1​=11,a2​=12,a3​=2,那么数组的权值为11122
• 现在要求出数组a的所有排列的权值和，答案对109+7取模
• 对于长度为n的数组有n!种排列，例如对于a1​,a2​,a3​来说，有6种排列分别是:a1​,a2​,a3​ ; a1​,a3​,a2​ ; a2​,a1​,a3​ ; a2​,a3​,a1​ ; a3​,a1​,a2​ ; a3​,a2​,a1​.

思路：

1. ai在每个排列的贡献，取决有前面的有多少个元素
2. 设dp[i][j]为前i个元素，处理了j个在前面产生的贡献，如果我们求出来dp[i][j]。显然ai前面有k个元素时，他的贡献就是A[k]*ai*dp[i][k]*A[n-1-k](A[]为排列数)
3. 怎么算dp的贡献呢，显然每个元素的贡献取决有他有多少位，设元素p有b位，显然有转移方程式(无论他插在j个元素里的哪个位置，显然都是使dp[i][j]的贡献在10进制上左移了b位（即*10^b)
4. 因为每个数讨论前面的数的情况是不能有他自己的，显然我们每个元素都要自己做一次dp，用背包优化可以设当降低复杂度

#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define endl             "\n"
#define int              long long
typedef pair<int, int> pii;
const int N = 2000+20;
 
int mycnt(int x)
{
	int ans=0;
	while(x)ans++,x/=10;
	return ans;
}
const int mod=1e9+7;
pii a[N];
int pre[N],A[N];//pre表示10的几次幂，A是排列数
void mysolve()
{
	int n;
	cin>>n;
	for(int i=1; i<=n; ++i)cin>>a[i].first,a[i].second=mycnt(a[i].first);
	int ans=0;
	for(int i=1; i<=n; ++i)
		{
			vector<int>dp(n+1);//讨论当前元素a[i]在所有排列的总贡献，先给他处理下dp
			dp[0]=1;
			for(int j=1,p=0; j<=n; ++j)if(i!=j)//背包优化
					{
						p++;//p表示处理了p个数
						for(int k=p; k; --k)dp[k]=(dp[k]+dp[k-1]*pre[a[j].second]%mod)%mod;
					}
			for(int j=0; j<n; ++j)//枚举ai前面有几个元素的情况时的贡献
				ans=(ans+a[i].first*A[n-j-1]%mod*dp[j]%mod*A[j]%mod)%mod;
		}
	cout<<ans<<endl;
}
 
int32_t main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	pre[0]=1,A[0]=1;
	for(int i=1; i<=2000; ++i)pre[i]=pre[i-1]*10%mod,A[i]=A[i-1]*i%mod;
	mysolve();
	system("pause");
	return 0;
}

寻宝

题意

• 探险队获得了一张藏宝图，藏宝图中有n个洞穴，还有n−1条道路连通这n个洞穴，对于任意两个不同的洞穴，都可以通过道路相互到达。
• 在藏宝图中，一些洞穴里被标记有宝藏。
• 探险队决定选取一些有宝物的洞穴作为寻宝计划，他们会从寻宝计划中的一个洞穴出发，依次到达每个寻宝计划中其他的洞穴收集宝物，最后再回到出发的洞穴，在这个过程中，他们会选择路程最少的寻宝路线。可以证明，无论从寻宝计划中的哪个洞穴出发，最终的最小路程都是相同的。
• 一次探险的路程是探险中经过的道路数量。
• 现在你需要计算对于每个k(1≤k≤n),在探险队任选k个有宝物的洞穴作为寻宝计划时，他们要走的最小路程最多是多少，最少是多少？

思路：

1. 树上dp，以最大值为例，dp[u][k]维护好处理到子树u，k个宝藏的最长距离。
2. 而答案就是每次子树给入父节点时更新答案

#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define endl             "\n"
const int INF = 0x3f3f3f3f;         //int型的INF
const double eps=1e-9;
const int N = 3e3 + 10;
 
vector<int>edge[N];
int mxans[N],mnans[N],mxdp[N][N],mndp[N][N],sz[N];
bool a[N];
int n;
void dfs(int u,int f)
{
	sz[u]=1;
	for(auto v:edge[u])if(v!=f)
			{
				dfs(v,u);
				for(int i=sz[u]; ~i; --i)for(int j=sz[v]; j; --j)
						{
							mxdp[u][i+j]=max(mxdp[u][i+j],mxdp[u][i]+mxdp[v][j]+2);
							mndp[u][i+j]=min(mndp[u][i+j],mndp[u][i]+mndp[v][j]+2);
							if(i)
								{
									mxans[i+j]=max(mxans[i+j],mxdp[u][i]+mxdp[v][j]+2);//这里不写mxdp[u][i+j],因为u的i+j是可以由i=0，j>0更新得到，但是子树合并必须ij均大于0合并，才算是最短路径的最大值，否者不符合最短路径的定义
									mnans[i+j]=min(mnans[i+j],mndp[u][i]+mndp[v][j]+2);
								}
						}
				sz[u]+=sz[v];
			}
}
void mysolve()
{
 
	cin>>n;
	for(int i=1; i<=n; ++i)
		{
			mxans[i]=-INF;
			mnans[i]=INF;
			for(int j=1; j<=n; ++j)mxdp[i][j]=-INF,mndp[i][j]=INF;
		}
	for(int i=1; i<=n; ++i)
		{
			cin>>a[i];
			if(a[i])mxdp[i][1]=mndp[i][1]=0,mxans[1]=mnans[1]=0;
		}
	int x,y;
	for(int i=1; i<n; ++i)cin>>x>>y,edge[x].push_back(y),edge[y].push_back(x);
	dfs(1,0);
	for(int i=1; i<=n; ++i)
		{
			if(mxans[i]>=0)cout<<mxans[i]<<" "<<mnans[i]<<endl;
			else
				cout<<-1<<" "<<-1<<endl;
		}
}
 
int32_t main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll t=1;
	//cin >> t;
	while (t--)
		{
			mysolve();
		}
	system("pause");
	return 0;
}

数三角形

题意：

• 作为一名学霸，当然要学会数数，不仅要会数正方体，也要会数三角形。
• 在二维平面上存在位置互不相同的n个点，这些点的横纵坐标均为整数,第i个点的坐标为(ai​,bi​)。你需要计算存在多少个三元组(i,j,k)(1≤i<j<k≤n)满足i,j,k三个点可以构成面积大于0的等腰三角形。
• 当然了,为了简化一些计算量，本题还满足一个特殊性质：这n个点仅存在于两条距离不超过10的平行于x轴的直线上。

思路：

1. 首先清楚三角形有2种，一种有一条腰在线上，一种是两条腰都不在线上。显然这两种不冲突（因为格点上不存在等边三角形）
2. 第一种情况，如果腰只有一条不在线上，那么首先他是完全平方数，而可以匹配的完全平方数的对数是很少的，这个可以暴力枚举
3. 对于第二种情况，需要枚举i+j=2*k,暴力是O(n)，发现ai<=1e5，那么用NNT实现nlogn求寻i+j的各种组合数

#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define int              long long
typedef pair<int, int> pii;
const int N = 3e5 + 10,G = 3, Gi = 332748118;
const int mod=998244353;
 
vector<pii>pre[15];
int limit,L;
int r[N];
void init()
{
	pre[3].push_back({4,5+4});
	pre[4].push_back({3,5+3});
	pre[5].push_back({12,13+12});
	pre[6].push_back({8,10+8});
	pre[7].push_back({24,25+24});
	pre[8].push_back({6,10+6});
	pre[8].push_back({15,17+15});
	pre[9].push_back({12,15+12});
	pre[9].push_back({40,41+40});
	pre[10].push_back({24,26+24});
}
 
ll fastmi(ll base, ll power)
{
	ll ans = 1;
	while (power)
		{
			if (power & 1)ans=ans*base%mod;
			base=base*base%mod;
			power >>=1;
		}
	return ans;
}
 
inline void NTT(ll *A, int type)
{
	for(int i = 0; i < limit; i++)
		if(i < r[i]) swap(A[i], A[r[i]]);
	for(int mid = 1; mid < limit; mid <<= 1)
		{
			ll Wn = fastmi( type == 1 ? G : Gi, (mod - 1) / (mid << 1));
			for(int j = 0; j < limit; j += (mid << 1))
				{
					ll w = 1;
					for(int k = 0; k < mid; k++, w = (w * Wn) % mod)
						{
							int x = A[j + k], y = w * A[j + k + mid] % mod;
							A[j + k] = (x + y) % mod,
							           A[j + k + mid] = (x - y + mod) % mod;
						}
				}
		}
}
 
ll aa[N],bb[N];
void mysolve()
{
	vector<int>a1,b1;
	unordered_map<int,int>a,b;
	int n,A,B;
	cin>>n>>A>>B;
	int x1,y1;
	for(int i=1; i<=n; ++i)
		{
			cin>>x1>>y1;
			if(y1==A)a[x1]=1,a1.push_back(x1);
			else b[x1]=1,b1.push_back(x1);
		}
	int ans=0;
	int d=abs(A-B);
	sort(a1.begin(),a1.end()),sort(b1.begin(),b1.end());
 
	for(auto v:a1)//暴力枚举第一种
		{
			for(pii u:pre[d])
				{
					if(b.count(v+u.first)&&b.count(v+u.second))ans++;
					if(b.count(v-u.first)&&b.count(v-u.second))ans++;
					if(b.count(v+u.first)&&b.count(v-(u.second-2*u.first)))ans++;
					if(b.count(v-u.first)&&b.count(v+(u.second-2*u.first)))ans++;
				}
			if(b.count(v+d)&&b.count(v))ans++;
			if(b.count(v-d)&&b.count(v))ans++;
			ans%=mod;
		}
	for(auto v:b1)
		{
			for(pii u:pre[d])
				{
					if(a.count(v+u.first)&&a.count(v+u.second))ans++;
					if(a.count(v-u.first)&&a.count(v-u.second))ans++;
					if(a.count(v+u.first)&&a.count(v-(u.second-2*u.first)))ans++;
					if(a.count(v-u.first)&&a.count(v+(u.second-2*u.first)))ans++;
				}
			if(a.count(v+d)&&a.count(v))ans++;
			if(a.count(v-d)&&a.count(v))ans++;
			ans%=mod;
		}
 
	limit=1,L=0;//NNT计算i+j枚举后各个数的出现次数
	while(limit<=2e5)limit<<=1,L++;
	for(int i = 0; i < limit; i++)
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
	for(int i=0; i<=1e5; ++i)
		{
			if(a[i])aa[i]=1;
			if(b[i])bb[i]=1;
		}
	NTT(aa,1),NTT(bb,1);
	for(int i=0; i<limit; ++i)aa[i]=aa[i]*aa[i]%mod,bb[i]=bb[i]*bb[i]%mod;//多项式a*a
	NTT(aa,-1),NTT(bb,-1);
	ll inv=fastmi(limit,mod-2);
	for(int i=0; i<=2e5; ++i)aa[i]=aa[i]*inv%mod,bb[i]=bb[i]*inv%mod;
 
	int res=0;
	for(int i=0; i<=1e5; ++i)
		{
			if(a[i])res+=bb[i<<1]-b[i];//减去i+i的情况
			if(b[i])res+=aa[i<<1]-a[i];
		}
	ans=(ans+res/2)%mod;//因为i+j与j+i各自算了一次，要除2
	cout<<ans<<endl;
}
 
int32_t main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll t=1;
	//cin >> t;
	while (t--)
		{
			init();
			mysolve();
		}
	system("pause");
	return 0;
}