Codeforces Round #605 (Div. 3) 比赛总结

比赛情况

2h才刀了A,B,C,D。E题的套路做的少，不过ygt大佬给我讲完思路后赛后2min就AC了这题。

比赛总结

比赛时不用担心“时间短，要做多快”，这样会匆匆忙忙，反而会做得慢。比赛时应该要不紧不慢，理性思考，内心平静，题目反而会迎刃而解。
这次比赛又看错了题（B,D）。

解决办法：这次比赛看错题是因为不够细心，不够细心是因为急躁，怕做不完。所以沉稳冷静的分析，反而能更好地完成比赛。

那么就开始上题解吧！

A

cf常出的分类讨论题（~~OI好像不考？~~）。

如果三个人的位置互不相同，我们希望最左和最右的两个人尽量靠近，中间这个人走不走没有影响。
如果有两个人位置相同，问题就转化为两个人的情况，我们希望这“两个人”尽量靠近。

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
int a[4];
void work() {
    a[1] = read(), a[2] = read(), a[3] = read();
    sort(a+1, a+1+3);
    if(a[1]==a[2]) {
        if(a[1]<a[3]) ++a[1], ++a[2];
        if(a[1]<a[3]) --a[3];
    } else if(a[2]==a[3]) {
        if(a[1]<a[3]) ++a[1];
        if(a[1]<a[3]) --a[2], --a[3];
    } else {
        if(a[1]<a[3]) ++a[1];
        if(a[3]>a[1]) --a[3];
    }
    printf("%d\n",abs(a[1]-a[2])+abs(a[1]-a[3])+abs(a[2]-a[3]));
}
int main()
{
    int q = read();
    while(q--) work();
    return 0;
}

B

cf常出的构造题（~~OI里面好像不考？~~）。

构造一个矩形。（‘L’这种指这个字符的数量）min(‘L’，‘R’)决定矩形的长，min(‘U’，‘D’)决定矩形的宽（不是严格的长和宽）。细节部分需要处理一下。

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
int a[5];
void work() {
    memset(a, 0, sizeof(a));
    string s; cin>>s;
    int len = s.length()-1;
    for(int i=0;i<=len;++i) {
        if(s[i] == 'L') a[1]++;
        if(s[i] == 'R') a[2]++;
        if(s[i] == 'U') a[3]++;
        if(s[i] == 'D') a[4]++;
    }
    int A = min(a[1],a[2]), B = min(a[3],a[4]);
    if(A==0 && B==0) puts("0");
    else {
        if(A==0) B = 1; if(B==0) A = 1;
        printf("%d\n",(A+B)*2);
        for(int i=1;i<=A;++i) cout<<"L";
        for(int i=1;i<=B;++i) cout<<"U";
        for(int i=1;i<=A;++i) cout<<"R";
        for(int i=1;i<=B;++i) cout<<"D";
    }
    cout<<endl;
}
int main()
{
    //freopen("test.out","w",stdout);
    int q = read();
    while(q--) work();
    return 0;
}

C

双指针计数题，~~OI里面考吧？~~

（不要问我为什么考场上5min就切了这题，因为~~CometOJ的模拟赛里出了类似的题目我写了个dp错了，惨痛的教训~~）

双指针如果找到一个合法区间 $（l，r）$ 就用等差数列求和计算这个区间的贡献 $\frac{(len+1)*len}{2} (len=r-l+1)$

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int MAXN = 2e5+7;
int n,K,ans;
bool ok[MAXN];
char s[MAXN];
int calc(int x) {
    return (x+1)*x/2;
}
signed main()
{
    n = read(), K = read();
    scanf("%s",s+1);
    for(int i=1;i<=K;++i) {
        char c; cin>>c;
        ok[c] = 1;
    }
    int l = 1, r = 1;
    while(r <= n) {
        while(ok[s[r]] && r<=n) ++r;
        ans += calc(r-l);
        l = r + 1, r = l;
    }
    printf("%lld\n",ans);
    return 0;
}

D

简单dp （~~怕CSP是不会考~~）。

设 $f[i,0/1]$ 表示 $0=> [1-i]$ 且以 i 结尾的最长上升子串， $1=> [i-n]$ 且以 i 开头的最长上升子串。

枚举断点 $Ans = max(Ans,f[i-1,0] + f[i+1,1])$

当然也可以不断点， $Ans$ 就是不断点里面最大的这个。看一下哪个 $Ans$ 最大。

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 2e5+7;
int n,ans;
int a[N];
int f[N][2];
int main()
{
    n = read();
    for(int i=1;i<=n;++i)
        a[i] = read();
    for(int i=1;i<=n;++i) {
        if(a[i-1]<a[i]) f[i][0] = f[i-1][0] + 1;
        else f[i][0] = 1;
        ans = max(ans,f[i][0]);
    }
    a[n+1] = INF;
    for(int i=n;i>=1;--i) {
        if(a[i+1]>a[i]) f[i][1] = f[i+1][1] + 1;
        else f[i][1] = 1;
        ans = max(ans,f[i][1]);
    }
    //printf("%d\n",f[6][0]);
    for(int i=2;i<=n-1;++i) {
        if(a[i-1] < a[i+1]) ans = max(ans,f[i-1][0]+f[i+1][1]);
    }
    printf("%d\n",ans);
    return 0;
}

E

题目大意

给你一个长度为 $n$ 的序列 $a[i]$ ， $a[i]$ 表示可以从 $i$ 点跳到 $i+a[i]$ 或 $i-a[i]$ （当然要满足 $i+a[i]<=n$ , $i-a[i]>=1$ ），如果当前的 $a[i]$ 是奇数，问按照这样跳，跳到一个 $a[i]$ 是偶数的格子最少步数是多少，反之亦然。输出一个数组 $g[i]$ 表示最小步数，如果 $i$ 号格子跳不到符号条件的格子，输出-1。

（~~这鬼畜的题意~~）

01最短路，（~~CSP-J2019 T4刚刚考完~~）

一开始想用记忆化搜索，但是如果反向思考一下，从最后的格子跳到给定格子，就会想到我们的好朋友 Bfs，因为 Bfs 有首次到达就是最短路径的性质。具体思路如下：

dist[i,0/1] 从其他点表示到达 $i$ 点且是 0/1(奇/偶) 的最短路长度
如果 i 点可达 $i-a[i]$ 或 $i+a[i]$ ，那么就反向建边，建一条 $(i-a[i]) => i$ 的边和一条 $(i+a[i]) => i$ 的边
把每个点的 $[i,a[i]\&1]$ 这个状态塞进队列，跑 Bfs

记得 dist[][] 数组初始值设为 $-1$ 。

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 2e5+7;
int n,cnt;
int head[N],a[N],dist[N][2];
struct Edge {
    int next,to;
}edge[N<<1];
inline void add(int u,int v) {
    edge[++cnt] = (Edge)<%head[u],v%>;
    head[u] = cnt;
}
void Bfs() {
    memset(dist, -1, sizeof(dist));
    queue<pair<int,bool> > q;
    for(int i=1;i<=n;++i) q.push(make_pair(i,a[i]&1)), dist[i][a[i]&1] = 0;
    while(!q.empty()) {
        pair<int,bool> u = q.front(); q.pop();
        for(int i=head[u.first];i;i=edge[i].next) {
            int v = edge[i].to;
            if(dist[v][u.second]==-1) {
                dist[v][u.second] = dist[u.first][u.second] + 1;
                q.push(make_pair(v,u.second));
            }
        }
    }
}
int main()
{
    n = read();
    for(int i=1;i<=n;++i) {
        a[i] = read();
        if(i+a[i] <= n) add(i+a[i],i);
        if(i-a[i] >= 1) add(i-a[i],i);
    }
    Bfs();
    for(int i=1;i<=n;++i)
        printf("%d ",dist[i][(a[i]&1)^1]);
    return 0;
}

F

补题成功！

My Solution