2022 BUAA Winter Training 1赛后补题

2022 BUAA Winter Training 1

$A-InterestingSubarray\backslash Large\{A\backslash \; -\backslash \; Interesting\backslash \; Subarray\}$ $[CodeForces-1270B]\{\backslash scriptstyle\; [\backslash \; CodeForces\backslash \; -\backslash \; 1270B\backslash \; ]\}$

题意

给定一个数组，要找出一个子数组使得数组中最大值与最小值的差大于等于数组长度，并输出左右端点。

解法

我们把题目转化一下就是：求一对$(i,j)(i,j)$使得：$\mathrm{\mid }{a}_j-a_i\mathrm{\mid }\ge j-i+1|a\_j-a\_i|\backslash geq\; j-i+1$

首先单调递增或者递减且差值不超过$11$的子数组一定不可行对吧。

那么可以发现最简单的情况就是相邻两个数$a_i,a_{i+1}a\_i,a\_\{i+1\}$满足条件即可。

因为只有相邻两位的差值大于$22$时，最大最小值的差才会有可能满足条件。

所以直接比较相邻两位即可。

（所以当场写树状数组求逆序对的我是个憨憨。。。）

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 2000010
using namespace std;
int n,val[MAXN];
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]);
    for(int i=2;i<=n;i++){
        if(abs(val[i]-val[i-1])>=2){
            printf("YES\n%d %d\n",i-1,i);
            return;
        }
    }
    printf("NO\n");
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--)solve();
    return 0;
}

$\backslash text\{\; \}$

$B-CowandFriend\backslash Large\{B\backslash \; -\backslash \; Cow\backslash \; and\backslash \; Friend\}$ $[CodeForces-1307B]\{\backslash scriptstyle\; [\backslash \; CodeForces\backslash \; -\backslash \; 1307B\backslash \; ]\}$

题意

从原点跳到$(x,0)(x,0)$点，每次只能跳给定的整数长度，但可以到非整数坐标点，问最少要跳几次。

解法

如果有能一步到的最好对吧。

没有的话就从能跳的长度中找最长的跳：如果长度的大于$xx$，显然跳两次就够了；如果长度小于$xx$，那么把能跳的长度跳完，最后一定会有剩余，这个距离一定小于两倍的长度，故只需要最后两次跳长度成三角形就好，故最后剩余距离只会贡献一次跳跃。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m;
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
	return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
void solve(){
    int ans=2147483647;
    n=read();m=read();
    for(int i=1,x;i<=n;i++){
        x=read();
        if(x<=m){
            if(m%x==0)ans=min(ans,m/x);
            else ans=min(ans,m/x+1);
        }
        else ans=min(ans,2);
    }
    printf("%d\n",ans);
}
int main(){
    int t=read();
    while(t--)solve();
    return 0;
}

$\backslash text\{\; \}$

$C-Arpaandanexamaboutgeometry\backslash Large\{C\backslash \; -\backslash \; Arpa\backslash \; and\backslash \; an\backslash \; exam\backslash \; about\backslash \; geometry\}$ $[CodeForces-851B]\{\backslash scriptstyle\; [\backslash \; CodeForces\backslash \; -\backslash \; 851B\backslash \; ]\}$

题意

给三个点$A,B,CA,B,C$的坐标，让这三个点绕某一点旋转一定的角度，使得$AA$转到$BB$的位置，$BB$转到$CC$的位置，求是否存在这样的点和角度。

解法

存在性嘛，只要判断就好了。

显然三点共线的情况是不存在的。

三个点的叉积为$00$就能判断三点共线了。

然后这三个点就会成为一个三角形。

我们发现如果点和角度存在，那么一定有$\mathrm{\mid }AB\mathrm{\mid }=\mathrm{\mid }BC\mathrm{\mid }|AB|=|BC|$。

而外接圆保证三个点一定能在旋转的同时相对位置不变。

于是这个题就做完了。

记得开$longlonglong\backslash \; long$。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct point{
    long long x,y;
}a,b,c;
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
	return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
inline long long cross(const point p,const point q,const point r){
	return (p.x-r.x)*(q.y-r.y)-(q.x-r.x)*(p.y-r.y);
}
inline long long dist(const point p,const point q){
    return (p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y);
}
void solve(){
    a.x=read();a.y=read();b.x=read();b.y=read();c.x=read();c.y=read();
    if(cross(a,b,c)==0)printf("No\n");
    else{
        if(dist(a,b)!=dist(b,c))printf("No\n");
        else printf("Yes\n");
    }
}
int main(){
    solve();
    return 0;
}

$\backslash text\{\; \}$

$D-PathsinaCompleteBinaryTree\backslash Large\{D\backslash \; -\backslash \; Paths\backslash \; in\backslash \; a\backslash \; Complete\backslash \; Binary\backslash \; Tree\}$ $[CodeForces-792D]\{\backslash scriptstyle\; [\backslash \; CodeForces\backslash \; -\backslash \; 792D\backslash \; ]\}$

题意

有一颗完全二叉树，按照先序遍历依次给节点标上序号。有$qq$个询问，每次寻问给出当前的出发点和一个仅有$U,L,RU,L,R$三种字符的字符串，按照字符串的指令在树上移动，问最后会到哪个节点。无法移动的无效操作直接忽略。

解法

和正常的以$11$为根的树序号不太一样。

手玩样例就会发现，对于一个非叶子节点$xx$，其左儿子序号是$x-[lowbit(x)>>1]x-[lowbit(x)>>1]$，其右儿子是$x\mathrm{\mid }[lowbit(x)>>1]x|[lowbit(x)>>1]$，其父亲的序号是。

而叶子节点只有父亲，根节点无父亲，注意边界条件的判断即可。

记得开$longlonglong\backslash \; long$。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 100010
using namespace std;
long long n;
int q,len;
char str[MAXN];
inline long long read(){
    long long date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
inline long long lowbit(long long x){return x&(-x);}
void solve(){
    long long now;
    n=read();q=read();
    while(q--){
        now=read();scanf("%s",str+1);
        len=strlen(str+1);
        for(int i=1;i<=len;i++){
            if(str[i]=='U'){
                if((lowbit(now)<<1)<=n)now=(now-lowbit(now))|(lowbit(now)<<1);
            }
            else if(str[i]=='L')now-=(lowbit(now)>>1);
            else if(str[i]=='R'){
                if(now+(lowbit(now)>>1)<=n)now|=(lowbit(now)>>1);
            }
        }
        printf("%lld\n",now);
    }
}
int main(){
    solve();
    return 0;
}

$\backslash text\{\; \}$

$E-DashaandPuzzle\backslash Large\{E\backslash \; -\backslash \; Dasha\backslash \; and\backslash \; Puzzle\}$ $[CodeForces-761E]\{\backslash scriptstyle\; [\backslash \; CodeForces\backslash \; -\backslash \; 761E\backslash \; ]\}$

题意

有一棵树，要求在平面直角坐标系中绘出，并且所有的边都要平行于坐标轴，求是否可行，以及每个点的坐标。

解法

首先一个想法就是只要出现度大于$44$的点，这棵树就一定不能绘制。

然后因为只要找出可行解，所以我们不妨把边都设的很大，比如第一层边设为$2^{31}2^\{31\}$。

这样能保证边不相交。

之后就是暴力往四个方向搜索即可。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 40
using namespace std;
const long long fx[4]={0,0,1,-1},fy[4]={1,-1,0,0};
int n,c=1;
int degree[MAXN],head[MAXN];
struct Edge{
    int next,to;
}a[MAXN<<1];
struct Point{
    long long x,y;
}point[MAXN];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
	return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
inline void add(int x,int y){
    a[c].to=y;a[c].next=head[x];head[x]=c++;
    a[c].to=x;a[c].next=head[y];head[y]=c++;
}
void dfs(int rt,int fa,int f,long long step){
    for(int i=head[rt],j=0,will;i;i=a[i].next){
        will=a[i].to;
        if(will!=fa){
            while((j^1)==f)j++;
            point[will].x=point[rt].x+fx[j]*step;
            point[will].y=point[rt].y+fy[j]*step;
            dfs(will,rt,j,(step>>1));
            j++;
        }
    }
}
void solve(){
    memset(head,0,sizeof(head));
    memset(degree,0,sizeof(degree));
    n=read();
    for(int i=1,x,y;i<n;i++){
        x=read();y=read();
        add(x,y);
        degree[x]++;degree[y]++;
    }
    for(int i=1;i<=n;i++)if(degree[i]>4){
        printf("NO\n");
        return;
    }
    printf("YES\n");
    point[1].x=point[1].y=0;
    dfs(1,0,5,2147483648LL);
    for(int i=1;i<=n;i++)printf("%lld %lld\n",point[i].x,point[i].y);
}
int main(){
    freopen("solve.in","r",stdin);
    freopen("solve.out","w",stdout);
    solve();
    return 0;
}

$\backslash text\{\; \}$

$F-CalendarAmbiguity\backslash Large\{F\backslash \; -\backslash \; Calendar\backslash \; Ambiguity\}$ $[CodeForces-1389E]\{\backslash scriptstyle\; [\backslash \; CodeForces\backslash \; -\backslash \; 1389E\backslash \; ]\}$

题意

伊甸园的日历一个年有$mm$个月，每个月都有$dd$天，而伊甸园的一个星期是$ww$天。求出所有的数对$(x,y)(x,y)$，使得$xx$月$yy$日和$yy$月$xx$日是相同的星期几，即在一周中是相同的天。

解法

数学题。

不妨设，那么很容易求出这两个日期之间的相差的天数是$(d-1)(y-x)(d-1)(y-x)$。

而要满足题目的条件，就是要满足$(d-1)(y-x)\mathrm{m}\mathrm{o}\mathrm{d}w==0(d-1)(y-x)\backslash mod\; w==0$。

转换一下：$y-x=k\times \frac{w}{d-1},(d-1)\mathrm{\mid }k,k\in \mathbb{Z}y-x=k\backslash times\backslash frac\{w\}\{d-1\},(d-1)|k,k\backslash in\; \backslash mathbb\{Z\}$。

也就是说$x,yx,y$之间相差的一定是整数，也一定是$\frac{w}{d-1}\backslash frac\{w\}\{d-1\}$的整数倍。

所以只要$xx$确定了，$yy$就一定是从一些满足条件的数中任意取。

令$n=\min (m,d),t=\frac{w}{gcd(w,d-1)}n=\backslash min(m,d),t=\backslash frac\{w\}\{gcd(w,d-1)\}$，那么$x,yx,y$的取值就是从$\frac{n}{t}\backslash frac\{n\}\{t\}$个块中取，最后会剩余一部分数，分开处理就好。

而任意取两个数的结果就是$C_n^{2}C\_n^2$。

于是这个题就做完了。

记得开$longlonglong\backslash \; long$。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
long long m,d,w,n,q,ans=0;
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
	return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
long long gcd(long long x,long long y){return !y?x:gcd(y,x%y);}
void solve(){
    ans=0;
    m=read();d=read();w=read();
    w/=gcd(w,d-1);
    n=min(m,d);
    q=n/w;
    if(n%w){
        ans=(n%w)*(q+1)*q/2+(w-n%w)*q*(q-1)/2;
    }
    else{
        ans=w*q*(q-1)/2;
    }
    printf("%lld\n",ans);
}
int main(){
    int t=read();
    while(t--)solve();
    return 0;
}

$\backslash text\{\; \}$

$G-EraseSubsequences\backslash Large\{G\backslash \; -\backslash \; Erase\backslash \; Subsequences\}$ $[CodeForces-1303E]\{\backslash scriptstyle\; [\backslash \; CodeForces\backslash \; -\backslash \; 1303E\backslash \; ]\}$

题意

给定两个字符串$s,ts,t$，从$ss$中最多提取出两个完全不同的子序列，首尾拼接后能拼出字符串$tt$，求是否存在可行方案。

解法

首先枚举$tt$的断点没话说。

现在有$t_1,t_{2}t\_1,t\_2$两个字符串，需要从$ss$中提取子序列以匹配。

设$dp[i][j]dp[i][j]$表示$ss$的前$ii$个字符中，$t_{1}t\_1$已经匹配了$jj$个，此时$t_{2}t\_2$能匹配的最大长度。

状态转移方程就长这个样：

注意边界问题，什么$dp[0][0]=0dp[0][0]=0$，枚举$jj$要满足$0\le j\le i0\backslash leq\; j\backslash leq\; i$，之类的。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 410
using namespace std;
int len,lengths,dp[MAXN][MAXN];
char str[MAXN],strings[MAXN];
void solve(){
    scanf("%s%s",str+1,strings+1);
    len=strlen(str+1);lengths=strlen(strings+1);
    for(int k=1;k<=lengths;k++){
        dp[0][0]=0;
        for(int i=1;i<=len;i++)for(int j=0;j<=k&&j<=i;j++){
            dp[i][j]=dp[i-1][j];
            if(j&&str[i]==strings[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
            if(dp[i-1][j]>=0&&str[i]==strings[k+dp[i-1][j]+1])dp[i][j]=max(dp[i][j],dp[i-1][j]+1);
        }
        if(dp[len][k]==lengths-k){
            printf("YES\n");
            return;
        }
        for(int i=1;i<=len;i++)for(int j=0;j<=k;j++)dp[i][j]=-1;
    }
    printf("NO\n");
}
int main(){
    int t;
    scanf("%d",&t);
    memset(dp,-1,sizeof(dp));
    while(t--)solve();
    return 0;
}

$\backslash text\{\; \}$

$H-ChessStrikesBack\backslash Large\{H\backslash \; -\backslash \; Chess\backslash \; Strikes\backslash \; Back\}$ $[CodeForces-1379F2]\{\backslash scriptstyle\; [\backslash \; CodeForces\backslash \; -\backslash \; 1379F2\backslash \; ]\}$

题意

有一个$2n\times 2m2n\backslash times\; 2m$的国际象棋棋盘，要在上面的白色格子中放$n\times mn\backslash times\; m$个国王，使得任意两个国王之间不能互相攻击，国王的攻击范围是以自身为中心的九宫格。给出$qq$次操作，每次将棋盘上某个白色格子设置为不能放国王。每次操作完成，求是否还有放置国王的可行解。

解法

我们会发现对于一个已经放了国王的白色格子，如果状态改变，那么一定是将国王移动到相邻的白色格子中。

所以我们可以将棋盘以$2\times 22\backslash times\; 2$的小格划分，这里选取左上和右下是白色格子的分法。

我们发现如果一个小格的左上角放置了国王，那么其左侧、上方以及左上方的所有小格都得是左上角放置国王。

同理对于右下角放置国王的小格，其右侧、下方以及右下方的所有小格都得是右下角放置国王。

如果两个角都能放置，自然就不用管这个小格对吧。

如果两个点都不能放置，自然答案就是"NO"对吧。

对于有限制的点，我们将限制左上角不能放置的点记为$LeftLeft$点，限制右下角不能放置的点记为$RightRight$点。

于是判断棋盘放置不合法的充要条件就是：存在一个$RightRight$点在一个$LeftLeft$点的右下方。

在这种情况下，两个点中间部分的矩形棋盘，其放置国王的方案是唯一的，但凡限制了其中一个点都是不合法的。

所以要维护每行的最左端的$LeftLeft$点和最右端的$RightRight$点，直接开两个$setset$即可。

然后对行开线段树维护最值和不合法情况判断标记。

记得合并小格的时候坐标除二之前要加一，不然会得出$00$的小格下标。

至于怎么记录坐标是否被限制就丢给了$mapmap$。（才不是不想写乱七八糟的玩意呢）

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#define LSON rt<<1
#define RSON rt<<1|1
#define MAX(rt) segment_tree[rt].maxn
#define MIN(rt) segment_tree[rt].minn
#define FLAG(rt) segment_tree[rt].flag
#define LSIDE(rt) segment_tree[rt].l
#define RSIDE(rt) segment_tree[rt].r
#define MAXN  200010
using namespace std;
int n,m,q;
set<int> leftset[MAXN],rightset[MAXN];
map<pair<int,int>,bool> limited;
struct Segment_Tree{
    int maxn,minn,l,r;
    bool flag;
}segment_tree[MAXN<<2];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
	return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
void pushup(int rt){
    MAX(rt)=max(MAX(LSON),MAX(RSON));
    MIN(rt)=min(MIN(LSON),MIN(RSON));
    FLAG(rt)=FLAG(LSON)|FLAG(RSON)|(MAX(RSON)>=MIN(LSON));
}
void buildtree(int l,int r,int rt){
    LSIDE(rt)=l;RSIDE(rt)=r;
    MAX(rt)=0;MIN(rt)=m+1;FLAG(rt)=false;
    if(l==r)return;
    int mid=l+r>>1;
    buildtree(l,mid,LSON);
    buildtree(mid+1,r,RSON);
}
void update(int pos,int rt){
    if(LSIDE(rt)==pos&&pos==RSIDE(rt)){
        MAX(rt)=rightset[pos].size()?*rightset[pos].rbegin():0;
        MIN(rt)=leftset[pos].size()?*leftset[pos].begin():m+1;
        FLAG(rt)=(MAX(rt)>=MIN(rt));
        return;
    }
    int mid=LSIDE(rt)+RSIDE(rt)>>1;
    if(pos<=mid)update(pos,LSON);
    else update(pos,RSON);
    pushup(rt);
}
void work(){
    int x,y;
    while(q--){
        x=read()+1;y=read()+1;
        if(limited[pair<int,int>(x,y)]){
            if(y&1)rightset[x>>1].erase(y>>1);
            else leftset[x>>1].erase(y>>1);
        }
        else{
            if(y&1)rightset[x>>1].insert(y>>1);
            else leftset[x>>1].insert(y>>1);
        }
        limited[pair<int,int>(x,y)]^=1;
        update(x>>1,1);
        printf(FLAG(1)?"NO\n":"YES\n");
    }
}
void init(){
    n=read();m=read();q=read();
    buildtree(1,n,1);
}
int main(){
    init();
    work();
    return 0;
}