今天下午的题目感觉比较简单（前两题），第三题很难
T1在北京时做过，然后就几分钟了出来
T2貌似也是一个暴力题，以为不打素数表会超时（其实不然），然而打表超代码内存，连交都交不上去，还真不知道代码内存是多少
T3差不多做了将近1.5h，然而题目真的很难读懂的，还有半个小时才知道屏幕上有样例解释（看不清楚）GG，放弃
T1
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <cmath> using namespace std; const int N = 1e5 + 10; string s; int answer = 0; int stack[N], l, r; int main() { freopen("shower.in", "r", stdin); freopen("shower.out", "w", stdout); cin >> s; int len = s.length(); l = 1, r = 0; for(int i = 0; i < len; i ++) { if(s[i] == '(') stack[++ r] = 1; else { if(l > r) { answer ++; stack[++ r] = 1; } else r --; } } answer += (r >> 1); printf("%d", answer); return 0; } /* )()()()()(()()()(( */
T2
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> using namespace std; const int N = 1000005; #define LL long long int s[N]; inline int read() { int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x; } int T, n, k, js; LL f[N]; bool vis[1000005], flag; inline bool check(int x) { LL ret = f[x + k - 1] - f[x - 1]; if(ret <= n) return 1; else return 0; } inline void make_s() { int ove = 1000005; for(int i = 2; i <= sqrt(ove) + 1; i ++) if(vis[i] == 0) for(int j = i * 2; j <= ove; j += i) vis[j] = 1; for(int i = 2; i <= ove; i ++) if(!vis[i]) s[++ js] = i; } int main() { //freopen("diary.in", "r", stdin); //freopen("bbbbb.out", "w", stdout); make_s(); for(int i = 1; i <= js; i ++) { f[i] = f[i - 1] + s[i]; } T = read(); while(T --) { n = read(); k = read(); int L = 1, R = js, mid, Ans; while(L <= R) { mid = (L + R) >> 1; if(check(mid)) L = mid + 1, Ans = mid; else R = mid - 1; } if(R == 0) { printf("-1 "); continue ; } int answer = f[Ans + k - 1] - f[Ans - 1]; if(answer > n) printf("-1 "); else printf("%lld ", answer); } return 0; } /* 3 20 2 20 3 20 4 1 659309 1 659299 */
T3
#include <algorithm> #include <cstdio> #include <map> #define mp std::make_pair const int N = 65; const int mod = 1000000007; typedef long long LL; typedef std::map<std::pair<LL, LL>, LL> Mapd; typedef std::map<LL, LL> Mapf; Mapd mapd[N]; Mapf mapf[N]; int a[N], b[N]; LL F[N], c[N], d[N], n[N], l[N]; LL dd(int i, LL x, LL y) { if (x > y) std::swap(x, y); if (x == y) return 0; Mapd::iterator it = mapd[i].find(mp(x, y)); if (it != mapd[i].end()) return it->second; LL na = n[a[i]]; if (x >= na) return mapd[i][mp(x, y)] = dd(b[i], x - na, y - na); else if (y < na) return mapd[i][mp(x, y)] = dd(a[i], x, y); else return mapd[i][mp(x, y)] = (dd(a[i], x, c[i]) + dd(b[i], d[i], y - na) + l[i]) % mod; } LL f(int i, LL j) { if (!i) return 0; Mapf::iterator it = mapf[i].find(j); if (it != mapf[i].end()) return it->second; LL na = n[a[i]]; if (j < na) return mapf[i][j] = (f(a[i], j) + n[b[i]] % mod * dd(i, j, d[i] + na) % mod + f(b[i], d[i])) % mod; else return mapf[i][j] = (f(b[i], j - na) + n[a[i]] % mod * dd(i, j, c[i]) % mod + f(a[i], c[i])) % mod; } int main() { freopen("cloth.in", "r", stdin); freopen("cloth.out", "w", stdout); int m; scanf("%d", &m); F[0] = 0; n[0] = 1; for (int i = 1; i <= m; ++i) { scanf("%d%d%I64d%I64d%I64d", &a[i], &b[i], &c[i], &d[i], &l[i]); n[i] = n[a[i]] + n[b[i]]; LL na = n[a[i]] % mod, nb = n[b[i]] % mod; l[i] %= mod; printf("%I64d ", F[i] = (F[a[i]] + F[b[i]] + nb * f(a[i], c[i]) % mod + na * f(b[i], d[i]) % mod + na * nb % mod * l[i] % mod) % mod); } return 0; }