HGOI 20191029 题解

Promblem A 小$G$的字符串

　　Solution ： 

　　　　我们考虑构造，显然是形如$a,b,a,b,...,c,d...$的字符串。

　　　　即从$[1,n-k+2]$交替填$a,b$，然后$[n-k+3,n]$依次填$c,d,e ... $

　　　　这样构造的时间复杂度是$O(n)$

# pragma GCC optimize(3)
# include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char ans[N];
int n,k;
int main() {
  freopen("str.in","r",stdin);
  freopen("str.out","w",stdout);
    scanf("%d%d",&n,&k);
    if (k == 1 && n == 1) {
        puts("a"); return 0;
    }
    if (k > n || k ==1) {
        puts("-1"); return 0;
    }
    char now='c';
    for (int i=n-k+3;i<=n;i++) ans[i]=now++;
    int op = 0;
    for (int i=1;i<n-k+3;i++,op=1-op) ans[i]='a'+op;
    for (int i=1;i<=n;i++) putchar(ans[i]);
    puts("");
    return 0;
}

str.cpp

Promblem B 小$G$的城堡

　　Solution ： 

　　　　我们将点分为$[1,k]$和$[k+1,n]$两部分来考虑。

　　　　第$1$部分的点进行连边，使得所有点都能走到$1$，对于上述数据范围直接$dfs$即可(事实上答案为$k^{k-1}$)。

　　　　第$2$部分的点随意连边即可，显然方案数$(n-k) ^ {n-k}$ 。

　　　　所以最后的答案就是$k^{k-1} (n-k)^{n-k}$。

　　　　时间复杂度就是$O(log_2 n )$。

# pragma GCC optimize(3)
# include<bits/stdc++.h>
# define int long long
using namespace std;
const int mo=1e9+7;
const int d[] = {0,1,2,9,64,625,7776,117649,2097152};
int Pow(int x,int n) {
    int ans=1;
    while (n) {
        if(n&1) ans=ans*x%mo;
        x=x*x%mo;
        n>>=1;
    }
    return ans%mo;
}
signed main()
{
  freopen("castle.in","r",stdin);
  freopen("castle.out","w",stdout);
    int n,k; cin >> n >> k;
    int ans = Pow((n-k)%mo,n-k) * d[k] % mo;
    cout<<ans<<'\n';
    return 0;
}

castle.cpp

Promblem C 小$G$坐电梯

Solution ： 

　　可以考虑一个$O(n^2k)$的暴力dp，设$f[i][j]$表示当前第$i$次走动后处在第$j$个位置，方案数。

　　考虑刷表，$f[i][j]$能转移到$f[i+1][k]$的条件是$k\neq j$且$|j-k|<|j-B|$

　　本题的状态数$O(n^2)$，考虑优化转移.

　　容易发现，每一次的刷表转移是一个区间加的过程，需要在最后维护每个单点的值。

　　也就说，当前状态为$(i,j)$,$k \in [\max\{j-|j-B|+1,1\} , \min\{n,j+|j-B|-1\}] , k \neq j$ 对于

　　直接差分就好了。

　　于是转移就变成均摊$O(1)$的。

　　总时间复杂度为$O(nk)$

# pragma GCC optimize(3)
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N=5e3+10;
const int mo=1e9+7;
int n,A,B,k;
int f[N],c[N];
signed main()
{
  freopen("lift.in","r",stdin);
  freopen("lift.out","w",stdout);
    cin >> n >> A >> B >> k; f[A]=1;
    for (int i=0;i<k;i++) {
        for (int j=1;j<=n;j++) c[j]=0;
        for (int j=1;j<=n;j++) {
            int ret = abs(j-B);
            int l = max(j-ret+1,1ll),r = min(n,j+ret-1);
            (c[l]+=f[j])%=mo; (c[r+1]+=mo-f[j])%=mo;
            if (j>=l&&j<=r) (c[j]+=mo-f[j])%=mo,(c[j+1]+=f[j])%=mo;
        }
        for (int j=1;j<=n;j++) (c[j]+=c[j-1])%=mo,f[j]=c[j];
    }
    int ans=0;
    for (int i=1;i<=n;i++) (ans+=f[i])%=mo;
    cout<< ans << '\n';
    return 0;
}

lift.cpp