NC24079. [USACO 2017 Feb B]Why Did the Cow Cross the Road II
描述
As we know, cows are creatures of habit, and they each cross the road the same way every day. Each cow crosses into the field at a different point from where she crosses out of the field, and all of these crossing points are distinct from each-other. Farmer John owns exactly 26 cows, which he has lazily named A through Z (he is not sure what he will do if he ever acquires a 27th cow...), so there are precisely 52 crossing points around the road. Farmer John records these crossing points concisely by scanning around the circle clockwise, writing down the name of the cow for each crossing point, ultimately forming a string with 52 characters in which each letter of the alphabet appears exactly twice. He does not record which crossing points are entry points and which are exit points.
Looking at his map of crossing points, Farmer John is curious how many times various pairs of cows might cross paths during the day. He calls a pair of cows (a,b) a "crossing" pair if cow a's path from entry to exit must cross cow b's path from entry to exit. Please help Farmer John count the total number of crossing pairs.
输入描述
The input consists of a single line containing a string of 52 upper-case characters. Each letter of the alphabet appears exactly twice.
输出描述
Please print the total number of crossing pairs.
示例1
输入:
ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ
输出:
1
说明:
In this example, only cows A and B are a crossing pair.Python3(3.9) 解法, 执行用时: 20ms, 内存消耗: 3192K, 提交时间: 2020-11-28 20:58:12
import collections
chickens = [[-1, -1] for _ in range(26)]
met = [False] * 26
s = input()
for i, char in enumerate(s):
index = ord(char) - ord('A')
#print(char, "index", index)
if not met[index]:
chickens[index][0] = i
met[index] = True
else:
chickens[index][1] = i
#print("chickends", chickens)
chickens.sort(key = lambda x: x[0])
cross = 0
for i, chicken in enumerate(chickens):
entry, end = chicken[0], chicken[1]
for j in range(i+1, 26):
if chickens[j][0] > end:
break
if chickens[j][0] < end and chickens[j][1] > end:
cross += 1
#print("cross", cross)
print(cross)
C++(clang++11) 解法, 执行用时: 4ms, 内存消耗: 384K, 提交时间: 2020-11-30 10:54:41
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
char s[N];
int main(){
cin>>s;
int ans=0;
int n=strlen(s);
for(int i=0;i<n;i++){
int r=n-1;
while(s[r]^s[i]) r--;
for(int j=i+1;j<r;j++){
if(s[j]^s[i])
ans++;
for(int k=i+1;k<j;k++){
if(s[k]==s[j]){
ans-=2;
break;
}
}
}
}
cout<<ans/2<<endl;
return 0;
}