2020-2021:teams:legal_string:组队训练比赛记录:contest4
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest4 [2021/07/20 15:23] 王智彪 |
2020-2021:teams:legal_string:组队训练比赛记录:contest4 [2021/07/25 00:00] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| ====== 题解 ====== | ====== 题解 ====== | ||
| + | |||
| + | ===== A. Arithmetic Progression ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一个序列，问有多少连续子串从小到大排列后可以构成等差序列。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 给定一个序列 $a_1,a_2\cdots a_n$，则 $\max(a_i)-\min(a_i)\ge (n-1)\times \text{gcd}(a_2-a_1,a_3-a_2\cdots a_n-a_{n-1})$。 | ||
| + | |||
| + | 等号成立充要条件为 $a_1,a_2\cdots a_n$ 从小到大排列后可以构成等差序列。具体见 [[..:jxm2001:other:结论_3#等差序列判定|证明]]。 | ||
| + | |||
| + | 于是问题转化为统计有多少区间满足 $\max(a[l\sim r])-\min(a[l\sim r])=(r-l)\text{gcd}(a_{l+1}-a_l\cdots a_r-a_{r-1})$。 | ||
| + | |||
| + | 考虑构造序列 $b_i=\max(a[i\sim r])-\min(a[i\sim r])+i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$。 | ||
| + | |||
| + | 线段树维护区间最小值和最小值个数，对固定的 $r$，统计 $[i,r](i\lt r)$ 贡献时，枚举 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的区间。 | ||
| + | |||
| + | 对每个区间将 $b_i=r\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 的数值个数计入贡献。 | ||
| + | |||
| + | 易知 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的区间最多只有 $O(\log v)$ 个，于是总询问次数 $O(n\log v)$。 | ||
| + | |||
| + | 然后移动 $r$ 更新区间，需要维护 $\max(a[l\sim r]),\min(a[l\sim r]),i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 的变化。 | ||
| + | |||
| + | 对 $\max(a[l\sim r]),\min(a[l\sim r])$ 的变化可以用单调栈维护，总更新次数 $O(n)$。 | ||
| + | |||
| + | 对 $i\times \text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 的变化，可以维护 $\text{gcd}(a_{i+1}-a_i\cdots a_r-a_{r-1})$ 不同的段。 | ||
| + | |||
| + | 每次 $r$ 变化时暴力遍历 $O(\log v)$ 个段，每个段的值发生变化时暴力遍历整个段更新。 | ||
| + | |||
| + | 由于每个位置的 $\text{gcd}$ 值最多变化 $O(\log v)$ 次，所以总更新次数 $O(n\log v)$。 | ||
| + | |||
| + | 于是线段树只需要支持区间加操作和区间查询操作，总时间复杂度 $O(n\log n\log v)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e5+5; | ||
| + | struct Node{ | ||
| + | LL v; | ||
| + | int cnt; | ||
| + | Node operator + (const Node &b)const{ | ||
| + | Node c; | ||
| + | if(v==b.v)c.v=v,c.cnt=cnt+b.cnt; | ||
| + | else if(v<b.v)c=*this; | ||
| + | else c=b; | ||
| + | return c; | ||
| + | } | ||
| + | }s[MAXN<<2]; | ||
| + | LL tag[MAXN<<2]; | ||
| + | int lef[MAXN<<2],rig[MAXN<<2]; | ||
| + | void push_up(int k){ | ||
| + | s[k]=s[k<<1]+s[k<<1|1]; | ||
| + | } | ||
| + | void push_add(int k,LL v){ | ||
| + | s[k].v+=v; | ||
| + | tag[k]+=v; | ||
| + | } | ||
| + | void push_down(int k){ | ||
| + | if(tag[k]){ | ||
| + | push_add(k<<1,tag[k]); | ||
| + | push_add(k<<1|1,tag[k]); | ||
| + | tag[k]=0; | ||
| + | } | ||
| + | } | ||
| + | void build(int k,int L,int R){ | ||
| + | lef[k]=L,rig[k]=R,tag[k]=0; | ||
| + | if(L==R){ | ||
| + | s[k].v=0; | ||
| + | s[k].cnt=1; | ||
| + | return; | ||
| + | } | ||
| + | int M=L+R>>1; | ||
| + | build(k<<1,L,M); | ||
| + | build(k<<1|1,M+1,R); | ||
| + | push_up(k); | ||
| + | } | ||
| + | void update(int k,int L,int R,LL v){ | ||
| + | if(L<=lef[k]&&rig[k]<=R){ | ||
| + | push_add(k,v); | ||
| + | return; | ||
| + | } | ||
| + | push_down(k); | ||
| + | int mid=lef[k]+rig[k]>>1; | ||
| + | if(mid>=L) | ||
| + | update(k<<1,L,R,v); | ||
| + | if(mid<R) | ||
| + | update(k<<1|1,L,R,v); | ||
| + | push_up(k); | ||
| + | } | ||
| + | Node query(int k,int L,int R){ | ||
| + | if(L<=lef[k]&&rig[k]<=R) | ||
| + | return s[k]; | ||
| + | push_down(k); | ||
| + | int mid=lef[k]+rig[k]>>1; | ||
| + | if(mid>=R) | ||
| + | return query(k<<1,L,R); | ||
| + | else if(mid<L) | ||
| + | return query(k<<1|1,L,R); | ||
| + | else | ||
| + | return query(k<<1,L,R)+query(k<<1|1,L,R); | ||
| + | } | ||
| + | int gcd(int a,int b){ | ||
| + | while(b){ | ||
| + | int t=b; | ||
| + | b=a%b; | ||
| + | a=t; | ||
| + | } | ||
| + | return a; | ||
| + | } | ||
| + | int a[MAXN],st1[MAXN],st2[MAXN]; | ||
| + | pair<int,int> st3[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int T=read_int(); | ||
| + | while(T--){ | ||
| + | int n=read_int(); | ||
| + | _rep(i,1,n)a[i]=read_int(); | ||
| + | build(1,1,n); | ||
| + | LL ans=n; | ||
| + | int top1=0,top2=0,top3=0; | ||
| + | _rep(i,1,n){ | ||
| + | while(top1&&a[st1[top1]]<=a[i]){ | ||
| + | update(1,st1[top1-1]+1,st1[top1],a[i]-a[st1[top1]]); | ||
| + | top1--; | ||
| + | } | ||
| + | st1[++top1]=i; | ||
| + | while(top2&&a[st2[top2]]>=a[i]){ | ||
| + | update(1,st2[top2-1]+1,st2[top2],a[st2[top2]]-a[i]); | ||
| + | top2--; | ||
| + | } | ||
| + | st2[++top2]=i; | ||
| + | if(i==1)continue; | ||
| + | st3[++top3]=make_pair(abs(a[i]-a[i-1]),i-1); | ||
| + | update(1,i-1,i-1,1LL*(i-1)*st3[top3].first); | ||
| + | for(int j=top3-1;j;j--){ | ||
| + | if(st3[j+1].first%st3[j].first!=0){ | ||
| + | int temp=st3[j].first; | ||
| + | st3[j].first=gcd(st3[j].first,st3[j+1].first); | ||
| + | _rep(k,st3[j-1].second+1,st3[j].second) | ||
| + | update(1,k,k,1LL*k*(st3[j].first-temp)); | ||
| + | } | ||
| + | } | ||
| + | int temp=0; | ||
| + | _rep(j,1,top3){ | ||
| + | if(st3[j].first==st3[temp].first) | ||
| + | st3[temp].second=st3[j].second; | ||
| + | else | ||
| + | st3[++temp]=st3[j]; | ||
| + | } | ||
| + | top3=temp; | ||
| + | _rep(j,1,top3){ | ||
| + | Node temp=query(1,st3[j-1].second+1,st3[j].second); | ||
| + | if(temp.v==1LL*i*st3[j].first) | ||
| + | ans+=temp.cnt; | ||
| + | } | ||
| + | } | ||
| + | enter(ans); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| ===== B. Cannon ===== | ===== B. Cannon ===== | ||
| 行 15: | 行 178: | ||
| 对于第一个子问题，我们发现可以把 $k!$ 提出来，之后对于里面的式子，可以变成两个组合数的乘积，再利用组合数的常用结论，可以推出其等于 $2^{k}k!C(n+m,k)$ ，这个式子可以通过预处理 $2$ 的方幂，阶乘以及阶乘的逆来 $O(1)$ 求得，于是总共复杂度 $O(n+m)$ 。 | 对于第一个子问题，我们发现可以把 $k!$ 提出来，之后对于里面的式子，可以变成两个组合数的乘积，再利用组合数的常用结论，可以推出其等于 $2^{k}k!C(n+m,k)$ ，这个式子可以通过预处理 $2$ 的方幂，阶乘以及阶乘的逆来 $O(1)$ 求得，于是总共复杂度 $O(n+m)$ 。 | ||
| - | 对于第二个子问题， $2^{k} \sum {\frac {n!} {(n-i)!}} {\frac {m!} {(m-(k-i))!}} = 2^{k} \sum {\frac {n!m!} {(n+m-k)!}} {\frac {(n+m-k)!} {(n-i)!(m-(k-i))!}} = 2^{k} {\frac {n!m!} {(n+m-k)!}} \sum_{i=n-k}^{n} C(n+m-k,i)$ | + | 对于第二个子问题， $2^{k} \sum {\frac {n!} {(n-i)!}} {\frac {m!} {(m-(k-i))!}} = 2^{k} \sum {\frac {n!m!} {(n+m-k)!}} {\frac {(n+m-k)!} {(n-i)!(m-(k-i))!}} = 2^{k} {\frac {n!m!} {(n+m-k)!}} \sum_{i=k-m}^{n} C(n+m-k,i)$ |
| 虽然没有直接的结论，但是这个可以用步移算法来解决。 | 虽然没有直接的结论，但是这个可以用步移算法来解决。 | ||
| 行 160: | 行 323: | ||
| } | } | ||
| enter(ans); | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== J. Product of GCDs ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给 $S$ 个数字，让你求出所有子集大小为 $k$ 的集合中的数的最大公因数之积。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 我们可以分成质数来考虑这个问题，分别统计不同数字在整个序列中有多少个数能除开它，这个操作是可以 $mlogm$ 完成的，其中 $m$ 是数字大小范围。 | ||
| + | |||
| + | 当我们统计出不同质数的方幂在序列中被除开的个数时，我们可以用组合数求出来有多少个集合的最大公约数能够除开这个数，并且统计这个集合的次数恰好等于这个质数的方幂数，我们将所有次数加在一起，是一个质数在最后答案出现的次数，先求出 $P$ 的欧拉函数，用次数取模，最后用快速幂算一下，将所有这些答案乘起来就是最后的答案了，又因为我们算的是乘法并且每次的质数不一样，所以保证了正确性。 | ||
| + | |||
| + | 其中我们需要预处理出 $P$ 的所有素因子（为了求欧拉函数值），处理出序列中有多少个数字能除开范围内的任意一个数字。处理出组合数对欧拉函数值取模，最后统计答案就是找所有的素数，看他们的方幂出现的次数，相加，对欧拉函数值取模，最后再快速幂乘起来，就可以愉悦 $AC$ 本题了。 | ||
| + | |||
| + | 当然，如果觉得慢可以用 $Pollard\_rho$ 来加速分解质因数过程，这样筛的时候就没必要筛到根号 $P$ 了，效率会快很多，如下面第二份代码所示。 | ||
| + | |||
| + | <hidden 代码1> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | |||
| + | inline int read() { | ||
| + | int X=0,w=1; | ||
| + | char c=getchar(); | ||
| + | while (c<'0'||c>'9') { | ||
| + | if (c=='-') w=-1; | ||
| + | c=getchar(); | ||
| + | } | ||
| + | while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar(); | ||
| + | return X*w; | ||
| + | } | ||
| + | inline void write(int x){ | ||
| + | char c[21],len=0; | ||
| + | if(!x)return putchar('0'),void(); | ||
| + | if(x<0)x=-x,putchar('-'); | ||
| + | while(x)c[++len]=x%10,x/=10; | ||
| + | while(len)putchar(c[len--]+48); | ||
| + | } | ||
| + | |||
| + | inline ll quick_mul(ll a,ll b,ll p){ | ||
| + | return (ll)((__int128)a*b%p); | ||
| + | } | ||
| + | inline ll quick_power(ll a,ll b,ll p){ | ||
| + | ll ret=1; | ||
| + | while(b){ | ||
| + | if(b&1) ret=quick_mul(ret,a,p); | ||
| + | a=quick_mul(a,a,p); | ||
| + | b>>=1; | ||
| + | } | ||
| + | while(ret<0) ret+=p; | ||
| + | return ret%p; | ||
| + | } | ||
| + | |||
| + | const int maxn=80000+5,maxs=40000+5,maxk=30+2,D=1e7+10,PD=1e6+3; | ||
| + | int T,S,k; | ||
| + | ll P; | ||
| + | int sum[maxn],prime[PD],ps; | ||
| + | long long C[maxs][maxk]; | ||
| + | bool isPrime[D]; | ||
| + | inline void initial() { | ||
| + | memset(isPrime, 1, sizeof(isPrime)); | ||
| + | for (int i = 2; i < D; ++i) { | ||
| + | if (isPrime[i]) { | ||
| + | prime[ps++]=i; | ||
| + | for (int j = i + i; j < D; j += i) { | ||
| + | isPrime[j] = false; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() { | ||
| + | initial(); | ||
| + | T=read(); | ||
| + | while(T--) { | ||
| + | S=read(); k=read(); scanf("%lld",&P); | ||
| + | for(int i=0;i<maxn;i++) sum[i]=0; | ||
| + | for(int i=0,tmp; i<S; i++) { | ||
| + | tmp=read(); | ||
| + | sum[tmp]++; | ||
| + | } | ||
| + | for(int i=2; i<maxn; i++) { | ||
| + | for(int j=i+i; j<maxn; j+=i) { | ||
| + | sum[i]+=sum[j]; | ||
| + | } | ||
| + | } | ||
| + | long long tmp=P,phi_ans=1; | ||
| + | for(int i=0; i<ps; i++) { | ||
| + | if(tmp%prime[i]==0) { | ||
| + | phi_ans=phi_ans*(prime[i]-1); | ||
| + | tmp/=prime[i]; | ||
| + | while(!(tmp%prime[i])) { | ||
| + | tmp/=prime[i]; | ||
| + | phi_ans*=prime[i]; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | if(tmp>1) phi_ans=phi_ans*(tmp-1); | ||
| + | for(int i=0; i<=S; i++) { | ||
| + | C[i][0]=1; | ||
| + | for(int j=1; j<=i&&j<=k; j++) { | ||
| + | C[i][j] = C[i-1][j] + C[i-1][j-1]; | ||
| + | while(C[i][j]>=phi_ans+phi_ans) C[i][j]-=phi_ans; | ||
| + | } | ||
| + | } | ||
| + | long long num; | ||
| + | ll ans=1; | ||
| + | for(int i=2; i<maxn; i++) { | ||
| + | if(isPrime[i]) { | ||
| + | num=0; | ||
| + | for(ll j=i; j<maxn; j*=i) { | ||
| + | num+=C[sum[j]][k]; | ||
| + | while(num>=phi_ans+phi_ans) num-=phi_ans; | ||
| + | } | ||
| + | ans=quick_mul(ans,quick_power(i,num,P),P); | ||
| + | //printf("%d %d %lld\n",i,num,ans); | ||
| + | } | ||
| + | } | ||
| + | printf("%lld\n",ans); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| + | |||
| + | |||
| + | |||
| + | <hidden 代码2> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | |||
| + | const int maxn=80000+5,maxs=40000+5,maxk=30+2; | ||
| + | int T,S,k; | ||
| + | ll P,maxv; | ||
| + | int sum[maxn],prime[maxn],ps; | ||
| + | long long C[maxs][maxk]; | ||
| + | bool isPrime[maxn]; | ||
| + | inline void initial() { | ||
| + | memset(isPrime, 1, sizeof(isPrime)); | ||
| + | for (int i = 2; i < maxn; ++i) { | ||
| + | if (isPrime[i]) { | ||
| + | prime[ps++]=i; | ||
| + | for (int j = i + i; j < maxn; j += i) { | ||
| + | isPrime[j] = false; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | inline int read() { | ||
| + | int X=0,w=1; | ||
| + | char c=getchar(); | ||
| + | while (c<'0'||c>'9') { | ||
| + | if (c=='-') w=-1; | ||
| + | c=getchar(); | ||
| + | } | ||
| + | while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar(); | ||
| + | return X*w; | ||
| + | } | ||
| + | inline void write(int x) { | ||
| + | char c[21],len=0; | ||
| + | if(!x)return putchar('0'),void(); | ||
| + | if(x<0)x=-x,putchar('-'); | ||
| + | while(x)c[++len]=x%10,x/=10; | ||
| + | while(len)putchar(c[len--]+48); | ||
| + | } | ||
| + | |||
| + | inline ll quick_mul(ll a,ll b,ll p) { | ||
| + | return (ll)((__int128)a*b%p); | ||
| + | } | ||
| + | inline ll quick_power(ll a,ll b,ll p) { | ||
| + | ll ret=1; | ||
| + | while(b) { | ||
| + | if(b&1) ret=quick_mul(ret,a,p); | ||
| + | a=quick_mul(a,a,p); | ||
| + | b>>=1; | ||
| + | } | ||
| + | while(ret<0) ret+=p; | ||
| + | return ret%p; | ||
| + | } | ||
| + | struct Pollard_rho { | ||
| + | bool check(ll a,ll n,ll x,ll t) { | ||
| + | ll ans=quick_power(a,x,n); | ||
| + | ll aans=ans; | ||
| + | for(int i=1; i<=t; i++) { | ||
| + | ans=quick_mul(ans,ans,n); | ||
| + | if(ans==1&&aans!=1&&aans!=n-1) return true; | ||
| + | aans=ans; | ||
| + | } | ||
| + | if(ans!=1) return true; | ||
| + | return false; | ||
| + | } | ||
| + | bool Miller_Rabin(ll n) { | ||
| + | if(n<2) return false; | ||
| + | if(n==2) return true; | ||
| + | if(!(n&1)) return false; | ||
| + | ll x=n-1,t=0; | ||
| + | while(!(x&1)) { | ||
| + | x>>=1; | ||
| + | t++; | ||
| + | } | ||
| + | for(int i=0; i<20; i++) { | ||
| + | ll a=rand()%(n-1)+1; | ||
| + | if(check(a,n,x,t)) return false; | ||
| + | } | ||
| + | return true; | ||
| + | } | ||
| + | ll gcd(ll x,ll y) { | ||
| + | if(!x) return y; | ||
| + | if(!y) return x; | ||
| + | if(x<0) x=-x; | ||
| + | if(y<0) y=-y; | ||
| + | ll t=__builtin_ctzll(x|y); | ||
| + | x>>=__builtin_ctzll(x); | ||
| + | do { | ||
| + | y>>=__builtin_ctzll(y); | ||
| + | if(x>y) swap(x,y); | ||
| + | y-=x; | ||
| + | } while(y); | ||
| + | return x<<t; | ||
| + | } | ||
| + | ll pollard_rho(ll x,ll c) { | ||
| + | ll ci=1,k=2; | ||
| + | srand(time(NULL)); | ||
| + | ll x0=rand()%(x-1)+1; | ||
| + | ll y=x0,t=1; | ||
| + | while(1) { | ||
| + | ci++; | ||
| + | x0=(quick_mul(x0,x0,x)+c)%x; | ||
| + | t=quick_mul(y-x0,t,x); | ||
| + | if(!t||!(y^x0)) return x; | ||
| + | if(ci==k) { | ||
| + | ll d=gcd(t,x); | ||
| + | if(d!=1) return d; | ||
| + | y=x0; | ||
| + | k<<=1; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | void findfac(ll n,ll k) { | ||
| + | if(n==1) return; | ||
| + | if(Miller_Rabin(n)) { | ||
| + | if(n>maxv) maxv=n; | ||
| + | return; | ||
| + | } | ||
| + | ll p=n,c=k; | ||
| + | while(p>=n) { | ||
| + | p=pollard_rho(p,c--); | ||
| + | } | ||
| + | findfac(p,k); | ||
| + | findfac(n/p,k); | ||
| + | } | ||
| + | }pr; | ||
| + | |||
| + | int main() { | ||
| + | initial(); | ||
| + | T=read(); | ||
| + | while(T--) { | ||
| + | S=read(); | ||
| + | k=read(); | ||
| + | scanf("%lld",&P); | ||
| + | for(int i=0; i<maxn; i++) sum[i]=0; | ||
| + | for(int i=0,tmp; i<S; i++) { | ||
| + | tmp=read(); | ||
| + | sum[tmp]++; | ||
| + | } | ||
| + | for(int i=2; i<maxn; i++) { | ||
| + | for(int j=i+i; j<maxn; j+=i) { | ||
| + | sum[i]+=sum[j]; | ||
| + | } | ||
| + | } | ||
| + | long long tmp=P,phi_ans=1; | ||
| + | maxv=0; | ||
| + | while(tmp!=1) { | ||
| + | pr.findfac(tmp,324757); | ||
| + | tmp/=maxv; | ||
| + | phi_ans*=(maxv-1); | ||
| + | while(tmp%maxv==0) { | ||
| + | tmp/=maxv; | ||
| + | phi_ans*=maxv; | ||
| + | } | ||
| + | maxv=0; | ||
| + | } | ||
| + | for(int i=0; i<=S; i++) { | ||
| + | C[i][0]=1; | ||
| + | for(int j=1; j<=i&&j<=k; j++) { | ||
| + | C[i][j] = C[i-1][j] + C[i-1][j-1]; | ||
| + | while(C[i][j]>=phi_ans+phi_ans) C[i][j]-=phi_ans; | ||
| + | } | ||
| + | } | ||
| + | long long num; | ||
| + | ll ans=1; | ||
| + | for(int i=2; i<maxn; i++) { | ||
| + | if(isPrime[i]) { | ||
| + | num=0; | ||
| + | for(ll j=i; j<maxn; j*=i) { | ||
| + | num+=C[sum[j]][k]; | ||
| + | while(num>=phi_ans+phi_ans) num-=phi_ans; | ||
| + | } | ||
| + | ans=quick_mul(ans,quick_power(i,num,P),P); | ||
| + | } | ||
| + | } | ||
| + | printf("%lld\n",ans); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | |||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== L. WeChat Walk ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一张图 $n$ 个点 $m$ 条边。每个点初始权值为 $0$，接下来 $q$ 个单位时间，每个单位时间仅增加一个点的权值。 | ||
| + | |||
| + | 当一个点的权值严格大于所有与自己相邻的点时，这个点成为冠军。问每个点作为冠军的时间。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 考虑分块，设分块大小为 $S\sim O(\sqrt n)$。每个点 $u$ 维护自己作为冠军的开始时间，当一个点不再是冠军时加入答案。 | ||
| + | |||
| + | 称度数不大于 $S$ 的点为一类点，其余点为二类点。 | ||
| + | |||
| + | 对于一类点，暴力遍历相邻的点判断自己是否称为冠军顺便更新相邻的点即可。 | ||
| + | |||
| + | 对于二类点 $u$，先考虑如何更新相邻点的冠军，考虑维护 $S(u,w)$ 表示与 $u$ 相邻且权值等于 $w$ 的点的集合。 | ||
| + | |||
| + | 设 $u$ 权值更新前为 $w_1$，更新后为 $w_2$，不难发现更新 $u$ 只会导致权值位于 $(w_1,w_2]$ 之间的点的冠军情况发生变化，于是暴力扫描即可。 | ||
| + | |||
| + | 最后需要判定 $u$ 是否为冠军，考虑维护 $\text{maxw}(u)$ 表示与 $u$ 相邻的点的最大权值。 | ||
| + | |||
| + | 于是只需要在更新所有类型点权值时暴力遍历相邻的二类点并更新他们即可。 | ||
| + | |||
| + | 由于二类点最多只有 $O(\sqrt n)$ 个，所以每次更新最多使得 $\sum |S(u,w)|$ 增加 $O(\sqrt n)$。于是总时间复杂度 $O(n\sqrt n)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=2e5+5,MAXS=505,MAXW=1e4+5; | ||
| + | vector<int> g[MAXN],g2[MAXN],g3[MAXS][MAXW]; | ||
| + | int ans[MAXN],val[MAXN],last[MAXN],maxw[MAXN],bmap[MAXN],bsz; | ||
| + | void update(int u,int v,int t){ | ||
| + | if(last[v]!=-1&&val[v]<=val[u]){ | ||
| + | ans[v]+=t-last[v]; | ||
| + | last[v]=-1; | ||
| + | } | ||
| + | if(g[v].size()>bsz){ | ||
| + | maxw[v]=max(maxw[v],val[u]); | ||
| + | g3[bmap[v]][val[u]].push_back(u); | ||
| + | } | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(),q=read_int(),bcnt=0; | ||
| + | bsz=sqrt(n)+1; | ||
| + | _for(i,0,m){ | ||
| + | int u=read_int(),v=read_int(); | ||
| + | g[u].push_back(v); | ||
| + | g[v].push_back(u); | ||
| + | } | ||
| + | _rep(u,1,n){ | ||
| + | if(g[u].size()>bsz){ | ||
| + | bmap[u]=bcnt++; | ||
| + | _for(i,0,g[u].size()){ | ||
| + | int v=g[u][i]; | ||
| + | if(g[v].size()>bsz) | ||
| + | g2[u].push_back(v); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | mem(last,-1); | ||
| + | _rep(tim,1,q){ | ||
| + | int u=read_int(),w=read_int(); | ||
| + | val[u]+=w; | ||
| + | if(g[u].size()<=bsz){ | ||
| + | if(last[u]==-1) | ||
| + | last[u]=tim; | ||
| + | _for(i,0,g[u].size()){ | ||
| + | int v=g[u][i]; | ||
| + | if(val[v]>=val[u]) | ||
| + | last[u]=-1; | ||
| + | update(u,v,tim); | ||
| + | } | ||
| + | } | ||
| + | else{ | ||
| + | if(val[u]>maxw[u]&&last[u]==-1) | ||
| + | last[u]=tim; | ||
| + | _for(i,0,g2[u].size()){ | ||
| + | int v=g2[u][i]; | ||
| + | update(u,v,tim); | ||
| + | } | ||
| + | int idx=bmap[u]; | ||
| + | _rep(k,val[u]-w+1,val[u]){ | ||
| + | _for(i,0,g3[idx][k].size()){ | ||
| + | int v=g3[idx][k][i]; | ||
| + | update(u,v,tim); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | _rep(u,1,n){ | ||
| + | if(last[u]!=-1) | ||
| + | ans[u]+=q-last[u]; | ||
| + | enter(ans[u]); | ||
| + | } | ||
| return 0; | return 0; | ||
| } | } | ||
| 行 169: | 行 751: | ||
| jxm：过了签到后就一直debug，先给自己de，然后帮队友de，<del>后来de不下去直接重写了一份</del>。再后来就开始罚坐了，甚至没把所有题看完，或许下次应该在罚坐的时候把所有题先看一遍？ | jxm：过了签到后就一直debug，先给自己de，然后帮队友de，<del>后来de不下去直接重写了一份</del>。再后来就开始罚坐了，甚至没把所有题看完，或许下次应该在罚坐的时候把所有题先看一遍？ | ||
| + | |||
| + | wzb：罚时场被干碎了，下次不能这么莽的... | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest4.1626765837.txt.gz · 最后更改: 2021/07/20 15:23 由 王智彪
