2024-03-30
扫描线
这两天讲课一直提到扫描线，学一下
看题解学会的，挺简单的感觉
本来以为半个小时就能写完
但是状态十分不好
小错很多，调了一个半小时/kk
注意离散化的是横坐标
而线段树存的是切割出来的线段
因此左端点要加 \(1\)，求长度的时候又得减回来
扫描线经典的技巧是将开始扫描这个矩形的边和结束这个矩形的扫描的边赋上不同的权值
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define ls (u<<1)
#define rs (u<<1|1)
using namespace std;
typedef long long ll;
const int N=1e6+100;
int n;
struct Seg {
ll lft,rgh,hgt,wgh;
bool operator<(const Seg &t)const {
if(hgt==t.hgt) return wgh>t.wgh;
return hgt<t.hgt;
}
}a[N*2];
int cnt;
vector<ll> nums;
ll g(ll x) {
return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
struct Node {
ll lft,rgh;
ll cnt,val;
}tr[N*8];
void pushup(int u) {
if(tr[u].cnt) tr[u].val=nums[tr[u].rgh]-nums[tr[u].lft-1];
else tr[u].val=tr[ls].val+tr[rs].val;
}
void build(int u,int lft,int rgh) {
tr[u].lft=lft,tr[u].rgh=rgh;
if(lft==rgh) return;
int mid=lft+rgh>>1;
build(ls,lft,mid),build(rs,mid+1,rgh);
}
void update(int u,int ul,int ur,int ux) {
if(tr[u].lft>=ul&&tr[u].rgh<=ur) {
tr[u].cnt+=ux;
pushup(u);
return;
}
int mid=tr[u].lft+tr[u].rgh>>1;
if(ul<=mid) update(ls,ul,ur,ux);
if(ur>mid) update(rs,ul,ur,ux);
pushup(u);
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
ll x1,y1,x2,y2;
scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
nums.push_back(x1),nums.push_back(x2);
cnt++,a[cnt].hgt=y1,a[cnt].lft=x1,a[cnt].rgh=x2,a[cnt].wgh=1;
cnt++,a[cnt].hgt=y2,a[cnt].lft=x1,a[cnt].rgh=x2,a[cnt].wgh=-1;
}
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
for(int i=1;i<=cnt;i++) a[i].lft=g(a[i].lft)+1,a[i].rgh=g(a[i].rgh);
build(1,1,nums.size()-1);
ll ans=0;
sort(a+1,a+cnt+1);
for(int i=1;i<cnt;i++) {
update(1,a[i].lft,a[i].rgh,a[i].wgh);
ans+=(a[i+1].hgt-a[i].hgt)*tr[1].val;
}
printf("%lld\n",ans);
return 0;
}
palin
上午的考试题
题意就是一张由小写字母组成的地图
从左上走到右下的路径中 经过的字符组成的字符串是回文串 的路径 的数量
考场上写的 \(O(n^4)\) DP
f[x][y][p][q] 表示从 \((x,y)\) 走到 \((p,q)\) 的路径中回文路径的数量
两端各有两个位置可以从那里扩展到当前状态
四种扩展方式加起来
当然，要判断 s[x][y]==s[p][q]
发现题目要求算从左上到右下的方案数
但是我们顺便把中间任意两个点之间的 答案 都计算出来了
说明有 冗余的信息
实际上，只有 \(x+y=n+m+2\) 的状态是有用的
所以 \(x,y,p,q\) 知道 \(3\) 个就可以求另外一个了
优化到了 \(O(n^3)\)，可以通过
注意枚举顺序
一开始数组开得稍微大了点，交到OJ上 段错误。搞不懂，不是开小了才段错误么
#include<iostream>
#include<cstring>
#include<algorithm>
#define mod 993244853
using namespace std;
const int N=505;
int n,m;
char s[N][N];
int f[N][N][N];
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int t=(n+m+2)/2;t>=2;t--) {
for(int x=1;x<t;x++) {
int y=t-x;
if(x>n||y>m) continue;
int d=n+m+2-2*t;
for(int i=0;i<=d;i++) {
int j=d-i;
int p=x+i,q=y+j;
if(p>n||q>m) continue;
if(s[x][y]!=s[p][q]) continue;
if(d<=1) {
f[t][x][p]=1;
continue;
}
f[t][x][p]=((f[t+1][x+1][p-1]+f[t+1][x][p-1])%mod+(f[t+1][x+1][p]+f[t+1][x][p])%mod)%mod;
}
}
}
printf("%d\n",f[2][1][n]);
return 0;
}
qsort
考试题
考场上降智了，啥也没想出来，就模拟了一下
其实挺简单的
按照题意
从前往后扫
- 如果当前这个数是
nan那么他就固定在这里了 - 否则如果这个数是
x把后面所有 严格小于x的数按顺序提到前面来
具体实现的时候
我们可以先把非 nan 的数提溜出来到 b 数组排好序，记一个指针 nw 表示当前b 输出到哪里了
扫的时候有 nan 就直接输出，否则一边输出 b 中的数 一边移动指针 nw 直到 b[nw]>=x
然后把 x 输出
这样我们可以自动把输出过的过滤掉（它们根本不会进 while 循环）
一开始忘记是严格小于了
但是这样有个问题
最后输出的那个 x 是不会经过 while 循环的，所以就有可能重复输出
所以最后输出 x 的时候判断一下 b 数组下一个数和当前的 x 要相等就行了
注意边界 nw<=cnt
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e5+50;
struct Number {
bool isnan;
int value;
}a[N];
Number rdnum() {
Number res;
char cc;
cc=getchar();
while(cc<'0'||cc>'9') {
if(cc=='n') {
res.isnan=true,res.value=0;
cc=getchar(),cc=getchar();
return res;
}
cc=getchar();
}
int xx=0;
while(cc>='0'&&cc<='9') {
xx=xx*10+cc-'0';
cc=getchar();
}
res.isnan=false,res.value=xx;
return res;
}
int n;
int b[N],cnt;
int main() {
int T;
scanf("%d",&T);
while(T--) {
cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
a[i]=rdnum();
if(!a[i].isnan) b[++cnt]=a[i].value;
}
sort(b+1,b+cnt+1);
if(cnt==n) {
for(int i=1;i<=n;i++) printf("%d ",b[i]);
puts("");
continue;
}
int nw=1;
for(int i=1;i<=n;i++) {
if(a[i].isnan) {
printf("nan ");
continue;
}
while(nw<=cnt&&b[nw]<a[i].value) printf("%d ",b[nw]),nw++;
if(nw<=cnt&&a[i].value==b[nw]) {
printf("%d ",a[i].value);
nw++;
}
}
puts("");
}
return 0;
}
chaotic evil
构造题 看懂题解了 但是不会写
