慕容琳的后花园
慕容琳的后花园
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("%lld\n",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,dp[2][5010],s[2][5010];
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;
    dp[0][st]=1;
    for(int i=1;i<ed;i++)s[0][i]=s[0][i-1]+dp[0][i];
    for(int i=1;i<=m;i++)
    {
        int p=i&1,q=p^1;
        for(int j=1;j<ed;j++)
        {
            dp[p][j]=(j==ed?0:(s[q][mid]-dp[q][j]+mod)%mod);
            s[p][j]=(s[p][j-1]+dp[p][j])%mod;
        }
    }
    printf("%d\n",s[m&1][ed-1]);
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

hgoi#20191029-1
T1-小G的字符串 给定n,k 构造一个长度为n,只能使用k种小写字母的字符串 要求相邻字符不能相同且k种字母都要出现 输出字典序最小的字符串,无解输出-1 解法 简单贪心 答案肯定形如abab…
扫描二维码继续阅读
2019-10-29
功能