题解 | #小竹与妈妈#

小竹与妈妈

https://ac.nowcoder.com/acm/contest/45670/A

显然小竹的年龄为 $\frac{x-b}{a}$ 直接输出即可。

#include<bits/stdc++.h>
using namespace std;
int a,b,x;
int main()
{
    cin>>a>>b>>x;
    cout<<(x-b)/a<<'\n';
    return 0;    
}

B.
记录每个房间有多少个出口连接记为 $cnt$ ,每次询问输出 $n-cnt_x$ 即可。

#include<bits/stdc++.h>
using namespace std;
int cnt[100005];
int n,m,q;

int main()
{
    cin>>n>>m>>q;
    assert(1<=n&&n<=1e5);
    assert(1<=m&&m<=1e5);
    assert(1<=q&&m<=1e5);
    for(int i = 1;i<=n;++i)
    {
        int x;
        cin>>x;
        assert(1<=x&&x<=m);
        cnt[x]++;    
    }
    while(q--)
    {
        int x;
        cin>>x;
        assert(1<=x&&x<=m);
        cout<<(n-cnt[x])<<'\n';    
    }
    
    return 0;
}

C.
用一个 $O(n^2)$ 的 $dp$ 即可解决该问题。
设 $dp_i$ 为选择前 $i$ 个数绳子的最大长度。

很容易能列出 $dp_i = \max_{j=1}^{i-k-1}dp_j+a_i$ 。

由于允许 $n^2$ 通过,直接模拟该过程即。最后的答案为 $\max_{i=1}^{n}dp_i$ 。

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[2005];
int dp[2005];
int ans;
 
int main()
{
    cin>>n>>k;
    assert(1<=n&&n<=2000);
    assert(1<=k&&k<=n);
    for(int i = 1;i<=n;++i)
    {
        cin>>a[i];
        assert(a[i]<=2000&&a[i]>=1);
    }
    for(int i = 1;i<=n;++i)
        for(int j = 0;j<=max(0,i-k-1);++j)
        {
            dp[i] = max(dp[j]+a[i],dp[i]);
            ans = max(ans,dp[i]);
        }
    cout<<ans<<'\n';
      
    return 0;
 }

D.
从起点开始 $bfs$ 求出起点到每个位置的最短路,从终点开始同样跑一遍 $bfs$ 求出终点到每个位置的最短路.对于每一个拥有刺激度高于 $x$ 游戏的店铺 $p$ ,要经过该店铺的答案即为起点到 $p$ 的最短路,加上终点到 $p$ 的最短路
时间复杂度 $O(nm)$ ;

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,x;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int sx,sy,ex,ey;
    assert(cin>>n>>m>>x);
    assert(cin>>sx>>sy>>ex>>ey);
    vector<vector<int>> s(n,vector<int>(m));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            assert(cin>>s[i][j]);
    sx--,sy--,ex--,ey--;
    s[sx][sy]=0,s[ex][ey]=0;
    vector<vector<int>> dista(n,vector<int>(m,1e9)),distb=dista;
    function<void(vector<vector<int>>&,int,int)> bfs=[&](vector<vector<int>> &dist,int x,int y)->void{
        array<int,4> dx ={-1,1,0,0},dy ={0,0,-1,1};
        dist[x][y]=0;
        using PII = pair<int,int>;
        queue<PII> qe;
        qe.push({x,y});
        while(qe.size()){
            PII var = qe.front();
            qe.pop();
            for(int i=0;i<4;i++){
                int x= var.first+dx[i],y=var.second+dy[i];
                if(x<0||y<0||x>=n||y>=m)continue;
                if(s[x][y]==-1)continue;
                if(dist[x][y] > dist[var.first][var.second]+1){
                    dist[x][y] = dist[var.first][var.second]+1;
                    qe.push({x,y});
                }
            }
        }
    };
    bfs(dista,sx,sy),bfs(distb,ex,ey);
    int ans = 1e9;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(s[i][j]>x)
                ans = min(ans,dista[i][j]+distb[i][j]);
    if(ans==1e9)
        ans=-1;
    cout << ans<<"\n";
}

E.
相邻结点满足有至少两个不同的共同质因子,也就相当于,相邻两个结点的 $\gcd$ 满足不为任何质数的幂次,且不为1

我们可以把所有质数的幂次使用一个标记数组 $flag$ 标记起来,然后进行树形dp

设 $dp_i$ 为以 $i$ 为根的最大优雅联通块,设 $son_i$ 为 $i$ 的子节点的集合，则

$dp_i = 1 + \sum_{v \in son_i} dp_{v}[flag_{\gcd(v,i)} = 1]$

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
int f[5*maxn+5];
int p[5*maxn+5];
int dp[maxn+5];
int a[maxn+5];
int n;
int ans;
vector<int> edge[maxn+5];
void dfs(int x,int fa)
{
    dp[x] = 1;
    for(auto v:edge[x])
    {
        if(v==fa) continue;
        dfs(v,x);
        if(!f[(__gcd(a[v],a[x]))])
            dp[x]+=dp[v]; 
    }
    ans = max(dp[x],ans);
}
int main()
{
    f[1] = 1;
    for(int i = 2;i<=5*maxn;++i)
        if(!p[i])
        {
            for(int j = i+i;j<=5*maxn;j+=i)
                p[j] = 1;
            for(long long j = i;j<=5*maxn;j*=i)
                f[j] = 1;
                 
        }
    cin>>n;
    assert(1<=n&&n<=1e6);
    for(int i = 1;i<=n;++i)
    {
        cin>>a[i];
        assert(a[i]<=5e6&&a[i]>=1);
    }
    for(int i = 1;i<n;++i)
    {
        int x,y;
        cin>>x>>y;
        assert(1<=x&&x<=n);
        assert(1<=y&&y<=n);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs(1,0);
    for(int i = 1;i<=n;++i)
        assert(dp[i]);
    cout<<ans<<'\n';

    return 0;
 }

F.
$\sum_{p \in permutation} inv(p) \sum_{x = 1}^{n} \sum_{i = 1}^x \sum_{j = x}^n f(p,i,j,x)$

$f(p,l,r,x) = \sum_{i = l}^r [p_i \geq p_x]$
先考虑后面那一堆式子，考虑算出每一个区间的贡献，区间内每一个数作为 $x$ 时，造成的贡献为区间内所有大于等于该数的数的个数。那么长度为 $len$ 的区间的贡献为 $\sum_{i = 1}^{len} i = \frac{len \times (len + 1)}{2}$

所以直接枚举区间长度
$\begin{aligned} & \ \ \ \ \ \sum_{len = 1}^{n} (n - len + 1) \frac{len \times (len + 1)}{2}\\ &= \frac{1}{2} \sum_{len = 1}^n -len^3 + nlen^2 + (n + 1)len\\ &= \frac{1}{2} \times (-\frac{n^2(n + 1)^2}{4} + \frac{n^2(n + 1)(2n + 1)}{6} + \frac{n(n + 1)^2}{2})\\ &= \frac{n^4 + 6n^3 + 11n^2 + 6n}{24}\\ &= \frac{n(n + 1)(n + 2)(n + 3)}{24}\\ &= C_{n + 3}^4 \end{aligned}$
我们发现这个式子与排列无关所以原式可以写成: $C_{n + 3}^4 \sum_{p \in permutation} inv(p)$

我们可以计算每一对逆序对 $(x,y)(x>y)$ 造成的贡献:
$x$ 放在 $y$ 前面有 $\frac{n(n - 1)}{2}$ 种方案，其他位置可以随便放，所以每一对逆序对的贡献为 $(n - 2)!\frac{n(n - 1)}{2}$
共有 $\frac{n(n - 1)}{2}$ 对不同的逆序对
$\sum_{p \in permutation} inv(p) = (n - 2)! (\frac{n(n - 1)}{2})^2$

答案即为 $C_{n + 3}^4(n - 2)!(\frac{n(n - 1)}{2})^2$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
int n; 
vector<int> js;
const int mod = 1e9+7;
ll fac[100006];
ll ifac[100006]; 
int maxn = 1e5+4;
ll ksm(ll x, ll y)
{
    ll ret = 1;
    do {
        if ( y & 1 )
            ret = ret * x % mod;
        x = x * x % mod;
    } while ( y >>= 1 );
    return ret;
}
void init()
{
    fac[0] = 1;
    for ( int i = 1;i <= maxn;i++ ) {
        fac[i] = fac[i - 1] * i % mod;
    }
    ifac[maxn - 1] = ksm(fac[maxn - 1], mod - 2);
    for ( int i = maxn - 1;i >= 1;i-- ) {
        ifac[i - 1] = ifac[i] * i % mod;
    }
}

ll C(int x, int y)
{
    return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}

void solve()
{
    int n;
    cin>>n;
    assert(1<=n&&n<=100000);
    ll ans = (((C(n+3,4))%mod*fac[(n-2)]%mod*(1ll*n*(n-1)/2)%mod*(1ll*n*(n-1)/2)%mod))%mod;
    assert(0<=ans&&ans<=1e9+7);
    cout<<ans<<'\n'; 
}
signed main()
{
    init();
    int t;
    cin>>t;
    assert(1<=t&&t<=100000);
    while(t--)
        solve();
    return 0;
}