第一场校队的集体Cf比赛QAQ

排名不是很高,到最后只切掉了ABD,C本来很简单,当时时间不多了于是就慌了。

果然,“比赛中的15分钟和比赛快要结束时的15分钟是不一样的啊”。

Rank1742,这次zzy大佬ABCD全都做出来了,然而A被Hack了(?)KVMC大佬只做了ABC……(貌似整个校队就我A题做的最慢???!!)

yts1999一小时切ABCD,Rank277,强啊。

大概这一场算是数论题+思考题吧,AB也不难,也就是PJ第二第三题难度。//然而并不能靠手速上分。

这儿是ABCD翻译&简短的题解。

A

大意就是维尼会去依次访问三个朋友家(这三个房子是三角形的三个顶点),并给出访问次数。一开始在其中一个顶点,给出三条边的边权,求给定次数的最少边权和。

//Solution

因为访问次数并不多,考虑dp

f[a][i]表示前a次访问,且第a次在顶点i时的最小边权和。 从f[a-1][j],f[a-1][k]取min转移即可。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;

int times,disa,disb,disc;
int f[120][10]={0},ans=0;

int main()
{
	scanf("%d%d%d%d",&times,&disa,&disb,&disc);
	
	memset(f,0x3f,sizeof(f));
	f[1][1]=0;
	if (times==1)
	{
		cout<<0<<endl;
		return 0;
	}

	for (int i=2;i<=times;i++)
	{
		f[i][1]=min(f[i-1][2]+disb,f[i-1][3]+disa);
		f[i][2]=min(f[i-1][1]+disb,f[i-1][3]+disc);
		f[i][3]=min(f[i-1][1]+disa,f[i-1][2]+disc);
	}
	ans=min(f[times][1],min(f[times][2],f[times][3]));
	cout<<ans<<endl;
	return 0;
}

B

给定一个数集A,要求构建一个含有k个元素的子集S,要求S中任意一个元素与其他元素的差的绝对值%m都为0。

若有多组解,任意输出一组。

//Solution

稍微思考一下,若|i-j|%m的余数为0的话,只需要i%m=j%m即可,移项并根据膜法结合律可知(i-j+m)%m=0

那么开m个对应的计数器编号1~m,碰到数就相应的+1,最后找一个数值>k的,记录下编号,扫一遍输入,然后判断、输出就行了。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<iterator>
#include<utility>
using namespace std;

int n,nums[100010]={0},k,m;
int restnum[100010]={0},ans=-1,c1=0;

int main()
{
	scanf("%d%d%d",&n,&k,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&nums[i]);
		restnum[nums[i]%m]++;
	}
	
	for (int i=0;i<m;i++)
	{
		if (restnum[i]>=k)
		{
			ans=i;
			break;
		}
	}
	
	if (ans==-1)
	{
		printf("No\n");
		return 0;
	}
	else 
	{
		printf("Yes\n");
		for (int i=1;i<=n;i++) if (nums[i]%m==ans)
		{
			printf("%d ",nums[i]);
			c1++;
			if (c1==k) return 0;
		}
	}
	return 0;
}

C

给定一个数m,求所有满足以下条件的数x (m,x均为positive integer,也就是正整数)

x加上十进制下的x所有位上的数字的和等于m

例:m=21 x=15     解释: 15+1+5=21

1≤m,x≤109

 

//Sulotion

考虑到数据范围于是考虑一个最大的x:99999999

那它对应的m就是100000071。很容易发现x≥ [m-(8*9)] (也就是这个x八位全是9)如此考虑从m-100枚举到m然后判断即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

int n,flag=0,ans[100]={0};

int sumdig(int x)
{
	int sum=0;
	while (x>0)
	{
		sum+=x%10;
		x/=10;
	}
	return sum;
}

int main()
{
	scanf("%d",&n);
	
	for (int i=n-81;i<=n;i++) if (i>0)
	{
		if (i+sumdig(i)==n)
		{
			ans[flag++]=i;
		}
	}
	if (!flag) printf("0\n");
	else
	{
		printf("%d\n",flag);
		for (int i=0;i<flag;i++) printf("%d ",ans[i]);
		putchar('\n');
	}
	return 0;
}

D

D大概是我唯一正经翻译的题了吧……这种思考题题面很毒啊???

最近,Dima在集邮店遇见了Sasha,从此他们一起收集硬币。他们最喜欢的职业是分类硬币的集合。萨沙喜欢井然有序,所以她希望她的硬币排成一排,这样一来,首先是不能流通的硬币,然后是仍在流通的硬币。

为了安排硬币,Dima使用以下算法。他的算法的一个循环如下:

1.他从左到右看着所有的硬币;

2.如果他看到第i个硬币还在流通中,并且(i + 1)硬币已经不流通,他会交换这两个硬币,继续从第(i + 1)个硬币看硬币。

Dima重复上述步骤,直到这一过程中没有交换任何两枚硬币。 Dima所谓的硬币排序困难度,是根据上述算法,对硬币序列进行排序的次数。

也就是说,他从序列起始位置开始查看硬币的次数。

例如,对于有序序列,困难度等于1。

 

今天Sasha邀请Dima玩一个游戏。首先,他把没有流通的n个硬币连在一起,然后萨沙选择一个硬币,替换成正在流通的硬币。一共替换n次。在这个过程中,Sasha不断地问Dima把此硬币序列排序的困难度是多少?

这个任务比较复杂,因为Dima不应该碰硬币,他应该心算将硬币序列变为有序的困难度。帮助Dima完成这个任务。

//Sulotion

这个很像牛顿摆。我们把正在流通的硬币看成一种球体,不流通的硬币看作空气。

我们用手撞击最左面的正在流通的硬币:

(注:运动规则

1.当一个硬币从左运动到它右面的硬币并撞击它的时候,这个硬币停止运动,被它撞击的硬币开始运动。

2.运动到硬币序列末尾则停止。

并把它撞到最右面的[正在流通的硬币]的硬币堆里去

根据1、2得到:这个硬币堆必须在硬币序列的最末尾

那这个问题可以O(N)解决了。

每一次更新硬币堆,就统计一下流通硬币的数量,并减去末尾硬币堆的硬币数量。维护末尾硬币堆的最左端指针p,判断seq[p-1]是不是被换成了流通硬币。

详见代码吧。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<iterator>
#include<utility>
using namespace std;

bool coinstr[300100]={false}; //False - out of circulation   True - in circulation
int coinnum,putpos[300100]={0},last,innum=0;

void updatelast()
{
	while (coinstr[last-1]==true) 
	{
		last--;
		innum--;
	}
}

int main()
{
	scanf("%d",&coinnum); last=coinnum+1;
	for (int i=1;i<=coinnum;i++) scanf("%d",&putpos[i]);
	printf("1 ");
	for (int i=1;i<=coinnum;i++)
	{	
		coinstr[putpos[i]]=true;
		innum++;
		
		if (putpos[i]==last-1) updatelast();
		
		printf("%d ",innum+1);
	}
	putchar('\n');
	return 0;
}

就这些了,立个不太稳当的Flag,有时间做完EF再来更新EF的翻译题解。

分类: Codeforces

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.