2022牛客OI赛前集训营-提高组（第五场） 赛后总结

A.喷泉

纯几何送分题……

对于白浅妹妹，她的位置即是圆心与直线的垂足，距离为：到圆心的距离-半径。

对于鸡尾酒，他的位置是两个端点中离圆心更远的那个，距离为：到圆心的距离+半径。

代码：

#include<bits/stdc++.h>
using namespace std;

double dist(int x1,int y1,int x2,int y2){return sqrt((long long)(x1-x2)*(x1-x2)+(long long)(y1-y2)*(y1-y2));}
int main()
{
    int T;
    cin>>T;
    int x1,y1,x2,y2,x3,y3,r;
    while(T--)
    {
        scanf("%d %d %d %d %d %d %d",&x1,&y1,&x2,&y2,&x3,&y3,&r);
        double a=y1-y2,b=x2-x1,c=(long long)x1*y2-(long long)x2*y1;
        double ans1=fabs(a*x3+b*y3+c)/sqrt(a*a+b*b)-r,ans2=max(dist(x1,y1,x3,y3)+r,dist(x2,y2,x3,y3)+r);
        printf("%.2lf %.2lf\n",ans1,ans2);
    }
    return 0;
}

B.红绿灯

考场写的记忆化答案，对于每个时刻模拟，若到一个红绿灯时上一个也恰好在等直接返回上次答案，写法太好拿了80pts（不出意外地被特殊性质卡了）。

考虑题目的实质，每次的 $aa$ 相当于是把数列中的每个数 $x_{i}x\_i$（初始值为1～n）变为 $\lceil {\displaystyle \frac{x_i}{a}}\rceil \times a\backslash lceil\backslash dfrac\{x\_i\}\{a\}\backslash rceil\backslash times\; a$。

每次操作后将数列离散化并记录对应区间，这样能拿70pts（题解说的）。

每次操作后记录数列的gcd，若a为gcd的因数，不用执行（因为这样 $x_{i}x\_i$ 全都整除 $aa$，操作后序列压根就没变）。

代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
long long val[MAXN];
int l[MAXN],r[MAXN];
int n,m,cnt;
long long d;
long long gcd(long long x,long long y){return y?gcd(y,x%y):x;}
void work(int x)
{
	if(d%x==0) return;
	int tmp=cnt;
	cnt=0;
	for(int i=1;i<=tmp;++i)
		if(i==1 || val[i]!=val[cnt]) val[++cnt]=val[i],l[cnt]=l[i],r[cnt]=r[i];
		else r[cnt]+=r[i]-l[i]+1;
	for(int i=1;i<=cnt;++i) val[i]=(val[i]%x==0?val[i]/x:val[i]/x+1)*x;
	d=val[1];
	for(int i=2;i<=cnt;++i) d=gcd(d,val[i]);
}
int main()
{
	cin>>n>>m;
	d=1,cnt=n;
	for(int i=1;i<=n;++i) val[i]=l[i]=r[i]=i;
	int x;
	for(int i=1;i<=m;++i) scanf("%d",&x),work(x);
	for(int i=1;i<=cnt;++i) for(int j=l[i];j<=r[i];++j) printf("%lld ",val[i]);	
	return 0;
}

C.子集

手玩一下大小为 $3,43,4$ 的集合，递归个三四层，发现 $F_k(S)={\sum }_{siz=0}^n{F}_0(T)\times k^{n-siz}F\_k(S)=\backslash sum\_\{siz=0\}^n\; F\_0(T)\backslash times\; k^\{n-siz\}$ ($TT$ 为 $SS$ 的子集)。

那么只要快速求出 $F_0(T)F\_0(T)$ 即可，考虑01背包，跑 $nn$ 遍，设 $dp[i][j]dp[i][j]$ 表示用了 $ii$ 个数，和为 $jj$ 的方案数。

此时 $ans={\sum }_{i=0}^{n}dp[i][m]\times k^{n-i}ans=\backslash sum\_\{i=0\}^ndp[i][m]\backslash times\; k^\{n-i\}$ ，时间复杂度 $O(n^{2}m)O(n^2m)$ ，结合特殊性质能拿70pts。

考虑优化，设 $dp[i][j]dp[i][j]$ 表示用了 $ii$ 个数，和为 $jj$ 的方案对答案的总贡献。

转移方程改为： $dp[i][j]=\sum dp[i-1][j-a[p]]\mathrm{/}kdp[i][j]=\backslash sum\; dp[i-1][j-a[p]]/k$ ,初始 $dp[0][0]=k^{n}dp[0][0]=k^n$，答案即为 ${\sum }_{i=0}^{n}dp[i][m]\backslash sum\_\{i=0\}^ndp[i][m]$，复杂度还是 $O(n^{2}m)O(n^2m)$。

发现其实我们并不需要管用了几个数，反正最后答案都是要累加的，不妨就设 $dp[i]dp[i]$ 表示和为 $ii$ 的子集对答案的总贡献，初始仍设 $dp[0]=k^{n}dp[0]=k^n$。

答案即为 $dp[m]dp[m]$,时间复杂度成功降至 $O(nm)O(nm)$ 。

代码：

#include<bits/stdc++.h>
using namespace std;

#define inv(x) quick_pow(x,MOD-2)
const int MAXN=5e3+5;
const int MOD=1e9+7;
int a[MAXN],dp[MAXN];
int quick_pow(int a,int b)
{
	int ret=1;
	while(b)
	{
		if(b&1) ret=(long long)ret*a%MOD;
		a=(long long)a*a%MOD,b>>=1;
	}
	return ret;
}
int main()
{
	int T;
	cin>>T;
	int n,m,k;
	while(T--)
	{
		scanf("%d %d %d",&n,&m,&k);
		for(int i=1;i<=n;++i) scanf("%d",&a[i]);
		memset(dp,0,sizeof(dp));
		dp[0]=quick_pow(k,n);
		int invk=inv(k);
		for(int i=1;i<=n;++i)
			for(int j=m;j>=a[i];--j)
				(dp[j]+=(long long)dp[j-a[i]]*invk%MOD)%=MOD;
		printf("%d\n",dp[m]);
	}
	return 0;
}

D.佛怒火莲

我们不生产题解，我们只是题解的搬运工

本题思路来源于ButterCake的代码，勿喷（说实话我也只是看懂了然后照着码了一遍）。

做法：二分答案+检验合法性

二分答案不用多说，答案显然具有单调性，该如何检查合法性？

这个时候借鉴题解的思路，将原有的属性打乱，按照打乱的顺序dp求最多能选多少个（当前答案下）。

值得注意的是单次打乱的正确概率很低,但执行 $700700$ 次正确的概率几乎为 $11$ 。

代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e4+5;
const int INF=0x3f3f3f3f;
struct node{int a,b;}p[MAXN];
vector<int>pos[MAXN],col;
mt19937 rnd(time(NULL));
int n,k,type,minum[5],dp[MAXN];
bool check(int mid)
{
    int tmp=700;
    while(tmp--)
    {
        shuffle(col.begin(),col.end(),rnd);
        for(int i=1;i<k;++i) minum[i]=INF;
        minum[0]=-INF;
        for(auto x:col)
        {
            for(auto i:pos[x])
            {
                dp[i]=upper_bound(minum,minum+k,p[i].b-mid)-minum;
                if(dp[i]==k) return 1;
            }
            for(auto i:pos[x]) minum[dp[i]]=min(minum[dp[i]],p[i].b);
        }
    }
    return 0;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%d %d %d",&n,&k,&type);
        col.clear();
        for(int i=1;i<=n;++i) pos[i].clear();
        for(int i=1;i<=n;++i) scanf("%d %d",&p[i].a,&p[i].b),pos[p[i].a].push_back(i),col.push_back(p[i].a);
        sort(col.begin(),col.end());
        col.erase(unique(col.begin(),col.end()),col.end());
        int l=1,r=1e6,ans=0;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(check(mid)) ans=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

//后记&总结：这次属于是人品爆发了（第一次进前 5 ），T1T2花了不到1h过了大样例就溜了，T3用了将近2h推式+优化，然后T4就打了个状压就结束了（甚至没想到打暴力），与前面那些dalao还是有很大差距吧

笔者能力有限，有未述详尽或有误之处，欢迎指正。