「雅礼集训 2017 Day2」水箱
我怎么知道这种题目都能构造树形结构。
根据高度构造一棵树，在树上倍增找到最大的小于约束条件高度的隔板，开一个 \(vector\) 记录一下，然后对于每个 \(vector\) 按照高度排序一下，树形 \(dp\) 即可
\(Code\ Below:\)
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define F first
#define S second
using namespace std;
const int maxn=200000+10;
int n,m,h[maxn],f[maxn],cnt[maxn],d[maxn],dp[maxn],ch[maxn][2],fa[maxn][18],num;
pii a[maxn];
vector<pii> g[maxn];
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
int find(int x){
return (x==f[x])?x:f[x]=find(f[x]);
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
memset(h,0,sizeof(h));
memset(ch,0,sizeof(ch));
memset(cnt,0,sizeof(cnt));
memset(d,0,sizeof(d));
memset(dp,0,sizeof(dp));
n=read(),m=read();
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<n;i++) h[i]=a[i].F=read(),a[i].S=i;
sort(a+1,a+n);
int x,y,t;num=n;
for(int i=1;i<n;i++){
x=find(a[i].S),y=find(a[i].S+1);
h[++num]=a[i].F;fa[num][0]=0;ch[num][0]=x;ch[num][1]=y;
f[x]=f[y]=f[num]=fa[x][0]=fa[y][0]=num;
}
for(int j=1;j<18;j++)
for(int i=1;i<=num;i++) fa[i][j]=fa[fa[i][j-1]][j-1];
for(int i=1;i<=num;i++) g[i].clear();
for(int i=1;i<=m;i++){
x=read(),y=read(),t=read();
for(int j=17;j>=0;j--)
if(fa[x][j]&&h[fa[x][j]]<=y) x=fa[x][j];
g[x].push_back(mp(y,t));cnt[x]+=(!t);
}
for(int i=1;i<=num;i++) sort(g[i].begin(),g[i].end());
int val;
for(int i=1;i<=num;i++){
dp[i]=val=d[ch[i][0]]+d[ch[i][1]]+cnt[i];
for(int j=0,k;j<g[i].size();j=k){
for(k=j;g[i][k].F==g[i][j].F&&k<g[i].size();k++) val+=(g[i][k].S?1:-1);
dp[i]=max(dp[i],val);
}
d[i]=val;dp[i]=max(dp[i],dp[ch[i][0]]+dp[ch[i][1]]+cnt[i]);
}
printf("%d\n",dp[num]);
}
return 0;
}
「雅礼集训 2017 Day2」棋盘游戏
同 \([JSOI2009]\) 游戏。
这么难的二分图匹配+博弈怎么才蓝呢？？？
\(Code\ Below:\)
#include <bits/stdc++.h>
#define id(x,y) (((x)-1)*m+(y))
using namespace std;
const int maxn=100000+10;
int n,m,a[110][110],ans[maxn],match[maxn],vis[maxn],tim,sta[maxn],top;
int head[maxn],to[maxn],nxt[maxn],tot;
int nx[4]={0,0,1,-1},ny[4]={1,-1,0,0};
char s[maxn];
inline void add(int x,int y){
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
int dfs1(int x){
for(int i=head[x],y;i;i=nxt[i]){
y=to[i];
if(vis[y]==tim) continue;
vis[y]=tim;
if(!match[y]||dfs1(match[y])){
match[y]=x;
return 1;
}
}
return 0;
}
void dfs2(int x){
ans[x]=1;
for(int i=head[x],y;i;i=nxt[i]){
y=to[i];
if(match[y]&&!ans[match[y]]) dfs2(match[y]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=m;j++)
if(s[j]=='.') a[i][j]=1;
}
int x,y;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j])
for(int k=0;k<4;k++){
x=i+nx[k];y=j+ny[k];
if(x<1||x>n||y<1||y>m) continue;
if(a[x][y]) add(id(i,j),id(x,y)+n*m),add(id(x,y)+n*m,id(i,j));
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]){
tim++;
if(!dfs1(id(i,j))) sta[++top]=id(i,j);
}
if(!top) puts("0");
else {
for(int i=1;i<=top;i++) dfs2(sta[i]);
top=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(ans[id(i,j)]) sta[++top]=id(i,j);
printf("%d\n",top);
for(int i=1;i<=top;i++) printf("%d %d\n",(sta[i]-1)/m+1,(sta[i]-1)%m+1);
}
return 0;
}
「雅礼集训 2017 Day2」线段游戏
李超线段树模板题。
\(Code\ Below:\)
#include <bits/stdc++.h>
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;
const int maxn=1000000+10;
const int lim=1000000;
const double inf=1e8;
int n,m,now[maxn<<3],cnt;
double k[maxn<<3],b[maxn<<3];
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
double f(int now,int x){
if(!now) return -inf;
return k[now]*x+b[now];
}
void modify(int l,int r,int x,int rt){
int mid=(l+r)>>1;
if(f(now[rt],mid)<f(x,mid)) swap(now[rt],x);
if(l == r) return ;
if(k[now[rt]]>k[x]) modify(l,mid,x,lson);
else modify(mid+1,r,x,rson);
}
void update(int L,int R,int x,int l,int r,int rt){
if(L <= l && r <= R){
modify(l,r,x,rt);
return ;
}
int mid=(l+r)>>1;
if(L <= mid) update(L,R,x,l,mid,lson);
if(R > mid) update(L,R,x,mid+1,r,rson);
}
double query(int x,int l,int r,int rt){
if(l == r) return f(now[rt],x);
int mid=(l+r)>>1;
if(x <= mid) return max(f(now[rt],x),query(x,l,mid,lson));
return max(f(now[rt],x),query(x,mid+1,r,rson));
}
int main()
{
n=read(),m=read();
int op,x0,x1,y1,x2,y2;double ans;
for(int i=1;i<=n;i++){
x1=read(),y1=read(),x2=read(),y2=read();
if(y1>y2) swap(y1,y2),swap(x1,x2);
k[++cnt]=(x1==x2)?0:1.0*(y2-y1)/(x2-x1);
b[cnt]=y2-k[cnt]*x2;
if(x1>x2) swap(x1,x2);
if(x1<=lim&&x2>=1) update(max(1,x1),min(lim,x2),cnt,1,lim,1);
}
for(int i=1;i<=m;i++){
op=read();
if(op==0){
x1=read(),y1=read(),x2=read(),y2=read();
if(y1>y2) swap(y1,y2),swap(x1,x2);
k[++cnt]=(x1==x2)?0:1.0*(y2-y1)/(x2-x1);
b[cnt]=(double)y2-k[cnt]*x2;
if(x1>x2) swap(x1,x2);
if(x1<=lim&&x2>=1) update(max(1,x1),min(lim,x2),cnt,1,lim,1);
}
else {
x0=read();
ans=query(x0,1,lim,1);
if(ans==-inf) puts("0");
else printf("%.2lf\n",ans);
}
}
return 0;
}