@xiaoziyao 2021-07-09T20:26:00.000000Z 字数 6687 阅读 913

Codeforces Round 685考试总结

考试总结

Codeforces Round #359 (Div. 1)考试总结：

2021年7月9日进行vp，DE两题，rk24，倒序开题nb。

CF685A Robbers' watch

题意：给定 $n,m$ ，求 $0\leqslant a<n$ 且 $0\leqslant b<m$ 且 $7$ 进制下没有相同数字的的数对 $(a,b)$ 数量。（ $1\leqslant n,m\leqslant 10^9$ ）

分析：诈骗题，一开始被诈骗了，想法非常诡异。

显然 $a,b$ 的数位长度和不超过 $7$ ，所以只需要考虑数位长度之和小于等于 $7$ 的情况，此时枚举数对 $(a,b)$ 的复杂度是可以接受的。

代码：

#include<stdio.h>
int n,m,lenx,leny,ans;
int cnt[10];
inline int max(int a,int b){
    return a>b? a:b;
}
int main(){
    scanf("%d%d",&n,&m),n--,m--;
    for(int i=n;i;i/=7,lenx++);
    for(int i=m;i;i/=7,leny++);
    lenx=max(lenx,1),leny=max(leny,1);
    if(lenx+leny>7){
        puts("0");
        return 0;
    }
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++){
            for(int k=0;k<=6;k++)
                cnt[k]=0;
            for(int k=1,p=i;k<=lenx;k++,p/=7)
                cnt[p%7]++;
            for(int k=1,p=j;k<=leny;k++,p/=7)
                cnt[p%7]++;
            int flg=1;
            for(int k=0;k<=6;k++)
                if(cnt[k]>1)
                    flg=0;
            ans+=flg;
        }
    printf("%d\n",ans);
    return 0;
}

CF685B Kay and Snowflake

题意：给定一棵 $n$ 个点的树，求每一棵树的子树重心。（ $1\leqslant n\leqslant3\times 10^5$ ）

分析：就是P5666 [CSP-S2019] 树的重心的做法，每个点的子树重心直接用重儿子的子树重心暴力跳就好了，复杂度是 $O(n)$ 。

代码：

#include<stdio.h>
const int maxn=300005;
int n,m,e;
int ans[maxn],start[maxn],to[maxn],then[maxn],size[maxn],iptson[maxn],fa[maxn];
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
void dfs(int x,int last){
    fa[x]=last,size[x]=1,iptson[x]=-1;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        dfs(y,x),size[x]+=size[y];
        if(iptson[x]==-1||size[iptson[x]]<size[y])
            iptson[x]=y;
    }
    if(iptson[x]!=-1){
        ans[x]=ans[iptson[x]];
        while(size[x]-size[ans[x]]>size[x]/2)
            ans[x]=fa[ans[x]];
    }
    else ans[x]=x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++){
        int x;
        scanf("%d",&x);
        add(x,i);
    }
    dfs(1,0);
    for(int i=1;i<=m;i++){
        int x;
        scanf("%d",&x);
        printf("%d\n",ans[x]);
    }
    return 0;
}

CF685C Optimal Point

更好的阅读体验

题意：给定 $n$ 个立体三维坐标系的整点（坐标范围 $[-10^{18},10^{18}]$ ），求一个点使得其与所有点的曼哈顿距离最大值最小。（ $1\leqslant n\leqslant 10^5$ ）

分析：

又优美又胖的题。

首先求最大值最小就可以知道要二分这个距离最大值。

考虑怎么 check 这个距离 $mid$ ，发现这等价于解这个方程组的解（其中 $x_0,y_0,z_0$ 为未知数）：

$\begin{cases}|x_1-x_0|+|y_1-y_0|+|z_1-z_0|\leqslant mid\\|x_2-x_0|+|y_2-y_0|+|z_2-z_0|\leqslant mid\\\cdots\\|x_n-x_0|+|y_n-y_0|+|z_n-z_0|\leqslant mid\end{cases}$

发现这个绝对值很难拆，但不难发现 $\max\{a-b,b-a\}=|a-b|$ ，所以每个不等式可以等价为：

$\begin{cases}x_i-x_0+y_i-y_0+z_i-z_0\leqslant mid\\x_0-x_i+y_i-y_0+z_i-z_0\leqslant mid\\x_i-x_0+y_0-y_i+z_i-z_0\leqslant mid\\x_0-x_i+y_0-y_i+z_i-z_0\leqslant mid\\x_i-x_0+y_i-y_0+z_0-z_i\leqslant mid\\x_0-x_i+y_i-y_0+z_0-z_i\leqslant mid\\x_i-x_0+y_0-y_i+z_0-z_i\leqslant mid\\x_0-x_i+y_0-y_i+z_0-z_i\leqslant mid\end{cases}$

然后不难发现这个不等式可以化作：

$\begin{cases}x_i+y_i+z_i-mid\leqslant x_0+y_0+z_0\leqslant x_i+y_i+z_i+mid\\-x_i+y_i+z_i-mid\leqslant -x_0+y_0+z_0\leqslant -x_i+y_i+z_i+mid\\x_i-y_i+z_i-mid\leqslant x_0-y_0+z_0\leqslant x_i-y_i+z_i+mid\\x_i+y_i-z_i-mid\leqslant x_0+y_0-z_0\leqslant x_i+y_i-z_i+mid\end{cases}$

设 $al,bl,cl,dl$ 为前四个式子的最大值， $ar,br,cr,dr$ 为后四个式子的最小值，， $a=-x_0+y_0+z_0,b=x_0-y_0+z_0,c=x_0+y_0-z_0$ ，那么等价于：

$\begin{cases}al\leqslant a+b+c\leqslant ar\\bl\leqslant a\leqslant br\\cl\leqslant b\leqslant cr\\dl\leqslant c\leqslant dr\end{cases}$

由于 $x_0=\frac{b+c}{2},y_0=\frac{a+c}{2},z_0=\frac{a+b}{2}$ ，它们都是整数，所以 $a\equiv b\equiv c\pmod 2$ 。

此时套路地枚举 $a,b,c$ 的最后一个二进制位 $t\in\{0,1\}$ ，那么模 $2$ 相同的限制就没了，最后不难用调整法算出一个答案。

时间复杂度： $O(n\log v)$ 。

代码：

#include<stdio.h>
#include<iostream>
#define inf 6000000000000000000
using namespace std;
const int maxn=100005;
int T,n;
long long ansx,ansy,ansz;
long long x[maxn],y[maxn],z[maxn];
inline long long ceil(long long x){
    return x>=0? (x+1)/2ll:-((-x)/2ll);
}
inline long long floor(long long x){
    return x>=0? x/2ll:-((-x+1)/2ll);
}
int check(long long mid){
    long long al=-inf,bl=-inf,cl=-inf,dl=-inf,ar=inf,br=inf,cr=inf,dr=inf;
    //al<=a+b+c<=ar,bl<=a<=br,cl<=b<=cr,dl<=c<=dr
    for(int i=1;i<=n;i++){
        al=max(al,x[i]+y[i]+z[i]-mid),ar=min(ar,x[i]+y[i]+z[i]+mid);
        bl=max(bl,-x[i]+y[i]+z[i]-mid),br=min(br,-x[i]+y[i]+z[i]+mid);
        cl=max(cl,x[i]-y[i]+z[i]-mid),cr=min(cr,x[i]-y[i]+z[i]+mid);
        dl=max(dl,x[i]+y[i]-z[i]-mid),dr=min(dr,x[i]+y[i]-z[i]+mid);
    }
    for(int t=0;t<=1;t++){
        long long wl=ceil(al-3*t),wr=floor(ar-3*t);
        long long xl=ceil(bl-t),xr=floor(br-t);
        long long yl=ceil(cl-t),yr=floor(cr-t);
        long long zl=ceil(dl-t),zr=floor(dr-t);
        if(wl<=wr&&xl<=xr&&yl<=yr&&zl<=zr&&xl+yl+zl<=wr&&xr+yr+zr>=wl){
            long long x=xl,y=yl,z=zl,up=max(0ll,wl-xl-yl-zl);
            x+=min(up,xr-xl),up-=min(up,xr-xl);
            y+=min(up,yr-yl),up-=min(up,yr-yl);
            z+=min(up,zr-zl),up-=min(up,zr-zl);
            x=((x<<1)|t),y=((y<<1)|t),z=((z<<1)|t);
            ansx=(y+z)>>1,ansy=(x+z)>>1,ansz=(x+y)>>1;
            return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
        long long L=-1,R=inf+1;
        while(L+1<R){
            long long mid=L+(R-L)/2ll;
            if(check(mid))
                R=mid;
            else L=mid;
        }
        check(R);
        printf("%lld %lld %lld\n",ansx,ansy,ansz);
    }
    return 0;
}

CF685D Kay and Eternity

更好的阅读体验

题意：网格中有 $n$ 个格子被涂黑，对于 $x\in[1,n]$ ，求大小为 $k\times k$ 且能覆盖 $x$ 个黑色格子的正方形数量。（ $1\leqslant n\leqslant 10^5,1\leqslant k\leqslant 300$ ，值域范围 $[-10^9,10^{9}]$ ）

分析：

考虑答案的范围是很广的，显然不能枚举每个答案并检验其覆盖黑色格子数量。

正难则反，我们发现每个黑色格子 $(x,y)$ 被覆盖当且仅当正方形的右下角在 $([x,x+k-1],[y,y+k-1])$ 范围内，也就是在一个以 $(x,y)$ 为左上角，边长为 $k$ 的正方形内。

问题被转化成对于 $x\in[1,n]$ ，求有多少个整点被 $x$ 个矩形覆盖，这是经典问题，扫描线的同时暴力统计一下就好了，复杂度 $O(nk)$ 。

代码：

扫描线注意细节。

#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=100005;
int n,k,tot;
int cnt[maxn<<1],num[maxn<<1],val[maxn<<1];
long long ans[maxn];
map<int,int>mp;
struct line{
    int x,ya,yb,opt;
}l[maxn<<1];
inline int cmp(line a,line b){
    return a.x<b.x;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        l[2*i-1]=line{a,b,b+k-1,1},l[2*i]=line{a+k,b,b+k-1,-1};
        num[2*i-1]=b,num[2*i]=b+k;
    }
    sort(num+1,num+1+2*n),sort(l+1,l+1+2*n,cmp);
    for(int i=1;i<=2*n;i++)
        if(i==1||num[i]!=num[i-1])
            mp[num[i]]=++tot,val[tot]=num[i];
    for(int i=1;i<=2*n;i++){
        int ya=mp[l[i].ya],yb=mp[l[i].yb+1],opt=l[i].opt,len=l[2*n].x-l[i].x;
        for(int j=ya;j<yb;j++){
            ans[cnt[j]]-=1ll*len*(val[j+1]-val[j]);
            cnt[j]+=opt;
            ans[cnt[j]]+=1ll*len*(val[j+1]-val[j]);
        }
    }
    for(int i=1;i<=n;i++)
        printf("%lld%c",ans[i],i==n? '\n':' ');
    return 0;
}

CF685E Travelling Through the Snow Queen's Kingdom

更好的阅读体验

题意：给定 $n$ 个点 $m$ 条边的无向图，第 $i$ 条边能且仅能在 $i$ 时刻经过，经过每一条边需要 $1$ 的时间， $q$ 次询问 $l$ 时刻在 $s$ 结点出发，能否在 $r$ 时刻前到达结点 $t$ 。（ $2\leqslant n\leqslant 1000,1\leqslant m,q\leqslant 2\times 10^5$ ）

分析：

这种区间限制一看就要离线搞，考虑把每个询问挂在某个时间点上扫一遍，维护一个限制之后再用 dp 求出最值看看能不能满足另一个限制。

具体的，我们发现 $O(n^2)$ 的空间复杂度和 $O(nm)$ 的时间复杂度都可以接受，所以考虑设 $dis_{a,b}$ 表示在当前的图内 $a$ 到达 $b$ 的最小时间点，然后每次加边时维护 $dis$ 。

将边按编号从大到小加入，每次类似 Floyd 地更新 $dis_{a,b}$ ，不难发现每次这样加入一定可以满足走完编号小的才能走编号大的边。

最后询问挂在 $l$ 上，然后直接查一下就可以了。

时间复杂度： $O(nm+q)$ 。

代码：

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
const int maxn=1005,maxm=200005,maxq=200005;
int n,m,q;
int x[maxm],y[maxm],R[maxq],S[maxq],T[maxq],ans[maxq],dis[maxn][maxn];
vector<int>v[maxm];
int main(){
    memset(dis,0x3f,sizeof(dis));
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=q;i++){
        int l;
        scanf("%d%d%d%d",&l,&R[i],&S[i],&T[i]);
        v[l].push_back(i);
    }
    for(int i=m;i>=1;i--){
        dis[x[i]][y[i]]=dis[y[i]][x[i]]=i;
        for(int j=1;j<=n;j++){
            dis[x[i]][j]=min(dis[x[i]][j],dis[y[i]][j]);
            dis[y[i]][j]=min(dis[y[i]][j],dis[x[i]][j]);
        }
        for(int j=0;j<v[i].size();j++){
            int k=v[i][j];
            ans[k]=(dis[S[k]][T[k]]<=R[k]);
        }
    }
    for(int i=1;i<=q;i++)
        puts(ans[i]==0? "No":"Yes");
    return 0;
}

Codeforces Round 685考试总结

CF685A Robbers' watch

CF685B Kay and Snowflake

CF685C Optimal Point

CF685D Kay and Eternity

CF685E Travelling Through the Snow Queen's Kingdom

内容目录