2019,11,4 长郡 csp

考试

今天又考炸了...真的有点无助...
前几天的题还没改完, 所以就粗糙地记录一下吧.

T1 学农 farm

题意

平面内有若干个点, 每个点有一个权值, 选定一个位置, 使得所有点到达这个位置的曼哈顿距离加上权值的最大值最小.

思路

"最大值最小", 果断二分,
但是我当时完全没用脑子....感觉不会check, 就跑了....

二分答案, 然后每个点的活动范围是一个菱形, 对这些菱形求交就行了(维护上下界, 左右界)

然后其实只要把这些点按照它们的权值拆成四个点, 然后找到一个最小的菱形, 使它能包围所有点就行了.

代码

#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
const int N=1e6+7;
const ll inf=1e12;
int n;
ll x[N],y[N],t[N];
db ans;
ll gi(){
    char c=getchar(); ll x=0,f=1;
    while(c<'0'||c>'9'){ f=c=='-'?-1:1; c=getchar(); }
    while(c>='0'&&c<='9'){ x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }
    return x*f;
}
int main(){
//  freopen("farm2.in","r",stdin);
    n=(int)gi();
    ll b1=-inf,b2=inf,b3=-inf,b4=inf;
    for(int i=1;i<=n;i++){ 
        x[i]=gi(); y[i]=gi(); t[i]=gi(); 
        b1=max(b1,y[i]-x[i]+t[i]);
        b2=min(b2,y[i]-x[i]-t[i]);
        b3=max(b3,y[i]+x[i]+t[i]);
        b4=min(b4,y[i]+x[i]-t[i]);
    }
    ans=max((b1-b2)/2.0,(b3-b4)/2.0);
    printf("%lf\n",ans);
    return 0;
}

T2 平面嵌入 planar

题意

平面上一堆点, 构成了一个网格, 其中某些格子的主对角线上有边(也就是固定了),
问是否存在一种点的位置分配方案, 使得存在一个格子的主对角线上的两个点的距离 $dis \not = \sqrt{2}$.

解法

一道神奇的题目...考场上想了好久, 什么都没想出来.....

首先, 如果一整列或一整行上面不存在固定了的格子, 那么这一行/列可以集体移动,

设存在一个固定了的格子(i,j), 若要移动第 i 行, 则第 j 列也要移动, 才能使这个格子不变形,

那我们对于每个固定了的格子(i,j), 都在 i,j 间连一条无向边, 若所有的行和列都在同一个联通块中, 则不存在一个合法的方案 (因为如果所有的行和列都移动了, 就相当于整个网格都移动了, 形状没有变化).

否则的话, 就随便找一个连通块, 把要移动的移动了就行了. (还要注意一下精度问题)

代码

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=1000+7;
const int M=250000+7;
int r,c,m;
db x[M],y[M],q2;
bool fd[M],mp[N][N],vis[N];
int main(){
//  freopen("planar.in","r",stdin);
//  freopen("planar.out","w",stdout);
    cin>>r>>c>>m; int t;
    for(int i=1;i<=m;i++){ scanf("%d",&t); fd[t]=1; }
    for(int i=1;i<r;i++)
        for(int j=1;j<c;j++)
            if(fd[(i-1)*c+j]){ mp[i+1][j+1+r]=mp[j+1+r][i+1]=1; }
    queue<int> q; int cnt=0;
    q.push(2); vis[2]=1;
    while(!q.empty()){
        int u=q.front(); q.pop(); cnt++;
        for(int v=1;v<=r+c;v++)
            if(mp[u][v]&&!vis[v]){ q.push(v); vis[v]=1; }
    }
    if(cnt==r+c-2){ puts("No"); return 0; }
    x[1]=y[1]=0; q2=1/sqrt(2);
    for(int i=1;i<=r;i++){
        int k=(i-1)*c+1;
        if(vis[i]){ x[k]=x[k-c]+q2; y[k]=y[k-c]+q2; }
        else if(i!=1){ x[k]=x[k-c]; y[k]=y[k-c]+1; }
        for(int j=2;j<=c;j++){
            int k=(i-1)*c+j;
            if(vis[j+r]){ x[k]=x[k-1]+q2; y[k]=y[k-1]-q2; }
            else{ x[k]=x[k-1]+1; y[k]=y[k-1]; }
        }
    }
    puts("Yes");
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            printf("%.8lf %.8lf\n",x[(i-1)*c+j],y[(i-1)*c+j]);  //这里如果按照默认的输出小数点后 6 位会过不了spj
    return 0;
}

T3 小球 ball

题意

有一棵树, 有若干次操作 (op,u),

若 op==1, 则在节点 u 放一个小球, 若 u 的子树中有空位, 小球会掉向 u 的子节点中, 子树中最小值最小的一个子节点, 并重复这个过程.
若op==2, 则删除节点 u 的球.

保证 op==1 时, u 上没有球, op==2 时, u 上有球.

思路

最后四十分钟, 题意都没看懂....................................................
题解的思路用到了kruskal重构树, 没太看懂, 但是做法应该都差不多.

结论 : 树上点的优先级等价于 用大根堆进行拓扑排序 得到的序列 的反序列.

我是这样理解的, 每次我们都要选择一个最小且未被覆盖的点, 然后再在它的子树中重复这个操作,
那么, 节点子树中的点的优先级大于根节点的优先级,
而对于没有附属关系的点, 数值小的点的优先级大于数值大的点优先级,
所以...拓扑排序 + 大根堆...

代码

#include<bits/stdc++.h>
using namespace std;
const int N=7e5+7;
const int L=20;
const int inf=0x3f3f3f3f;
int n,q,de[N],cnt,num[N],dfn[N],en[N],rec[N],f[N][L+7],p[4*N];
int lst[N],nxt[N],to[N],tot;
bool b[N];
priority_queue<int> h;
int gi(){
    char c=getchar(); int x=0,f=1;
    while(c<'0'||c>'9'){ f=c=='-'?-1:1; c=getchar(); }
    while(c>='0'&&c<='9'){ x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }
    return x*f;
}
void add(int x,int y){ nxt[++tot]=lst[x]; to[tot]=y; lst[x]=tot; }
void read(){
    n=gi(); q=gi();
    for(int i=2;i<=n;i++){
        f[i][0]=gi();
        add(f[i][0],i); de[i]++;
    }
}
void topo(){
    h.push(1); num[0]=-inf;
    while(!h.empty()){
        int u=h.top(); h.pop();
        num[u]=++cnt;
        for(int i=lst[u];i;i=nxt[i]){
            de[to[i]]--;
            if(!de[to[i]]) h.push(to[i]);
        }
    }
    cnt=0;
}
void pre(int u){
    dfn[u]=++cnt; rec[cnt]=u;
    for(int i=1;i<=L;i++) f[u][i]=f[f[u][i-1]][i-1];
    for(int i=lst[u];i;i=nxt[i]) pre(to[i]);
    en[u]=cnt;
}
void build(int k,int l,int r){
    if(l==r){ p[k]=rec[l]; ; return; }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    p[k]= num[p[k<<1]]>num[p[k<<1|1]] ?p[k<<1] :p[k<<1|1];
}
void modify(int k,int l,int r,int x,int t){
    if(l==r&&l==r){ p[k]=t; return; }
    int mid=(l+r)>>1;
    if(x<=mid) modify(k<<1,l,mid,x,t);
    else modify(k<<1|1,mid+1,r,x,t);
    p[k]= num[p[k<<1]]>num[p[k<<1|1]] ?p[k<<1] :p[k<<1|1];
}
int query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return p[k];
    int mid=(l+r)>>1,t1=0,t2=0;
    if(x<=mid) t1=query(k<<1,l,mid,x,y);
    if(y>mid) t2=query(k<<1|1,mid+1,r,x,y);
    return num[t1]>num[t2] ?t1 :t2;
}
int find(int x){
    for(int i=L;i>=0;i--)
        if(b[f[x][i]]) x=f[x][i];
    return x;
}
void run(){
    int op,x;
    for(int i=1;i<=q;i++){
        op=gi(); x=gi();
        if(op==1){
            int t=query(1,1,n,dfn[x],en[x]);
            printf("%d\n",t); b[t]=1;
            modify(1,1,n,dfn[t],0);
        }
        else{
            int t=find(x); b[t]=0;
            modify(1,1,n,dfn[t],t);
        }
    }
}
int main(){
//  freopen("ball.in","r",stdin);
//  freopen("ball.out","w",stdout);
    read();
    topo();
    pre(1);
    build(1,1,n);
    run();
    return 0;
}