2019CCPC哈尔滨站题解（F、I、J、K）
F - Fixing Banners
题意：
T组测试样例，每组样例输入6个字符串(都是小写)，现在需要在每个字符串中取且只取一个字母，请问能否在该操作下得到"harbin"（顺序任意，得到这六个字母即可）。
样例：
Input
2 welcome toparticipate inthe ccpccontest inharbin inoctober harvest belong ninja reset amazing intriguing
Output
No Yes
思路：
很容易想到先定义一个二维数组check[6][6]，check[i][j]代表第i个串中出现了第j个字母(h=0,a=1,r=2,b=3,i=4,n=5)
得到这个记录了字母的数组之后问题来了。怎样在每个串中只取一个字母得到harbin呢？
有两种方法，我最先想到的就是dfs搜索，用一个辅助数组记录每个字母是否被取过。正当我准备敲dfs时，我看到了I题的题目——
我默念了两遍permutation，这不是排列吗，我的脑海闪过全排列函数next_permutation()，正好可以把所有可能性遍历一遍，只有6!应该不会超时，然后我就敲的next_permutaiton()。
后面想了一下，dfs似乎更快一点，但是全排列也过了。还是数据要是更大比如heilongjiang啥的还是建议用dfs
代码如下
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int main(void)
{
int t;
string s[6];
cin>>t;
int check[6][6];
int a[6];
while(t--)
{
memset(check,0,sizeof(check));
memset(a,0,sizeof(a));
for(int i=0;i<6;i++)
{
cin>>s[i];
for(int j=0;j<s[i].size();j++)
{
if(s[i][j]=='h')
{
check[i][0]=1;
}
else if(s[i][j]=='a')
{
check[i][1]=1;
}
else if(s[i][j]=='r')
{
check[i][2]=1;
}
else if(s[i][j]=='b')
{
check[i][3]=1;
}
else if(s[i][j]=='i')
{
check[i][4]=1;
}
else if(s[i][j]=='n')
{
check[i][5]=1;
}
}
}
for(int i=0;i<6;i++)
{
a[i]=i;
}
int flag=1;
do
{
/* for(int i=0;i<6;i++)
cout<<a[i]<<" ";
cout<<endl;
//cout<<endl;*/
flag=1;
for(int i=0;i<6;i++)
{
if(check[a[i]][i]==0)
{
flag=0;
break;
}
}
if(flag==1)
{
break;
}
}while(next_permutation(a,a+6));;
if(flag==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
I - Interesting Permutation
题意：
有趣的排列，有如下定义
Fi=max{a1,a2.....an}。
Gi=min{a1,a2......an}。
Hi=Fi-Gi
a1-an为1-n的全排列。
T组测试样例，每个样例第一行给一个n，下一行输入n个H,代表H1,H2....Hn.
请问1-n有多少个排列组合能够满足？结果对1e9+7取余。
样例：
Input
3 3 0 2 2 3 0 1 2 3 0 2 3
Output
2 4 0
思路:
特判情况：
第一，我们能够知道的是h1=0,否则不合法输出0即可。
第二，Hn一定小于n，因为最小值为1，最大值为n，不合法输出0。
第三，n==1&&H1==0，直接输出1，只有1一种情况
正常情况：
Hi的意义是在一个区间内max-min。
那么H(I+1)的意义是 在Hi的基础上加上一个数，如果加上的这个数ai+1大于max{a1,a2...ai}||这个数ai+1小于min{a1,a2...ai}，则H(i+1)>H(i).那么有两种情况ans=ans*2.
如果Hi==H(i+1)，那么加上的之个数在(min—max)的区间内，那么有Hi+1-（i-1)种情况。ans=ans*(Hi+2-1).
如果H(i+1)<Hi，不可能，因为加上一个数不能使最大值变小或者最小值变大。直接break输出0.
对了，一开始我用的都是cin、cout竟然超时了，但是我想不到剪枝的办法了，该printf、scanf过了，有其他方法可以教我一下。
代码如下:
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=100050;
const ll mod=1e9+7;
int main(void)
{
ll a[maxn];
int t;
scanf("%d",&t);
int n;
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
if(n==1&&a[1]==0)
{
printf("1n");
continue;
}
int flag=0;
if(a[1]!=0)
{
printf("0n");
continue;
}
ll ans=1;
for(int i=2;i<=n;i++)
{
if(a[i]>=n||a[i]<a[i-1])
{
flag=1;
break;
}
if(a[i]>a[i-1])
{
ans=ans*2%mod;
}
else if(a[i]==a[i-1])
{
ans=ans*(a[i]-i+2)%mod;
}
}
if(flag)
printf("0n");
else
printf("%lldn",ans);
}
}J - Justifying the Conjecture
题意：
有人猜想任何一个正整数都能拆成一个质数和一个合数之和，现在输入一个数，把他拆成一个质数和一个合数吧。不能拆的话输出-1
思路：
如果这个数X是奇数，那么X-3一定是偶数，偶数一定是合数（除了2）。3是质数，满足题意。
如果这个数X是偶数，那么X-2一定是偶数，偶数一定是合数(除了2)。2是质数，满足题意。
最后对X-3=2,X-2=2,以及1既不是质数也不是合数，进行特判，即X<=5输出-1.
代码如下：
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
void solve(ll x)
{
if(x<=5)
{
cout<<-1<<endl;
}
else if(x&1)
{
cout<<3<<" "<<x-3<<endl;
}
else
{
cout<<2<<" "<<x-2<<endl;
}
}
int main(void)
{
int t;
ll x;
cin>>t;
while(t--)
{
cin>>x;
solve(x);
}
}K - Keeping Rabbits
题意：
n个兔子，重量为(w1,w2....wn)每天给他们扔一个胡萝卜，他们会为了胡萝卜打架，体重越大，越可能胜利，获胜的概率为：
吃了这根胡萝卜，他的体重+1，问k天过后，每只兔子的体重期望是多少？（兔子体重不会减少）
思路：
公式题，公式做。k天之后的重量为Wi+(Wi/sum(W1+W2+...+Wn))*k.注意保留小数以及计算时转化类型即可。
代码如下:
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
int main(void)
{
ll t,n,k;
ll a[100005];
cin>>t;
while(t--)
{
cin>>n>>k;
double sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
}
for(int i=1;i<n;i++)
{
printf("%.8lf ",a[i]+((double)a[i]/(sum))*k);
}
printf("%.8lfn",a[n]+((double)a[n]/(sum))*k);
}
}