Codeforces Round 918 (Div. 4)补题

这篇具有很好参考价值的文章主要介绍了Codeforces Round 918 (Div. 4)补题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Odd One Out(Problem - A - Codeforces)

题目大意:有三个数,其中两个相同,找出不同的那个数。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		vector<int>p;
		for(int i=1;i<=3;i++)
		{
			int x;
			cin>>x;
			p.push_back(x);
		}
		sort(p.begin(),p.end());
		if(p[0]==p[1]) cout<<p[2]<<endl;
		else cout<<p[0]<<endl;
	}
}

Not Quite Latin Square(Problem - B - Codeforces)

题目大意:有一个3*3的矩阵,每行每列都由1,2,3三个元素构成,且同行同列中的元素不同,先有一个地方出现空缺,要求输出空缺位置的元素。

思路:A==1,B==2,C==3,遍历每行求和,不等于6的,输出对应值。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int c;
		for(int i=1;i<=3;i++)
		{
			string s;
			cin>>s;
			int flag=0;
			for(int i=0;i<3;i++)
			{
				if(s[i]!='?')
					flag += s[i]-'A'+1;
			}
			if(flag!=6) c=6-flag;
		}
		if(c==1) cout<<'A'<<endl;
		else if(c==2) cout<<'B'<<endl;
		else cout<<'C'<<endl;
	}
}

Can I Square?(Problem - C - Codeforces)

题目大意:有n的人,每人有a[i]块1*1的小正方形,问所有人的方块都用上,能不能拼成一个大正方形。

思路:求和,判断和是否为完全平方数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	int t;
	scanf("%lld",&t);
	while(t--)
	{
		int n;
		scanf("%lld",&n);
		int ans=0;
		for(int i=1;i<=n;i++) 
		{
			int x;
			scanf("%lld",&x);
			ans+=x;
		}
		int t=(int)sqrt(ans);
		if(ans*1.0/t==t) printf("YES\n");
		else printf("NO\n");
	}
}

Unnatural Language Processing(Problem - D - Codeforces)

题目大意:已知五个字母a,b,c,d,e,其中a,e为元音字母,记为V,b,c,d为辅音字母,记为C,音节有两种划分方式CVC,CV,现给定一串字符串,要求按照音节进行划分。

思路:CVCV,CVCCV,可以发现,当我们访问到一个辅音字母的时候,我们只用往后看3个,看那个位置的字母是否为辅音字母,如果是就划出来3个,如果不是就划出来两个,再注意一下往后看越界的问题即可。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	map<char,int>mp;
	mp['a']=1,mp['e']=1;
	mp['b']=2,mp['c']=2,mp['d']=2;
	//21,212
	while(t--)
	{
		int n;
		string s;
		cin>>n>>s;
		vector<string>p;
		for(int i=0;i<s.size();i++)
		{
			if(mp[s[i]]==2)
			{
				int k=i;
				k+=3;
				string a="";
				if(k==s.size()+1)
				{
					a+=s[i];
					a+=s[i+1];
					i=k-2;
				}
				else if(k==s.size())
				{
					a+=s[i];
					a+=s[i+1];
					a+=s[i+2];
					i=k-1;
				}
				else if(mp[s[k]]==2)
				{
					a+=s[i];
					a+=s[i+1];
					a+=s[i+2];
					i=k-1;
				}
				else
				{
					a+=s[i];
					a+=s[i+1];
					i=k-2;
				}
				p.push_back(a);
			}
			
		}
		for(int i=0;i<p.size();i++) 
		{
			if(i) cout<<".";
			cout<<p[i];
		}
		cout<<endl;
	}
}

Romantic Glasses(Problem - E - Codeforces)

题目大意:现在有n个酒杯,每个杯子中装的酒的数量不同,A只喝奇数序号杯子中的酒,B只喝偶数序号杯子中的酒,问能否找出一个区间,两人都只喝区间范围内的酒,并且喝的酒的量是相同的。

思路:相当于区间内奇数位的和等于偶数位的和,那么我们将奇数位视为正数,偶数位视为负数,从头开始加,一旦某个位置和为0,那么肯定可以,或者,当某个位置的和之前出现过,那么说明中间这一段的和为0,进而问题解决。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200010],s[200010],d[200010];
signed main()
{
	int t;
	scanf("%lld",&t);
	while(t--)
	{
		int n;
		scanf("%lld",&n);
		for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
		map<int,int>mp;
		int sum=0;
		int flag=0;
		for(int i=1;i<=n;i++)
		{
			if(i%2) sum += a[i];
			else sum -= a[i];
			if(sum==0||(i!=1&&mp[sum])) 
			{
				flag=1;
				break;
			}
			mp[sum]=1;
		}
		if(flag) printf("YES\n");
		else printf("NO\n");
	}
}

Greetings(Problem - F - Codeforces)

题目大意:有n个人,每个人的起点和终点都不同,但它们的速度是相同的,当两人相遇的时候会打一次招呼,问到所有人都到终点为止,共打了多少次招呼。

思路:速度一样就不会产生追击,所以唯一会出现打招呼的情况就是一个区间完全覆盖另一个区间,那么就是找出每个区间完全覆盖了多少个区间,然后求和即可。这里可以先按照一边排序,然后将另一端点放入一个容器中,去容器中查找目前已经访问过的有多少合适即可。比如我们按照右端点从小到大排序,每访问一个就将它的左端点放入容器中,新的访问开始时,当前访问的右端点大于所有已经访问过的点的右端点,只要找出已经访问过的部分中哪些区间的左端点大于它的左端点即可,因为这些区间是被它完全覆盖的。用vector<>记录,那就无序,只能暴力查找,肯定是超时的,如果用set记录,那么即使用set中内置的upper_bound查找,计算距离的时候distance()函数还是会超时,所以这里利用红黑树来计算。

定义如下:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;
/*
第一个参数 int 表示键的类型。
第二个参数 __gnu_pbds::null_type 表示映射的类型,这里使用 null_type 表示这是一个集合,不包含任何值。
第三个参数 less<int> 是比较函数,用于比较两个键的大小。
第四个参数 __gnu_pbds::rb_tree_tag 表示使用红黑树作为底层数据结构。
第五个参数 __gnu_pbds::tree_order_statistics_node_update 是一个策略,它允许我们通过索引来访问树中的元素,还可以获取某个键的排序位置。
*/

然后它有一个函数order_of_key(key),可以获得key在红黑树中排在第几位,进而就可以知道key前面有多少个元素,通过元素总数减去前面的元素个数就得到了大于它的元素个数,也就是我们的目标。(ps:key不需要在树中,求出来的是严格小于key的值的个数),对它的所有操作时间复杂度都是O(logn),所以不会超时。

完整代码:

#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
typedef __gnu_pbds::tree<int,__gnu_pbds::null_type,less<int>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>ordered_set;
ordered_set s;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		vector<pair<int,int>>p;
		for(int i=1;i<=n;i++) 
		{
			int a,b;
			scanf("%d%d",&a,&b);
			p.push_back({b,a});
		}
		sort(p.begin(),p.end());
		s.clear();
		long long ans=0;
		for(auto it:p)
		{
			ans += s.size()-s.order_of_key(it.second);
			s.insert(it.second);
		}
		printf("%lld\n",ans);
	}
}

Bicycles(Problem - G - Codeforces)

题目大意:现在有n个城市,n个城市之间共有m条边,城市与城市之间通行必须使用自行车,每个城市都有一辆自行车出售,第j个城市的自行车的系数为sj,每条边有一个边权wi,当我们用第j辆自行车去通过第i条边的时候,花费的时间是sj*wi,当然我们可以换自行车,也可以就着一辆自行车骑很远,只要我们买了它,问从1到n的最少花费的时间是多少。

思路:这道题问从1到n的最少花费,实际就是最短路问题,但是又有一点不同,因为我们可以换自行车,所以如果绕路可以使后面的sj*wi更小,实际上绕路更划算,如下图

Codeforces Round 918 (Div. 4)补题,codeforces补题,算法

直接从1->2->5:最小是5*2+2*7=24,但是如果绕路走1->2->3->2->4->5:那么就是5*2+2*1+1*1+5*1+1*1=19,显然比直接走要快。所以我们就从这个角度入手,用堆优化的dijstra写,堆中多存一个自行车种类的变量,我们每到一个城市就判断一下从这个城市再出发的时候需不需要更换自行车,最后只用循环遍历以不同的自行车到n的值,找出最小的即可。 对了,最短路长度可能大于int的范围,要记得处理一下。

#include<bits/stdc++.h>
using namespace std;
typedef pair<long long,pair<int,int>> piii;
int s[3000];
long long d[3000][3000];
int h[3000],e[6000],ne[6000],w[6000],idx;
int n,m;
void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void sp()
{
	memset(d,0x3f,sizeof d);
	priority_queue<piii,vector<piii>,greater<piii>>p;
	d[1][s[1]]=0;
	p.push({0,{1,s[1]}});
	while(p.size())
	{
		auto t=p.top();
		p.pop();
		int u=t.second.first,k=t.second.second;
		long long dis=t.first;
		for(int i=h[u];i!=-1;i=ne[i])
		{
			int j=e[i];
			int c=min(s[j],k);//决定是否换交通工具
			if(d[j][k]>dis+(long long)k*w[i])
			{
				d[j][k]=dis+k*w[i];
				p.push({d[j][k],{j,c}});
			}
		}
	}
	long long mi=2e18;
	for(int i=1;i<=n;i++)
	{
		mi=min(mi,d[n][s[i]]);
	}
	cout<<mi<<endl;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		memset(h,-1,sizeof h);
		idx=0;
		for(int i=1;i<=m;i++)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,c);
			add(b,a,c);
		}
		for(int i=1;i<=n;i++) scanf("%d",&s[i]);
		sp();
	}
}

因为可以换车也可以不换,所以并非简单的修改下边权即可,对于每个点,可能骑不同的车过来,这个需要处理一下。文章来源地址https://www.toymoban.com/news/detail-790130.html

到了这里,关于Codeforces Round 918 (Div. 4)补题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Codeforces Round 871 (Div. 4)

    给定n个长度为10的字符串,问其与codeforces字符串的对应下标字母不同的个数。 对于每个字符串从前往后依次和“codeforces”对应字符比较然后统计不同字母数即可 给定长度为n的数组,问连续相邻为0的最大长度 维护一个全局最大长度res,和当前连续序列的长度cnt。从前往后扫

    2024年02月03日
    浏览(52)
  • Codeforces Round 894 (Div. 3)

    签到题 a数组里,大于等于前一个值的a[i]会被写到b里。直接遍历b,如果b[i]比前一个小就在它前面插一个相等的值 计算反过来的长度,判断是否相等就行 对于没有重复口味的集合,能选出的方案是n*(n-1)/2 (从n个里面选2个的组合数)。二分找出需要多少不同口味的冰淇淋,

    2024年02月11日
    浏览(44)
  • Codeforces Round 867 (Div. 3)

    从所有a[i]+i-1=t的选择种取个max即可 实际上就是取同符号乘积的最大值 找规律,发现结果与边长n的关系是:res = n * (n + 3) - (n - 2) ①当n为奇数时,除了1其他均无解 ②当n为偶数时,我们可以构造一个形如n,1,n - 2,3,...的数列 首先我们可以发现n必定出现在起始位置。如果n不在起

    2024年02月02日
    浏览(48)
  • Codeforces Round 912 (Div. 2)

    大等于2依据冒泡排序即可排序,因此判断下1即可 对每一个数字找哪一位肯定为0填0其他的填1 从后往前考虑加到当前集合或新立一个集合 从最高位开始考虑能否为1,计算能否时每个数当前位为1

    2024年02月04日
    浏览(44)
  • Codeforces Round 866 (Div. 2)

    给出一个仅由_或^组成的字符串,你可以在任意位置添加_或^字符,使得字符串满足: 任意字符要么属于^_^的一部分,要么属于^^的一部分。求最少添加的字符数量。 对于_我们只需处理没有组成^_^的_: ①如果_在首位置且左边没有^则添加^ ②如果_在尾位置且右边没有^则添加

    2023年04月25日
    浏览(56)
  • Codeforces Round 881 (Div. 3)

    给定一个数组,给每个元素涂色。求最大的代价。 代价为每个颜色的代价和。 每个颜色的代价为涂了该颜色的元素的极差。 因为是极差,每个元素要么对答案有正的贡献,要么有负的贡献,要么无贡献。且正负贡献的个数要相同。 因为要最大值,自然就是想有正贡献的是最

    2024年02月09日
    浏览(43)
  • Codeforces Round 926 (Div. 2)

    类似于倍投法,就是在一赔一的情况下,第一次压一块钱,每输一次就押注上一次两倍的金额. 假如资金无限的话,这种方法赢的期望为无穷大.原理类似于二进制,不论你输再多次,只要赢一次总额就增加了1.比如 15 二进制1111,前3把一直输,但是只要第4把赢,就一定可以增加 1

    2024年02月20日
    浏览(44)
  • Codeforces Round 874 (Div. 3)

    用最少的长度为2的字符串按一定规则拼出s。规则是:前一个字符串的尾与后一个字符串的首相同。 统计s中长度为2的不同字符串数量。 给定数组a[n]和b[n],重排b后,令任意|ai−bi|≤k成立(1≤k≤n)数据保证一定有解。 将a和b分别按从小到大的顺序匹配便是最优的,一定能满足

    2024年02月05日
    浏览(37)
  • Codeforces Round 868 Div 2

    要求构造一个仅包含 (1) 和 (-1) 的长度为 (n) 的数组 (a) ,使得存在 (k) 个下标对 ((i, j), i j) 满足 (a_i times a_j = 1) 。 当有 (x) 个 (1) , (y) 个 (-1) 时,其满足条件的下标对数量为 (frac{x (x - 1)}{2} + frac{y (y - 1)}{2}) 。 由于 (n) 只有 (100) ,直接枚举 (x) 即可。

    2024年02月01日
    浏览(44)
  • Codeforces Round 920 (Div. 3)

    Codeforces Round 920 (Div. 3) 题意:随机给出正方形在平面坐标系上的四个顶点的坐标,求正方形的面积,正方形边与xy轴平行。 思路:因为正方形与坐标轴平行,所以找出相同的两x或y坐标即可找到一条边的长度,平方就是面积,注意结果返回整型。 AC code: 题意:给出两个01字符

    2024年01月17日
    浏览(67)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包