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更小，实际上绕路更划算，如下图

直接从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();
	}
}

因为可以换车也可以不换，所以并非简单的修改下边权即可，对于每个点，可能骑不同的车过来，这个需要处理一下。