2022-10-13 22:38 西北大学 C++ 发布于上海

关注

10.13 OI 集训营提高组第五场题解

^{T1 喷泉}

^{根据初中数学知识，可以知道，一个定点到圆上点的最大（小）距离等于其到圆心的距离加（减）半径的长度，而一个定点到一条线段的最大距离显然是到线段两端之一，最小距离是垂线段长度（题目保证垂足在线段上）。

于是输出圆心到线段距离减半径，到两端点的最大距离加半径即可。

别溢出了。

具体证明问初中数学老师，剩下的就是解析几何计算了。}

^{#include <bits/stdc++.h>
using namespace std;
signed main(){
	#define int long long
	int t, x1, y1, x2, y2, x3, y3, r;
    cin >> t;
	while(t--){
		cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> r;
		int A=y1-y2,B=x2-x1;
		int C=-(A*x1+B*y1);
		long double minm=abs(A*x3+B*y3+C)/sqrt((long double)A*A+B*B)-r;
		long double maxm=sqrt((long double)(x3-x1)*(x3-x1)+(y3-y1)*(y3-y1));
		maxm=max(maxm,sqrt((long double)(x3-x2)*(x3-x2)+(y3-y2)*(y3-y2)))+r;
		// printf("%.2lf %.2lf\n",(double)minm,(double)maxm);
		printf("%.2Lf %.2Lf\n",minm,maxm);
	}
	return 0;
}}

T2 红绿灯

其实本题暴力就大致能通过了，只不过有一些大优化。

题目简述：维护一个长度为 $n$ 的序列，初始为 $1$ 至 $n$ 。之后有 $m$ 次操作，每次输入一个整数 $a$ ，将序列中每一个元素 $x$ 变成 $\lceil\dfrac{x}{a}\rceil\times a$ ，问最终序列。

可以发现在一系列操作之后整个序列中有很多相同的元素，那么我们去重一下，并且记录一下每一个数字出现在序列中的哪些位置，显然是一个区间。

这样，我们记录的数字个数就大大减少，可以拿到约 $70pts$ 。

可以发现在 $2,3$ 循环的数据中跑的很慢，而我们输出序列发现在之后的操作中，序列甚至一点都没变。

这是因为序列中的每一个元素都整除了 $a$ ，所以根本不会变。

这样我们可以在每一次操作后，求一下整个序列所有元素的 $gcd$ ，一旦操作的 $a$ 是 $gcd$ 的约数，直接跳过不用修改。

由于本题数据较为随机，所以可以通过。

^{#include<bits/stdc++.h>
#define int long long
using namespace std;
int b[300001][2];
int a[300001][2],n,m;
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
signed main(){
	cin >> n >> m;
	a[0][0]=n;
	for(int i=1;i<=n;i++)a[i][0]=b[i][0]=i;
	int G=1, x;
	int sum=0;
	for(int i=1;i<=m;i++){
		cin >> x;
		if(G%x==0)continue;
		int now=i&1,las=now^1;
		sum+=a[0][las];
		a[0][now]=0;
		for(int j=1;j<=a[0][las];j++)a[j][las]=((a[j][las]-1)/x+1)*x;
		for(int j=1;j<=a[0][las];j++){
			if(j==1||a[j][las]!=a[j-1][las])
				a[++a[0][now]][now]=a[j][las];
			b[a[0][now]][now]=b[j][las];
		}
		G=a[1][now];
		for(int j=1;j<=a[0][now];j++)G=gcd(G,a[j][now]);
	}
	sum+=a[0][m&1];
	int j=0;
	for(int i=1;i<=n;i++){
		while(b[j][m&1]<i)j++;
		cout << a[j][m&1] << " ";
	}
}}

^{T3 子集}

^{注意到一个结论：

其中。

证明：时显然成立。

若对任意均有成立，那么当时：

因此同样成立。从而，对任意正整数均有成立。

因此我们现在要做的就是：对每个和为的子集，计算其贡献，最后加到一起。

可以考虑一个显然的 dp：设表示前个数中选了个，其和为的方案数。

枚举最后一个数选不选，不难得到转移方程

那么答案就是

时间复杂度为，可以获得分。

考虑优化一下状态设计：设表示的所有和为的子集的贡献之和。

同样考虑最后一个数选不选：

- 如果没有选，那么相当于式中的加了，因此的指数也会；
- 反之，则也会，那么原封不动加进来就行了。

因此，我们得到

时间复杂度，可以通过。}

^{#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MN=5005;
const int mod=1e9+7;
int a[MN],dp[MN][MN],n,M,k;
void solve(){
    memset(dp,0,sizeof(dp));
	cin >> n >> M >> k;
    for(int i=1;i<=n;i++) cin >> a[i];
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=M;j++){
            dp[i][j]=dp[i-1][j]*k%mod;
            if(j>=a[i])dp[i][j]=(dp[i][j]+dp[i-1][j-a[i]])%mod;
        }
    }
    cout<<dp[n][M]%mod<<endl;
}
signed main(){
    int tt;
    cin >> tt;
    while(tt--)solve();
}}

^{T4 佛怒火莲}

^{测试点1,2：考虑直接暴力选最多5个数字，的复杂度是的，所以直接就行。

测试点3~6：对所有火焰按照排序，用表示考虑了前个火焰，且我选了第个火焰，当前选了这个颜色集合的火焰时，我的最大间隔是多少，转移是的。总复杂度是。

测试点11~14：只需要选三种火焰，我们可以枚举中间的火焰是谁，然后，有一个显而易见的结论是，如果中间的火焰是，那么选定的另外两朵火焰，一定在左边最远的两种不同色火焰中选一朵，右边最远的两种不同色火焰中选一朵，直接暴力预处理两遍即可，除了排序以外，复杂度是的。

测试点15~17：考虑优化3~6的，我们二分答案，然后只需要可行性了就。表示我们考虑了前个火焰，并且选了，当前选的状态是的情况下，是否可行，这样子就有转移：

，其中是二进制下去掉第位后的值，，这里的是我们二分的答案。

这个显然可以维护前缀的最大值，来使得转移变成。

这样总复杂度，可以轻松通过。

测试点7~10：我们考虑把所有不同种类的随机映射到这种颜色去，然后去做上面的，那么，答案对应的个火焰，有的概率恰好分配到了种不同的颜色，也就是说，我们的即便在的情况下，也有的概率获得正确的结果。

那么我们就把随机分配颜色这个事情模拟次，就可以有的正确率了。

时间复杂度是。

> 考虑到能想到这一步的人，应该都会的，所以没留暴力的分数

测试点1~20：

我们考虑进一步优化我们的。

我们的本质上最多压了个，那么我们直接用一个把他存下来就可以了。

用表示考虑了前个位置以后，所有二进制状态到分别行不行，我们把它存到的每一位上。

然后转移方程就是：

表示对于颜色，哪些二进制状态里面不含有第种颜色。

此处比较绕，建议自己推一下细节，注意是会爆的。}

^{#include <bits/stdc++.h>
#define ll long long
#define maxn 10005
using namespace std;
unsigned int dp[maxn];
unsigned int tmp;
pair<int,int> a[maxn];
int n,k,tp;
int col[maxn],best;
int ok[maxn];
void init()
{
	memset(ok,0,sizeof(ok));
	for (int i=0;i<k;i++)
	{
		for (int sta=0;sta<(1<<k);sta++) //for每一个二进制位 
		{
			if ((sta&((unsigned int)1<<i))==0) //如果sta里面不包含二进制下第i位
				ok[i]|=(((unsigned int)1<<sta));
		}	
	}		
}

void add(int i) {tmp|=dp[i];}
int check(int lim)
{
	memset(dp,0,sizeof(dp));
	dp[0]=1; tmp=1;  
	int pos=0;
	for (int i=1;i<=n;i++)
	{
		while (pos+1<i && a[i].first-a[pos+1].first>=lim) add(++pos);
		int se=col[a[i].second];
		
		dp[i]=dp[i-1]|((tmp&ok[se])<<((unsigned int)1<<se));
	}
	while (pos<n) add(++pos);
	return tmp>>(((unsigned int)1<<k)-1);
}

void work()
{
	for (int i=1;i<=n;i++) col[i]=rand()%k; //给个0~k-1之间的颜色
	int now=-1;
	for (int step=(1<<20);step>=1;step=step>>1)
	if (check(now+step)==1)
		now+=step;
	best=max(best,now);
	return;
}

int main()
{
	srand(time(0));
	int T;
	cin>>T;
	while (T--)
	{
		best=0;
		cin>>n>>k>>tp;
		init();
		for (int i=1;i<=n;i++) cin>>a[i].second>>a[i].first;
		sort(a+1,a+n+1);
		for (int turn=1;turn<=200;turn++) work();
		cout<<best<<endl;	
	}
}}

时间复杂度变成 $O(200\times log(10^6)\times n)$ 。

> 实际上测试点11~14直接少随一些次数，直接暴力 $dp$ 也是可以通过的。

> 实际上还可以暴力 $dp$ 的时候，随机次数按数据范围来定，小数据随机200次，大数据就随机50~60次，大概率能拿到90及以上。（这个分数要看评测机的脸***r />