hgoi#20191029-1
T1- 小 G 的字符串
给定 n,k 构造一个长度为 n,只能使用 k 种小写字母的字符串 要求相邻字符不能相同且 k 种字母都要出现 输出字典序最小的字符串,无解输出 -1
解法
简单贪心 答案肯定形如 ababa...cdefg...
ac 代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
string s;
int main()
{
freopen("str.in","r",stdin);
freopen("str.out","w",stdout);
scanf("%d%d",&n,&m);
if(n<m)puts("-1"),exit(0);
if(m==1)
{
if(n==1)puts("a"),exit(0);
else puts("-1"),exit(0);
}
int l=n-(m-2);
for(int i=1;i<=l;i++)
if(i&1)s+='a';
else s+='b';
for(int i=3;i<=m;i++)s+='a'+i-1;
cout<<s<<endl,exit(0);
return 0;
}
T2- 小 G 的城堡
给定 n,k 构造一幅有向图,每个点出度为 1 使 1~k 的点都能走到 1,k+1~n 的点都不能走到 1 输出方案数
解法
简单数学题 可以发现对于 k +1->n 的点,只要边走到的点不在 1 ->k 中即可 这一部分答案贡献为 $(n-k)^{n-k}$ 对于 1~k 的点,可以 k^k 枚举边走到的点,然后判断合法性 通过暴力还可以发现这一部分的贡献即为 $k^{k-1}$
ac 代码
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
ll p(ll a,ll b)
{
a%=mod;
ll ret=1;
while(b)
{
if(b&1)ret=ret*a%mod;
a=a*a%mod,b/=2;
}
return ret;
}
ll n,m,cnt;
int main()
{
freopen("castle.in","r",stdin);
freopen("castle.out","w",stdout);
scanf("%lld%lld",&n,&m);
printf("%lldn",p(m,m-1)*p(n-m,n-m)%mod);
return 0;
}
T3- 小 G 坐电梯
给定 n,A,B,k 在长度为 n 的数轴上起点为 A,限制点为 B 你可以走 k 步,每次从 x 点走到 y 点需要满足 x 到 y 的距离小于 x 到 B 的距离 求走的方案数
解法
简单 dp 题 容易得到永远不会跨过 B 如果 A 在 B 的右边就翻转整个数轴 使得我们永远在 B 的左端走 dp[i][j]表示走了 i 步,当前在 j 的方案数 dp[i][j]=sum(dp[i-1][1~mid-1])-d[i-1][j] 前缀和优化一下即可
ac 代码
#include<bits/stdc++.h>
#define mod 1000000007
#define mid ((j+ed+1)/2-1)
using namespace std;
int n,m,st,ed,dp2,s2;
int main()
{
freopen("lift.in","r",stdin);
freopen("lift.out","w",stdout);
scanf("%d%d%d%d",&n,&st,&ed,&m);
if(st>ed)
st=n-st+1,ed=n-ed+1;
dp0=1;
for(int i=1;i<ed;i++)s0=s0+dp0;
for(int i=1;i<=m;i++)
{
int p=i&1,q=p^1;
for(int j=1;j<ed;j++)
{
dpp=(j==ed?0:(sq-dpq+mod)%mod);
sp=(sp+dpp)%mod;
}
}
printf("%dn",sm&1);
return 0;
}