• 2021牛客OI赛前集训营-提高组（第六场）题解

    T1 旋律的总数

    Description

    牛牛最近在思考，音乐的主旋律似乎数目是有限的。

    真正的音乐旋律比较复杂，为了简化问题，牛牛把旋律简化成一个长度为 n \mathrm{n} n 的时间相关的序列 a 1 ∼ a n a_1 \sim a_n a1​∼an​ 。

    序列可以填入的数字为 1 ∼ m 1 \sim \mathrm{m} 1∼m。

    但是对于转调前后的旋律应当被认为是一致的，换言之，如果序列

    ∃ k , ∀ i , a i = b i + k (   m o d     m ) \exists k, \forall i, a_i=b_i+k(\bmod\ m) ∃k,∀i,ai​=bi​+k(mod m)

    则视为 a a a 序列和 b b b 序列是相同的。

    牛牛想知道对于给定的 n n n 和 m m m ，有多少种这样的旋律，也就是有多少个各不相同的序列 a a a 。

    答案对 1 0 9 + 7 10^9+7 109+7 取模。

    T ≤ 10 , 1 ≤ n ≤ 1 0 9 , 1 ≤ m ≤ 1 0 6 T\le 10,1\le n\le 10^9,1\le m\le 10^6 T≤10,1≤n≤109,1≤m≤106。

    Solution

    首先显然，当 k ≥ m k\ge m k≥m 的时候，可以转换成 k % m k\%m k%m，所以对于一个给定的序列 a a a，仅有 m m m 个（包括自身）序列和它本质相同。

    我们把这 m m m 个称为一组，那么组与组之间肯定是本质不同的，于是现在只需要求出组数即可。

    序列总数是 m n m^n mn 个， m m m 个为一组，那么就有 m n − 1 m^{n-1} mn−1 组。直接快速幂求出答案。

    Code

    #include
#define mod 1000000007
#define ll long long
using namespace std;
int T;
ll n,m;
ll ksm(ll x,ll y)
{
    if (!y) return 1;
    ll res=1;
    while (y)
    {
        if (y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%lld%lld",&n,&m);
        printf("%lld\n",ksm(m,n-1));
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    T2 水果加工

    Description

    某水果公司有 n \mathrm{n} n 片果园，第 i i i 片果园上种着 a i a_i ai​ 吨水果，公司有 2 个加工基地来加工这些水果，并且，公司雇佣了运输公司将果园上的水果送往各个基地。

    水果加工的流程如下:

    • 运输公司将各片果园的水果输往各个基地。
    • 所有水果均运输完毕后，基地开始加工。

    从第 j \mathrm{j} j 片果园运输水果到第 i \mathrm{i} i 个基地的运输成本为每吨 d i , j d_{i,j} di,j​ 小时。假设第 j \mathrm{j} j 片果园往第 i \mathrm{i} i 个基地运送了 w i , j w_{i,j} wi,j​ 吨水果，则运输时间为 Max ⁡ ( d i , j × w i , j ) ( 1 ≤ i ≤ 2 , 1 ≤ j ≤ n ) \operatorname{Max}\left(d_{i,j} \times w_{i,j}\right)(1 \leq i \leq 2,1 \leq j \leq n) Max(di,j​×wi,j​)(1≤i≤2,1≤j≤n)

    第 i \mathrm{i} i 个基地有 b i b_i bi​ 台机器来加工水果，并且第 i \mathrm{i} i 个基地需要 c i , j c_{i,j} ci,j​ 台机器组成的生产线来加工第 j j j 片果园的水果，加工时间为每吨 u i , j u_{i,j} ui,j​ 分钟。假设第 j \mathrm{j} j 片果园往第 1 个基地运送了 w i , j w_{i,j} wi,j​ 吨水果，则加工时间为 Max ⁡ ( u i , j × w i , j ) ( 1 ≤ i ≤ 2 , 1 ≤ j ≤ n ) \operatorname{Max}\left(u_{i,j} \times w_{i,j}\right)(1 \leq i \leq 2,1 \leq j \leq n) Max(ui,j​×wi,j​)(1≤i≤2,1≤j≤n) 。

    完成水果加工所需要的总时间为 T = Max ⁡ ( d i , j × w i , j ) + Max ⁡ ( u i , j × w i , j ) ( 1 ≤ i ≤ 2 , 1 ≤ j ≤ n ) T=\operatorname{Max}\left(d_{i,j} \times w_{i,j}\right)+\operatorname{Max}\left(u_{i,j} \times w_{i,j}\right)(1 \leq i \leq 2,1 \leq j \leq n) T=Max(di,j​×wi,j​)+Max(ui,j​×wi,j​)(1≤i≤2,1≤j≤n)

    合法的加工方案应该满足:

    • 加工基地对于每片果园里的水果最多只分配 1 条生产线。

    • 对于基地i，基地中所有生产线上的机器数量和不超过 b i b_i bi​ ，即 ∑ j c i , j ≤ b i \sum_j c_{i,j} \leq b_i ∑j​ci,j​≤bi​。

    数据保证存在满足加工流程的方案。

    问合法完成水果加工所需要的最小时间是多少，请输出最少时间。

    n ≤ 40 , a i ≥ 1 , ∑ a i ≤ 40 , 1 ≤ b i ≤ 40 , 1 ≤ c i j ≤ 40 , 0 ≤ d i j ≤ 1 0 9 , 0 ≤ u i j ≤ 1 0 9 n \leq 40,a_i \geq 1,\sum a_i \leq 40,1 \leq b_i \leq 40,1 \leq c_{i j} \leq 40,0 \leq d_{i j} \leq 10^9,0 \leq u_{i j} \leq 10^9 n≤40,ai​≥1,∑ai​≤40,1≤bi​≤40,1≤cij​≤40,0≤dij​≤109,0≤uij​≤109。

    Solution

    比较显然的想到 dp。

    数据不大，而又不可能状压，考虑多维 dp。

    设 f i , j , k 1 , k 2 f_{i,j,k1,k2} fi,j,k1,k2​ 表示第 i i i 片果园的水果已经运完，运了 j j j 个去一号基地，一号基地用了 k 1 k1 k1 台机器，二号基地用了 k 2 k2 k2 台机器的最优运输时间， g i , j , k 1 , k 2 g_{i,j,k1,k2} gi,j,k1,k2​ 表示同意义下的最优加工时间。

    我们从 i i i 推到 i + 1 i+1 i+1 时，枚举 i + 1 i+1 i+1 果园往一号基地运多少水果（记为 l l l)，然后分 l = 0 , l = a i + 1 , 0 < l < a [ i + 1 ] l=0,l=a_{i+1},0l=0,l=ai+1​,0<l<a[i+1] 转移。

    f i , j , k 1 , k 2 ⇒ { f i + 1 , l , k 1 , k 2 + c 2 , i + 1   , l = 0 f i + 1 , l , k 1 + c 1 , i + 1 , k 2   , l = a i + 1 f i + 1 , l , k 1 + c 1 , i + 1 , k 2 + c 1 , i + 1   , 0 < l < a i + 1 f_{i,j,k1,k2}\Rightarrow

    {fi+1,l,k1,k2+c2,i+1 ,l=0fi+1,l,k1+c1,i+1,k2 ,l=ai+1fi+1,l,k1+c1,i+1,k2+c1,i+1 ,0<l<ai+1" role="presentation" style="position: relative;">{fi+1,l,k1,k2+c2,i+1 ,l=0fi+1,l,k1+c1,i+1,k2 ,l=ai+1fi+1,l,k1+c1,i+1,k2+c1,i+1 ,0<l<ai+1
    fi,j,k1,k2​⇒⎩ ⎨ ⎧​fi+1,l,k1,k2+c2,i+1​​ ,l=0fi+1,l,k1+c1,i+1​,k2​ ,l=ai+1​fi+1,l,k1+c1,i+1​,k2+c1,i+1​​ ,0<l<ai+1​​

    g g g 同理。

    显然转移后更优才转移。

    注意在转移的过程中我们关注的是最大值，最后求答案的时候才看最小值。

    Code

    #include
#include
#include
#define N 45
#define inf 3000000000000
#define ll long long
using namespace std;
int n,num1,num2;
ll ans,a[N],c[3][N],d[3][N],u[3][N],f[N][N][N<<1][N<<1],g[N][N][N<<1][N<<1];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
        scanf("%lld",&a[i]);
    scanf("%d%d",&num1,&num2);
    for (int i=1;i<=2;++i)
        for (int j=1;j<=n;++j)
            scanf("%lld",&c[i][j]);
    for (int i=1;i<=2;++i)
        for (int j=1;j<=n;++j)
            scanf("%lld",&d[i][j]);
    for (int i=1;i<=2;++i)
        for (int j=1;j<=n;++j)
            scanf("%lld",&u[i][j]);
    for (int i=1;i<=n;++i)
    	for (int j=0;j<=a[i];++j)
    		for (int k1=0;k1<=num1;++k1)
    			for (int k2=0;k2<=num2;++k2)
    				f[i][j][k1][k2]=g[i][j][k1][k2]=inf;
    for (int i=0;i<=n;++i)
    	for (int j=0;j<=a[i];++j)
    		for (int k1=0;k1<=num1;++k1)
    			for (int k2=0;k2<=num2;++k2)
					for (int l=0;l<=a[i+1];++l)
					{
						ll now=max(f[i][j][k1][k2],max((ll)d[1][i+1]*l,(ll)d[2][i+1]*(a[i+1]-l)))+max(g[i][j][k1][k2],max((ll)u[1][i+1]*l,(ll)u[2][i+1]*(a[i+1]-l)));
						if (l==0)
						{
							if (now<f[i+1][l][k1][k2+c[2][i+1]]+g[i+1][l][k1][k2+c[2][i+1]]) 
							{ 
								f[i+1][l][k1][k2+c[2][i+1]]=max(f[i][j][k1][k2],d[2][i+1]*a[i+1]);
								g[i+1][l][k1][k2+c[2][i+1]]=max(g[i][j][k1][k2],u[2][i+1]*a[i+1]);
							}
						}
						else if (l==a[i+1])
						{
							if (now<f[i+1][l][k1+c[1][i+1]][k2]+g[i+1][l][k1+c[1][i+1]][k2]) 
							{
								f[i+1][l][k1+c[1][i+1]][k2]=max(f[i][j][k1][k2],d[1][i+1]*a[i+1]);
								g[i+1][l][k1+c[1][i+1]][k2]=max(g[i][j][k1][k2],u[1][i+1]*a[i+1]);
							}
						}
						else 
						{
							if (now<f[i+1][l][k1+c[1][i+1]][k2+c[2][i+1]]+g[i+1][l][k1+c[1][i+1]][k2+c[2][i+1]])
							{
								f[i+1][l][k1+c[1][i+1]][k2+c[2][i+1]]=max(f[i][j][k1][k2],max((ll)d[1][i+1]*l,(ll)d[2][i+1]*(a[i+1]-l)));
								g[i+1][l][k1+c[1][i+1]][k2+c[2][i+1]]=max(g[i][j][k1][k2],max((ll)u[1][i+1]*l,(ll)u[2][i+1]*(a[i+1]-l)));
							}
						}
					}
	ans=inf;
	for (int i=0;i<=a[n];++i)
		for (int j=0;j<=num1;++j)
			for (int k=0;k<=num2;++k)
				ans=min(ans,f[n][i][j][k]+g[n][i][j][k]);
	printf("%lld\n",ans);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    T3 最佳位置

    Description

    牛牛最近在研究一个问题，他将其称之为“最佳位置”问题。

    有 n n n 个座位从左到右排成一行，相邻之间两两距离为 1 ，编号从 1 到 n n n 。

    会有 m m m 个人按顺序进来，选择一个座位坐下，新来的人会计算每个位置，离最近的已被坐的座位的距离。新来的人会选择距离最大的座位坐下，如果有多个，他会选择编号最小的。如果场上都是空位置，来的人会选择坐在位置 1 。

    如 xoooxoxx, 离被坐的座位的距离就分别为 01210100 ，如果这时候新来一个人，会选择坐在位置 3 ，变成 xoxoxoxx。

    当然，这些人也会离开，而空出当前的位置。

    牛牛现在拿到了一张进入和离开的顺序表，他想知道每个人落座时，会选择什么位置。

    1 ≤ n ≤ 1 0 9 , 1 ≤ m ≤ 3 × 1 0 5 , m ≤ n 1\le n\le 10^9,1\le m\le 3\times 10^5,m\le n 1≤n≤109,1≤m≤3×105,m≤n。

    Solution

    如果我们用堆来维护连续空串，那么这道题其实就是动态维护堆的过程，其中我们可以插入元素和删除任意元素。这可以通过懒惰删除法来解决。

    具体来说，堆的每个元素维护四个值：空段长度，来人的落位位置，左边界的人的编号，右边界的人的编号。特殊地，将 0 号位的人的编号记为 0， n + 1 n+1 n+1 号位的人的编号记为 m + 1 m+1 m+1。

    同时记录 l i , r i l_i,r_i li​,ri​ 表示 i i i 号人作为左/右边界的那个空串的右/左边界的人的编号。

    那么当进入的时候，先进行删除，即删除堆中从顶开始那些 l x [ r ] ≠ x [ l ] l_{x[r]}\not =x[l] lx[r]​=x[l] 或者 r x [ l ] ≠ x [ r ] r_{x[l]}\not =x[r] rx[l]​=x[r] 的位置。随后就是将堆顶拿出来，更新答案，同时将堆顶区间拆开，重新加入到堆中。

    当离开的时候，只更新 l , r l,r l,r，不对堆进行修改。同时将被 x x x 分开的两个区间重新合并，再加回堆中。

    Code

    #include
#include
#include
#include
#define M 300005
using namespace std;
struct node{int dis,pos,lid,rid;};
int n,m,num,ans[M],lid[M],rid[M];
bool b[M];
node d[M<<1];
priority_queue<node> q;
bool operator <(const node &x,const node &y) {return x.dis<y.dis||(x.dis==y.dis&&x.pos>y.pos);}
int main()
{
    scanf("%d%d",&n,&m);
    memset(lid,-1,sizeof(lid));memset(rid,-1,sizeof(rid)); 
    lid[m+1]=0;rid[0]=m+1;
	node x;
	x.dis=m;x.pos=1;x.lid=0;x.rid=m+1;
	q.push(x);
	for (int i=1;i<=m<<1;++i)
	{
		int x;
		scanf("%d",&x);
		if (!b[x])
		{
			node now,nxt;
			while (true)
			{
				now=q.top();q.pop();
				if (lid[now.rid]==now.lid&&rid[now.lid]==now.rid) break;
			}
			ans[x]=now.pos;
			rid[now.lid]=lid[now.rid]=x;
			lid[x]=now.lid;rid[x]=now.rid;
			if (now.lid==0)
			{
				nxt.dis=now.pos-1;nxt.pos=1;
				nxt.lid=0;nxt.rid=x;
				q.push(nxt);
			}
			else
			{
				nxt.dis=(now.pos-ans[now.lid])/2;nxt.pos=(now.pos+ans[now.lid])/2;
				nxt.lid=now.lid;nxt.rid=x;
				q.push(nxt);
			}
			if (now.rid==m+1)
			{
				nxt.dis=n-now.pos;nxt.pos=n;
				nxt.lid=x;nxt.rid=m+1;
				q.push(nxt);
			}
			else
			{
				nxt.dis=(ans[now.rid]-now.pos)/2;nxt.pos=(ans[now.rid]+now.pos)/2;
				nxt.lid=x;nxt.rid=now.rid;
				q.push(nxt);
			}
			b[x]=true;
		}
		else
		{
			int l=lid[x],r=rid[x];
			lid[rid[x]]=lid[x];rid[lid[x]]=rid[x];
			lid[x]=rid[x]=-1;
			node nxt;
			if(l!=0&&r!=m+1)
			{
				nxt.dis=(ans[r]-ans[l])/2;nxt.pos=(ans[r]+ans[l])/2;
				nxt.lid=l;nxt.rid=r;
				q.push(nxt);
			}
			else if (l==0)
			{
				nxt.dis=ans[r]-1;nxt.pos=1;
				nxt.lid=0;nxt.rid=r;
				q.push(nxt);
			}
			else if (r=m+1)
			{
				nxt.dis=n-ans[l];nxt.pos=n;
				nxt.lid=l;nxt.rid=m+1;
				q.push(nxt);
			}
		}
	}
    for (int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91

    T4 跑步路线

    Description

    牛牛最近开始晨跑了，他把城市的路线抽象成了一张无向图，每个路口视为一个点，路口之间的路视为一条边。

    牛牛估计了跑过每条边的所需时间，为了保守估计所需时间，牛牛认为经过每一个点也需要 t 0 t_0 t0​ 的时间。 比如对于路线 1->3->2->4 ，其中 3 和 2 各经过了一遍，需要花费 2 × t 0 2\times t_0 2×t0​ 的时间。

    在经过很多次槽糕的路线体验之后，牛牛决定请你来帮他设计一条路线，他的要求是:

    1. 需要按顺序经过 k k k 个点，用 a 1 , a 2 , ⋯   , a k a_1, a_2, \cdots, a_k a1​,a2​,⋯,ak​ 表示，这些点可能重复。偶尔可能会有相邻的点相同的情况，这种情况下不需要额外计算 t 0 t_0 t0​ 的花费。
    2. 牛牛希望经过的路线在地图的最小生成树上。
    3. 在满足以上两条的需求下，使总距离尽可能短。

    牛牛起点在位置 a 1 a_1 a1​ ，牛牛梖知道这样的路线中，最短的路线的距离是多少。

    Solution

    非常板的一道题。

    首先先求出图的最小生成树。

    然后我们看题目要求什么：两点间路径长和两点间的点数。

    而这都是经典的用 L C A \mathrm{LCA} LCA 处理的问题。

    最后处理一下额外的 t 0 t_0 t0​ 代价。

    Code

    #include
#include
#define N 200005
#define ll long long
#define ull unsigned long long
using namespace std;
int n,m,tot,k,ti,lst,num,fb[N],f[N<<1][18];
__int128 ans,dep[N],dis[N];
struct edg{int x,y;ll z;}w[N];
struct node{int to,next,head;ll val;}a[N<<1];
bool cmp(edg x,edg y) {return x.z<y.z;}
int find(int x) {return fb[x]==x?x:fb[x]=find(fb[x]);}
void add(int x,int y,int z)
{
    a[++tot].to=y;a[tot].val=z;a[tot].next=a[x].head;a[x].head=tot;
    a[++tot].to=x;a[tot].val=z;a[tot].next=a[y].head;a[y].head=tot;
}
void dfs(int x,int fa)
{
    dep[x]=dep[fa]+1;f[x][0]=fa;
    for (int i=a[x].head;i;i=a[i].next)
    {
        int y=a[i].to;
        if (y==fa) continue;
        dis[y]=dis[x]+a[i].val;
        dfs(y,x);
    }
}
int LCA(int x,int y)
{
    if (dep[x]!=dep[y])
    {
        if (dep[x]<dep[y]) swap(x,y);
        for (int i=17;i>=0;--i)
            if (dep[f[x][i]]>=dep[y]) x=f[x][i];
    }
    if (x==y) return x;
    for (int i=17;i>=0;--i)
        if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
void print(__int128 x)
{
	if (x==0) return;
	print(x/10);
	putchar(x%10+'0');
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i)
        scanf("%d%d%lld",&w[i].x,&w[i].y,&w[i].z);
    sort(w+1,w+m+1,cmp);
    for (int i=1;i<=n;++i)
        fb[i]=i;
    for (int i=1;i<=m;++i)
    {
        int x=find(w[i].x),y=find(w[i].y);
        if (x!=y) fb[x]=y,add(w[i].x,w[i].y,w[i].z);
    }
    dfs(1,0);
    for (int j=1;j<=17;++j)
        for (int i=1;i<=n;++i)
            f[i][j]=f[f[i][j-1]][j-1];
    scanf("%d%d",&k,&ti);
    scanf("%d",&lst);
    for (int i=2;i<=k;++i)
    {
        int x;
        scanf("%d",&x);
        if (lst==x) continue;
        int lca=LCA(lst,x);
        ans+=(dis[x]+dis[lst]-2*dis[lca])+(ull)(dep[x]+dep[lst]-2*dep[lca])*(__int128)ti;
        lst=x;
    }
    ans-=ti;
    print(ans);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
  • 相关阅读:
    Android学习笔记 2.4.3 实例——使用QuickContactBadge关联联系人 && 2.4.4 实例——可折叠的悬浮按钮
    go使用zap + lumberjack重构项目的日志系统
    调用MapReuce对文件中各单词出现次数统计
    【busybox记录】【shell指令】chown
    前端字符串方法汇总
    PX4实战之旅（五）：利用T265实现室内定点飞行
    【C++】十大排序算法之 插入排序 & 希尔排序
    mysql 中 substring_index的用法，小白都能看懂的。
    java 连接SSH工具操作服务器 (构建者模式+Util类) 分享
    Dubbo 一些你不一定知道但是很好用的功能
  • 原文地址：https://blog.csdn.net/LZX_lzx/article/details/126909156