前言
光顾着想 T2 了,但是不知道哪儿假了,只有 \(\dfrac{n}{k}\le 5\) 的点是对的,然后居然只有二十分,发现数据放错了,找喵喵改了成五十了。
然后 T1 因为重边挂没了。
T3 没调出来,确切的说是省的时间不多了打不完,就写了个部分分。
T4 咕了。
机房凳子没靠椅,一直坐着腰快折了肿么办。
T1 传送
按照横坐标(纵坐标)排序,\(i\to i+1\) 连边,再连上 \(m\) 调隧道,跑 dijkstra 就行了。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10,M=1.2e6+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,tot,head[N],nxt[M],to[M],w[M]; ll dis[N]; bitset<N>vis;
void _(int x,int y,int z)
{nxt[++tot]=head[x],to[tot]=y,w[tot]=z,head[x]=tot;}
void add(int x,int y,int z) {_(x,y,z),_(y,x,z);}
struct aa {int x,y,id;}e[N];
void dijkstra()
{
memset(dis,0x3f,sizeof(dis)),dis[1]=0;
priority_queue<pair<ll,int> >q; q.push(make_pair(0,1));
while(!q.empty())
{
int x=q.top().second; q.pop();
if(vis[x]) continue; vis[x]=1;
for(int i=head[x],y;y=to[i];i=nxt[i]) if(dis[y]>dis[x]+w[i])
dis[y]=dis[x]+w[i],q.push(make_pair(-dis[y],y));
}
}
signed main()
{
freopen("teleport.in","r",stdin),freopen("teleport.out","w",stdout);
read(n,m); for(int i=1,x,y;i<=n;i++) read(x,y),e[i]={x,y,i};
sort(e+1,e+1+n,[&](aa a,aa b){return a.x<b.x;});
for(int i=1;i<n;i++) add(e[i].id,e[i+1].id,e[i+1].x-e[i].x);
sort(e+1,e+1+n,[&](aa a,aa b){return a.y<b.y;});
for(int i=1;i<n;i++) add(e[i].id,e[i+1].id,e[i+1].y-e[i].y);
for(int i=1,x,y,z;i<=m;i++) read(x,y,z),add(x,y,z);
dijkstra(); for(int i=2;i<=n;i++) write(dis[i]),putchar_unlocked(' ');
}
T2 排列
-
部分分 \(50pts\):考虑 \(\dfrac{n}{k}\le 5\) 时不会有算重的情况,遂组合一下就好了。
-
正解:
因为 \(\dfrac{n}{k}\le 10\),考虑状压。
\(f_{i,j,k}\) 表示处理到第 \(i\) 位,这 \(\dfrac{n}{k}\) 数的出现情况为 \(j\),结尾是 \(k\) 的方案数,\(k=0\) 表示不是以这 \(\dfrac{n}{k}\) 中的一个结尾,直接转移即可。
acsoders 跑得太快了,所以需要卡卡常,预处理 \(\gcd\) 或每个状态的合法结尾数,复杂度 \(O(n2^{\frac{n}{k}}k)\),可以滚一下优化空间。点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort using namespace std; const int N=3010,M=1024,P=998244353; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar_unlocked(); for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0; for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);} template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');} template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);} template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);} int n,m,k,ans,cnt[M],f[2][M][11]; vector<int>e[M]; inline int mod(int x,int y) {return (x+=y)>=P?x-P:x;} inline int gcd(int x,int y) {return !y?x:gcd(y,x%y);} signed main() { freopen("permutation.in","r",stdin),freopen("permutation.out","w",stdout); read(n,k),m=n/k; f[0][0][0]=1; for(int i=0;i<(1<<m);cnt[i]=e[i].size(),e[i++].push_back(0)) for(int j=__lg(i);j>=0;j--) if((i>>j)&1) e[i].push_back(j+1); for(int i=1,x=1,y=0;i<=n;i++,x^=1,y^=1) { memset(f[x],0,sizeof(f[x])); for(int j=0;j<(1<<m);j++) if(cnt[j]<=i) { for(int k:e[j]) f[x][j][0]=mod(f[x][j][0],f[y][j][k]); f[x][j][0]=1ll*f[x][j][0]*(n-m-(i-cnt[j])+1)%P; for(int k:e[j]) if(k) { f[x][j][k]=mod(f[x][j][k],f[y][j^(1<<(k-1))][0]); for(int h:e[j]) if(h&&k!=h&&gcd(k,h)!=1) f[x][j][k]=mod(f[x][j][k],f[y][j^(1<<(k-1))][h]); } } } for(int i=0;i<=m;i++) ans=mod(ans,f[n&1][(1<<m)-1][i]); write(ans); }
-
还有个 \(O(2^{\frac{n}{k}}\dfrac{n}{k})\) 的做法,没有写。
T3 战场模拟器
-
第一档部分分:\(l=r\),暴力。
-
第二档部分分:没有死亡的也没有套盾的,线段树维护最小值及其个数即可。
-
第三档部分分:最多套 \(n\) 个盾,线段树标记一下往下递归即可。
-
正解:和第三档类似,死亡的也只会死一次,若最小值不够扣往下递归到叶子即可,若这个区间已经死光了结束递归就行了,注意实现的细节。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort #define mid (l+r>>1) #define ls (mid<<1) #define rs (mid<<1|1) using namespace std; const int N=2e5+10; const ll inf=2e14; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar_unlocked(); for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0; for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);} template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');} template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);} template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);} int n,m,a[N],h[N<<1],sum[N<<1],cnt[N<<1]; ll val[N<<1],add[N<<1]; void pushup(int p,int l,int r) { val[p]=min(val[ls],val[rs]),cnt[p]=cnt[ls]+cnt[rs],h[p]=h[ls]+h[rs]; sum[p]=val[ls]==val[rs]?sum[ls]+sum[rs]:(val[ls]<val[rs]?sum[ls]:sum[rs]); } void spread(int p,int l,int r) { if(val[ls]!=inf) val[ls]+=add[p],add[ls]+=add[p]; if(val[rs]!=inf) val[rs]+=add[p],add[rs]+=add[p]; add[p]=0; } void build(int p,int l,int r) { if(l==r) return val[p]=a[l],sum[p]=1,void(); build(ls,l,mid),build(rs,mid+1,r),pushup(p,l,r); } void change(int p,int l,int r,int vl,int vr,int d) { if(val[p]==inf) return ; if(vl<=l&&vr>=r&&(d>0||!h[p])) {val[p]+=d; if(val[p]>=0) return add[p]+=d,void();} if(l==r&&h[p]&&d<0) return h[p]--,void(); if(l==r&&val[p]+d<0) return val[p]=inf,cnt[p]=1,void(); if(add[p]) spread(p,l,r); if(vl<=mid) change(ls,l,mid,vl,vr,d); if(vr>mid) change(rs,mid+1,r,vl,vr,d); pushup(p,l,r); } void protect(int p,int l,int r,int x) { if(val[p]==inf) return ; if(l==r) return h[p]++,void(); if(add[p]) spread(p,l,r); x<=mid?protect(ls,l,mid,x):protect(rs,mid+1,r,x),pushup(p,l,r); } int dead(int p,int l,int r,int vl,int vr) { if(val[p]==inf) return min(vr,r)-max(l,vl)+1; if(vl<=l&&vr>=r) return cnt[p]; if(add[p]) spread(p,l,r); int res=0; if(vl<=mid) res+=dead(ls,l,mid,vl,vr); if(vr>mid) res+=dead(rs,mid+1,r,vl,vr); return res; } int dying(int p,int l,int r,int vl,int vr) { if(val[p]!=0) return 0; if(vl<=l&&vr>=r) return (!val[p])*sum[p]; if(add[p]) spread(p,l,r); int res=0; if(vl<=mid) res+=dying(ls,l,mid,vl,vr); if(vr>mid) res+=dying(rs,mid+1,r,vl,vr); return res; } signed main() { freopen("simulator.in","r",stdin),freopen("simulator.out","w",stdout); read(n); for(int i=1;i<=n;i++) read(a[i]); build(1,1,n),read(m); for(int i=1,op,l,r,x;i<=m;i++) { read(op); switch(op) { case 1: read(l,r,x),change(1,1,n,l,r,-x); break; case 2: read(l,r,x),change(1,1,n,l,r,x); break; case 3: read(x),protect(1,1,n,x); break; case 4: read(l,r),write(dead(1,1,n,l,r)),puts(""); break; case 5: read(l,r),write(dying(1,1,n,l,r)),puts(""); break; } } }
T4 点亮
咕了咕了。
标签:unlocked,int,08,多校,Tp,CSP2024,read,inline,void From: https://www.cnblogs.com/Charlieljk/p/18472910