挂分了，垫底啦！！！
rank 8挂成rank27啦！！！
rank 27，T1 28，T2 0,T3 0，T4 0
T2 内存限制256MB，我打了一个257MB的，然后MLE了。
T3 暴力挂了9pts？
T1 传送 (teleport)
是简单题，但我不会
对\(X,Y\)分开看，如果我们在最优解中⾛了某⼀步，可以看做是在对应维度上⾛了⼀段。
那么这⼀段上的点可以看做是依次经过的。
因此我们把所有点按照\(X，Y\)分别排序，然后将排序后相邻的点连边即可。
复杂度\(O(n\log m)\)。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#define Infile(x) freopen(#x".in","r",stdin)
#define Outfile(x) freopen(#x".out","w",stdout)
#define Ansfile(x) freopen(#x".ans","w",stdout)
#define Errfile(x) freopen(#x".err","w",stderr)
#ifdef LOCAL
FILE *InFile = Infile(in),*OutFile = Outfile(out);
// FILE *ErrFile = Errfile(err);
#else
FILE *InFile = Infile(teleport),*OutFile = Outfile(teleport);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define int long long
const int N = 2e5 + 10;
struct EDGE{int to,next,w;}e[N<<3];
int head[N],cnt;
inline void add(int u,int v,int w){
e[++cnt] = {v,head[u],w};
head[u] = cnt;
e[++cnt] = {u,head[v],w};
head[v] = cnt;
}
int n,m;
struct node{int x,y,p;}a[N];
ll dist[N];
bitset<N> vis;
#define pii pair<int,int>
#define mk make_pair
inline void dijkstra(int s){
vis.reset();
memset(dist,0x3f,sizeof dist);
dist[s] = 0;
priority_queue<pii,vector<pii>,greater<pii> > q;
q.push(mk(dist[s],s));
while(q.size()){
int x = q.top().second;q.pop();
for(int i = head[x]; i;i = e[i].next){
int y = e[i].to;
if(dist[y] > dist[x] + e[i].w){
dist[y] = dist[x] + e[i].w;
q.push(mk(dist[y],y));
}
}
}
}
inline void solve(){
cin>>n>>m;
rep(i,1,n,1) cin>>a[i].x>>a[i].y,a[i].p = i;
sort(a+1,a+1+n,[](node a,node b){return a.x<b.x;});
rep(i,2,n,1) add(a[i-1].p,a[i].p,abs(a[i].x-a[i-1].x));
sort(a+1,a+1+n,[](node a,node b){return a.y<b.y;});
rep(i,2,n,1) add(a[i-1].p,a[i].p,abs(a[i].y-a[i-1].y));
rep(i,1,m,1){
int u,v,w;cin>>u>>v>>w;
add(u,v,w);
}
dijkstra(1);
rep(i,2,n,1) cout<<dist[i]<<' ';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
排列 (permutation)
写了一个\(O(n(\frac{n}{k})^22^{n/k})\)，但是常数小加特判比较多，于是就轻松过掉，甚至比一些\(O(10!\times 10)\)的还快。
发现当两个数的\(\gcd\)可能为\(k\)时，当且仅当这两个数都为\(k\)的倍数，然后由于\(\frac{n}{k}\)很小，记录一下这个就好了。
记\(f_{i,j,k}\)表示第\(i\)个位置填\(j\)，\(k\)是状态压缩，记录当前是否选择\(k\times (i+1)\)。
发现\(j\)除了为\(k\)的倍数时，其余的状态转移是一样的，就考虑将\(j\)缩小，改变一下\(j\)的定义即可，令\(j\)表示当前位置填\(k\times j\)。当\(j=\left\lfloor\frac{n}{k}\right\rfloor + 1\)时，表示填其它非\(k\)的倍数的数。
然后转移方程比较显然，优化和转移方程，具体看代码吧，因为有点分讨，懒得打\(\LaTeX\)了。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#define Infile(x) freopen(#x".in","r",stdin)
#define Outfile(x) freopen(#x".out","w",stdout)
#define Ansfile(x) freopen(#x".ans","w",stdout)
#define Errfile(x) freopen(#x".err","w",stderr)
#ifdef LOCAL
FILE *InFile = Infile(in),*OutFile = Outfile(out);
// FILE *ErrFile = Errfile(err)
#else
FILE *InFile = Infile(permutation),*OutFile = Outfile(permutation);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 3001,mod = 998244353;
int n,k,mx,a[11],f[N][11][1<<10],ar[11][11],st[1<<11];
//注意f的最后一维要开1<<10，或者滚动数组优化
inline bool gp(int x,int p){return ((x>>p)&1);}
inline int get(int x){
int res = 0;
while(x) x-= (x&(-x)),res++;
return res;
}
inline void solve(){
cin>>n>>k;
rep(i,1,10,1){
if(i*k > n) break;
mx = i-1,a[i-1] = i*k;
}
int ms = (1<<(mx+1)) - 1;
rep(i,0,mx,1) rep(j,0,mx,1)
if(i != j && __gcd(a[i],a[j]) == k)
ar[i][j] = true;//表示第i个和第j个冲突
rep(i,0,ms,1) st[i] = get(i);
mx++;//当j=mx时
int len = n-mx;
f[0][mx][0] = 1;
rep(i,1,n,1){
f[i][mx][0] = 1ll*f[i-1][mx][0] * (max(len-(i-1),0))%mod;
rep(s,1,ms,1){
int sz = st[s];
if(sz > i) continue;//优化1，当状态数的popcount>i，跳过。
rep(now,0,mx,1){
if(now == mx){
rep(last,0,mx,1){
if(last == mx || (last != mx && gp(s,last)))
f[i][now][s] = (1ll*f[i-1][last][s]*(max(len-(i-1-sz),0))%mod + f[i][now][s])%mod;//len-(i-1-sz)表示当前位置可以选择的非k的倍数的数的个数
}
}
else{
if(!gp(s,now)) continue;//优化2，当当前要填的数不在状态中，跳过
rep(last,0,mx,1){
if(last == now && last != mx) continue;
if(last != mx && !gp(s,last)) continue;
if(ar[now][last]) continue;
f[i][now][s] = (f[i-1][last][s^(1<<now)] + f[i][now][s])%mod;
}
}
}
}
}
int ans = 0;
rep(i,0,mx,1) ans = (ans+f[n][i][ms]%mod)%mod;
cout<<ans;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
战场模拟器 (simulator)
线段树题，还是有点意思的。
统计区间最小值，区间最小值的个数，区间盾的个数，区间死亡个数，区间加的tag标记。
发现最多只会有\(q\)个护盾，死亡人数最多为\(n\)人，所以如果有人死了或者有人用了护盾，就直接暴力跑到叶子就可以了，时间复杂度\(O((n+q)\log n)\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#define Infile(x) freopen(#x".in","r",stdin)
#define Outfile(x) freopen(#x".out","w",stdout)
#define Ansfile(x) freopen(#x".ans","w",stdout)
#define Errfile(x) freopen(#x".err","w",stderr)
#ifdef LOCAL
FILE *InFile = Infile(in),*OutFile = Outfile(out);
// FILE *ErrFile = Errfile(err);
#else
FILE *InFile = Infile(simulator),*OutFile = Outfile(simulator);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const ll N = 2e5 + 10,inf = 0x3f3f3f3f3f3f3f3f;
int n,q,a[N];
struct Segment_Tree{
struct segment_tree{
ll mn,lazy;
int l,r,ms,d,ct;//mn 最小值，ms 最小值个数，d 死亡人数，ct 盾的个数，lazy 区间加tag
#define l(x) tree[x].l
#define r(x) tree[x].r
#define mn(x) tree[x].mn
#define ms(x) tree[x].ms
#define d(x) tree[x].d
#define ct(x) tree[x].ct
#define lz(x) tree[x].lazy
}tree[N<<2];
inline void pushup(int k){
int ls = k<<1,rs = k<<1|1;
mn(k) = min(mn(ls),mn(rs));
d(k) = d(ls) + d(rs);
ct(k) = ct(ls) + ct(rs);
ms(k) = 0;
if(mn(k) == mn(ls)) ms(k) += ms(ls);
if(mn(k) == mn(rs)) ms(k) += ms(rs);
}
inline void pushdown(int k){
if(lz(k)){
int ls = k<<1,rs = k<<1|1;
lz(ls) += lz(k),lz(rs) += lz(k);
mn(ls) += lz(k),mn(rs) += lz(k);
lz(k) = 0;
}
}
void build(int k = 1,int l = 1,int r = n){
l(k) = l,r(k) = r;
if(l == r) return mn(k) = a[l],d(k) = ct(k) = 0,ms(k) = 1,void();
int mid = (l + r) >> 1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
pushup(k);
}
void upd1(int k,int l,int r,int v){
if(l <= l(k) && r(k) <= r && mn(k) >= v && !ct(k))
return mn(k) -= v,lz(k) -= v,void();
if(l(k) == r(k)){
if(ct(k)) return ct(k)--,void();
d(k) = 1,ct(k) = 0;
mn(k) = inf;return;
}
pushdown(k);
int mid = (l(k) + r(k)) >> 1;
if(l <= mid) upd1(k<<1,l,r,v);
if(r > mid) upd1(k<<1|1,l,r,v);
pushup(k);
}
void upd2(int k,int l,int r,int v){
if(l <= l(k) && r(k) <= r)
return mn(k) += v,lz(k) += v,void();
pushdown(k);
int mid = (l(k) + r(k)) >> 1;
if(l <= mid) upd2(k<<1,l,r,v);
if(r > mid) upd2(k<<1|1,l,r,v);
pushup(k);
}
void upd3(int k,int pos){
if(l(k) == r(k)) return ct(k)++,void();
int mid = (l(k) + r(k)) >> 1;
pushdown(k);
if(pos <= mid) upd3(k<<1,pos);
else upd3(k<<1|1,pos);
pushup(k);
}
int q1(int k,int l,int r){
if(l <= l(k) && r(k) <= r) return d(k);
pushdown(k);
int mid = (l(k) + r(k)) >> 1,res = 0;
if(l <= mid) res += q1(k<<1,l,r);
if(r > mid) res += q1(k<<1|1,l,r);
return res;
}
int q2(int k,int l,int r){
if(mn(k)) return 0;
if(l <= l(k) && r(k) <= r) return ms(k);
int mid = (l(k) + r(k))>>1,res = 0;
pushdown(k);
if(l <= mid) res += q2(k<<1,l,r);
if(r > mid) res += q2(k<<1|1,l,r);
return res;
}
}T;
inline void solve(){
cin>>n;rep(i,1,n,1) cin>>a[i];T.build();
cin>>q;
while(q--){
int op,l,r,x;cin>>op;
if(op == 1) cin>>l>>r>>x,T.upd1(1,l,r,x);
if(op == 2) cin>>l>>r>>x,T.upd2(1,l,r,x);
if(op == 3) cin>>x,T.upd3(1,x);
if(op == 4) cin>>l>>r,cout<<T.q1(1,l,r)<<'\n';
if(op == 5) cin>>l>>r,cout<<T.q2(1,l,r)<<'\n';
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
也有分块做法，答题思路一样，时间复杂度\(O(q\sqrt{n})\)的。
代码来自神
点此查看代码
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
FILE *InFile=freopen("simulator.in","r",stdin),*OutFile=freopen("simulator.out","w",stdout);
#endif
const int N=2e5+3,L=200,S=N/L+3;
int id[N],ch[N],bln,n,q; llt ca[N]; bool dd[N];
struct BK{int l,r,cmi,cdd; llt ad=0,mi; bool h,dd;}bk[S];
void Dwn(BK &k){for(int i=k.l;i<=k.r;++i) if(!dd[i]){ca[i]+=k.ad; if(ca[i]<0){dd[i]=1; continue;}} k.ad=0;}
void Bld(BK &k){
k.mi=0x3f3f3f3f,k.cmi=k.cdd=k.h=0,k.dd=1;
for(int i=k.l;i<=k.r;++i)
if(!dd[i]){
k.dd=0;
if(ca[i]<k.mi) k.mi=ca[i],k.cmi=1;
else if(ca[i]==k.mi) ++k.cmi;
if(ch[i]) k.h=1;
}else ++k.cdd;
}
void Sub(int l,int r,int x){for(int i=l;i<=r;++i) if(!dd[i]){if(ch[i]) --ch[i]; else{ca[i]-=x; if(ca[i]<0) dd[i]=1;}}}
void Sub(BK &k,int x){
if(k.dd) return;
if(k.h) return Dwn(k),Sub(k.l,k.r,x),Bld(k),void();
k.ad-=x; if(k.mi+k.ad<0) Dwn(k),Bld(k);}
void Add(int l,int r,int x){for(int i=l;i<=r;++i) if(!dd[i]) ca[i]+=x;}
void Add(BK &k,int x){if(k.dd) return ; k.ad+=x;}
int Cdd(int l,int r){int cnt=0; for(int i=l;i<=r;++i) cnt+=dd[i]; return cnt;}
int Cdy(int l,int r){int cnt=0; for(int i=l;i<=r;++i) if(!dd[i]) cnt+=(ca[i]==0); return cnt;}
int Cdy(BK &k){return (k.mi+k.ad==0)?k.cmi:0;}
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n; bk[++bln].l=1;
for(int i=1;i<=n;++i){if(i%L==0) bk[bln].r=i-1,bk[++bln].l=i; cin>>ca[i],id[i]=bln;} bk[bln].r=n;
for(int i=1;i<=bln;++i) Bld(bk[i]);
cin>>q;
for(int cs=1;cs<=q;++cs){
int opt; cin>>opt;
if(opt==1){
int l,r,x; cin>>l>>r>>x;
if(id[l]==id[r]) Dwn(bk[id[l]]),Sub(l,r,x),Bld(bk[id[l]]);
else{
Dwn(bk[id[l]]),Dwn(bk[id[r]]),Sub(l,bk[id[l]].r,x),Sub(bk[id[r]].l,r,x),Bld(bk[id[l]]),Bld(bk[id[r]]);
for(int i=id[l]+1;i<id[r];++i) Sub(bk[i],x);
}
}else if(opt==2){
int l,r,x; cin>>l>>r>>x;
if(id[l]==id[r]) Dwn(bk[id[l]]),Add(l,r,x),Bld(bk[id[l]]);
else{
Dwn(bk[id[l]]),Dwn(bk[id[r]]),Add(l,bk[id[l]].r,x),Add(bk[id[r]].l,r,x),Bld(bk[id[l]]),Bld(bk[id[r]]);
for(int i=id[l]+1;i<id[r];++i) Add(bk[i],x);
}
}else if(opt==3){int h; cin>>h; if(!dd[h]) ++ch[h],bk[id[h]].h=1;}
else if(opt==4){
int l,r,ans=0; cin>>l>>r;
if(id[l]==id[r]) ans=Cdd(l,r);
else{
ans=Cdd(l,bk[id[l]].r)+Cdd(bk[id[r]].l,r);
for(int i=id[l]+1;i<id[r];++i) ans+=bk[i].cdd;
}
cout<<ans<<endl;
}else{
int l,r,ans=0; cin>>l>>r;
if(id[l]==id[r]) Dwn(bk[id[l]]),ans=Cdy(l,r),Bld(bk[id[l]]);
else{
Dwn(bk[id[l]]),Dwn(bk[id[r]]),ans=Cdy(l,bk[id[l]].r)+Cdy(bk[id[r]].l,r),Bld(bk[id[l]]),Bld(bk[id[r]]);
for(int i=id[l]+1;i<id[r];++i) ans+=Cdy(bk[i]);
}
cout<<ans<<endl;
}
}
}
点亮 (light)
二项式反演。
柿子是这个柿子
\[f(n)=\sum_{i=n}^m\mathrm{C}_i^ng(i)\Leftrightarrow g(n)=\sum_{i=n}^m(-1)^{i-n}\mathrm{C}_i^nf(i) \]发现每个连通块块的结构为边权最大的边被点亮了两次，其它边被点亮一次，所以本质上是求有\(k\)个边权最大的边(以下称其为核心边)的概率。
核心边是肯定不会相邻的，所以核心边的数量最多只有\(\frac{n}{2}\)条，且位于核心边上的点为\(2\times k\)个。
以下记核心边两端的点为关键点
当\(2k>n\)时，直接输出0即可。
假设\(S\)为一个边集，\(g_S\)表示最终核心边集合为\(S\)的概率，那么答案就是\(\sum\limits_{|S|=k}g_S\)。
根据二项式反演，考虑设\(f_S\)表示最终核心边集合包含\(S\)的概率，那么如何求\(f_S\)。
假设\(|S|=i\)，考虑\(S\)中每条边的优先级，有\(i!\)。
考虑选中每一条边的概率，就是\(\prod\limits_{j=1}^i\frac{1}{\mathrm{C}_n^2-\mathrm{C}_{n-2j}^2}\)
所以\(f(S)=i!\prod\limits_{j=1}^i\frac{1}{\mathrm{C}_n^2-\mathrm{C}_{n-2j}^2}\)
简单解释一下\(i!\)就表示将选择的\(i\)条边按优先级排序的方案数，而后面的柿子就是在完全图\(E\)中任意选择1条边的方案数，减去不选已经选过的点的方案数，再取倒数就是概率。至于为什么\(j\)不从0开始？你算算\(\frac{1}{0}\)是多少？于是就定义它为1就行了。
然后考虑\(|S|=i\)的\(S\)有几个，就是\(\frac{1}{i!2^i}\times \frac{n!}{(n-2i)!}\)
解释一下，就是从\(n\)个点中选出\(2i\)个点作为关键点，然后取个全排列，将第\(i\)个点和第\(i+1\)个点连边(\(i\)为奇数)。但是发现会有重复的，比如\(1234,1243,2143,2134,3412,4312,4321,3421\)，这些都是重复的，考虑将其除去。每组边有两种排列方式，所以要除以个\(2^i\)，然后再将这\(i\)条边的全排列除去，就是除以\(i!\)。
以上纯属我这个菜鸡瞎口胡，如果有错误请大佬指出，感激不尽
有\(f_i=\frac{1}{i!2^i}\frac{n!}{(n-2i)!}\times i!\prod\limits_{j=1}^i\frac{1}{\mathrm{C}_n^2-\mathrm{C}_{n-2j}^2}\)
然后套二反柿子就行了。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#define Infile(x) freopen(#x".in","r",stdin)
#define Outfile(x) freopen(#x".out","w",stdout)
#define Ansfile(x) freopen(#x".ans","w",stdout)
#define Errfile(x) freopen(#x".err","w",stderr)
#ifdef LOCAL
FILE *InFile = Infile(in),*OutFile = Outfile(out);
// FILE *ErrFile = Errfile(err)
#else
FILE *InFile = Infile(light),*OutFile = Outfile(light);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 5e5 + 10,mod = 1e9 + 7,m = 500000;
int n,k,fac[N],inv[N],f[N],ipw[N];
inline int power(int a,int b,int mod){
int res = 1;
for(; b;b >>= 1,a = 1ll*a*a%mod)
if(b&1) res = 1ll*res*a%mod;
return res;
}
inline int Inv(int a){return power(a,mod-2,mod);}
inline int C(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline int get(int n,int k){
return 1ll*fac[n]*power(inv[2],k,mod)%mod*inv[n-2*k]%mod*f[k]%mod;
}
inline void solve(){
fac[0] = 1;
rep(i,1,m,1) fac[i] = 1ll*fac[i-1]*i%mod;
inv[m] = Inv(fac[m]);
drep(i,m-1,0,1) inv[i] = 1ll*inv[i+1]*(i+1)%mod;
int T; cin>>T;
while(T--){
cin>>n>>k;
if(k*2 > n){cout<<"0\n";continue;}
f[0] = 1;
rep(i,1,n/2,1) f[i] = 1ll*f[i-1]*Inv((C(n,2)-C(n-2*i,2)+mod)%mod)%mod;
int ans = 0;
rep(i,k,n/2,1){
int res = C(i,k);
if((i-k)&1) res = (mod - res)%mod;
ans = (ans + 1ll*res*get(n,i)%mod)%mod;
}
cout<<ans<<'\n';
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}