题目描述
A confused Dutchman trying to speak English could say “I am in the war”, even though there is no hostile activity going on. The confusion 1 here is that the English sentence “I am confused” is translated in Dutch as “Ik ben in de war”, which is phonetically (“sounding”) quite close to the first sentence. Such confusion leads to much enjoyment, but can complicate matters a bit.
Given a sentence in Dutch and a dictionary containing both correct translations as well as phonetic (incorrect) translations of individual words, find the translation of the sentence and indicate whether it is correct, or in case there is more than one find the total number of correct and incorrect translations. A sentence is correctly translated when each word of the sentence is correctly translated.
输入
The input consists of:
• One line with an integer n (1 ≤ n ≤ 20), the number of words in the Dutch sentence.
• One line with n words, the Dutch sentence s.
• One line with an integer m (1 ≤ m ≤ 10 5 ), the number of words in the dictionary.
• m lines, each with three strings d, e and c, a Dutch word, the English translation, and “correct” if this is the correct translation or “incorrect” otherwise.
A word consists of between 1 and 20 lowercase letters. Each word in s appears at least once as a Dutch word in the dictionary, no word appears more than 8 times as a Dutch word in the dictionary, and each combination of a Dutch and English word appears at most once.
输出
In case there is only a single translation of s, output one line with the translation followed by one line with “correct” or “incorrect”. In case there is more than one translation, output one line with the number of possible correct translations followed by “correct”, and one line with the number of possible incorrect translations followed by “incorrect”.
样例输入
7
als mollen mollen mollen mollen mollen mollen
4
als when correct
mollen moles correct
mollen destroy correct
mollen mills incorrect
样例输出
64 correct
665 incorrect
题意，给出一具丹麦语，给出字典，并给出字典的每个翻译是否正确，计算有多少总组合排列的意思是对的，有多少是错的。若只有一组排列，输出这组排列，并输出他是对是错。注意计数可能爆int
水题，模拟就好。
#include<bits/stdc++.h>///组合，最后样例没给出所有题意有坑点，只有一种排列时输出那种排列并判断
#define LL long long
using namespace std;
map<string,int>mp;
map<string,string>link;
LL poww(LL a,LL b)
{
LL ans=1;
while(b)
{
if(b&1)ans*=a;
a*=a;
b>>=1;
}
return ans;
}
int main()
{
int n,num[30],cnt[30],worry[30],sum;
string str[30];
while(scanf("%d",&n)!=EOF)
{
sum=0;
mp.clear();
link.clear();
memset(num,0,sizeof(num));
memset(cnt,0,sizeof(cnt));
memset(worry,0,sizeof(worry));
for(int i=0; i<n; i++)
{
cin>>str[i];
if(mp[str[i]]==0) mp[str[i]]=++sum;
num[mp[str[i]]]++;
}
int m;
string l,r,ju;
scanf("%d",&m);
for(int i=0; i<m; i++)
{
cin>>l>>r>>ju;
if(mp[l])link[l]=r;
if(ju[0]=='c'&&mp[l])cnt[mp[l]]++;
else if(ju[0]=='i'&&mp[l])worry[mp[l]]++;
}
LL ans=1,right=1;
for(int i=1; i<=sum; i++)
{
right*=poww((LL)cnt[i],(LL)num[i]);
ans*=poww((LL)cnt[i]+(LL)worry[i],(LL)num[i]);
}
if(ans==1)
{
for(int i=0;i<n;i++)
{
cout<<link[str[i]];
if(i==n-1)printf("
");
else printf(" ");
}
printf("%s
",right==1?"correct":"incorrect");
}
else
{
ans=ans-right;
printf("%lld correct
%lld incorrect
",right,ans);
}
}
}