Noip模拟31 2021.8.5
2024-09-06 02:22:53
T1 Game
当时先胡了一发$\textit{Next Permutation}$。。。
然后想正解，只想到贪心能求最大得分，然后就不会了。。
然后就甩个二十分的走了。。。
正解的最大得分（叫它$k$）是在树上维护的。
权值线段树上维护一个$A,B$表示$a,b$权值出现的次数。
那么$A$的右子树权值一定比$B$左子树权值大，每次取$min$递归就能找到$k$
然后考虑如何找到字典需最小方案
每次取出$b$（注意大小写的区分）中一个元素，找有没有比他大的$a$
用二分可以解决
如果没有，就找到比他小的里面最大的合法的$a$
也用二分解决
至于如何实现使用一个$multiset$维护，删除节点信息就行了
1 #include<bits/stdc++.h>
2 #define lid (id<<1)
3 #define rid (id<<1|1)
4 using namespace std;
5 const int NN=1e6+5;
6 int n,a[NN],b[NN],k,ta[NN],tb[NN],ans;
7 multiset<int> st;
8 struct SNOWtree{
9 int ll[NN<<2],rr[NN<<2],A[NN<<2],B[NN<<2];
10 inline void pushup(int id){
11 if(ll[id]==rr[id]) return;
12 int now=min(B[lid],A[rid]); ans+=now;
13 A[id]=A[lid]+A[rid]-now;
14 B[id]=B[lid]+B[rid]-now;
15 }
16 void build(int id,int l,int r){
17 ll[id]=l; rr[id]=r;
18 if(l==r){A[id]=ta[l]; B[id]=tb[l];return;}
19 int mid=l+r>>1;
20 build(lid,l,mid); build(rid,mid+1,r);
21 pushup(id);
22 }
23 void update(int id,int pos){
24 if(ll[id]==rr[id]){A[id]=ta[pos];B[id]=tb[pos];return;}
25 ans-=min(B[lid],A[rid]);
26 int mid=ll[id]+rr[id]>>1;
27 if(pos<=mid) update(lid,pos);
28 else update(rid,pos);
29 pushup(id);
30 }
31 }tr;
32 inline bool check(int mid,int opt){
33 --ta[mid]; tr.update(1,mid);
34 int tmp=ans+opt;
35 ++ta[mid]; tr.update(1,mid);
36 return tmp==k;
37 }
38 namespace WSN{
39 inline short main(){
40 scanf("%d",&n);
41 for(int i=1;i<=n;i++) scanf("%d",&b[i]),++tb[b[i]];
42 for(int i=1;i<=n;i++) scanf("%d",&a[i]),++ta[a[i]],st.insert(a[i]);
43 tr.build(1,1,*(--st.end())); k=ans;
44 for(int i=1;i<=n;i++){
45 --tb[b[i]]; tr.update(1,b[i]);
46 int l=b[i]+1,r=*(--st.end()),wsn=0;
47 while(l<=r){
48 int mid=l+r>>1;
49 if(check(mid,1)) l=mid+1,wsn=mid;
50 else r=mid-1;
51 }
52 if(!wsn){
53 int ll=0,rr=b[i];
54 while(ll<=rr){
55 int mid=ll+rr>>1;
56 if(check(mid,0)) ll=mid+1,wsn=mid;
57 else rr=mid-1;
58 }
59 }else --k;
60 --ta[wsn]; tr.update(1,wsn); st.erase(st.find(wsn));
61 printf("%d ",wsn);
62 }
63 return 0;
64 }
65 }
66 signed main(){return WSN::main();}
T2 Time
一眼找逆序对
然后貌似想到了所有正解
然后不会快速求逆序对。。。。
只会生硬的$O(n^2)$求，比较可恶，对于正解一点优化都加不上
无奈交了$O(n^2)$的暴力求逆序对方法，可恶。。。。。
正解就是扫一遍位置，找到他前面比他大的数有几个（就是求与他构成逆序对的个数）
后面比他大的数有几个（同理，正序对个数），取$min$加和就行了，正确性显然
$18$行的优秀代码，终于比$DeepinC$学长的代码短了一次嘿嘿。
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,a[1000005],ans=0,tr[1000005],pre[1000005],nxt[1000005];
4 inline int lowbit(int x){return x&(-x);}
5 inline void update(int x,int v){for(int i=x;i<=n;i+=lowbit(i))tr[i]+=v;}
6 inline int query(int x){int ans=0;for(int i=x;i;i-=lowbit(i))ans+=tr[i];return ans;}
7 namespace WSN{
8 inline short main(){
9 scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]);
10 for(int k=1;k<=n;k++) pre[k]=k-1-query(a[k]),update(a[k],1);
11 for(int i=0;i<=n;i++) tr[i]=0;
12 for(int k=n;k>=1;k--) nxt[k]=query(n)-query(a[k]),update(a[k],1);
13 for(int k=1;k<=n;k++) ans+=min(pre[k],nxt[k]);
14 printf("%d\n",ans);
15 return 0;
16 }
17 }
18 signed main(){return WSN::main();}
T3 Cover
包含和不相交关系，构成树，$skyh$讲树形$dp$时说过，
于是这题就是道树形$dp$，然后就不想打了，因为$dp$打不对。。。
想打$dfs$骗分，可是时间却不多，无法细致的调了，惨报零。。。
其实就是建树然后$dp$，那么我们也分两步说
一，建树：
这一方面，我们可以开一个$multiset$存所有的$id$和位置信息
然后递归建树，这一方面你为了正确的进行$\textit{lower_bound}$操作
需要一波重载运算符，然后在每次查的时候$id$赋值$0$，目的是不找到相同的值
前提是在重载运算符时提到关于$id$的比较，详见代码
剩下的只需看区间是否被传递的$l,r$包含，然后递归建边即可，注意跳出就行。
二，$dp$：
设$dp_{i,j}$表示以$i$为根的子树中至多选择$j$个区间的最大美观程度
因为子树内的点表示的区间信息都被$i$的信息所包含
所以这个$j$能够同理表示那个题目里走廊上的点被$j$个彩灯覆盖
于是可以得到状态转移方程：
$dp_{i,j}=max(\sum (dp_{son_i,j-1})+w_i,\sum dp_{son_i,j})$
此时$dp_{i,j}$表示的是恰好选择$j$个区间的美观度
然后需要把它的意义变成至多，要加上一步：
$dp_{i,j}=max(dp_{i,j},dp_{i,j-1})$
发现可以使用差分维护，配合一波$\textit{priority_queue}$就可以维护出答案的差分了
然后前缀和加起来输出即可
1 #include<bits/stdc++.h>
2 #define int long long
3 #define pb push_back
4 using namespace std;
5 const int NN=3e5+5,inf=2e9;
6 int n,m,w[NN],val[NN];
7 struct SNOW{
8 int l,r,id;
9 friend bool operator<(SNOW a,SNOW b){
10 return a.l==b.l?(a.r==b.r?a.id<b.id:a.r>b.r):a.l<b.l;
11 }
12 }s[NN];
13 multiset<SNOW> st;
14 priority_queue<int> Q[NN];
15 vector<int> e[NN];
16 inline void build(int id,int l,int r){
17 while(!st.empty()){
18 auto it=st.lower_bound((SNOW){l,r,0});
19 if(it==st.end()) break;
20 SNOW k=*it;
21 if(l<=k.l&&k.r<=r){
22 e[id].pb(k.id);
23 st.erase(it);
24 build(k.id,k.l,k.r);
25 }else break;
26 }
27 }
28 inline void dfs(int x){
29 int son=m+1;
30 for(int i=0;i<e[x].size();i++){
31 dfs(e[x][i]);
32 if(Q[e[x][i]].size()>Q[son].size()) son=e[x][i];
33 }swap(Q[son],Q[x]);
34 for(int i=0;i<e[x].size();i++){
35 if(e[x][i]==son) continue;
36 int k=Q[e[x][i]].size();
37 for(int j=1;j<=k;j++) val[j]=Q[x].top(),Q[x].pop();
38 for(int j=1;j<=k;j++) val[j]+=Q[e[x][i]].top(),Q[e[x][i]].pop();
39 for(int j=1;j<=k;j++) Q[x].push(val[j]);
40 }Q[x].push(w[x]);
41 }
42 namespace WSN{
43 inline short main(){
44 scanf("%lld%lld",&n,&m);
45 for(int i=1;i<=m;i++){
46 s[i].id=i;scanf("%lld%lld%lld",&s[i].l,&s[i].r,&w[i]);
47 st.insert(s[i]);
48 }build(0,1,n); dfs(0);
49 int k=Q[0].size();
50 for(int i=1;i<=k;i++) val[i]=Q[0].top(),Q[0].pop();
51 for(int i=1;i<=m;i++) val[i]+=val[i-1],printf("%lld ",val[i]);
52 return 0;
53 }
54 }
55 signed main(){return WSN::main();}
最新文章
- win7的优化-1:隐藏我的电脑导航栏里的收藏等项目
- oracle表相关
- Office导入导出组件权限配置汇总
- 关于lib,dll,.a,.so,静态库和动态库的解释说明
- 【概率】Uva 10900 - So you want to be a 2n-aire?
- AngularJS 拦截器和好棒例子
- 【深度学习系列】用PaddlePaddle和Tensorflow实现GoogLeNet InceptionV2/V3/V4
- SSH连接工具：SecureCRT设置，另一个SSH连接工具：Xshell。在Windows和Linux之间互传文件可用WinSCP
- rsync源目录写法的一点小细节
- iOS解决cell重用问题
- laravel compact的用法
- 归并排序Python 实现
- ZJOI 2019 划水记
- [P3452][POI2007]BIU-Offices (BFS)
- 【Java123】Java基础知识点
- django-chunks文件
- delphi clientdataset判断某一行值是否存在
- TreeMap（红黑树）源码分析
- Unity3d学习笔记记录
- mysql--SQL编程(关于mysql中的日期,实例,判断生日是否为闰年) 学习笔记2.1