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;
}