题面
预计得分:70 + 60 + 30 = 160
实际得分:40 + 60 + 0 = 100
T1数组开小了
T2比赛结束后5min AC
T3加了个记忆话搜索wa了、、
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;
}
很显然每个位置就那么几种可能
直接暴力判断就好,前缀和优化
/*
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
*/
神仙题。
很显然答案是一棵树,那么直接书上倍增就好
满分做法不会。。