2021年度训练联盟热身训练赛第五场（A B C E F G H I）

比赛链接

OP

前面几道题还是比较快乐的，后面就开始日常罚坐了；

A Binary Seating

概率

思路

求离场时间的期望；

离场时间只与本考场考试用时最长的学生有关;
假设参加考试共$n$个学生，按考试用时降序排列为$t_1,t_2,...,t_n$;

则考试总用时为$t_1$的概率为$1/2$;
考试总用时为$t_2$的情况为一号考生未选择此考场，二号考生选择了此考场，概率为$1/4$;
以此类推，考试总用时为$t_3$的概率为$1/8$，考试总用时为$t_n$的概率为$1/2^n$；

所以期望为 ${\sum }_{i=1}^n{t}_i/2^i$

代码

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

int main()
{
	int n,a[45];
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	double s=0;
	for(int i=n;i>=1;i--)s+=1.0*a[i]/pow(2,n-i+1);
	printf("%.5lf",s);
    return 0;
}

B Cutting Corners

几何

思路

题目要求：对于给定的w与h，输出$w+h?\sqrt{w^2+h^2}$;

代码

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

int main()
{
	int w,h;
	cin>>w>>h;
	printf("%.9lf",1.0*w+h-sqrt(w*w+h*h));
    return 0;
}

C Ducky Debugging

字符串

思路

~~~

代码

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

int main()
{
	string c;
	while(1)
	{
		getline(cin,c);
		if(!strcmp(c.c_str(),"I quacked the code!"))
			break;
		else if(c[c.length()-1]=='.')
			printf("*Nod*\n");
		else if(c[c.length()-1]=='?')
			printf("Quack!\n");
	}
    return 0;
}

E Figure Skating

字符串

思路

map记录字符串对初始位置的映射，第二轮循环中比较即可；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string,int> mp;
int main()
{
	string g;
	int n;
	cin>>n;
    getchar();
	for(int i=1;i<=n;i++)
	{
		getline(cin,g);
		mp[g]=i;
	}
	int m=0;
	string mg;
	for(int i=1;i<=n;i++)
	{
		getline(cin,g);
		if(mp[g]-i>m)
		{
			m=mp[g]-i;
			mg=g;
		}
	}
	if(m)
	{
		cout<<mg;
	}
	else printf("suspicious");
    return 0;
}

F Group Project

并查集扩展域

思路

用并查集及扩展域存储同类关系和异类关系；

介于数据并没有保证可以用唯一方法分出两个班，这里用并查集产生的结果只是一种可能的区分方案，但与结果最大的分配方案通过下面的特判后结果相同

有一种情况需要特判：
如果两班均是奇数个人，且有一班中某人的敌人数小于另一班人数，则说明此人可以与另一班某同学组组；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> vec,tn[100005];//vec存一班的同学编号，tn[i]存储i号同学的敌人
int fa[200005];//扩展域并查集
int find(int x)//此题中，find(x)的返回值为1或0
{
	if(fa[x]!=x)return  fa[x]=find(fa[x]);
	return x;
}
int main()
{
	int n,m;
	int a,b;
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		if(a>b)swap(a,b);
		tn[a].push_back(b);
		tn[b].push_back(a);
		fa[b]=a+n;
		fa[b+n]=a;
	}
	int s,l;s=l=0;//l与s存储两班人数
	for(int i=1;i<=n;i++)
	{
		if(find(i))l++;
		else s++,vec.push_back(i);
	}
	if(s&1&&l&1)
	{
		for(int i=0;i<vec.size();i++)
		if(tn[vec[i]].size()!=l){s--,l++;break;}
	}
	printf("%d",s/2+l/2);
    return 0;
}

G Human Pyramid

DP

思路

感觉是dp题，但是用了好几个dp方程都没有找到合适的解法，最后参考了这里；

我们将整个金字塔向左推至左对齐后，即可得每一名S，其正下与右下均为S；
也就是说如果此时的从左到右第 p 列至少有 x 名S的话，第 p+1 列至少有x-1名；

建立dp方程：
$$a[i][j][k]=a[i][j][k+1]+a[i?1][j?k][k?1](k<=\sqrt{2?j})$$
此处 i 为金字塔宽度，一共使用 j 名S，最左列至少有 k 名S；
第一项为 左列至少有 k 名s时，包含左列至少有 k+1 名S的情况；
第二项为 考虑次左列人数至少为 最左列人数-1 的情况
（注：最大左列人数可以近似为$\sqrt{2?j}$）；

最后特殊处理，避免k-1<0即可；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
ll a[102][5053][102];
int main()
{
	int n,r,i,j,k,l;
	cin>>n>>r;
	a[0][0][0]=1;
	for(i=1;i<=n;i++)
	{
		for(j=0;j<=r;j++)
		{
            int sq=sqrt(j<<1);
			for(k=sq;k>=0;k--)
			{
				a[i][j][k]=a[i][j][k+1]+a[i-1][j-k][max(k-1,0)];
				a[i][j][k]%=M;
				//printf("a[%d][%d][%d]=%lld\n",i,j,k,a[i][j][k]);
			}
		}
	}
	cout<<a[n][r][0];
    return 0;
}

H In-place Sorting

贪心

思路

我们可以制定一下贪心策略：

对于第一个数，将所有9变为6，使其尽可能小；
对于其余数，我们先把其所有6均变为9：
——如果此时此数仍小于上数，则排序失败；
——如果此时此数恰好等于上数，则直接处理下一个数；
——如果此时此数大于上数，则从高位（1e18）到低位（1e0），将所有能转换为6的9（转换为6后此数仍大于上数的9）转换为6；
（如果从低位到高位，则可能导致某些本可以转换为6的较高位无法转换，详见样例二）

注：pow返回值类型为double，与long long转换可能会出现问题；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string,int> mp;
int main()
{
	ll n,m;
	int a[10004][20]={0};
	ll g,num[10004],ten[20]={1};
	for(int i=1;i<=18;i++)ten[i]=10*ten[i-1];
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>g;
		num[i]=g;
		for(int j=0;j<=18;g/=10,j++)
			a[i][j]=g%10;
	}
	for(int i=18;i>=0;i--)
	{
		if(a[1][i]==9)a[1][i]=6,num[1]-=3*ten[i];
	}
	int f=1,b=0,s;
	for(int i=2;i<=n&&f;i++)
	{
		for(int j=0;j<=18;j++)
		{
			if(a[i][j]==6)
			{
				num[i]+=3*ten[j];
				a[i][j]=9;
			}
		}
		if(num[i]==num[i-1])continue;
		else if(num[i]<num[i-1])f=0;
		else
		{
			for(int j=18;j>=0;j--)
			{
				if(a[i][j]==9&&num[i]-3*ten[j]>=num[i-1])
				{
					num[i]-=3*ten[j];
					a[i][j]=6;
				}
			}
		}
	}
	int pf=0;
	if(f)
	{
		printf("possible\n");
		for(int i=1;i<=n;i++)
		{
			printf("%lld\n",num[i]);
		}
	}
	else printf("impossible");
    return 0;
}

I Jam-packed

数学

二分解法

思路

对于二分出的mid，如果每箱装mid个，剩余的可以装入除一个箱子外（该箱子装mid个）其余每一个箱子的剩余部分，则说明答案大于等于mid；

此处感谢大佬 qq_30106825 的提醒，错误已更正

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll n,m;
	cin>>n>>m;
	ll l=1,r=m,mid;
	while(l<r)
    {
        mid=l+r+1>>1;
		if(n%mid<=(m-mid)*(n/mid))l=mid;
        else r=mid-1;
	}
	printf("%lld",l);
    return 0;
}

O(1)解法

思路

如果n能被m整除，则可以每箱装m个；
否则，则需要n/m+1个箱子，如果我们将瓶子浮点化，则每一个箱子平均装n/(?n/m?+1)（浮点除法）个瓶子，而瓶子数量是离散的，则n/(n/m+1)（整数除法）即为装瓶数最小的箱子的装瓶数；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string,int> mp;
int main()
{
	ll n,m;
	cin>>n>>m;
	if(n%m==0)printf("%lld",m);
    else printf("%lld",n/(n/m+1));
    return 0;
}

ED

\