站外题求助
  • 板块灌水区
  • 楼主HuangTingFu
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/10 20:03
  • 上次更新2024/6/10 21:47:30
查看原帖
站外题求助
1014715
HuangTingFu楼主2024/6/10 20:03

题意: 约翰的农场的布局很奇特,奶牛白天吃草的草场周围有一条很大的环形路。每天早晨,奶牛们穿过这条路走向草场,每天晚上它们离开草场回到谷仓时,又都要穿过这条路。

正如我们所知,牛是有习性的动物,它们每天都以同样的方式过马路。每头奶牛走进草场的位置都不同于它走出草场的位置,而所有这些交叉点都是不同的。农夫约翰恰好拥有26头牛,他把这26头牛懒洋洋地命名为A到Z(他不确定如果他有了第27头牛,他会怎么做……),所以整条路有52个交叉点。农夫约翰顺时针扫描圆圈,写下每一个交叉点的牛的名字,最后形成一个由52个字符组成的字符串,其中每个字母恰好出现两次。他没有记录哪些交叉点是入口点,哪些是出口点。

看着他的十字路口地图,农夫约翰很好奇在有多少对奶牛会交叉。一对牛(a,b)为“交叉”的定义是,如果牛a从入口到出口的路径会穿过牛b从入口到出口的路径。请帮助农民约翰数一数交叉的总数。

输入格式(Format Input) The input consists of a single line containing a string of 52 upper-case characters. Each letter of the alphabet appears exactly twice. 输入由一行组成,其中包含一个由52个大写字母组成的字符串。字母表中的每个字母恰好出现两次。 输出格式(Format Output) Please print the total number of crossing pairs. 请打印交叉的总数。 输入样例(Sample Input) ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ 输出样例(Sample Output) 1 限制(Restrictions) 时间限制(Time Limit): 1000 ms 内存限制(Memory Limit): 65536KB 说明/提示(Hint) In this example, only cows A and B are a crossing pair. 在这个例子中,只有牛A和牛B是交叉的。

代码:

#include<bits/stdc++.h>
using namespace std;
int ans;
char c[10001];
struct haowan{
	int x1,x2;
} a[260];// ASCLL A~Z:65~90
int main()
{
	cin>>c+1;
	for(int i=1;i<=52;i++)
	{
		if(a[int(c[i])].x1!=0)
		{
			a[int(c[i])].x2=i;
		}
		else a[int(c[i])].x1=i;
	} 
	for(int i=65;i<=90;i++)
	{
		for(int j=65;j<=i-1;j++)
		{
			if(a[i].x1>a[j].x1&&a[i].x1<a[j].x2&&a[i].x2>a[j].x2)
			{
				ans++;
			}
		}
	}
	cout<<ans;
}

二十分,WA求助

2024/6/10 20:03
加载中...