算法学习
写的题
20221020
沈阳ICPC 2019
L
感觉像铜牌题
完全图中剔除一棵树,询问剩下的图存在多少种边为n的匹配,很容易想到容斥,并且只剔除了一颗树,剩下的一定可以在剩下子图中匹配。
考虑 fi,j,0/1 表示以 i 为根的子树中包含 k 种匹配的方案数,那么显然有一个树形背包的转移方式。
1 2 3
| g[k+l][0]=(g[k+l][0]+1ll*f[x][k][0]*(f[j][l][1]+f[j][l][0]))%modp; g[k+l][1]=(g[k+l][1]+1ll*f[x][k][1]*(f[j][l][1]+f[j][l][0]))%modp; g[k+l+1][1]=(g[k+l+1][1]+1ll*f[x][k][0]*f[j][l][0])%modp;
|
根据容斥原理,总的方案数即为
ans=i=0∑n(−1)nf1,i,0/1
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 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=4040; const int modp=998244353;
int f[maxn][maxn][2]; int n,s1ze,head[maxn],sz[maxn]; int inv[maxn],p[maxn],_2n[maxn]; int ans,g[maxn][2];
struct edge{ int next,to; }e[maxn*2];
void addedge(int next,int to) { e[++s1ze].to=to; e[s1ze].next=head[next]; head[next]=s1ze; }
int ksm(int x,int y) { int ans=1,z=y; while(z) { if(z&1) ans=(ans*y)%modp; ans=(ans*ans)%modp; } return ans; }
void getsz(int x,int fat) { sz[x]=1; f[x][0][0]=1; for(int i=head[x];i;i=e[i].next) { int j=e[i].to; if(j==fat) continue; getsz(j,x); for(int k=0;k<=(sz[x]+sz[j])/2;k++) g[k][1]=g[k][0]=0; for(int k=sz[x]/2;k>=0;k--) { for(int l=0;l<=sz[j]/2;l++) { g[k+l][0]=(g[k+l][0]+1ll*f[x][k][0]*(f[j][l][1]+f[j][l][0]))%modp; g[k+l][1]=(g[k+l][1]+1ll*f[x][k][1]*(f[j][l][1]+f[j][l][0]))%modp; g[k+l+1][1]=(g[k+l+1][1]+1ll*f[x][k][0]*f[j][l][0])%modp; } } sz[x]+=sz[j]; for(int k=0;k<=sz[x]/2;k++) { f[x][k][1]=g[k][1],f[x][k][0]=g[k][0]; } }; int tmp=1; }
int C(int x,int y) { return (((1ll*p[y]*inv[x])%modp)*inv[y-x])%modp; }
int main() { ios::sync_with_stdio(false); cin>>n; n*=2; int t1,t2; for(int i=1;i<n;i++) { cin>>t1>>t2; addedge(t1,t2); addedge(t2,t1); } p[0]=1; _2n[0]=1; inv[0]=1; inv[1]=1; for(int i=1;i<=n;i++) p[i]=(1ll*p[i-1]*i)%modp; for(int i=2;i<=n;i++) inv[i]=1ll*(modp-modp/i)*inv[modp%i]%modp; for(int i=1;i<=n;i++) _2n[i]=(1ll*_2n[i-1]*inv[2])%modp; for(int i=1;i<=n;i++) inv[i]=(1ll*inv[i-1]*inv[i])%modp;
getsz(1,0); n/=2; for(int i=0;i<=n;i++) { long long tmp=(f[1][i][0]+f[1][i][1]); tmp=(tmp*C((n-i),(n-i)*2))%modp; tmp=(tmp*p[n-i])%modp; tmp=(tmp*_2n[n-i])%modp; if(i&1) tmp=modp-tmp; ans=(ans+tmp)>=modp?ans+tmp-modp:ans+tmp; } cout<<ans<<endl;
}
|
H
银牌题
前置芝士: 线图
题目大意:给定 G{V,E} ,询问线图的顶点匹配最大值,匹配的边的边权为原来图上两边边权和
显然,线图的匹配在原图即为两条相邻的边的匹配。
那么,如果边数为偶数,答案显然是所有边权之和。
如果为奇数,只需要删去一条边,但是如果这条边是割边,并且两个连通子图边数都为奇数,说明不用删,一定有更优解,因为接下来两个子图还要找到最小边删除,但是我们可以直接删除最小边,(如果最小边还是割边,那么两边都要递归下去,因此可以说明这种割边一定不是最优方案。
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
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=400200;
int a[maxn*2],n,m; int sz[maxn],dep[maxn],f[maxn]; int bj[maxn],s1ze=1,head[maxn]; long long ans;
struct edge{ int next,to,dis; }e[maxn*2];
void addedge(int next,int to,int dis) { e[++s1ze].to=to; e[s1ze].next=head[next]; e[s1ze].dis=dis; head[next]=s1ze; }
void dfs(int t,int fat) { dep[t]=dep[fat]+1; int looker=0; for(int i=head[t];i;i=e[i].next) { int j=e[i].to; if(j==fat) { looker=i; continue; } if(dep[j]) { if(dep[t]<dep[j]) f[t]--; \\dfs找割边,可以证明一定不存在depj和depi相等的情况 else if(dep[t]>dep[j]) sz[j]++,f[t]++; \\f表示返祖边的个数 } else { dfs(j,t); f[t]+=f[j]; sz[t]+=sz[j]+1; } } if(t!=1&&(sz[t]%2==1)&&!f[t]) bj[looker]=1,bj[looker^1]=1; }
int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=m;i++) { int t1,t2,t3; cin>>t1>>t2>>t3; addedge(t1,t2,t3); addedge(t2,t1,t3); ans+=t3; } if(m%2==0) { cout<<ans<<endl; return 0; } dfs(1,1); long long looker=ans; ans=0; for(int i=2;i<=s1ze;i++) { if(!bj[i]) ans=max(ans,looker-e[i].dis); } cout<<ans<<endl; }
|
CF1730B
每个人分别在坐标轴的 ai 位置,现在他们希望集合,每个人打扮时间 bi 求哪里集合他们最快。
显然,可以二分集合时间,此时检查函数就变成维护一个区间 [l,r]
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
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<stack> #include<vector> #include<queue> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=100100;
int n,T,a[maxn],b[maxn]; double lasans=0;
int check(double tmp) { const double eps=1e-7; double l=0,r=1e9; for(int i=1;i<=n;i++) { if(tmp-b[i]<eps) return 0; l=max(l,a[i]-(tmp-b[i])); r=min(r,a[i]+(tmp-b[i])); if(r-l<eps) return 0; } lasans=l; return 1; }
void getans() { if(n==1) { cout<<a[1]<<endl; return ; } double l=0,r=1e9,mid; double ans=0; const double eps=1e-7; while(r-l>eps) { mid=(l+r)/2; if(check(mid)) ans=mid,r=mid; else l=mid; } printf("%.6lf\n",lasans);
}
int main() {
cin>>T; while(T--) { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; getans(); } }
|
20221022
前言
今天写了三道题,很菜的一天
Educational Codeforces Round 138 (Rated for Div. 2)
C
题目大意:给你一个数组 a ,你需要找到一个最大的 k 满足:
在第 i 次中能够找到 a 中小于 k−i+1 的一个数 aj 删去它,并且将另外一个数字加上 k−i+1 ,总共进行 k 轮
分析,k+1 的能够做的轮数时候一定不小于 k+1 ,因此是个单调的,可以二分 k
并且,对每轮选择的数字,一定是选择最小的,将其加上 k−i+1 最优,删除最接近 k−i+1 的最优
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
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=220;
int n,T; int a[maxn],b[maxn];
int getplace(int x) { int l,r,mid,ans; l=1,r=n,ans=n; while(l<=r) { mid=(l+r)>>1; if(b[mid]<=x) ans=mid,l=mid+1; else r=mid-1; } return ans; }
int check(int x) { if(x==0) return 1; for(int i=1;i<=n;i++) b[i]=a[i]; sort(b+1,b+n+1); for(int i=1;i<=x;i++) { int target=getplace(x-i+1); if(b[target]>x-i+1) return 0; b[target]=0x3f3f3f3f; if(target!=1) b[1]+=x-i+1; sort(b+1,b+n+1); } return 1; }
void getans() { int l,r,ans,mid; l=0,r=n; while(l<=r) { mid=(l+r)>>1; if(check(mid)) l=mid+1,ans=mid; else r=mid-1; } cout<<ans<<endl; }
int main() { ios::sync_with_stdio(false); cin>>T; while(T--) { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; getans(); } }
|
D
题目大意: 一个序列 a ,如果可以它的下标 i 满足,gcd(ai,i)=1 那么 i 号位置的数就是可删除的,删除i 之后右边的数下标都要 −1 , 一个数组一定可以存在一个删除序列,现在需要你找到长度不多于 n ,值域在 [1,m] 范围内,满足删除序列不多于一种的序列个数
正难则反,考虑一共有 i=1∑nmi 个序列,在考虑只有一种的序列,显然这个第 i 位的数满足是前面下标 lcm 的倍数,换句话说记 [1,i] 的素数积为 primei ,答案即为i=1∑nmi−i=1∑nΠ⌊primeim⌋
另外需要显著注意一点是,这个是整数除法,没法用逆元(也不是没法,但是不是单独除过去)
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
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=1e6+10; const long long modp=998244353;
long long n,m,ans; int is_prime[maxn]; long long m0; int p[maxn],cnt;
void getprime(int x) { is_prime[1]=1; for(int i=2;i<=n;i++) { if(!is_prime[i]) p[++cnt]=i; for(int j=1;j<=cnt&&i*p[j]<=n;j++) { is_prime[i*p[j]]=1; if(i%p[j]==0) break; } } }
int ksm(long long x,long long y) { long long ans=1; while(y) { ans=(1ll*ans*ans)%modp; if(y&1) ans=(1ll*ans*x)%modp; y>>=1; } return ans; }
int main() { ios::sync_with_stdio(false); cin>>n>>m; if(n==1&&m==1) { cout<<1<<endl; return 0; } m0=m; getprime(n); m%=modp; long long tmp=m; for(int i=1;i<=n;i++) { ans=(ans+tmp)%modp; tmp=(tmp*m)%modp; }
long long looker=1; tmp=1; for(int i=1;i<=n;i++) { if(!is_prime[i]&&looker<=m0) looker=(looker*i); tmp=tmp*((m0/looker)%modp)%modp;
ans=(modp+ans-tmp)%modp; } cout<<ans<<endl; }
|
Codeforces Round #822 (Div. 2)
D
大意: 你是一坨史莱姆,在 k 位置 ,每次你需要向左走或者向右走,代价是你的质量会减少 ai (假如你去了 i 位置 ) ,你需要保证你的质量不是负数,你需要走到 0 或者 n+1 位置
很显然的一点是,你需要往左走的话,你更需要尽可能多吃右边的,因此你要贪心吃尽可能多的左边。
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
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
#define int long long
using namespace std;
const int maxn=2e5+10;
int n,a[maxn],s[maxn]; int k,T;
void solve() { memset(s,0,sizeof(s)); for(int i=k-1; i>=1; i--) s[i]=s[i+1]+a[i]; for(int i=k+1; i<=n; i++) s[i]=s[i-1]+a[i]; int nowl,nowr,nxtl,nxtr; int sl,sr; sl=sr=a[k]; nowl=nowr=k; nxtl=nxtr=k; if(sl<0) { cout<<"NO"<<endl; return ; } for(; nxtl>=1&&nxtr<=n;) { nowl=nxtl; nowr=nxtr; while(sr+s[nxtl]>=0&&nxtl>=1) sl=max(sl,a[k]+s[nxtl]),nxtl--; while(sl+s[nxtr]>=0&&nxtr<=n) sr=max(sr,a[k]+s[nxtr]),nxtr++; if(nxtl==nowl&&nxtr==nowr) { cout<<"NO"<<endl; return ; } } cout<<"YES"<<endl; return ; }
signed main() { ios::sync_with_stdio(false); cin>>T; while(T--) { cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; solve(); } }
|
20201023~20201024 训练
前言 打了一场 cf ,fst 到了只 A 了 2A,2B
Codeforces Round #829 (Div. 2)
A
给你一段包含 Q,A 的字符串,并且以 Q 开始,每个Q 必须对应一个或者多个 A ,询问这个字符串是否合法,每个 A 仅能对应一个 Q
显然,贪心,每个Q 对对应一个 A 然后第一个再对应剩下的即可。
B
询问长度为 n 的排列,使得 $\min|p_i-p_{i+1}| 1\leq i< n $
显然答案是 ⌊2n⌋
1 2
| if(n%2==1) cout<<n<<" ",n--; for(int i=1;i<=n/2;i++) cout<<i+n/2<<" "<<i<<" ";
|
C
给定一个仅包含 0,±1 序列,定义一个区间的值为 pl,r=i=l∑r(−1)i−lai
如何划分这个区间,使得区间的值和为 0
记录所有数的和为 total 如果它为 0 答案就输出 n 个 [i,i]
如果它是奇数,显然无解
如果它是偶数,假设当时 1 多了,只要之前是 −1,1,0 任意一种,把区间合并成 [i−1,i] 就可以让 1 的个数少 1 ,同时让 −1多 1 , 显然可以这样操作使得答案成为 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
| #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=600100;
int n,T; int a[maxn],tot;
int main() { ios::sync_with_stdio(false); cin>>T; while(T--) { cin>>n; tot=0; for(int i=1;i<=n;i++) cin>>a[i],tot+=a[i]; if(tot&1) { cout<<"-1"<<endl; continue; } if(tot<0) { cout<<n+tot/2<<endl; for(int i=1;i<=n;i++) { if(tot<0&&a[i+1]==-1) cout<<i<<" "<<i+1<<endl,tot+=2,i++; else cout<<i<<" "<<i<<endl; } } else if(tot>0) { cout<<n-tot/2<<endl; for(int i=1;i<=n;i++) { if(tot>0&&a[i+1]==1) cout<<i<<" "<<i+1<<endl,tot-=2,i++; else cout<<i<<" "<<i<<endl; } } else if(tot==0) { cout<<n<<endl; for(int i=1;i<=n;i++) cout<<i<<" "<<i<<endl; } } }
|
D
给你 n 个数字和 m ,询问这 n 个数字阶乘之和能否被 m! 整除
设当前有 ai 个 i 显然每 i+1 个数可以合并并且使 ai+1+1
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
| #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=600100;
int T,n,m; int tot1,totz; int a[maxn],modp,cnt; int sz[maxn];
int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i],sz[a[i]]++; sort(a+1,a+n+1); int looker=1; for(int i=1;i<=m;i++) if(sz[i]>i) sz[i+1]+=sz[i]/(i+1),sz[i]%=(i+1); for(int i=1;i<m;i++) if(sz[i]>=1) looker=0; if(looker) cout<<"Yes"<<endl; else cout<<"No"<<endl; }
|
E
题目大意,给你一个 01 序列,每次随机交换,询问期望排列从小到大有序的次数交换 ($\mod p $ 意义下)
记这个序列有 k 个 0
正难则反,考虑一个动态规划, fi 表示前面 k 个数字中又 i 个 0 的期望操作数,那么显然的,我们可以倒过来写一个期望
假设前 k 个数中 1 与后面 n−k 个数中 0 交换的概率是 p,假设当前前k 个数中有 i 个 1
p=Cn2(k−i)∗(k−i)
第一个 k−i 的意义是前面的 1 的个数,第二个的意义是后面的 0 的个数
fi=p∗fi+1+(i−p)∗fi 移项即可
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
| #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=600100; const int modp=998244353;
int n,T; int a[maxn]; int f[maxn];
int ksm(int x,int y) { int ans=1; while(y) { if(y&1) ans=(1ll*ans*x)%modp; x=(1ll*x*x)%modp; y>>=1;
} return ans; }
void solve() { int cnt=0,ccnt=0; for(int i=1;i<=n;i++) cnt+=!a[i]; for(int i=1;i<=cnt;i++) ccnt+=!a[i]; memset(f,0,sizeof(f)); f[cnt]=0;
for(int i=cnt-1;i>=ccnt;i--) { int p=(2ll*(cnt-i)*(cnt-i))%modp*(ksm(1ll*n*(n-1)%modp,modp-2))%modp; f[i]=1ll+1ll*f[i+1]*p%modp; f[i]=1ll*f[i]*ksm(p,modp-2)%modp; } cout<<f[ccnt]<<endl; }
int main() { ios::sync_with_stdio(false); cin>>T; while(T--) { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; solve(); } }
|
830
C1
菜鸡只会 C1
给定一个序列,定义 fl,r=i=l∑rai−al⊕al+1⊕...⊕ar
有一个十分显然的的是,r 增大,这个函数单调不下降。
我们能不能找到这个单调不下降的最大次数?
很感性的猜想的 log 级别
以为我们把每个数字二进制拆分,如果最后 k 个数字在二进制下面没有交集,那么 fl,r 不会变,显然,这个是 logC 级别,C 为值域
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
| #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
#define int long long
using namespace std;
const int maxn=200100;
int s[maxn],x[maxn]; int n,a[maxn]; int T,q,ans,ansl,ansr; int qz[maxn],cnt; int f[maxn];
signed main() { ios::sync_with_stdio(false); cin>>T; while(T--) { cin>>n>>q; ans=0; memset(s,0,sizeof(s)); memset(x,0,sizeof(x));
cnt=0; int ansl,ansr,anslen=0; int tsum=0,txor=0; for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i],x[i]=x[i-1]^a[i]; qz[++cnt]=1; for(int i=2;i<=n;i++) { if(a[i]) qz[++cnt]=i; else if(a[i-1]) qz[++cnt]=i; else if(a[i+1]) qz[++cnt]=i;
} int looker=cnt; for(int i=n;i;i--) { if(qz[looker]>i) looker--; f[i]=looker; } for(int i=1;i<=q;i++) { int l,r; ans=0; cin>>l>>r; ansl=l;ansr=r; int rr=f[r]-1; if(qz[f[r]]<=r) rr++;
int rl=f[l]; for(int i=rl;i<=min(rr,rl+120);i++) for(int j=rr;j>=max(rl,rr-120)&&j>=i;j--) { int ii=qz[i],jj=qz[j]; int tmpans=s[jj]-s[ii-1]-(x[jj]^x[ii-1]); if(tmpans>ans) { ans=tmpans; ansl=ii,ansr=jj; anslen=jj-ii+1; } else if(tmpans==ans&&jj-ii<ansr-ansl) { ansl=ii,ansr=jj; anslen=jj-ii+1; } } cout<<ansl<<" "<<ansr<<endl; } } }
|
但是 C2 我还不会,可见我菜爆了
20221026
Educational Codeforces Round 129 (Rated for Div. 2)
F
题目大意,询问所有点对的路径中,边的只有一种权值数量的和。
显然,对于边权为 x 的边,我们先把这个树的这些边断掉,形成一个森林,然后这条边的贡献就是与之相连的两条树的个数之积。
我们需要运用并查集按秩合并,每次并查集的复杂度是 O(logn) 级别
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 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=500500;
struct edge{ int x,y,dis; bool operator <(const edge &b) { return dis<b.dis; } }e[maxn];
int n; int looker[maxn]; int st[maxn]; long long ans;
struct dsu{ struct status{ int x,y; int fx,fy; int six,siy; }q[maxn]; int f[maxn],sz[maxn]; void st() { for(int i=1;i<=n;i++) { f[i]=i,sz[i]=1; } } void werge(int i) { int x=e[i].x; int y=e[i].y; int tx=x,ty=y; while(f[tx]!=tx) tx=f[tx]; while(f[ty]!=ty) ty=f[ty]; q[i].x=x; q[i].y=y; q[i].fx=tx,q[i].fy=ty; q[i].six=sz[tx],q[i].siy=sz[ty]; if(sz[tx]>sz[ty]) { f[ty]=tx; sz[tx]+=sz[ty]; } else { f[tx]=ty; sz[ty]+=sz[tx]; } } void inwerge(int i) { int x=e[i].x; int y=e[i].y; f[q[i].fx]=q[i].fx; f[q[i].fy]=q[i].fy; sz[q[i].fx]=q[i].six; sz[q[i].fy]=q[i].siy; } int _find(int x) { while(x!=f[x]) x=f[x]; return sz[x]; } }msu;
void dfs(int l,int r) { if(l==r) { if(!looker[l]) return ; int x,y; for(int i=st[l];;i++) { if(e[i].dis>l) return ; x=msu._find(e[i].x); y=msu._find(e[i].y); ans+=1ll*x*y; } return ; } int mid; mid=(l+r)>>1; int lasi=0; for(int i=st[mid+1];;i++) { if(e[i].dis>r) break ; lasi=i; msu.werge(i); } dfs(l,mid); for(int i=lasi;i>=st[mid+1];i--) { if(e[i].dis>r) break ; msu.inwerge(i); } for(int i=st[l];;i++) { if(e[i].dis>mid) break ; lasi=i; msu.werge(i); } dfs(mid+1,r); for(int i=lasi;i>=st[l];i--) { if(e[i].dis>mid) break ; msu.inwerge(i); } }
int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<n;i++) { cin>>e[i].x>>e[i].y>>e[i].dis; looker[e[i].dis]=1; } sort(e+1,e+n); e[n].dis=0x3f3f3f3f; msu.st(); for(int i=1;i<n;i++) st[e[i].dis]=st[e[i].dis]?st[e[i].dis]:i; for(int i=n;i;i--) if(!st[i]) st[i]=st[i+1]; dfs(1,e[n-1].dis); cout<<ans<<endl; }
|
感觉这段代码有一点麻烦,应该不需要一个分治过程。
20221027
前言
今天写了三道题,终于不那么摆了
看到神仙在打派,于是在qq群疯狂膜拜,然后过一分钟撤回美滋滋
P8710 [蓝桥杯 2020 省 AB1] 网络分析
题目描述
小明正在做一个网络实验。
他设置了 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 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 92 93 94 95 96 97 98 99 100 101 102
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=100100;
struct que{ int opt,x,y,k; }q[maxn];
int n,m,lazy[maxn]; int f[maxn],sz[maxn];
struct dsu{ struct hisopt { int x,y; int sizx,sizy; int looker; }h[maxn]; void getf() { for(int i=1;i<=n;i++) f[i]=i,sz[i]=1; for(int i=1;i<=m;i++) h[i].looker=1; } void werge(int i) { int x=q[i].x; int y=q[i].y; while(x!=f[x]) x=f[x]; while(y!=f[y]) y=f[y]; if(x==y) { h[i].looker=0; return ; } h[i].x=x; h[i].sizx=x; h[i].y=y; h[i].sizy=y; if(sz[x]>sz[y]) f[y]=x,sz[x]+=sz[y]; else f[x]=y,sz[y]+=sz[x]; } void adtg(int i,int t) { int x=q[i].x; while(x!=f[x]) x=f[x]; lazy[x]+=t; return ; } int fd(int x) { while(x!=f[x]) x=f[x]; return x; } void inwerge(int i) { if(!h[i].looker) return ; int x=h[i].x,y=h[i].y; if(sz[x]<sz[y]) swap(x,y); lazy[y]+=lazy[x]; f[y]=y; sz[x]-=sz[y]; } }dsu;
int main() { ios::sync_with_stdio(false); int x,y,opt; cin>>n>>m; dsu.getf(); for(int i=1;i<=m;i++) { cin>>q[i].opt>>q[i].x>>q[i].y; if(q[i].opt==1) dsu.werge(i); } for(int i=m;i;i--) { if(q[i].opt==1) dsu.inwerge(i); else dsu.adtg(i,q[i].y); } for(int i=1;i<=n;i++) { cout<<lazy[dsu.fd(i)]<<" "; } return 0; }
|
CF Round 830 DIV2
D
大意,给你一个只有 0 的序列,你需要维护这个序列:
1.插入一个数
2.删除一个数
3.询问 k 的倍数中,最小的不在这个序列的数是多少
先考虑一个简单版本,只插入和询问
显然,对于同一个 k ,每次答案单调不下降,因此只需要记录 k 上一次的答案,这次从上开始查找即可
考虑复杂度的正确性,假设我们有 1,2,3,...,n 这个数列,如果想让他们移动次数最多,就需要 1,2,3,4,5..n 这样插入,复杂度即为调和级数,~三江方士证明它收敛 ,即为 O(nlogn)
那么如果有删除呢,我们只需要考虑当当前这个数字曾经对那些没有产生贡献,显然根据上面的结论,它的因子个数(产生过影响的)也是 O(logn) 级别的,因此依旧大力维护即可。
UPD 第二问不能用平均复杂度来证明,因为一旦找到一个数,可以不断插入删除,比如 2∗2∗2∗2∗2∗3∗3∗3∗3∗3∗3=23328 ,它的因子有 log2n 级别了,虽然前面乘了一个小常数
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
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=100100;
set <long long> s; map <long long ,int > mp; map <long long ,set<long long> > ms; map <long long ,vector<long long> > primenum;
int n;
int main() { ios::sync_with_stdio(false); cin>>n; char opt; long long x; for(int i=1;i<=n;i++) { cin>>opt>>x; if(opt=='+') { for(auto &pi: primenum[x]) { ms[pi].erase(x/pi); } s.insert(x); } if(opt=='-') { for(auto &pi:primenum[x]) { ms[pi].insert(x/pi); } s.erase(x); } if(opt=='?') { if(ms[x].empty()) { while(s.find((mp[x]+1)*x)!=s.end()) { primenum[(mp[x]+1)*x].push_back(x); mp[x]++; } cout<<(1ll*mp[x]+1)*x<<endl; } else cout<<(1ll*x*(*ms[x].begin()))<<endl; } } }
|
Educational Codeforces Round 136 (Rated for Div. 2)
D
给定一棵树,你可进行一下操作 k 次
断掉一条边,将不与根相连的那部分接到根上面,根深度为 0 ,询问最后树的深度
这是一个很显然的二分加上 dfs ,每次二分最大深度
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
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=200100;
struct edge{ int next,to; }e[maxn];
int s1ze,head[maxn]; int dep[maxn],n,k,T; int cutcnt,dm;
void addedge(int next,int to) { e[++s1ze].to=to; e[s1ze].next=head[next]; head[next]=s1ze; }
void dfs(int t) { dep[t]=1; for(int i=head[t];i;i=e[i].next) { int j=e[i].to; dfs(j); if(dep[j]>=dm&&t!=1) cutcnt++; else dep[t]=max(dep[t],dep[j]+1); } }
void solve() { int l=1,r=n,ans=0,mid; while(l<=r) { memset(dep,0,sizeof(dep)); mid=(l+r)>>1; cutcnt=0; cutcnt=0; dm=mid; dfs(1); if(cutcnt<=k) ans=mid,r=mid-1; else l=mid+1; } cout<<ans<<endl; }
int main() { cin>>T; while(T--) { memset(head,0,sizeof(head)); s1ze=0; cin>>n>>k; int t1; for(int i=2;i<=n;i++) { cin>>t1; addedge(t1,i); } solve(); } }
|
20221029
今天 cf 大大大大大大大大大大大坐牢
突然想到,cf 的题目格式我还得改改,例如下面这种
CF 1733 D Zero-One
题目大意,给你一个两个 01 序列 a,b 定义操作change(l,r)
为吧 al=1−al,ar=1−ar
change(l,r)={xyr−l=1r−l=1
询问将 a 序列变成 b 序列的最小价值,如果不能实现,输出 -1
每次操作显然可以让两个不同的地方变成相同的地方,如果有奇数个下标不同,说明无法实现,输出 -1
即可。
很显然的,全部进行 y 操作的次数肯定比全部进行 x 操作次数第,如果,如果 y<x 显然全部进行 y 操作,这也是 $ \text{easy}$ 的解法。
否者我们考虑一个 dp,设 fi,j 表示 [i,j] 个不同的点位全部操作完成的最小值,显然操作 x 的代价一定是两个相近的最低,而 y 操作与下标无关。
我们考虑 fi,j 的转移来源
fi,j=min⎩⎨⎧fi+1,j−1+yfi+2,j+(pi+1−pi)×xfi,j−2+(pj−1−pj−2)×x
至于为什么不需要考虑相邻的用 y 操作,很显然,那么远的也一定会用上 y 操作。
pi 代表第 i 个不同的位置在原数组的下标
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
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
#define int long long
using namespace std;
const int maxn=5100;
int p[maxn],a[maxn],n,x,y; int T,f[maxn][maxn];
void solve() { cin>>n>>x>>y; char t; int cnt=0; for(int i=1;i<=n;i++) cin>>t,a[i]=t-'0'; for(int i=1;i<=n;i++) cin>>t,a[i]^=t-'0'; for(int i=1;i<=n;i++) if(a[i]) p[++cnt]=i; if(cnt&1) { cout<<-1<<endl; return ; } if(cnt==2) { if(p[2]-p[1]==1) y*=2; cout<<min((p[2]-p[1])*x,y)<<endl; return ; }
for(int len=2;len<=cnt;len++) for(int i=1;i<cnt;i++) { int j=i+len-1; f[i][j]=f[i+1][j-1]+y; f[i][j]=min(f[i][j],min(f[i+2][j]+(p[i+1]-p[i])*x,f[i][j-2]+x*(p[j]-p[j-1]))); } cout<<f[1][cnt]<<endl; }
signed main() { ios::sync_with_stdio(false); cin>>T; while(T--) { solve(); } }
|
CF372C Watching Fireworks is Fun
一个单调队列优化 dp
头脑处于十级昏迷写出来的,毕竟是先看题解学习再学的
考虑一个 fi,j 表示第 i 个烟花炸了的时候在 j 号位置的最大收益,有一个转移方程 fi,j=maxfi−1,k+bi−(ai−j)
其中, k 的范围就是 max(1,j−d∗(ti−ti−1)≤k≤min(n,j+d∗(ti−ti−1)))
很显然的,恰好满足单调队列优化的条件,即每次移动 1 ,并且只有最大值产生影响
不过这道题足以体现我有多菜,单调队列都写不来了
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
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
#define int long long
using namespace std;
const int maxn=150030,maxm=330;
int f[2][maxn]; int q[maxn],n,m,d; int a[maxn],t[maxn],b[maxn];
signed main() { ios::sync_with_stdio(false); cin>>n>>m>>d; for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>t[i]; for(int i=1;i<=n;i++) f[1][i]=-0x3f3f3f3f3f3f3f; for(int i=1;i<=m;i++) { int ll=1,rr=0; int tmp=i&1; int k=1; for(int j=1;j<=n;j++) { for(;k<=min(n,j+d*(t[i]-t[i-1]));k++) { while(f[!tmp][q[rr]]<=f[!tmp][k]&&ll<=rr) rr--; q[++rr]=k; } while(q[ll]<max(1ll,j-d*(t[i]-t[i-1]))&&ll<=rr) ll++; f[tmp][j]=f[!tmp][q[ll]]+b[i]-abs(a[i]-j); } } int ans=-0x3f3f3f3f3f3f3f3f; for(int i=1;i<=n;i++) ans=max(ans,f[m&1][i]); cout<<ans<<endl; }
|