Codeforces Round #620 (Div. 2) 题解

Before Read

Solve 4 of 7
Rank:1120
Rating Change:+29 1735 → 1764
Contest Link

A. Two Rabbits

Describe


两只可爱的兔子分别从$x,y$出发,相向而行,其中,左边的兔子一次跳$a$个单位,右边的兔子一次跳$b$个单位,数据保证$x<y$。
现有$t(0 \leq t\leq 1000)$组,保证$(0\leq x< y \leq {10}^9 ,1\leq a ,b\leq {10}^9)$。
问每组兔子是否能相遇(都跳$ans$次使其在同一点),若可以输出$ans$否则输出$-1$。

Solution

Codeforces的A题一般都是比较简单的qwq
这就是大名鼎鼎的小学相遇问题。
那么直接路程差除以速度和是否是整数即可。

Code

(请忽略窝比赛时随手定义的变量名qwq)

int T,x,y,a,b;
signed main(){
    T=I.read();
    while(T--){
        x=I.read();y=I.read();a=I.read();b=I.read();
        int sb=y-x,nc=b+a;
        if(sb%nc==0){
            I.write(sb/nc);putchar('\n');
        } else{
            puts("-1");
        }
    }
}

B. Longest Palindrome

Describe

有$n(1\leq n\leq 100)$个字符串,每个字符串长度均为$m(1\leq m \leq 50)$,你可以选取其中的几个字符串,任意顺序组合,使其为一个回文字符串,输出最长的字符串长度与这个字符串。

Solution

由于所有字符串的长度均为$m$,所以要将两两互相回文的字符串组合即可,比如说样例1(这个bat蝙蝠是不是预示着什么…)

tab
one
bat

我们可以$O(N^2 \times M)$的求出两个字符串是否互相回文,比如说$\texttt{tab}$与$\texttt{bat}$互相回文。
那么我们可以将其组合起来。
设我们已经组合出来了$s_i,t_i$是互相回文的,那么答案就是$s_1,s_2,s_3…s_k,t_k,t_{k-1},t_{k-2}…t_1$。
当然这种方法是不完美的。
比如说这个数据:

tab
xxx
bat

那么显然$xxx$可以放在中间。
所以我们在最后特判一下即可。

int n,m,dp[110][110],vis[110],ans;//dp[i][j]表示i与j两个字符串是否互相回文,vis[i]表示i是否使用
char a[110][60],stk[110],sbk[110],cnt;//stk,sbk均为输出使用
int kkk[110],tot;//kkk表示可以放在中间的串
signed main(){
    n=I.read();m=I.read();
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int ff=0;
            for(int k=0;k<m;k++){
                if(a[i][k]==a[j][m-k-1]){
                    //ff=0;
                }else ff=1;
            }
            dp[i][j]=(ff==0);
        }
    }
    for(int i=1;i<=n;i++){
        int ff=0;
        for(int j=0;j<m/2;j++){
            if(a[i][j]==a[i][m-j-1]) ;
            else ff=1;
        }
        if(ff==0){
            ++tot;
            kkk[tot]=i;
        }
    }
//  cout<<tot<<endl;
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            for(int j=i+1;j<=n;j++){
                if(vis[j]==0&&dp[i][j]==1){
                    vis[i]=vis[j]=1;
                    ans+=2;
                    stk[++cnt]=i;
                    sbk[cnt]=j;
                    break;
                }
            }
        }
    }
    int sss=-1;
    for(int i=1;i<=tot;i++){
        if(vis[kkk[i]]==0){
            sss=kkk[i];
            ans++;
            break ;
        }
    }
    ans*=m;//别忘记乘上长度
    I.write(ans);putchar('\n');
    for(int i=1;i<=cnt;i++){
        for(int j=0;j<m;j++){
            cout<<a[stk[i]][j];
        }
    }
    if(sss==-1 ) ;
    else{
        for(int i=0;i<m;i++) {
            cout<<a[sss][i];
        }
    }
    for(int i=cnt;i>=1;i--){
        for(int j=0;j<m;j++){
            cout<<a[sbk[i]][j];
        }
    }
    cout<<endl;
}

C. Air Conditioner

Describe

餐厅里有个空调,在任意一个时刻,空调可以关(温度不变),加热(温度$+1$),降温(温度$-1$)。
给出$n(1\leq n\leq 100)$个限制,在$t(1\leq t\leq {10}^9)$时,温度要在$[l,r](-{10}^9 \leq l \leq r \leq {10}^9)$区间之内。
一开始时间为$0$,温度为$m(-{10}^9\leq m \leq {10}^9)$,问能否满足全部限制。
总共$q(1\leq q\leq 500)$组数据。

Solution

显然可以用区间乱搞。
设$L,R$表示当前可以到达的温度区间。
一开始$L=R=m$。
那么在接下来的时间可以到达$[L-(t_i-t_{i-1}),R-(t_i-t_{i-1})]$内任意一个温度,只要判断是否与$[l_i,r_i]$有相交即可。别忘记最后要更新区间呦~

Code

int q,n,m,dp[110],nowt,L,R;
struct node{
    int t,l,r;
}a[110];
inline int cmp(node x,node y){
    return x.t<y.t;
}
signed main(){
    q=I.read();
    while(q--){
        n=I.read();m=I.read();
        for(int i=1;i<=n;i++){
            a[i].t=I.read(),a[i].l=I.read(),a[i].r=I.read();
        }
        sort(a+1,a+n+1,cmp);//先按照时间从小到大排序
        re int now=m;nowt=0;L=m;R=m;
        int ff=1;
        for(int i=1;i<=n;i++){
            L-=a[i].t-nowt;
            R+=a[i].t-nowt;//可行范围
            nowt=a[i].t;
            if(a[i].l<=R||L<=a[i].r) ;//有相交
            else{
                ff=0;
                break ;
            }
            L=max(L,a[i].l);R=min(R,a[i].r);//更新区间
            if(L>R){
                ff=0;
                break ;
            }
        }
        if(ff==0){
            puts("NO");
        }else{
            puts("YES");
        }
    }
}

D. Shortest and Longest LIS

Describe

给出一个由$<$和$>$组成的序列,第$i$个表示$a_i$和$a_{i+1}$的大小关系,求出两个满足这个条件的序列,其中一个$LIS$最长,一个$LIS$最短,多组询问,询问的序列长度和不超过$2\times {10}^5$。
P.S:LIS是最长不下降子序列长度

Solution

构造题。
最长构造:


最短构造:

那么构造就好了

Code

int T,n,m,now;
char a[200010];
signed main(){
    T=I.read();
    while(T--){
        n=I.read();
        cin>>a+1;m=n;
        for(int j,i=1;i<=n;i=j+1){
            j=i;
            while(j<n&&a[j]=='<') ++j;
            m-=j-i+1;
            for(int k=m+1;k<=m+j-i+1;k++) I.write(k),putchar(' ');
        }
        putchar('\n');
        m=n;now=1;
        for(int j,i=1;i<=n;i=j+1){
            j=i;
            while(j<n&&a[j]=='<') ++j;
            for(int k=i;k<j;k++) I.write(now),putchar(' '),now++;
            I.write(m);putchar(' ');
            m--;
        }
        putchar('\n');
    }
}

E. 1-Trees and Queries

Describe

给定树,$q$此询问如果加入边$(a,b)$,$x$到$y$是否有长度为$k$的路径(不一定是简单路径)。

Solution

先$LCA$预处理,$logN$求任意两点间距离。
那么加入$(a,b)$边,$x$到$y$的路径只有$3$种情况:
– x–> y
– x–>a–>b–>y
– x–>b–>a–>y
所以乱搞就好了(注意可以走重复点所以直接%2即可)。

Code

int n,m,s;
int Dep[MAXN],f[MAXN][25];
int fir[MAXN],nxt[MAXN*2],son[MAXN*2],tot;
void add(int x,int y){
    ++tot;
    nxt[tot]=fir[x];
    fir[x]=tot;
    son[tot]=y;
}
void init(int u,int fa){
    Dep[u]=Dep[fa]+1;
    for(int i=0;i<=21;i++){
        f[u][i+1]=f[f[u][i]][i];
    }
    for(int i=fir[u];i;i=nxt[i]){
        int to=son[i];
        if(to==fa) continue ;
        f[to][0]=u;
        init(to,u);
    }
}
int lca(int x,int y){
    if(Dep[x]<Dep[y]) swap(x,y);
    for(int i=22;i>=0;i--){
        if(Dep[f[x][i]]>=Dep[y]) x=f[x][i];
        if(x==y) return x;
    }
    for(int i=22;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int dist(int x,int y){
    return Dep[x]+Dep[y]-2*Dep[lca(x,y)];
}
int main(){
    n=I.read();s=1;
    for(int i=1;i<=n-1;i++){
        int x=I.read(),y=I.read();
        add(x,y);add(y,x);
    }
    init(s,0);
    m=I.read();
    for(int x,y,a,b,k,i=1;i<=m;i++){
        x=I.read(),y=I.read(),a=I.read(),b=I.read(),k=I.read();
        swap(x,a);
        swap(y,b);
        int ans=dist(x,y);
        int ff=0;
        if(ans<=k&&(k-ans)%2==0) ff=1;
        ans=dist(x,a)+dist(b,y)+1;
        if(ans<=k&&(k-ans)%2==0) ff=1;
        ans=dist(x,b)+dist(a,y)+1;
        if(ans<=k&&(k-ans)%2==0) ff=1;
        if(ff==1) puts("YES");
        else puts("NO");
    }
    return 0;
}

F. Animal Observation

太难了不会qwq
挂个题解链接:戳这里

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇