CF1214

2019-09-06

CF1214

C题WA3发的菜鸡还能涨分

A

发现货币面值都是倍数关系,直接暴力枚举第第一种换了多少个更新答案就好了

B

按照题意模拟

C

首先,左括号的数量不等于有括号的数量一定无解

想等的话在括号匹配的过程有在某一时刻栈中存在两个或者以上的右括号便无解

错误原因:思路出了点小问题

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 5e5 + 3;
char s[N];
int sta[N];
int n;
inline int read(){
    int v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;
}
int sum1;
int tot;
int main(){
    n = read();
    scanf("%s",s + 1);
    for(int i = 1;i <= n;++i)
        sum1 += (s[i] == ')');  
    if(sum1 != n - sum1){printf("No\n");return 0;}
    for(int i = 1;i <= n;++i){
        if(s[i] == '(') tot++;  
        else{
            tot--;
            if(tot <= -2){printf("No\n");return 0;}
        }
    }
    if(tot >= 2) printf("No\n");
    else printf("Yes\n");
    return 0;
}

D

我也不知道自己写了个什么算法,但是它过掉了

考虑这种情况

分享图片

如图,如果黄色障碍点的话

绿色的点不管是不是障碍,都可以当做障碍去看

之后我们扩展一下

\(dis_{x,y}\)表示把经过\((x,y)\)发出的路径全部搞死的最小代价

如果\((x,y)\)是空地并且\((x,y)\)\((1,1)\)联通

\(dis_{x,y} = (dis_{x + 1,y} > 0 ) + (dis_{x,y + 1} > 0)\)

否则\(dis_{x,y} = 0\)

我们需要倒着这么转移

当然边界情况需要判断一下

之后我们就可以枚举所有的对角线的dis值之和

取个\(min\)

但是,答案如果涨这个样子怎么办

分享图片

很明显我们只需要堵住一个格子

但是很明显答案不是对角线

想想我们\(dp\)的过程,我们已经把下面的贡献转移到了上面

所以他的dis数组是这样的,

\[ \begin{array}{|c|c|c|c|}\hline 1 & {2} & {1} & {0} \\ \hline 1 & {1} & {1} & {0} \\ \hline 0 & {0} & {1} & {0} \\ \hline 0 & {0} & {1} & {1} \\ \hline\end{array} \]
然后这样发现答案也是1

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 1e6 + 3;
string s[N];
bool book[N << 1];
int n,m;
int dis[N << 1];
int dx[2] = {0,1},dy[2] = {1,0};
inline int read(){
    int v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;
}
inline int bfs(){
    memset(book,0,sizeof(book));
    book[0] = 1;
    queue <int> q;q.push(0);
    while(!q.empty()){
        int k = q.front();q.pop();
        int x = k / m,y = k % m;
        for(int i = 0;i < 2;++i){
            int xx = x + dx[i],yy = y + dy[i];
    //      if(book[]) continue;
            if(xx < 0 || xx >= n || yy < 0 || yy >= m || book[xx * m + yy] || s[xx][yy] == '#') continue;
            int z = xx * m + yy;
            q.push(xx * m + yy);
            book[xx * m + yy] = 1;
        }
    }
}
int sum[N << 1];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 0;i < n;++i) cin >> s[i];
    memset(dis,0x3f,sizeof(dis));
    for(int i = 0;i < n;++i){
        for(int j = 0;j < m;++j)
        if(s[i][j] == '#') dis[i * m + j] = 0;
    }
    bfs();
    dis[n * m - 1] = 1;
    for(int i = n - 1;i >= 0;--i){
        for(int j = m - 1;j >= 0;--j){
            int x = i * m + j;
            if(s[i][j] == '#') continue; 
            if(!book[i * m + j]){dis[x] = 0;continue;}
            if(i == n - 1 && j == m - 1) continue;
            if(i == n - 1) dis[x] = (dis[x + 1] > 0);
            else if(j == m - 1) dis[x] = (dis[x + m] > 0);
            else dis[x] = (dis[x + 1] > 0) + (dis[x + m] > 0);
        }
    }
    int ans = 2;
    for(int i = 0;i < n;++i){
        for(int j = 0;j < m;++j){
            sum[i + j] += (dis[i * m + j] > 0);
        }
    }
    for(int i = 1;i <= n + m - 2 - 1;++i) ans = min(ans,sum[i]);
//  ans = min(ans,sum[1]);
    printf("%d\n",ans); 
    return 0;
}

update:赛后被刁神吊打了Orz

这道题完全不需要这么麻烦

因为搜索出所有可能到达的点之后,维护两个指针

一个能向下走就向下走,另外一个能向右走就向右走

如果这两个路径有交点,那么一定是所有路径的必经点

直接把这个点删掉就好了QAQ

E

构造题

我们先把所有距离从大到小排序

因为题目保证有解

我们先构造一条这样的链

咕咕咕

F

咕咕咕