Noip模拟22 2021.7.21
2024-09-06 02:23:06
T1 d
简化题意就是找到相对平均长宽的偏移量较大的矩形给他删掉
可以说是个贪心，按照a，b分别为第一关键字排序
然后假装删去要求的那么多个按a排序的较小的，然后再去b中，
找到 删去的a中的那几个矩形 比 按b排序的却并未删去的矩形 优的加回到最终用的矩形集合中
上述操作用经典指针可以实现。（%%zxs活学活用指针场上A掉此题）
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 inline int read(){
5 int x=0,f=1; char ch=getchar();
6 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
7 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
8 return x*f;
9 }
10 inline int max(int a,int b){return a>b?a:b;}
11 inline int min(int a,int b){return a<b?a:b;}
12 const int NN=1e5+5,inf=1e18;
13 int T,n,m,cnt,ita,itb,ans,tmp;
14 int ta[NN],tb[NN];
15 bool vis[NN];
16 struct node{int a,b,id;}s[NN],aa[NN],bb[NN];
17 inline bool cmp1(node x,node y){return x.a==y.a? x.b<y.b:x.a<y.a;}
18 inline bool cmp2(node x,node y){return x.b==y.b? x.a<y.a:x.b<y.b;}
19 inline void clear(){
20 memset(vis,0,sizeof(vis));
21 memset(ta,0,sizeof(ta));
22 memset(tb,0,sizeof(tb));
23 ans=0; ita=itb=inf; tmp=1;
24 }
25 inline void move(){
26 while(!ta[ita]) ita++;
27 while(!tb[itb]) itb++;
28 ans=max(ans,ita*itb);
29 }
30 namespace WSN{
31 inline int main(){
32 T=read(); if(!T) return 0;
33 while(T--){
34 clear();
35 n=read();m=read();
36 for(int i=1;i<=n;i++) s[i].a=read(),s[i].b=read(),s[i].id=i;
37 for(int i=1;i<=n;i++){
38 aa[i]=s[i]; bb[i]=s[i];
39 ta[s[i].a]++; tb[s[i].b]++;
40 ita=min(ita,s[i].a); itb=min(itb,s[i].b);
41 }
42 sort(aa+1,aa+n+1,cmp1); sort(bb+1,bb+n+1,cmp2);
43 for(int i=1;i<=m;i++){
44 vis[aa[i].id]=1;
45 --ta[aa[i].a]; --tb[aa[i].b];
46 } move();
47 for(int i=1;i<=m;i++){
48 if(aa[m-i+1].b<=itb) continue;
49 vis[aa[m-i+1].id]=0; ++ta[aa[m-i+1].a]; ++tb[aa[m-i+1].b];
50 if(aa[m-i+1].a<ita) ita=aa[m-i+1].a;
51 while(vis[bb[tmp].id]) tmp++; --ta[bb[tmp].a]; --tb[bb[tmp].b]; vis[bb[tmp].id]=1;
52 move();
53 }
54 printf("%lld\n",ans);
55 }
56 return 0;
57 }
58 }
59 signed main(){return WSN::main();}
T2 e
题目好理解，用：
树链剖分套线段书套平衡树可以解决（Splay没有FHQ—treap更具奇迹性）
我打的Splay无法过掉最大的点，但是JYFHYX打的FHQ—treap却可以
这就是treap的复杂度奇迹性。。。。
1 #include<bits/stdc++.h>
2 #define lid (id<<1)
3 #define rid (id<<1|1)
4 inline int max(int a,int b){return a>b?a:b;}
5 inline int min(int a,int b){return a<b?a:b;}
6 inline void swap(int &x,int &y){x^=y^=x^=y;}
7 using namespace std;
8 inline int read(){
9 int x=0,f=1; char ch=getchar();
10 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
11 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
12 return x*f;
13 }
14 inline void write(int x){
15 if(x<0){ putchar('-'); x=-x;}
16 if(x>9) write(x/10);
17 putchar(x%10+'0');
18 }
19 const int NN=1500000,inf=2e9;
20 int n,q,typ,a[NN],x[NN],r,k,Q[NN],tot,rt[NN<<2],ans;
21 int dfn[NN],rk[NN],son[NN],fa[NN],top[NN],siz[NN],dep[NN],cnt;
22 struct SNOW{int to,next;};SNOW e[NN<<1]; int head[NN],rp;
23 struct Splay{int son[2],fa,cnt,siz,val;}s[NN];
24 inline void add(int x,int y){
25 e[++rp]=(SNOW){y,head[x]};head[x]=rp;
26 e[++rp]=(SNOW){x,head[y]};head[y]=rp;
27 }
28 inline void dfs1(int f,int x){
29 siz[x]=1;dep[x]=dep[f]+1;fa[x]=f;
30 for(int i=head[x];i;i=e[i].next){
31 int y=e[i].to;
32 if(y==f) continue;
33 dfs1(x,y); siz[x]+=siz[y];
34 if(siz[son[x]]<siz[y]) son[x]=y;
35 }
36 }
37 inline void dfs2(int x,int t){
38 top[x]=t; dfn[x]=++cnt; rk[cnt]=x;
39 if(!son[x]) return;
40 dfs2(son[x],t);
41 for(int i=head[x];i;i=e[i].next){
42 int y=e[i].to;
43 if(y!=fa[x]&&y!=son[x]) dfs2(y,y);
44 }
45 }
46 inline int LCA(int x,int y){
47 while(top[x]!=top[y]){
48 if(dep[top[x]]<dep[top[y]]) swap(x,y);
49 x=fa[top[x]];
50 }if(dfn[x]>dfn[y]) swap(x,y);
51 return x;
52 }
53 struct SPLAY{
54 void pushup(int x){s[x].siz=s[s[x].son[0]].siz+s[s[x].son[1]].siz+s[x].cnt;}
55 int get(int x){return x==s[s[x].fa].son[1];}
56 void rotate(int x){
57 int y=s[x].fa,z=s[y].fa,xpos=get(x),ypos=get(y);
58 s[z].son[ypos]=x; s[x].fa=z;
59 s[y].son[xpos]=s[x].son[xpos^1]; s[s[x].son[xpos^1]].fa=y;
60 s[x].son[xpos^1]=y; s[y].fa=x;
61 pushup(y); pushup(x);
62 }
63 void splay(int x,int goal,int root){
64 while(s[x].fa!=goal){
65 int y=s[x].fa,z=s[y].fa,xpos=get(x),ypos=get(y);
66 if(z!=goal){
67 if(xpos==ypos) rotate(y);
68 else rotate(x);
69 }rotate(x);
70 }if(!goal) rt[root]=x;
71 }
72 void insert(int val,int root){
73 int u=rt[root],fa=0;
74 while(u && s[u].val!=val) fa=u,u=s[u].son[val>s[u].val];
75 if(u) s[u].cnt++;
76 else{
77 u=++tot;
78 if(fa) s[fa].son[val>s[fa].val]=u;
79 s[u].son[0]=s[u].son[1]=0; s[u].val=val; s[u].fa=fa;
80 s[u].siz=s[u].cnt=1;
81 }splay(u,0,root);
82 }
83 void find_rank(int val,int root){
84 int u=rt[root];
85 if(!u) return;
86 while(s[u].son[val>s[u].val] && val!=s[u].val) u=s[u].son[val>s[u].val];
87 splay(u,0,root);
88 }
89 int prenxt(int val,int op,int root){
90 find_rank(val,root);int u=rt[root];
91 if(s[u].val>=val && op) return u;
92 if(s[u].val<=val &&!op) return u;
93 u=s[u].son[op];
94 while(s[u].son[op^1]) u=s[u].son[op^1];
95 return u;
96 }
97 }sp;
98 struct SNOWtree{
99 void build(int id,int l,int r){
100 sp.insert(inf,id); sp.insert(-inf,id);
101 if(l==r) return;
102 int mid=l+r>>1;
103 build(lid,l,mid); build(rid,mid+1,r);
104 }
105 void insert(int id,int l,int r,int pos,int val){
106 sp.insert(val,id);
107 if(l==r) return; int mid=l+r>>1;
108 if(pos<=mid) insert(lid,l,mid,pos,val);
109 else insert(rid,mid+1,r,pos,val);
110 }
111 int pre(int id,int l,int r,int L,int R,int val){
112 if(l>R||r<L) return -inf;
113 if(L<=l&&r<=R) return s[sp.prenxt(val,0,id)].val;
114 int mid=l+r>>1;
115 return max(pre(lid,l,mid,L,R,val),pre(rid,mid+1,r,L,R,val));
116 }
117 int nxt(int id,int l,int r,int L,int R,int val){
118 if(l>R||r<L) return inf;
119 if(L<=l&&r<=R) return s[sp.prenxt(val,1,id)].val;
120 int mid=l+r>>1;
121 return min(nxt(lid,l,mid,L,R,val),nxt(rid,mid+1,r,L,R,val));
122 }
123 }tr;
124 inline int houj(int x,int y,int k){
125 int ans=inf;
126 while(top[x]!=top[y]){
127 if(dep[top[x]]<dep[top[y]]) swap(x,y);
128 ans=min(ans,tr.nxt(1,1,n,dfn[top[x]],dfn[x],k));;
129 x=fa[top[x]];
130 }if(dfn[x]>dfn[y]) swap(x,y);
131 ans=min(ans,tr.nxt(1,1,n,dfn[x],dfn[y],k));
132 return ans;
133 }
134 inline int qian(int x,int y,int k){
135 int ans=-inf;
136 while(top[x]!=top[y]){
137 if(dep[top[x]]<dep[top[y]]) swap(x,y);
138 ans=max(ans,tr.pre(1,1,n,dfn[top[x]],dfn[x],k));
139 x=fa[top[x]];
140 }if(dfn[x]>dfn[y]) swap(x,y);
141 ans=max(ans,tr.pre(1,1,n,dfn[x],dfn[y],k));
142 return ans;
143 }
144 namespace WSN{
145 inline int main(){
146 // freopen("e7.in","r",stdin);
147 // freopen("6.out","w",stdout);
148 n=read(); q=read(); typ=read();if(!q) return 0;
149 for(int i=1;i<=n;i++) a[i]=read();
150 for(int i=1;i<n;i++) add(read(),read());
151 dfs1(0,1); dfs2(1,1); tr.build(1,1,n);
152 for(int i=1;i<=n;i++) tr.insert(1,1,n,dfn[i],a[i]);
153 for(int w=1;w<=q;w++){
154 r=read(),k=read();
155 for(int i=1;i<=k;i++) Q[i]=x[i]=read();
156 if(typ) for(int i=1;i<=k;i++) Q[i]=(x[i]-1+ans*typ)%n+1;
157 ans=inf;
158 int Lca=Q[1]; for(int i=2;i<=k;i++) Lca=LCA(Lca,Q[i]);
159 for(int i=1;i<=k;i++){
160 int pre=qian(Lca,Q[i],r);
161 int nxt=houj(Lca,Q[i],r);
162 ans=min(ans,min(abs(r-pre),abs(r-nxt)));
163 } write(ans); putchar('\n');
164 }
165 return 0;
166 }
167 }
168 signed main(){return WSN::main();}
80分树套树套树
正解是个主席树板子，所以打完这道题后就去打了主席树专题
1 #include<bits/stdc++.h>
2 inline int max(int a,int b){return a>b?a:b;}
3 inline int min(int a,int b){return a<b?a:b;}
4 inline void swap(int &x,int &y){x^=y^=x^=y;}
5 using namespace std;
6 inline int read(){
7 int x=0,f=1; char ch=getchar();
8 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
9 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
10 return x*f;
11 }
12 inline void write(int x){
13 if(x<0){ putchar('-'); x=-x;}
14 if(x>9) write(x/10);
15 putchar(x%10+'0');
16 }
17 const int NN=100005,inf=2e9;
18 int n,q,typ,a[NN],x[NN],r,k,Q[NN],tot,ans;
19 int dfn[NN],rk[NN],son[NN],fa[NN],top[NN],siz[NN],dep[NN],cnt;
20 int rt[NN];
21 struct SNOW{int to,next;};SNOW e[NN<<1]; int head[NN],rp;
22 inline void add(int x,int y){
23 e[++rp]=(SNOW){y,head[x]};head[x]=rp;
24 e[++rp]=(SNOW){x,head[y]};head[y]=rp;
25 }
26 inline void dfs1(int f,int x){
27 siz[x]=1;dep[x]=dep[f]+1;fa[x]=f;
28 for(int i=head[x];i;i=e[i].next){
29 int y=e[i].to;
30 if(y==f) continue;
31 dfs1(x,y); siz[x]+=siz[y];
32 if(siz[son[x]]<siz[y]) son[x]=y;
33 }
34 }
35 inline void dfs2(int x,int t){
36 top[x]=t; dfn[x]=++cnt; rk[cnt]=x;
37 if(!son[x]) return;
38 dfs2(son[x],t);
39 for(int i=head[x];i;i=e[i].next){
40 int y=e[i].to;
41 if(y!=fa[x]&&y!=son[x]) dfs2(y,y);
42 }
43 }
44 inline int LCA(int x,int y){
45 while(top[x]!=top[y]){
46 if(dep[top[x]]<dep[top[y]]) swap(x,y);
47 x=fa[top[x]];
48 }if(dfn[x]>dfn[y]) swap(x,y);
49 return x;
50 }
51 struct SNOWtree{
52 int num,ll[NN*80],rr[NN*80],sum[NN*80];
53 inline int New(int x){sum[++num]=sum[x]; ll[num]=ll[x]; rr[num]=rr[x]; return num;}
54 inline void pushup(int x){sum[x]=sum[ll[x]]+sum[rr[x]];}
55 inline int insert(int id,int l,int r,int pos){
56 id=New(id); ++sum[id];
57 if(l==r) return id;
58 int mid=l+r>>1;
59 if(pos<=mid) ll[id]=insert(ll[id],l,mid,pos);
60 else rr[id]=insert(rr[id],mid+1,r,pos);
61 pushup(id); return id;
62 }
63 inline int pre(int id1,int id2,int l,int r,int pos){
64 if(sum[id1]==sum[id2]) return -inf;
65 if(l==r) return l;
66 int mid=l+r>>1;
67 if(pos<=mid) return pre(ll[id1],ll[id2],l,mid,pos);
68 else{
69 int tmp=pre(rr[id1],rr[id2],mid+1,r,pos);
70 if(tmp!=-inf) return tmp;
71 else return pre(ll[id1],ll[id2],l,mid,mid);
72 }
73 }
74 inline int nxt(int id1,int id2,int l,int r,int pos){
75 if(sum[id1]==sum[id2]) return inf;
76 if(l==r) return l;
77 int mid=l+r>>1;
78 if(pos>mid) return nxt(rr[id1],rr[id2],mid+1,r,pos);
79 else{
80 int tmp=nxt(ll[id1],ll[id2],l,mid,pos);
81 if(tmp!=inf) return tmp;
82 else return nxt(rr[id1],rr[id2],mid+1,r,mid+1);
83 }
84 }
85 }tr;
86 namespace WSN{
87 inline int main(){
88 // freopen("e7.in","r",stdin);
89 // freopen("6.out","w",stdout);
90 n=read(); q=read(); typ=read();if(!q) return 0;
91 for(int i=1;i<=n;i++) a[i]=read();
92 for(int i=1;i<n;i++) add(read(),read());
93 dfs1(0,1); dfs2(1,1);
94 for(int i=1;i<=n;i++) rt[i]=tr.insert(rt[fa[i]],1,inf,a[i]);
95 for(int w=1;w<=q;w++){
96 r=read(),k=read();
97 for(int i=1;i<=k;i++) Q[i]=x[i]=read();
98 if(typ) for(int i=1;i<=k;i++) Q[i]=(x[i]-1+ans*typ)%n+1;
99 ans=inf;
100 int Lca=Q[1]; for(int i=2;i<=k;i++) Lca=LCA(Lca,Q[i]);
101 for(int i=1;i<=k;i++){
102 int pre=tr.pre(rt[fa[Lca]],rt[Q[i]],1,inf,r);
103 int nxt=tr.nxt(rt[fa[Lca]],rt[Q[i]],1,inf,r);
104 //cout<<"pre="<<pre<<endl;
105 //cout<<"nxt="<<nxt<<endl;
106 ans=min(ans,min(abs(r-pre),abs(r-nxt)));
107 } write(ans); putchar('\n');
108 }
109 return 0;
110 }
111 }
112 signed main(){return WSN::main();}
T3 f
沽沽沽～～～
最新文章
- Security1:Create Login
- Git Merge Commit忘了选分支？数据丢失？ 刚刚做的都丢失了？别急！
- Fast-paced Multiplayer
- Unix: How to Install BerkeleyDB From Source
- Linux系统故障处理案例(一)
- oracle中的exists 和not exists 用法详解(转)
- HDU 2063 裸奔的二分图最大匹配
- CSS3边框
- flask + wtform + google storage
- <p></p>标签为什么不能包含块级标签?还有哪些特殊的HTML标签？
- 零基础新手学习Java必须知道的市场行情
- 服务器资源监控插件(jmeter)
- Java使用RSA加密解密签名及校验
- springboot秒杀课程学习整理1-2
- JAVA EE 的学习目标
- JS调用摄像头并上传图片到服务器
- MongoDB入门（一）
- 数据库的连接使用——使用ADO.NET连接数据库
- 使用VisualStudio进行脚本|样式文件压缩
- [UE4]修改相机裁剪距离