蒟蒻S组的题根本写不来
T1 airport
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <bits/stdc++.h> #define X first #define Y second #define to_max(x, y) (x < y ? x = y: 0) // #define debug using namespace std; typedef pair<int, int> PII; const int N = 1e5 + 10; PII a[N], b[N]; int res1[N], res2[N]; inline char GET_CHAR() { static char buf[N], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, N, stdin), p1 == p2) ? EOF: *p1 ++; } template<class T> inline void read(T &x) { x = 0; int f = 0; char ch = GET_CHAR(); while (ch < '0' || ch > '9') { f |= (ch == '-'); ch = GET_CHAR(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = GET_CHAR(); } x = f ? -x: x; } void work(PII a[], int n, int m, int res[]) { priority_queue<PII, vector<PII>, greater<PII>> p; /* 表示已经有飞机的廊桥 X--->飞机离开的时间 Y--->廊桥的编号 */ priority_queue<int, vector<int>, greater<int>> q; /* 表示当前是空的廊桥 */ for (int i = 1; i <= n; ++ i) q.push(i); for (int i = 1; i <= m; ++ i) { while (p.size() && p.top().X <= a[i].X) { /* 如果一个廊桥中的飞机可以出 则空出这个廊桥 */ q.push(p.top().Y); p.pop(); } /* 如果有空闲的廊桥则将当前的飞机安排到编号最小的飞机上 */ if (q.size()) { int t = q.top(); q.pop(); ++ res[t]; p.push({a[i].Y, t}); } } for (int i = 1; i <= n; ++ i) res[i] += res[i - 1]; } int main() { int n, m1, m2; read(n), read(m1), read(m2); for (int i = 1; i <= m1; ++ i) read(a[i].X), read(a[i].Y); for (int i = 1; i <= m2; ++ i) read(b[i].X), read(b[i].Y); sort(a + 1, a + 1 + m1); sort(b + 1, b + 1 + m2); work(a, n, m1, res1); work(b, n, m2, res2); int res = 0; for (int i = 0; i <= n; ++ i) to_max(res, res1[i] + res2[n - i]); printf(%d\n, res); } |
T2 bracket
这题怎么想都不会写，，，
看题解应该是区间dp
就贴一个xs的15pts的暴力好了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include<bits/stdc++.h> using namespace std; const int N=510,M=1e9+7; typedef long long ll; int n,k; string s; char now[N]; vector<char> add; int cnt=0; bool check(){ if(now[0]=='*'||now[n-1]=='*') return 0; vector<char> kuo,youu; int xin=0; for(int i=0;i<n;i++){ if(now[i]=='('){ xin=0; kuo.push_back(now[i]); if(now[i+1]=='*') youu.push_back(1); else youu.push_back(0); } else if(now[i]=='*'){ xin++; if(xin>k) return 0; } else{ xin=0; if(kuo.empty()) return 0; kuo.pop_back(); if(now[i-1]=='*'&&youu.back()){ for(int j=i-1;now[j]!='(';j--){ if(now[j]==')') return 0; } } youu.pop_back(); } } if(!kuo.empty()) return 0; return 1; } ll dfs(char ss){ add.push_back(ss); if(add.size()==cnt){ for(int i=0,j=0;i<n;i++){ if(s[i]!='?') now[i]=s[i]; else now[i]=add[j++]; } // for(int i=0;i<n;i++) printf(%c,now[i]); // cout<<\n; if(check()){ add.pop_back(); return 1; } else{ add.pop_back(); return 0; } } ll ans=((dfs('(')+dfs(')'))%M+dfs('*'))%M; add.pop_back(); return ans; } int main(){ //freopen(bracket.in,r,stdin); //freopen(bracket.out,w,stdout); scanf(%d%d,&n,&k); cin>>s; for(int i=0;i<n;i++){ if(s[i]=='?'){ cnt++; } } printf(%lld,((dfs('(')+dfs(')'))%M+dfs('*'))%M); return 0; } |
T3 palin
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int v[N]; char ans[N], cur[N]; struct Deque { int s[N], hh, tt; inline int ft() {return s[hh];} inline int bk() {return s[tt - 1];} inline void pushbk(int x) {s[tt ++] = x;} inline void pushft(int x) {s[-- hh] = x;} inline void popbk() {-- tt;} inline void popft() {++ hh;} inline void cr() {hh = tt = 0;} inline bool empty() {return hh >= tt;} inline int size() {return tt - hh;} inline void debug() { for (int i = hh; i < tt; cout << s[i ++] << ' '); puts(); } } a, b; int see(int l, int r, int val) { for (int i = l; i <= r; ++ i) if (v[i] == val) return i; return -1; } bool pan(int n) { int id = 1; while (id <= (n << 1) && cur[id] == ans[id]) ++ id; return id <= (n << 1) && cur[id] < ans[id]; } void check(int n) { int now = 2; while (true) { #ifdef DEbug cout << NOW_is_debug: << now << endl; a.debug(), b.debug(); #endif if (a.empty() && b.empty()) break; else if (b.empty()) { if (a.ft() != a.bk()) { cur[1] = 'Z'; return; } cur[now] = cur[n * 2 - now + 1] = 'L'; a.popbk(), a.popft(); } else if (a.empty()) { if (b.bk() != b.ft()) { cur[1] = 'Z'; return; } cur[now] = cur[2 * n - now + 1] = 'R'; b.popft(), b.popbk(); } else { if (a.ft() == a.bk() && a.size() > 1) { cur[now] = cur[2 * n - now + 1] = 'L'; a.popft(), a.popbk(); } else if (a.bk() == b.ft()) { cur[now] = 'L'; cur[2 * n - now + 1] = 'R'; b.popft(), a.popbk(); } else if (b.bk() == a.ft()) { cur[now] = 'R'; cur[2 * n - now + 1] = 'L'; a.popft(), b.popbk(); } else if (b.bk() == b.ft() && b.size() > 1) { cur[now] = 'R'; cur[2 * n - now + 1] = 'R'; b.popft(), b.popbk(); } else { cur[1] = 'Z'; return; } } ++ now; } } int main() { int T; scanf(%d, &T); while (T --) { int pos, n; ans[1] = 'Y'; scanf(%d, &n); for (int i = 1; i <= n * 2; ++ i) scanf(%d, v + i); a.cr(), b.cr(); pos = see(2, n * 2, v[1]); for (int i = pos - 1; i >= 2; -- i) a.pushbk(v[i]); for (int i = pos + 1; i <= n * 2; ++ i) b.pushbk(v[i]); cur[1] = 'L'; cur[n * 2] = 'L'; check(n); if (pan(n)) { for (int i = 1; i <= n * 2; ++ i) ans[i] = cur[i]; } a.cr(), b.cr(); pos = see(1, n * 2 - 1, v[n * 2]); for (int i = pos - 1; i; -- i) a.pushbk(v[i]); for (int i = pos + 1; i <= n * 2 - 1; ++ i) b.pushbk(v[i]); cur[1] = 'R'; cur[n * 2] = 'L'; check(n); if (pan(n)) { for (int i = 1; i <= n * 2; ++ i) ans[i] = cur[i]; } // for (int i = 1; i <= n * 2; ++ i) printf(%c, ans[i]); // puts(); if (ans[1] == 'Y') puts(-1); else { for (int i = 1; i <= n * 2; ++ i) printf(%c, ans[i]); puts(); } } return 0; } |
T4 traffic
黑题就nm离谱
发表评论