2023牛客暑期多校第一场部分题解_graph 牛客暑期2023
赞
踩
B
官方题解说是乱搞题，而我队友实际上也确实乱搞过去了（
就是先随便取两个点，有了两个点之后第三个点肯定选离这两个点构成的直线最远的那个，要不然没法包含整个凸多边形。这个过程可以用个三分。
但是确定了第三个点之后，第一个点又不一定合法了，再用二三点确定新的第一个点，然后用新的第一个点和第三个点确定新的第二个点……
就这样反复操作，直到找到一组解。时间复杂度不会证，但感性理解应该是很快能找到的。
题是队友写的，有空再补我自己的代码吧。
C
首先题目有个障眼法，先把两个操作的+x/k,-1改成+x,-k，变成整数运算之后才好考虑。
但是赛时并没有做出来（
题解做法很妙，2操作不考虑不够k的不减k这个限制，每次区间内所有树都集体减
k
k
k。记一棵树上的胡萝卜数量为
a
i
a_i
ai，
a
i
a_i
ai 的历史最小值为
a
m
i
n
a_{min}
amin，第
i
i
i 棵树被Pick了
d
d
d 次，那么存在结论：若
a
m
i
n
<
0
a_{min}<0
amin<0，则这
d
d
d 次中有
⌈
−
a
m
i
n
k
⌉
\lceil\dfrac {-a_{min}} k \rceil
⌈k−amin⌉ 次Pick是Pick失败的。
要理性证明不难，但是从感性上其实也能明显感觉到其合理性。具体一点儿就是，某次2操作假如Pick失败了，那么 ⌈ − a m i n k ⌉ \lceil\dfrac {-a_{min}} k \rceil ⌈k−amin⌉ 的值一定会比操作前减小恰好 1 1 1。
这种先不考虑限制暴力做，然后根据暴力做的结果求出有限制下的结果的思想其实感觉以前还见过挺多次的，这次要长个教训记住了。
所以第 i i i 棵树对答案的贡献就是 d − ⌈ − a m i n k ⌉ d-\lceil\dfrac {-a_{min}} k \rceil d−⌈k−amin⌉，问题变成了求每棵树的 a m i n a_{min} amin，考虑线段树分治。
一般的线段树分治只需要维护一个全局的解，这里有 n n n 个解要求，难道要整 n n n 棵线段树吗？不整也不行，但直接整又会超时。注意到每棵树的线段树其实可以在上一棵树的基础上转移过来，并且转移次数是 2 m 2m 2m 次，时间复杂度 O ( m log m ) O(m\log m) O(mlogm)（官方题解复杂度好像写成了 O ( n ) O(n) O(n)），于是就做完了。
代码相当好写：
#include <bits/stdc++.h> using namespace std; #define ll long long #define cn getchar template<class TY>void read(TY &x){ x=0;int f1=1;char ch=cn(); while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();} while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1; } template<class TY>void write2(TY x){ if(x>9)write2(x/10); putchar(x%10+'0'); } template<class TY>void write(TY x){ if(x<0)putchar('-'),x=-x; write2(x); } int n,m,k; struct par{ int x,z,t; }; vector<par> b; bool cmp(par x,par y){return x.x<y.x;} struct node{ int l,r,mid; long long mi,sum; node *zuo,*you; node(int x,int y):l(x),r(y),mid(l+r>>1),mi(0),sum(0),zuo(NULL),you(NULL){ if(l==r)return; zuo=new node(l,mid); you=new node(mid+1,r); } void change(int x,int z){ if(l==r){ sum+=z;mi+=z; return; } if(x<=mid)zuo->change(x,z); else you->change(x,z); mi=min(zuo->mi,zuo->sum+you->mi); sum=zuo->sum+you->sum; } }*rt=NULL; int main() { read(n);read(m);read(k); long long ans=0; for(int i=1;i<=m;i++){ int type,x,y; read(type);read(x);read(y); if(type==1){ int z;read(z); b.push_back((par){x,z,i}); if(y<n)b.push_back((par){y+1,-z,i}); }else{ ans+=y-x+1; b.push_back((par){x,-k,i}); if(y<n)b.push_back((par){y+1,k,i}); } } sort(b.begin(),b.end(),cmp); rt=new node(1,m); for(int i=1,j=0;i<=n;i++){ while(j<b.size()&&b[j].x==i) rt->change(b[j].t,b[j].z),j++; long long mi=rt->mi; if(mi<0)mi=(-mi+k-1)/k; else mi=0; ans-=mi; } write(ans); }
- 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
D
虽然是个大水题，但其实也是个老早就有的小trick，比如这个题：
1~n n n n 个数，每次可以选还存在的某个数 x x x，拿走 x x x 以及它的所有因子，无法操作者失败，问先手是否必胜。
重点就是 1 1 1 一定会在第一次操作后被拿走，因为是所有数字的因子。如果取 2 2 2 ~ n n n 能赢就取，不能就取 1 1 1 把这个必败态丢给对面。
这题一样，
(
1
,
1
)
(1,1)
(1,1) 位置就承担了这个能把必败态丢给对面的角色。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
if(n==1&&m==1)printf("Walk Alone");
else printf("Kelin");
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
H
交换 a a a 里两个和交换 b b b 里两个是等价的，假设就交换 a a a 里的吧。并且显然 a i = b i a_i=b_i ai=bi 的位置不需要考虑。
假设把 ( a i , b i ) (a_i,b_i) (ai,bi) 或 ( b i , a i ) (b_i,a_i) (bi,ai) 看做一个区间，那么如果交换 i , j i,j i,j 能使答案变小，那么一定有 [ a i < b i ] ≠ [ a j < b j ] [a_i<b_i]\neq [a_j<b_j] [ai<bi]=[aj<bj]，同时他们俩的区间还有交集。（证明的话画画图一眼就看明白了）
将 a i < b i a_i<b_i ai<bi 和 a i > b i a_i>b_i ai>bi 的分成两类，求出最大交集即可。
感觉比J还简单一点儿，为啥比J过的人数少这么多（
代码如下：
#include <bits/stdc++.h> using namespace std; int n,a[1000010],b[1000010]; struct par{ int l,r,p; }; vector<par> s; bool cmp(par x,par y){return x.l<y.l;} int R[2]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); long long sum=0; for(int i=1;i<=n;i++){ if(a[i]<b[i])s.push_back((par){a[i],b[i],0}); if(a[i]>b[i])s.push_back((par){b[i],a[i],1}); sum+=abs(a[i]-b[i]); } int ans=0; sort(s.begin(),s.end(),cmp); R[0]=R[1]=-1e9; for(auto i:s){ ans=max(ans,min(i.r,R[i.p^1])-i.l); R[i.p]=max(R[i.p],i.r); } printf("%lld",sum-2ll*ans); }
- 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
J
仔细观察发现每次赌赢，都比上一次赌赢恰好多 1 1 1 元。
所以不妨将两次赌赢之间视作一轮，也就是输输输…输赢为一轮。那么每轮之间输掉的概率是独立的，假设第
i
i
i 轮输掉的概率为
f
(
i
)
f(i)
f(i)，那么最后获胜的概率就是
∏
i
=
n
n
+
m
−
1
(
1
−
f
(
i
)
)
\prod_{i=n}^{n+m-1}\left(1-f(i)\right)
∏i=nn+m−1(1−f(i))。
而 f ( i ) f(i) f(i) 也很好算，连续输第 i i i 次时会少 2 i − 1 2^{i-1} 2i−1 元，假设 2 k − 1 − 1 ≤ i < 2 k − 2 2^{k-1}-1\leq i<2^k-2 2k−1−1≤i<2k−2，那么最多可以输 k − 1 k-1 k−1 轮，输完 k − 2 k-2 k−2 轮后的钱数就不足以支付第 k k k 轮了，那么输掉的概率就是 1 2 k − 1 \dfrac 1 {2^{k-1}} 2k−11。
而将概率相同的分组，一共只有 log \log log 组，每组分别求出对答案的贡献即可。
代码如下：
#include <bits/stdc++.h> using namespace std; #define mod 998244353 int ksm(int x,int y){ int re=1; for(;y;y>>=1){ if(y&1)re=1ll*re*x%mod; x=1ll*x*x%mod; } return re; } #define inv(x) ksm(x,mod-2) const int inv2=(mod+1)/2; int main() { int n,m;cin>>n>>m; int ans=1; for(int k=2;k<=31;k++) if((1ll<<k)>n+1){ int p=(1-ksm(inv2,k-1)+mod)%mod; if((1ll<<k)>n+m+1){ ans=1ll*ans*ksm(p,n+m+1-max(1<<k-1,n+1))%mod; break; }else{ ans=1ll*ans*ksm(p,(1ll<<k)-max(1<<k-1,n+1))%mod; } } cout<<ans; }
- 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
K
首先从 1 1 1 向外跑最短路，将图分层，保留距离 k k k 以内的点，以及求一棵最短路树。
显然是可以贪心的，对于不在最短路树上的边 ( u , v ) (u,v) (u,v)，就狠狠加点，加到最大贡献。假设 d i d_i di 为 i i i 到 1 1 1 的最短距离，那么一条边的贡献就是 ( k − d u ) + ( k − d v ) (k-d_u)+(k-d_v) (k−du)+(k−dv)。
假如是最短路树上的边，那么肯定不动最好，不然的话它加一个点，子树内所有点 d i + 1 d_i+1 di+1，非树边的贡献减少的肯定不止 1 1 1，那答案一定会变劣。
但有一种特殊情况，就是这条边是叶子边，并且叶子不和任何非树边相连，那么往这条边上加点就没有额外影响，直接加满即可。
代码如下：
#include <bits/stdc++.h> using namespace std; #define maxn 200010 int n,m,k; struct edge{int y,next;}e[maxn<<2]; int first[maxn],et=1; void buildroad(int x,int y){ e[++et]=(edge){y,first[x]}; first[x]=et; } void addedge(int x,int y){ buildroad(x,y);buildroad(y,x); } int dis[maxn],from[maxn]; int q[maxn],st,ed; void bfs(){ memset(dis,63,sizeof(dis)); q[st=ed=1]=1;dis[1]=0; while(st<=ed){ int x=q[st++]; for(int i=first[x];i;i=e[i].next){ int y=e[i].y; if(dis[y]>dis[x]+1){ dis[y]=dis[x]+1; from[y]=i; q[++ed]=y; } } } } bool chu[maxn]; int main() { scanf("%d %d %d",&n,&m,&k); for(int i=1;i<=m;i++){ int x,y; scanf("%d %d",&x,&y); addedge(x,y); } bfs(); long long ans=0; for(int i=1;i<=n;i++) if(dis[i]<=k)ans++; for(int i=1;i<=n;i++)if(dis[i]<k) for(int j=first[i];j;j=e[j].next) if((j^1)!=from[i])chu[i]=true; for(int i=1;i<=n;i++)if(dis[i]<k) for(int j=first[i];j;j=e[j].next){ int x=i,y=e[j].y; if(!chu[x])continue; if((j^1)==from[x])continue; // int Ans=ans; if(j!=from[y])ans+=k-dis[x]; else if(!chu[y])ans+=k-dis[y]; // printf("%d %d : %d\n",x,y,ans-Ans); } printf("%lld",ans); }
- 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
L
对于 x x x，每三次操作后会变成 A B C x A_{B_{C_x}} ABCx，可以将 A ∘ B ∘ C i A\circ B\circ C_i A∘B∘Ci 看做一个新数组，对于 y , z y,z y,z 处理方法类似。由于 A , B , C A,B,C A,B,C 都是 n n n 的排列，所以 A ∘ B ∘ C A\circ B\circ C A∘B∘C 也是 n n n 的排列，所以 i i i 向 A ∘ B ∘ C i A\circ B\circ C_i A∘B∘Ci 连边的话也会成环。
只要想到上面的性质，接下来就很好做了，跑 e x c r t excrt excrt 对 x , y , z x,y,z x,y,z 以及 A y , B z , C x A_y,B_z,C_x Ay,Bz,Cx， A B z , B C x , C A y A_{B_z},B_{C_x},C_{A_y} ABz,BCx,CAy 分别求解即可。
代码如下：
#include <bits/stdc++.h> using namespace std; #define maxn 100010 #define ll long long #define inf 1000000000000000000ll int n,m,A[maxn],B[maxn],C[maxn]; ll exgcd(ll a,ll b,ll &x,ll &y){ if(!b){x=1;y=0;return a;} ll g=exgcd(b,a%b,y,x); return y-=a/b*x,g; } ll ksc(ll x,ll y,ll mod){ return (ll)((__int128)x%mod*y%mod); } ll excrt(vector<ll> &m,vector<ll> &a){ ll x=a[0],M=m[0]; for(int i=1;i<m.size();i++){ ll nowa=(a[i]-x%m[i]+m[i])%m[i],X,Y; ll g=exgcd(M,m[i],X,Y),bg=m[i]/g; if(nowa%g)return inf; X=ksc(X,nowa/g,bg);x+=X*M; M*=bg;x=(x%M+M)%M; } return x; } struct sol{ int ne[maxn],be[maxn],sz[maxn],pos[maxn]; void init(){ for(int i=1;i<=n;i++)if(!be[i]){ be[i]=i;sz[i]=1;pos[i]=0; for(int j=ne[i],p=1;j!=i;j=ne[j],p++) be[j]=i,sz[i]++,pos[j]=p; } } }d1,d2,d3; int dis(int x,int y,int z){ return (y-x+z)%z; } ll calc(int x,int y,int z,int xx,int yy,int zz){ vector<ll> m(3),a(3); if(d1.be[x]!=d1.be[xx]||d2.be[y]!=d2.be[yy]||d3.be[z]!=d3.be[zz])return inf; m[0]=d1.sz[d1.be[x]],m[1]=d2.sz[d2.be[y]],m[2]=d3.sz[d3.be[z]]; a[0]=dis(d1.pos[x],d1.pos[xx],d1.sz[d1.be[x]]); a[1]=dis(d2.pos[y],d2.pos[yy],d2.sz[d2.be[y]]); a[2]=dis(d3.pos[z],d3.pos[zz],d3.sz[d3.be[z]]); return excrt(m,a); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&A[i]); for(int i=1;i<=n;i++)scanf("%d",&B[i]); for(int i=1;i<=n;i++)scanf("%d",&C[i]); for(int i=1;i<=n;i++){ d1.ne[i]=A[B[C[i]]]; d2.ne[i]=B[C[A[i]]]; d3.ne[i]=C[A[B[i]]]; } d1.init();d2.init();d3.init(); scanf("%d",&m); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d %d %d",&x,&y,&z); ll ans=inf; ans=min(ans,3ll*calc(1,1,1,x,y,z)); ans=min(ans,3ll*calc(A[1],B[1],C[1],x,y,z)+1); ans=min(ans,3ll*calc(A[B[1]],B[C[1]],C[A[1]],x,y,z)+2); if(ans>=inf)puts("-1"); else printf("%lld\n",ans); } }
- 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
M
好像很多人猜结论直接就冲过去了，当时没往猜结论上想，就一直在试图找最优的操作方式，实际上不如先猜结论再尝试构造，也是一种找最优操作方式的好途径。
先上结论，解
A
a
+
B
b
=
x
Aa+Bb=x
Aa+Bb=x 方程，用裴蜀定理即是否满足
gcd
(
A
,
B
)
∣
x
\gcd(A,B)|x
gcd(A,B)∣x，满足则有解，否则输出-1。
而对于一组解
(
a
,
b
)
(a,b)
(a,b)，对应的答案为：
A
n
s
(
a
,
b
)
=
{
2
(
a
+
b
)
(
a
>
0
,
b
>
0
)
2
∣
a
−
b
∣
−
1
(
a
b
<
0
)
Ans(a,b)=
另外，显然不存在
a
<
0
,
b
<
0
a<0,b<0
a<0,b<0 的情况，所以上面没有。
而对于 a > 0 , b > 0 a>0,b>0 a>0,b>0 的情况，很显然只有 让 A A A 装满喝掉 a a a 次，再让 B B B 装满喝掉 B B B 次 是最优的，已经没有任何额外浪费的步骤了。因此需要 2 ( a + b ) 2(a+b) 2(a+b) 次。
而 a b < 0 ab<0 ab<0 的情况，不妨假设 a > 0 , b < 0 a>0,b<0 a>0,b<0， 2 ∣ a − b ∣ − 1 2|a-b|-1 2∣a−b∣−1 步的构造方法为：
不断把 A A A 装满（一共 a a a 次），每次装满后都尽量倒给 B B B， B B B 如果满了就倒掉（除了最后一次（即只倒 − b − 1 -b-1 −b−1 次），这样可以省一步），然后 A A A 接着倒给 B B B，直到 A A A 空了为止。
当 B B B 已经倒掉 − b − 1 -b-1 −b−1 次时，就开始不断喝 A A A 里的水，喝完倒满接着喝。
或者可以看官方题解里的伪代码写法：
如何证明这样只需要恰好
2
∣
a
−
b
∣
−
1
2|a-b|-1
2∣a−b∣−1 步呢（上面假设了
a
>
0
,
b
<
0
a>0,b<0
a>0,b<0，所以此时答案为
2
a
−
2
b
−
1
2a-2b-1
2a−2b−1）？
- A A A 被装满了 a a a 次，这里 a a a 步。
- B B B 被喝了 − b + 1 -b+1 −b+1 次，这里 − b + 1 -b+1 −b+1 步。
- 而剩下的
A给B倒水和喝A两个操作，每次都恰好会导致A没水或B满水其中一种情况发生（喝 A A A 看做A没水，因为此时 B B B 没变化所以不认为两种情况同时发生），而 A A A 会被装满 a a a 次，那么也一定会空 a a a 次， B B B 会被喝 b − 1 b-1 b−1 次且最后会被装满，所以 B B B 会满 − b -b −b 次。那么这两种情况总共会发生 a − b a-b a−b次，所以这两个操作一定恰好进行了 a − b a-b a−b 次。 - 你可能会问，为什么不可能
A没水和B满水同时发生呢？即 A A A 给 B B B 倒水之后恰好 A A A 倒没了 B B B 倒满？如果有这种情况，显然之前是在浪费步数，因为 A A A 倒满若干次然后把水给 B B B 倒掉，最后一滴水没喝，不如直接省略掉这些步数。所以在最优解里这种情况一定不会出现。
现在只是证明了存在 2 ∣ a − b ∣ − 1 2|a-b|-1 2∣a−b∣−1 步的操作方法，而还没有证明这就是最优解。
而官方题解里有个很好的证明方法可以证明
2
∣
a
−
b
∣
−
1
2|a-b|-1
2∣a−b∣−1 步就是上限：
所以结论证明完了。
有了这个结论，先用扩欧求一个解，然后要使答案尽可能小，那么最优的解一定是离原点最近的几个，都试试就行了。
代码如下：
#include <bits/stdc++.h> using namespace std; int exgcd(int a,int b,long long &x,long long &y){ if(b==0){x=1,y=0;return a;} int g=exgcd(b,a%b,y,x); return y-=a/b*x,g; } int main() { cin.sync_with_stdio(false); int T;cin>>T;while(T--){ int A,B,C; cin>>A>>B>>C; if(A>B)swap(A,B); long long x,y; int g=exgcd(A,B,x,y); if(C%g){ cout<<"-1\n"; continue; } x*=C/g;y*=C/g; //此时因为A<=B，要使x,y离原点最近那么优先将x往原点靠，因为x每次变动幅度是比y大的 y+=x/(B/g)*(A/g); x-=x/(B/g)*(B/g); long long ans=1e18; for(int t=-1;t<=1;t++){ long long xx=x+t*(B/g),yy=y-t*(A/g); if(xx>=0&&yy>=0)ans=min(ans,2*(xx+yy)); else ans=min(ans,2*abs(xx-yy)-1); } cout<<ans<<'\n'; } }
- 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
