D-Link with Game Glitch

来源: 牛客多校训练营2 算法: 图论题目链接: https://ac.nowcoder.com/acm/contest/33187/D 补完: Yes 完成时间: July 25, 2022

算法

①二分答案+SPFA判负环

②Karp的最小平均权重环路算法

题解

这里考虑法②

题目有对于配方\(i\)有: 以\(a_i\)个物品 \(b_i\)为原料,制造\(c_i\)个物品\(d_i\)为产品

\[ a_i\times b_i\to c_i \times d_i \]

可以理解为对于配方\(i\)有: 以\(\frac{a_i}{c_i}\)个物品 \(b_i\)为原料,制造\(1\)个物品\(d_i\)为产品

\[ \frac{a_i}{c_i}\times b_i \to d_i \]

对于连续\(k\)个配方可以由配方的系数乘积从原料制造出产品

\[ \prod_{i}^k\frac{a_i}{c_i} 原料\to 产品 \]

若某物品经过\(k\)道配方, 最终可以制造自己, 称为一循环配方

\[ \prod_{i}^k\frac{a_i}{c_i} 物品\to 物品 \]

以\(n\)种物品为点, \(m\)种配方为边, \(\frac{a_i}{c_i}\)为边权建立有向图, 循环配方表现为环

设循环配方中任意物品原有数量为\(x\),个则每次循环后可变为为\(\frac {x}{\prod_{i}^k\frac{a_i}{c_i}}\)个,

要使物品不会变多, 则必须\(x≥\frac {x}{\prod_{i}^k\frac{a_i}{c_i}}\), 也即

\[ \prod_{i}^k\frac{a_i}{c_i}≥1 \]

引入生产修正参数\(w\)

\[ a_i\times b_i\to w\times c_i \times d_i \]

可以理解为

\[ \frac{a_i}{wc_i}\times b_i \to d_i \]

可推得

\[ \prod_{i}^k\frac{a_i}{wc_i} 物品\to 物品 \]

将\(w\)提出有

\[ \frac1{w^k}\prod_{i}^k\frac{a_i}{c_i} 物品\to 物品 \]

重复上文推论

以\(n\)种物品为点, \(m\)种配方为边, \(\frac{a_i}{wc_i}\)为边权建立有向图, 循环配方表现为环

设循环配方中任意物品原有数量为\(x\),个则每次循环后可变为为\(\frac {x}{\frac1{w^k}\prod_{i}^k\frac{a_i}{c_i}}\)个,

要使物品不会变多, 则必须\(x≥\frac {x}{\frac1{w^k}\prod_{i}^k\frac{a_i}{c_i}}\), 也即

\[ \prod_{i}^k\frac{a_i}{c_i}≥w^k \]

对于不同的环有不同的\(\prod_{i}^k\frac{a_i}{c_i}\), 即要求在每一个环中都满足上式,即

\[ \min(\prod_{i}^k\frac{a_i}{c_i})≥w^k \]

且要求\(w\)取最大, 则要求

\[ \min(\prod_{i}^k\frac{a_i}{c_i})=w^k \]

化简得

\[ w=\min\left(\sqrt[k]{\prod_{i}^k\frac{a_i}{c_i}}\right) \]

其中连乘可用对数处理

\[ \ln(\prod_{i}^k\frac{a_i}{c_i})=\sum_i^k\ln(\frac{a_i}{c_i}) \]

化简得

\[ \prod_{i}^k\frac{a_i}{c_i}=e^{\sum_i^k\ln(\frac{a_i}{c_i})} \]

即要求

\[ w^k=e^{\min(\sum_i^k\ln(\frac{a_i}{c_i}))} \]

最终

\[ w=\min(\sqrt[k]{e^{\sum_i^k\ln(\frac{a_i}{c_i})}}) \]

\[ w=\exp\left(\min(\frac{\sum_i^k\ln(\frac{a_i}{c_i})}{k})\right) \]

则理解为求环的最小平均权重

以\(\ln(\frac{a_i}{c_i})\)为边权建图\(G(V,E)\)

有\(Karp的最小平均权重环路算法\)

让\(F[k][v]\)为从任意点出发,经过\(k\)条边到达\(v\)点的最短距离, 对每条边\(u\to v\) 有

\[ F[k][v]=\min_{e\in E}\{F[k-1][u]+w[u][v]\} \]

\[ ans = \min_{v\in V}\{\max_{0≤k≤n-1}\{\frac{F[n][v]-F[k][v]}{n-k}\}\} \]

参考

****有向图中的最小平均权值回路****

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2005;
int n,m,b,d;
double a,c,ans;
double dp[maxn][maxn];
struct edge {
    int u;
    int v;
    double w;
};
vector<edge> edges;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c>>d;
        edges.push_back({b,d,log(a/c)});
    }
    for (int i=1;i<=n;i++) {
        for (auto [u,v,w] : edges) {
            dp[i][v] = min(dp[i][v],dp[i-1][u]+w);
        }
    }
    for(int v=1;v<=n;v++){
        double t = -INFINITY;
        for(int k=0;k<n;k++){
            t = max(t,(dp[n][v]-dp[k][v])/(n-k));
        }
        ans = min(t,ans);
    }
    printf("%.15lf\n",exp(ans));
    return 0;
}

G-Link with Monotonic Subsequence

来源: 牛客多校训练营2 算法: 构造题目链接: https://ac.nowcoder.com/acm/contest/33187/G 补完: Yes 完成时间: August 2, 2022

题意概括

给定一个整数n，由整数1~n任意排列组成一个序列p

\(p的价值=\max(lis(p),lds(p))\)

lis(p)是p的最长递增子序列长度

lds（p)是p的最长递减子序列长度

求所有排列中价值最小的序列（多个只需输出其中一个即可）

即：构造出一个由整数1~n组成的序列，使得其最长递增子序列的长度和最长递减子序列的长度的最大值最小，输出该序列。

解题思路

理解题意后采用逆向思维，想办法怎么破坏子序列的递增和递减性

首先想到，将整个序列分成两部分，使得两段的递减段无法连起来，例如n=8时，4321 8765，开心的交了一发，WA了。。。

再想想，举个大一点的数，n=9时，按上述方式构造应该是：54321 9876，仔细想想。。好像可以分成三段：321 654 987，这样的价值就变成了3

如果是n=10呢？就只能分成4段了：4321 8765 109

总结归纳一下就是：一个序列的价值应该为\([\sqrt{n} ]\)。

代码

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin>>n;
    int a = (int)sqrt(n);
    if(a*a!=n)a++;
    for(int j=1;j<=a;j++){
        for(int i=0;i<a;i++){
            if(j*a-i<=n)
                printf("%d ",j*a-i);
        }
    }
    printf("\n");
}
int main(){
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

H-Take the Elevator

来源: 牛客多校训练营2 算法: 前缀和, 离散化题目链接: https://ac.nowcoder.com/acm/contest/33187/H 补完: Yes 完成时间: July 29, 2022

题解

高\(k\)层的楼用容量为\(m\)的电梯运\(n\)人从\(a_i\)层去\(b_i\)层. 求电梯最快下班时间.

有人上楼有人下楼, 电梯在从下往上运人和从上往下运人之间不冲突.

设有\(up(i)\)人需要从第\(i\)层到第\(i+1\)层, 有\(dn(i)\)人需要从第\(i+1\)层到第\(1\)层,

则电梯在\(i\)到\(i+1\)层之间至少需要从下往上运行\(\lceil \frac{up(i)}{m} \rceil\)次, 至少需要从上往下运行\(\lceil \frac{dn(i)}{m} \rceil\)次,

电梯每次工作都对应一次上升和下降, 则在在\(i\)到\(i+1\)层之间至少需要运行\(\max(\lceil \frac{up(i)}{m} \rceil,\lceil \frac{dn(i)}{m} \rceil)\)个回合, 即为至少要到达\(i+1\)层的回合数, 记为

\[ need[i] = \max(\lceil \frac{up(i)}{m} \rceil,\lceil \frac{dn(i)}{m} \rceil) \]

电梯每次工作都要一次性升到此次任务最高点然后返回第一层, 即在满足高层需求时, 低层需求也会被顺带满足, 故优先考需高层任务. 若高层的任务更多, 低层没有任务却仍会被经过, 因而低层的实际运行次数会被高层的运行次数覆盖, 记实际在\(i\)到\(i+1\)层之间运行的回合数为

\[ cnt[i] = \max_{j≥i}\{need[j]\} \]

统计所有楼层间的运行时间即为最终答案, 每个回合含上下楼两个操作, 每个操作花费\(1\)时间

\[ ans=2*\sum_{i=2}^k cnt[i] \]

按人流方向差分前缀和处理, 上下累加方向相反可反向差分, 然后从高层开始累计.

本题\(k\)比较大, 需要离散化处理 ## 代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n,m,k,sum;
int c[2*MAXN];
int a[MAXN],b[MAXN];
int up[2*MAXN],dn[2*MAXN];
int cnt[2*MAXN];
long long ans;
int main(){
    cin>>n>>m>>k;
    for(int i = 1;i<=n;i++){
        cin>>a[i]>>b[i];
        c[sum++] = a[i];
        c[sum++] = b[i];
    }
    sort(c,c+sum);
    sum = unique(c,c+sum) - c;
    for(int i = 1;i<=n;i++){
        int l = lower_bound(c,c+sum,a[i]) - c;
        int r = lower_bound(c,c+sum,b[i]) - c;
        if(l<r){
            up[l+1]++;
            up[r+1]--;
        }
        else{
            dn[r+1]++;
            dn[l+1]--;
        }
    }
    for(int i = 1;i<sum;i++){
        up[i]+=up[i-1];
        dn[i]+=dn[i-1];
        int need = max((up[i]+m-1)/m,(dn[i]+m-1)/m);
        cnt[need] = max(cnt[need],c[i]-1);
    }
    for(int i = n;i>=1;i--){
        cnt[i] = max(cnt[i+1],cnt[i]);
        ans+=cnt[i];
    }
    cout<<ans*2<<'\n';
    return 0;
}

I-let fat tension

来源: 牛客多校训练营2 算法: 向量, 矩阵乘法补完: Yes 完成时间: August 3, 2022

题解

给\(n\)个练功的大师, 每个大师有\(k\)种属性值和\(d\)种技能等级, 定义为

\[ X_i\in \mathbb R^k, Y_i\in \mathbb R^d \]

大师相互学习, 技能等级得到提升, 其中第\(i\)个大师向第\(j\)个大师学习第\(o\)个技能会有:

\[ y_{i,o}^{i-j}=\frac{X_i\cdot X_j}{|X_i||X_j|} y_{j,o} \]

大师同时向所有大师学习,最终有

\[ y_{i,o}^{new}=\sum_{j=1}^n\frac{X_i\cdot X_j}{|X_i||X_j|} y_{j,o} \]

对于求向量点乘和向量模有

\[ A\cdot B=\sum_{i=1}^La_ib_i\\ |A|=\sqrt{\sum_{i=1}^La_i^2} \]

代入有

\[ y_{i,o}^{new}=\sum_{j=1}^n\frac{\sum_{p=1}^kx_{i,p}x_{j,p}}{\sqrt{\sum_{p=1}^kx_{i,p}^2}\sqrt{\sum_{p=1}^kx_{j,p}^2}} y_{j,o} \]

改变求和顺序可以减少复杂度

\[ y_{i,o}^{new}=\sum_{p=1}^k\frac{x_{i,p}}{\sqrt{\sum_{p=1}^kx_{i,p}^2}} \sum_{j=1}^n\frac{x_{j,p}}{\sqrt{\sum_{p=1}^kx_{i,p}^2}} y_{j,o} \]

大师的属性可以预处理

\[ x_{i,p}'=\frac{x_{i,p}}{\sqrt{\sum_{p=1}^kx_{i,p}^2}} \]

但是直接记录\(x_{i,p}'\)会出问题, 记录分母即可

最后

\[ y_{i,o}^{new}=\sum_{p=1}^kx_{i,p}' \sum_{j=1}^nx_{j,p}'y_{j,o} \]

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int MAXM = 55;

double x[MAXN][MAXM],y[MAXN][MAXM],xx[MAXN],op[MAXN][MAXN];

void solve(){
    int n,k,d;
    cin>>n>>k>>d;
    for(int i = 1; i <= n; i++){
        for(int p = 1; p <= k; p++){
            cin>>x[i][p];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int o = 1; o <= d; o++){
            cin>>y[i][o];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int p = 1; p <= k; p++){
            xx[i] += x[i][p]*x[i][p];
        }
        xx[i] = sqrt(xx[i]);
    }
    for(int o = 1; o <= d; o++){
        for(int p = 1; p <= k; p++){
            for(int j = 1; j <= n; j++){
                op[o][p] += x[j][p]*y[j][o]/xx[j];
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int o = 1; o <= d; o++){
            double ans = 0;
            for(int p = 1; p <= k; p++){
                ans += x[i][p]*op[o][p]/xx[i];
            }
            printf("%lf ",ans);
        }
        printf("\n");
    }
}
int main(){
    int T = 1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

J-Link with Arithmetic Progression

来源: 牛客多校训练营2 算法: 数论题目链接: https://ac.nowcoder.com/acm/contest/33187/J 补完: Yes 完成时间: July 31, 2022

题解

一元线性回归,套公式即可

\[ Y=kx+a \]

\[ k=\frac{\sum(x_i-\bar x)(y_i-\bar y)}{\sum(x_i-\bar x)^2} \]

\[ a=\bar y - k\bar x \]

代码

#include<bits/stdc++.h>
using namespace std;
long double xbar,ybar,x[300005],y[300005],k,k1,k2,a,ans,t;
void solve(){
    xbar=ybar=0;
    k1=k2=0;
    ans=0;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        x[i]=(long double)i;
        xbar+=x[i];
        cin>>y[i];
        ybar+=y[i];
    }
    xbar/=(long double)n;
    ybar/=(long double)n;
    for(int i=1;i<=n;i++){
        k1+=(i-xbar)*(y[i]-ybar);
        k2+=(i-xbar)*(i-xbar);
    }
    k=k1/k2;
    a=ybar-k*xbar;
    for(int i=1;i<=n;i++){
        t=(y[i]-(a+k*x[i]));
        ans+=t*t;
    }
    printf("%.15llf\n",ans);
}
int main(){
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

K-Link with Bracket Sequence I

来源: 牛客多校训练营2 算法: 动态规划题目链接: https://ac.nowcoder.com/acm/contest/33187/K 补完: Yes 完成时间: July 26, 2022

题解

从子序列构造原序列, 求可满足的原序列数量.

考虑\(dp[i][j]\)为以子序列的前\(j\)个字符为子序列能构造出的长度为\(i\)的原序列数量.

或以长度为\(i\)的原序列最多可以提取出的以子序列的前\(j\)个字符为子序列的数量.

对于子序列的第\(j+1\)个字符, 无法在[原序列的被第\(j\)个字符匹配的字符之后、第\(i\)个字符之前]找到.

本题中子序列为可能合法的括号序列, 原序列为合法的括号序列.

在括号序列中, 为使原序列合法, 每个左括号都要有与其匹配的右括号.

增设一维\(dp[i][j][k]\), 其中\(k\)表示原序列中未得到匹配的左括号数量或表示\(i\)个字符之后还需要\(k\)个右括号使原序列合法, 仅当\(k==0\)时原序列为合法括号序列.

对\(dp[i][j][k]\), 若不为合法序列, 让我们继续构造原序列:
- 设原序列的第\(i+1\)个字符为左括号, 则未匹配的左括号数量增多, 此时
  
  若子序列的第\(j+1\)个字符为左括号则恰好得到对应, 即两序列长度都得到增加, 有
  
  \[ dp[i+1][j+1][k+1] += dp[i][j][k] \]
  
  若子序列的第\(j+1\)个字符非左括号则无法得到对应, 仅原序列的长度得到增加, 有
  
  \[ dp[i+1][~~~j~~~][k+1] += dp[i][j][k] \]
- 设原序列的第\(i+1\)个字符为右括号, 则未匹配的左括号数量减少, 此时
  
  若子序列的第\(j+1\)个字符为右括号则恰好得到对应, 即两序列长度都得到增加, 有
  
  \[ dp[i+1][j+1][k-1] += dp[i][j][k] \]
  
  若子序列的第\(j+1\)个字符非右括号则无法得到对应, 仅原序列的长度得到增加, 有
  
  \[ dp[i+1][~~~j~~~][k-1] += dp[i][j][k] \]

初始情况, 有空子序列构造空原序列, 为\(1\)种可能

\[ dp[0][0][0]=1 \]

最终答案为

\[ dp[m][n][0] \]

计算过程中子序列长度不会超过原序列长度故有\(j<=i\)

同时待匹配左括号数量不会超过原序列长度故有\(k<=i\)

为防止越界,与\(k\)相关的指针\(+1\)处理

代码

#include<bits/stdc++.h>
using namespace std;
const int P = 1e9+7;
int dp[205][205][205];
int n,m;
string a;
void add(int& a,int b){
    a = (a+b)%P;
}
void solve(){
    scanf("%d%d%s",&n,&m,&a[1]);
    memset(dp,0,sizeof(dp));
    dp[0][0][0+1] = 1;
    for(int i=0;i<m;i++){
        for(int k=0+1;k<=i+1;k++){
            for(int j=0;j<=i;j++){
                if(a[j+1]=='('){
                    add(dp[i+1][j+1][k+1],dp[i][j][k]);
                }else{
                    add(dp[i+1][ j ][k+1],dp[i][j][k]);
                }
                if(a[j+1]==')'){
                    add(dp[i+1][j+1][k-1],dp[i][j][k]);
                }else{
                    add(dp[i+1][ j ][k-1],dp[i][j][k]);
                }
            }
        }
    }
    printf("%d\n",dp[m][n][0+1]);
}
int main(){
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

L-Link with Level Editor I

来源: 牛客多校训练营2 算法: 动态规划题目链接: https://ac.nowcoder.com/acm/contest/33187/L 补完: Yes 完成时间: July 27, 2022

题解

给\(n\)个世界, 每个世界有含\(m\)个点的有向图, 每个世界可以图上走一步或者不走.

从第一个世界的点\(1\)出发, 想要走到点\(m\), 求最少经过几个世界. 如果走不到就输出\(-1\).

要求

事实上整张地图是立体的, 在第\(i\)个世界时,

对每个点\(u_i\), 若不走则到达下个世界的这个点, 化为有向边\(<u_i,u_{i+1}>\), 对由这个点发出的有向边\(<u_i,v_i>\), 若走一步, 可以化为连向下一个世界的有向边 \(<u_{i},v_{i+1}>\).

记\(dp[i][j]\)为到达第\(i\)个世界的第\(j\)个点需要经过的最小步数, 则可通过上述推出到下一个世界的最小步数.

若没有边指向此点, 仅在上一层的此点基础上加一.

\[ dp[i+1][u_{i+1}]=dp[i][u_{i}]+1 \]

若有边指向此点, 则选步数最小的一点加一

\[ dp[i+1][v_{i+1}]=\min_{u\to v\in E} \{ {dp[i][u_i]+1}\} \]

我们可以选择任意一个世界作为起点, 故第一个点始终求得\(1\)

\[ dp[i+1][1]=dp[i][1]+1=1 \]

故每次循环都要刷新

\[ dp[i][1]=0 \]

其他未到达的点设为无穷大表示不能走到