2018.7.21NOIP模拟赛?解题报告

题面

预计得分:70 + 60 + 30 = 160

实际得分:40 + 60 + 0 = 100

T1数组开小了

T2比赛结束后5min AC

T3加了个记忆话搜索wa了、、

T1

zbq吊打std啊Orz

此题$O(nlog)$做法:

一个很显然的思路:对每个做括号维护一个大根堆,每次取最大的。

但是这样有不优的情况,比如$()), 1, 3, 5$

那么我们还需要对每个已经加入的右括号维护一个小根堆。每次判断是否替换掉更小的会更优

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#define LL long long 
using namespace std;
const int MAXN = 2 * 1e5 + 10, INF = 1e9;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N;
priority_queue<int> mx;
priority_queue<int, vector<int>, greater<int> >mi;
char s[MAXN];
int a[MAXN];
int main() {
    freopen("bracket.in", "r", stdin);
    freopen("bracket.out", "w", stdout);
    N = read();
    scanf("%s", s + 1);
    for(int i = 1; i <= N; i++) a[i] = read();
    int ans = 0;
    for(int i = 1; i <= N; i++) {
        if(s[i] == '(') mx.push(a[i]);
        if(s[i] == ')')
            if(!mx.empty() && a[i] + mx.top() > 0) {
                if(mi.empty() || (!mi.empty() && mx.top() > - mi.top())) ans += a[i] + mx.top(), mx.pop(), mi.push(a[i]);                            
                else if(!mi.empty() && a[i] > mi.top()) ans -= mi.top(), mi.pop(), ans += a[i], mi.push(a[i]);
            } else if(!mi.empty() && a[i] > mi.top())  ans -= mi.top(), mi.pop(), ans += a[i], mi.push(a[i]);
            
    }
    printf("%d", ans);
    return 0;
}

T2

很显然每个位置就那么几种可能

直接暴力判断就好,前缀和优化

/*
60:直接BFS 
*/
#include<cstdio>
#include<algorithm>
#include<queue>
#define LL long long 
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, K;
int a[1001][1001], down[MAXN], vis[1001][1001];
struct Node {
    int xx1, yy1, xx2, yy2;
}p[MAXN];
bool pd(int x, int y) {
    if(x < 1 || x > N || y < 1 || y > M) return 1;
    return 0;
}
int hsum[1001][1001], lsum[1001][1001]; 
bool line(int x1, int y11, int x2, int y2, int id) {
    if(pd(x1, y11) || pd(x2, y2)) return 1;
    if(x1 == x2) {
        if(y11 > y2) swap(y11, y2);
        if(hsum[x1][y2] - hsum[x1][y11 - 1] == 0) return 0;
        if(a[x1][y11] == id && hsum[x1][y2] - hsum[x1][y11] == 0) return 0;
        if(a[x1][y2] == id && hsum[x1][y2 - 1] - hsum[x1][y11 - 1] == 0) return 0;  
        return 1;
    }
    if(y11 == y2) {
        if(x1 > x2) swap(x1, x2);
        if(lsum[x2][y2] - lsum[x1 - 1][y2] == 0) return 0;
        if(a[x1][y11] == id && lsum[x2][y2] - lsum[x1][y2] == 0) return 0;
        if(a[x2][y11] == id && lsum[x2 - 1][y2] - lsum[x1 - 1][y2] ==0) return 0;
        return 1;
    }
}
int main() {
    freopen("linking.in", "r", stdin);
    freopen("linking.out", "w", stdout);
    N = read(); M = read(); K = read();
    for(int i = 1; i <= K; i++) {
        int xx1 = read(), yy1 = read(), xx2 = read(), yy2 = read();
        a[xx1][yy1] = i;
        a[xx2][yy2] = i;
        p[i] = (Node) {xx1, yy1, xx2, yy2};
    }
    for(int i = 1; i <= N; i++) 
        for(int j = 1; j <= M; j++)
            hsum[i][j] = hsum[i][j - 1] + a[i][j], 
            lsum[i][j] = lsum[i - 1][j] + a[i][j];
    int ans = 0;
    for(int i = 1; i <= K; i++) {
        int xx1 = p[i].xx1, yy1 = p[i].yy1, xx2 = p[i].xx2, yy2 = p[i].yy2, flag = 0;
        if(yy1 > yy2) swap(yy1, yy2), swap(xx1, xx2);
        for(int k = 1; k <= N; k++) 
            if(!line(xx2, yy2, k, yy2, i) && !line(xx1, yy1, k, yy1, i) && !line(k, yy1, k, yy2, i))
                {ans++; flag = 1; break;}
        if(flag == 1) continue;    
        for(int k = 1; k <= M; k++) 
            if(!line(xx2, yy2, xx2, k, i) && !line(xx2, k, xx1, k, i) && !line(xx1, yy1, xx1, k, i))
                {ans++; break;}
    }
    printf("%d", ans);
    return 0;
}
/*
20 20 3
1 1 20 20
2 1 2 20
3 1 1 20


3 3 3
1 3 2 2
1 1 3 3
1 2 2 1


*/

T3

神仙题。

很显然答案是一棵树,那么直接书上倍增就好

满分做法不会。。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

cf1027F. Session in BSU(并查集 匈牙利)

$n$个人,每个人可以在第$a_i$天或第$b_i$,一天最多考一场试,问在最优的情况下,最晚什么时候结束

1291
来自专栏数据结构与算法

P1807 最长路_NOI导刊2010提高(07)

题目描述 设G为有n个顶点的有向无环图,G中各顶点的编号为1到n,且当为G中的一条边时有i < j。设w(i,j)为边的长度,请设计算法,计算图G中<1,n>间...

3117
来自专栏数据结构与算法

BZOJ3498: PA2009 Cakes(三元环)

如果\(v\)的度数\(\leqslant M\),那么就再暴力枚举\(v\)连出去的点\(t\),看\(u\)与\(t\)是否联通(打标记)

802
来自专栏灯塔大数据

每周学点大数据 | No.30前序计数

No.30期 前序计数 Mr. 王:我们再来说说父子关系判定的应用。前序计数是一种非常常用的对树进行处理的方法。前序计数实现的就是对各个节点按照其前序遍...

3437
来自专栏calmound

HDU 2011 菜鸟杯

A:该题写了很久,一直TLE,主要是枚举到n/2时间复杂度实在太高了,其实嘛,这道题就是因式分解,所以就是i*i=n,也就是sqrt(n) #include<s...

3144
来自专栏云霄雨霁

字符串查找----查找算法的选择

2860
来自专栏数据结构与算法

cf567E. President and Roads(最短路计数)

首先确定哪些边一定在最短路上,一个条件是 从起点到该点的最短路 + 边权 + 从该点到终点的最短路 = 从起点到终点的最短路

1152
来自专栏数据结构与算法

1225 八数码难题

题目描述 Description Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们. 问题描述 在3×3的棋盘上,...

3387
来自专栏小樱的经验随笔

详解斯坦纳点及斯坦纳树及模版归纳总结

①什么是斯坦纳点?   假设原来已经给定了个点,库朗等指出需要引进的点数至多为,此种点称为斯坦纳点。过每一斯坦纳点,至多有三条边通过。若为三条边,则它们两两交成...

8566
来自专栏数据结构与算法

1225 八数码难题

1225 八数码难题  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Descri...

2864

扫码关注云+社区

领取腾讯云代金券