网站建设 山东,黄页88会员一年多少钱,做旅游计划的网站,东莞网页设计费用比赛经过
日常 20 m i n 20min 20min 后开考 稍微想了一下 T 1 T1 T1#xff0c;手玩了几个数据 样例的树形结构发现和 l o w b i t lowbit lowbit 关系较大#xff0c;遂往这个方向考虑#xff0c;大概回了#xff0c;写了很久#xff0c;中间有些细节不确定调了很久…比赛经过
日常 20 m i n 20min 20min 后开考 稍微想了一下 T 1 T1 T1手玩了几个数据 样例的树形结构发现和 l o w b i t lowbit lowbit 关系较大遂往这个方向考虑大概回了写了很久中间有些细节不确定调了很久大概 1 h 1h 1h 过了 T 2 T2 T2 一眼感觉第二种法术在最下面的根号左右层才有用算了一下发现是 6 n \sqrt {6n} 6n 有 800 800 800 左右 n f l s nfls nfls 机子很慢在乘上一些常数感觉有点过不去 去和其他人讨论了一下发现没有更好的解法 遂冲了一发很快过了大样例测了一波极限数据 0.3 s 0.3s 0.3s怎么跑这么快这时大概是 2 h 2h 2h T 3 T3 T3 题目很长花了一会才懂是个缝合怪题第二部分很快会了 q l o g n qlogn qlogn 做法但第一个问题 n*m的网格中有k个矩形对每一行求出有多少个矩形被覆盖了lim次(lim10) 一直只有 O ( n n ) O(n\sqrt n) O(nn ) 的想法差不多 2 h 50 m i n 2h50min 2h50min 左右还没想出来于是开始写到 3 h 20 m i n 3h20min 3h20min 左右调完过了大样例 1 − 5 1-5 1−5大概能拿 65 p t s 65pts 65pts 想摆看了一眼部分分 l i m 1 lim1 lim1那不直接线段树维护最小值吗诶我好像会了直接线段树维护前 l i m lim lim 个最小值及出现次数不就可以了吗还有 50 m i n 50min 50min于是开始冲在还剩 20 m i n 20min 20min 时过了所有样例但最大样例有点慢卡了卡常放在 n f l s nfls nfls 上测了一下很快遂摆 预估分数 100 100 100 5 305 1001001005305 1001001005305 实际分数 100 100 100 5 305 1001001005305 1001001005305
反思 T 2 T2 T2 想到根号做法却因为常数问题浪费了 30 m i n 30min 30min 没冲是一个错误 感觉自己一些普通问题上的思考也不够感觉线段树维护 l i m lim lim 小值很板
题解
A
没什么好说的直接组合数算一下
#include bits/stdc.h
using namespace std;
const int N10000100,K1000100,P998244353;
int n,q,fac[N],inv[N],v[K];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
int binom(int a,int b){if(a0||b0||ab) return 0;return 1ll*fac[a]*inv[b]%P*inv[a-b]%P;
}
int qmi(int a,int b){int res1;for(;b;b1){if(b1) res1ll*res*a%P;a1ll*a*a%P;}return res;
}
inline void inc(int x,int y){ xy;if(xP) x-P;}
int main(){freopen(tree.in,r,stdin);freopen(tree.out,w,stdout);fac[0]1;for(int i1;iN;i) fac[i]1ll*fac[i-1]*i%P;inv[N-1]qmi(fac[N-1],P-2);for(int iN-2;i0;i--) inv[i]1ll*inv[i1]*(i1)%P;nread(),qread();while(q--){int kread();for(int i1;ik;i) v[i]read();v[k]n;int dread(),ans0;for(int i1;ik;i){int curdd-(i-1);if(i1) inc(ans,binom(v[i],curd)),inc(ans,P-binom(v[i-1],curd-1));else inc(ans,binom(v[i],curd));}printf(%d\n,ans);}fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
T2
观察到第二种法术只有在后 6 n \sqrt{6n} 6n 层才会施展于是直接暴力 d p dp dp 即可状态是 f i , j f_{i,j} fi,j 表示到第 i i i 列施展第二种法术的位置的 m a x x y j max{xy}j maxxyj 的最小代价
#include bits/stdc.h
#define x first
#define y second
#define pb push_back
using namespace std;
const int N100100,B800,inf1e9;
typedef pairint,int pii;
int n,k,sum[B100],ans[B100];
pii p[N];
vectorint vec[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
int main(){freopen(tower.in,r,stdin);freopen(tower.out,w,stdout);nread(),kread();for(int i1;ik;i) p[i].xn-read()1,p[i].yread();sort(p1,pk1);int tot0;for(int i1;ik;i){if(p[i].xB) tot3;else vec[p[i].y].pb(p[i].x);}memset(ans,0x3f,sizeof(ans));ans[0]0;for(int i1;in;i){int yn-i1,limmin(B,y);for(int x:vec[i]) sum[x];sum[lim1]0;for(int jlim;j;j--) sum[j]sum[j1];int mninf;for(int j0;jlim;j){int tans[j];ans[j]min(ans[j],j*(j1)/22mn)3*sum[j1];mnmin(mn,t);}int tans[0];for(int j0;jlim;j) ans[j]ans[j1];ans[0]min(ans[0],t),ans[lim]inf;for(int j0;jlim;j) sum[j]0;}printf(%d\n,ans[0]tot);fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
C
首先第二问是好处理的直接按照 m i n min min 男女的数量排序处理一下前缀和即可 考虑第一问也就扫描线然后用线段树维护前 l i m lim lim 小值和其出现次数即可 时间复杂度 O ( n k l o g n q l o g n ) O(nklognqlogn) O(nklognqlogn)
#pragma GCC optimize(3)
#include bits/stdc.h
#define pb push_back
using namespace std;
typedef long long LL;
const int N300100;
struct RANGE{ int l,r,neg;};
int n,m,c,lim,q,v[N];
LL sum1[N],sum2[N];
vectorRANGE range[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
struct Node{ int mn[10],times[10];}seg[N2];
int tag[N2];
void down(int x,int tg){ for(int i0;ilim;i) seg[x].mn[i]tg;tag[x]tg;}
void build(int l,int r,int x){seg[x].mn[0]0,seg[x].times[0]r-l1;for(int i1;ilim;i) seg[x].mn[i]1e9,seg[x].times[i]0;if(lr) return;int mid(lr)1;build(l,mid,x1),build(mid1,r,x1^1);
}
void pushdown(int x){if(tag[x]) down(x1,tag[x]),down(x1^1,tag[x]),tag[x]0;
}
void pushup(Node ret,Node lc,Node rc){for(int i0,j0,k0;ilim;i){if(lc.mn[j]rc.mn[k]) ret.mn[i]lc.mn[j],ret.times[i]lc.times[j]rc.times[k],j,k;else if(lc.mn[j]rc.mn[k]) ret.mn[i]lc.mn[j],ret.times[i]lc.times[j],j;else ret.mn[i]rc.mn[k],ret.times[i]rc.times[k],k;}
}
void modify(int l,int r,int x,int L,int R,int v){if(LlrR){ down(x,v);return;}pushdown(x);int mid(lr)1;if(midL) modify(l,mid,x1,L,R,v);if(midR) modify(mid1,r,x1^1,L,R,v);pushup(seg[x],seg[x1],seg[x1^1]);
}
int main(){freopen(army.in,r,stdin);freopen(army.out,w,stdout);nread(),mread(),cread(),limread(),qread();for(int i1;ic;i){int x1read(),y1read(),x2read(),y2read();range[x1].pb({y1,y2,1}),range[x21].pb({y1,y2,-1});}build(1,m,1);for(int i1;in;i){for(auto ran:range[i]) modify(1,m,1,ran.l,ran.r,ran.neg);auto finseg[1];int res0;for(int j0;jlimfin.mn[j]lim;j) resfin.times[j];v[i]min(res,m-res);}sort(v1,vn1);for(int i1;in;i) sum1[i]sum1[i-1]v[i],sum2[i]sum2[i-1]1ll*v[i]*v[i];while(q--){int xread(),yread();LL ans0;int poslower_bound(v1,vn1,y/2)-v;if(n-pos1x) ans1ll*x*(y/2)*(y-y/2);else ans1ll*(n-pos1)*(y/2)*(y-y/2)1ll*y*(sum1[pos-1]-sum1[n-x])-(sum2[pos-1]-sum2[n-x]);printf(%lld\n,ans);}fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
D
没补不会
