训练周记#1

Day1

挑战一天背完九上所有古诗文，咕咕咕

Day2

掉分场 计数dp 一句话题解：恰好$k$个转换为钦定$k$个，剩下随意，二项式反演然后$dp$

Day3

计数dp/神必复杂度 几句话题解：首先枚举最小值，发现最小值最大只有$\frac{V}{k}$，对每个最小值进行$dp$，求出$dp[i][j]$表示前$i$个，选了$j$个，最小值大于等于枚举的值的方案数，发现可以双指针+前缀和做到$O(nk)$,最后差分统计答案，复杂度$O(Vk)$。 分数规划 一句话：套路题，二分比值然后树上背包。

Day4

决策单调性 比较有价值所以单独写了一篇博客。

Day5

星期五要上物理课 咕咕咕

Day6

BIT+扫描线 一眼题， 脑残边界写错好几次，调试三小时，我的做法貌似和网上大部分博客不太一样，一条竖线的贡献同样是经过横线的数量，如果有线坐标是$[0,1e6]$则$ans++$,先是对竖线扫描线，对于靠左的横线，如果他的$r_i\ge x$，会造成贡献，则对右端点排序，一个个加入树状数组，靠右的反之亦然。

#include<bits/stdc++.h> #define int long long #define N 1000015 #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--) #define inf 0x3f3f3f3f #define pb push_back #define mp make_pair #define lowbit(i) ((i)&(-i)) #define VI vector<int> #define left fuck #define right ffuucckk #define All(x) x.begin(),x.end() #define debug(x) for(auto v:x) cout << v.l << ' ' << v.r << endl;cout <<"end" << endl; using namespace std; int n,m,t[N],ans; const int M = 1e6; struct hori{ int l,r,y; hori(){} hori(int a,int b,int c){l = a;r = b;y = c;} bool operator<(const hori&o) const{ if(l == 0) return o.r < r; if(r == M) return o.l > l; } }; struct ver{ int l,r,x; ver(){} ver(int a,int b,int c){l = a;r = b;x = c;} bool operator<(const ver&o) const{ return x < o.x; } }; struct BIT{ int a[N]; void add(int x,int d){ x++; for(;x<=M+1;x+=lowbit(x)) a[x]+=d; } int query(int x){ x++; int res = 0; for(;x;x-=lowbit(x)) {res+=a[x];} return res; } int query(int l,int r){ return query(r)-query(l-1); } }A,B; vector<ver> line; vector<hori> left,right; signed main(){ //freopen(".in","r",stdin); //freopen(".out","w",stdout); cin>>n>>m; rep(i,1,n){ int l,r,y; cin>>y>>l>>r; if(l == 0) left.pb(hori(l,r,y)); else if(r == M) right.pb(hori(l,r,y)); if(l==0&&r==M) ans++; } rep(i,1,m){ int l,r,y; cin>>y>>l>>r; if(l == 0&&r == M) ans++; line.pb(ver(l,r,y)); } sort(All(line));sort(All(left));sort(All(right)); int sz = line.size(),z = right.size(); int cur = 0; rep(i,0,sz-1){ while(cur < z&&right[cur].l <= line[i].x){ A.add(right[cur].y,1); cur++; } t[i] += A.query(line[i].l,line[i].r); } cur = 0,z = left.size(); per(i,0,sz-1){ while(cur < z&&left[cur].r >= line[i].x){ B.add(left[cur].y,1); cur++; } t[i] += B.query(line[i].l,line[i].r); } rep(i,0,sz-1) ans += max(t[i],0ll); printf("%lld\n",ans+1); return 0; }

明天晚上打算掉场分。

Day7

线段树lazy 两个操作分别相当于 将深度$=k$的节点左右儿子儿子互换 或者 将深度 $>=k$的节点左右儿子儿子互换。注意到一换就是一整层，用$lazy[x]$表示第$x$层要不要换，在递归的时候传层数这个参数，如果当前层是$1$，往下走时反着走。 分治 找到当前序列最小值，将所有值减去最小值，左右继续分治，或者直接取$r-l+1$做答案。

开学第一周效率有点低，争取一天三道题吧