# 2018.7.21NOIP模拟赛？解题报告

T1数组开小了

T2比赛结束后5min AC

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

## T1

zbq吊打std啊Orz

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#define LL long long
using namespace std;
const int MAXN = 2 * 1e5 + 10, INF = 1e9;
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);
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;
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() {
for(int i = 1; i <= K; i++) {
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

*/

1811 篇文章120 人订阅

0 条评论

## 相关文章

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

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

1291

3117

802

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

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

3437

### HDU 2011 菜鸟杯

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

3144

2860

1152

3387

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

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

8566

### 1225 八数码难题

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

2864