Codeforces Round #447-白红宇

Codeforces Round #447

阅读量：5036 次

发布时间：2019-06-12

本文共 15605 字，大约阅读时间需要 52 分钟。

QAQ

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using std::vector;using std::sort;int cmp(const void * x, const void * y) {    //x < y#define datatype int    return (*((datatype *)(x))) > (*((datatype *)(y))) ? 1 : -1;#undef datatype}char str[105];int l[105], r[105];int main() {#ifndef ONLINE_JUDGE    freopen("input.txt", "r", stdin);#endif    scanf("%s", str);    int n = strlen(str);    memset(l, 0, sizeof(l));    if (str[0] == 'Q') l[0] = 1;    memset(r, 0, sizeof(r));    if (str[n - 1] == 'Q') r[n-1] = 1;    for (int i = 1; i < n; i++) {        l[i] = l[i - 1];        if (str[i] == 'Q') l[i]++;    }    for (int i = n - 2; i >= 0; i--) {        r[i] = r[i + 1];        if (str[i] == 'Q') r[i]++;    }    int ans = 0;    for (int i = 0; i < n; i++) {        if (str[i] == 'A') ans += l[i] * r[i];    }    printf("%d\n", ans);    return 0;}

View Code

Ralph And His Magic Field

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include 
           
            using namespace std;/*using std::vector;using std::sort;*/int cmp(const void * x, const void * y) { //x < y#define datatype int return (*((datatype *)(x))) > (*((datatype *)(y))) ? 1 : -1;#undef datatype}class BigNum {#define MAXSIZEOFBIGNUM 500#define BASE 10#define DLEN 1public: int Len; int d[MAXSIZEOFBIGNUM];public: BigNum(void); BigNum(const int); BigNum(const long long); BigNum(const char *); BigNum(const BigNum &); BigNum & operator = (const BigNum &); void clear(void); friend istream& operator>>(istream&, BigNum&); friend ostream& operator<<(ostream&, BigNum&); bool operator == (const BigNum &) const; bool operator > (const BigNum &) const; bool operator < (const BigNum &) const; bool operator >= (const BigNum &) const; bool operator <= (const BigNum &) const; BigNum operator + (const BigNum &) const; BigNum operator - (const BigNum &) const; BigNum operator * (const BigNum &) const; BigNum operator / (const BigNum &) const; BigNum operator % (const BigNum &) const; void operator ++ (void); void operator -- (void); BigNum operator + (const int &) const; BigNum operator - (const int &) const; BigNum operator * (const int &) const; BigNum operator / (const int &) const; int operator % (const int &) const; BigNum operator ^ (const int &) const; ~BigNum() {}};BigNum::BigNum() { Len = 0; memset(d, 0, sizeof(d));}BigNum::BigNum(const int ops) { int x = ops; if (ops == 0) Len = 1; else Len = 0; memset(d, 0, sizeof(d)); while (x) { Len++; d[Len] = x % BASE; x /= BASE; }}BigNum::BigNum(const long long ops) { long long x = ops; if (ops == 0) Len = 1; else Len = 0; memset(d, 0, sizeof(d)); while (x) { Len++; d[Len] = x % BASE; x /= BASE; }}BigNum::BigNum(const char * ops) { int L = strlen(ops) - 1, b = 0; memset(d, 0, sizeof(d)); while (ops[b] == '0') { b++; } Len = 0; while (L - b + 1 >= DLEN) { int x = 0; for (int i = L - DLEN + 1; i <= L; i++) { x = x * 10 + ops[i] - '0'; } Len++; d[Len] = x; L -= DLEN; } int x = 0; for (int i = b; i <= L; i++) { x = x * 10 + ops[i] - '0'; } Len++; d[Len] = x;}BigNum::BigNum(const BigNum &ops) : Len(ops.Len) { memset(d, 0, sizeof(d)); for (int i = 1; i <= Len; i++) { d[i] = ops.d[i]; }}BigNum & BigNum::operator = (const BigNum &ops) { memset(d, 0, sizeof(d)); Len = ops.Len; for (int i = 1; i <= Len; i++) { d[i] = ops.d[i]; } return *this;}void BigNum::clear(void) { for (int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++) { if (d[i] < 0) { d[i] += BASE; d[i + 1]--; } if (d[i] >= BASE) { d[i] -= BASE; d[i + 1]++; } } for (int i = MAXSIZEOFBIGNUM - 1; i >= 1; i--) if (d[i] > 0) { Len = i; return; } Len = 0;}istream& operator>>(istream &in, BigNum &ops) { char str[MAXSIZEOFBIGNUM + 100]; in >> str; int L = strlen(str), b = 0; while (str[b] == '0') { b++; } ops.Len = 0; for (int i = L - 1; i >= b; i--) { ops.Len++; ops.d[ops.Len] = str[i] - '0'; } return in;}ostream& operator<<(ostream& out, BigNum& ops) { for (int i = ops.Len; i >= 1; i--) { out << ops.d[i]; } if (ops.Len == 0) { out << "0"; } return out;}bool BigNum::operator == (const BigNum &ops) const { if (Len != ops.Len) { return false; } for (int i = Len; i >= 1; i--) if (d[i] != ops.d[i]) { return false; } return true;}bool BigNum::operator > (const BigNum &ops) const { if (Len < ops.Len) { return false; } else if (Len > ops.Len) { return true; } else { for (int i = Len; i >= 1; i--) if (d[i] < ops.d[i]) { return false; } else if (d[i] > ops.d[i]) { return true; } } return false;}bool BigNum::operator < (const BigNum &ops) const { if (Len < ops.Len) { return true; } else if (Len > ops.Len) { return false; } else { for (int i = Len; i >= 1; i--) if (d[i] < ops.d[i]) { return true; } else if (d[i] > ops.d[i]) { return false; } } return false;}bool BigNum::operator >= (const BigNum &ops) const { if (Len < ops.Len) { return false; } else if (Len > ops.Len) { return true; } else { for (int i = Len; i >= 1; i--) if (d[i] < ops.d[i]) { return false; } else if (d[i] > ops.d[i]) { return true; } } return true;}bool BigNum::operator <= (const BigNum &ops) const { if (Len < ops.Len) { return true; } else if (Len > ops.Len) { return false; } else { for (int i = Len; i >= 1; i--) if (d[i] < ops.d[i]) { return true; } else if (d[i] > ops.d[i]) { return false; } } return true;}BigNum BigNum::operator + (const BigNum &ops) const { BigNum ret(*this); for (int i = 1; i <= ops.Len; i++) { ret.d[i] += ops.d[i]; } ret.clear(); return ret;}BigNum BigNum::operator - (const BigNum &ops) const { BigNum ret(*this); for (int i = ops.Len; i >= 1; i--) { ret.d[i] -= ops.d[i]; } ret.clear(); return ret;}BigNum BigNum::operator * (const BigNum &ops) const { BigNum ret, now(*this); for (int i = 1; i <= now.Len; i++) for (int j = 1; j <= ops.Len; j++) { ret.d[i + j - 1] += now.d[i] * ops.d[j]; } for (int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++) if (ret.d[i] >= BASE) { ret.d[i + 1] += ret.d[i] / BASE; ret.d[i] %= BASE; } for (int i = MAXSIZEOFBIGNUM - 1; i >= 1; i--) if (ret.d[i] > 0) { ret.Len = i; break; } return ret;}BigNum BigNum::operator / (const BigNum &ops) const { BigNum now = (*this), div, mod; div.Len = now.Len; mod.Len = 0; for (int j = now.Len; j >= 1; j--) { mod.Len++; for (int p = mod.Len; p >= 2; p--) { mod.d[p] = mod.d[p - 1]; } mod.d[1] = now.d[j]; while (mod >= ops) { div.d[j]++; mod = mod - ops; } if (mod.Len == 1 && mod.d[1] == 0) { mod.Len--; } } div.clear(); mod.clear(); return div;}BigNum BigNum::operator % (const BigNum &ops) const { BigNum now = (*this), div, mod; div.Len = now.Len; mod.Len = 0; for (int j = now.Len; j >= 1; j--) { mod.Len++; for (int p = mod.Len; p >= 2; p--) { mod.d[p] = mod.d[p - 1]; } mod.d[1] = now.d[j]; while (mod >= ops) { div.d[j]++; mod = mod - ops; } if (mod.Len == 1 && mod.d[1] == 0) { mod.Len--; } } div.clear(); mod.clear(); return mod;}void BigNum::operator ++ (void) { d[1]++; for (int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++) if (d[i] >= BASE) { d[i] -= BASE; d[i + 1]++; } else { break; } if (d[Len + 1] > 0) { Len++; }}void BigNum::operator -- (void) { d[1]--; for (int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++) if (d[i] < 0) { d[i] += BASE; d[i + 1]--; } else { break; } if (d[Len] == 0) { Len--; }}BigNum BigNum::operator + (const int & ops) const { BigNum ret = (*this); ret.d[1] += ops; ret.clear(); return ret;}BigNum BigNum::operator - (const int & ops) const { BigNum ret = (*this); ret.d[1] -= ops; ret.clear(); return ret;}BigNum BigNum::operator * (const int & ops) const { BigNum ret(*this); for (int i = 1; i <= ret.Len; i++) { ret.d[i] *= ops; } for (int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++) if (ret.d[i] >= BASE) { ret.d[i + 1] += ret.d[i] / BASE; ret.d[i] %= BASE; } for (int i = MAXSIZEOFBIGNUM - 1; i >= 1; i--) if (ret.d[i] > 0) { ret.Len = i; return ret; } ret.Len = 0; return ret;}BigNum BigNum::operator / (const int & ops) const { BigNum ret; int down = 0; for (int i = Len; i >= 1; i--) { ret.d[i] = (d[i] + down * BASE) / ops; down = d[i] + down * BASE - ret.d[i] * ops; } ret.Len = Len; while (ret.d[ret.Len] == 0 && ret.Len > 1) { ret.Len--; } return ret;}int BigNum::operator % (const int &ops) const { int mod = 0; for (int i = Len; i >= 1; i--) { mod = ((mod * BASE) % ops + d[i]) % ops; } return mod;}BigNum BigNum::operator ^ (const int &ops) const { BigNum t, ret(1); if (ops == 0) { return ret; } if (ops == 1) { return *this; } int m = ops, i; while (m > 1) { t = *this; for (i = 1; (i << 1) <= m; i <<= 1) { t = t * t; } m -= i; ret = ret * t; if (m == 1) { ret = ret * (*this); } } return ret;}long long n, m;int k;long long ans, mi;int x[500], len;int main() {#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin);#endif scanf("%lld%lld%d", &n, &m, &k); if (n % 2 != m % 2 && k == -1) { printf("0\n"); return 0; } BigNum bn(n), bm(m); BigNum power; power = (bn - 1) * (bm - 1); len = 0; while (power > 0) { if (power % 2 == 1) x[len++] = 1; else x[len++] = 0; power = power / 2; } mi = 2, ans = 1; if (x[0]) ans *= 2; for (int i = 1; i < len; i++) { mi = (mi * mi) % 1000000007; if (x[i]) { ans = (ans * mi) % 1000000007; } } printf("%lld\n", ans); return 0;}

View Code

Marco and GCD Sequence

最小的数应该是所有数的约数

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include 
           
            using std::vector;using std::sort;int cmp(const void * x, const void * y) { //x < y#define datatype int return (*((datatype *)(x))) > (*((datatype *)(y))) ? 1 : -1;#undef datatype}int s[1005];int main() {#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin);#endif int n, m; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &s[i]); } if (n == 1) { printf("1\n%d\n", s[0]); return 0; } for (int i = 1; i < n; i++) { if (s[i] % s[0] != 0) { printf("-1\n"); return 0; } } printf("%d\n", 2 * n); for (int i = 0; i < n; i++) { printf("%d %d ", s[0], s[i]); } return 0;}

View Code

Ralph And His Tour in Binary Country

记录每个点到子树中各个点的距离，按从小到大排序，因为这是一个完全二叉树，所以排序的时候可以直接归并。

solve(x,h)表示从x节点开始往子树中走，以h的初始happy程度最多能获得的happy。

对于每次查询，首先从A点的子节点中找，然后向A点父亲的方向扩展，直到h耗尽或走到了所有点。

#pragma comment(linker, "/STACK:102400000,102400000")#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                //#include
                
                 using namespace std;typedef long long lint;lint a[2000005];vector
                 
                   G[2000005], P[2000005];int cmp(const void * x, const void * y) {#define datatype int datatype dx = *((datatype *)(x)), dy = *((datatype *)(y)); //x < y return dx > dy ? 1 : -1;#undef datatype}lint solve(int x, lint h) { int ptr = lower_bound(G[x].begin(), G[x].end(), h) - G[x].begin(); return h * ptr - P[x][ptr - 1];}int main() {#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin);#endif std::ios::sync_with_stdio(0), cin.tie(0); int n, q, dep = 1; cin >> n >> q; for (int i = 2; i <= n; i++) cin >> a[i]; while ((dep << 1) <= n) dep <<= 1; for (int i = dep; i <= n; i++) { G[i].push_back(0); } while (dep > 1) { for (int i = dep >> 1; i < dep; i++) { G[i].push_back(0); int j = 0, k = 0, l = i << 1, r = (i << 1) + 1; while (j < G[l].size() && k < G[r].size()) { if (G[l][j] + a[l] < G[r][k] + a[r]) { G[i].push_back(G[l][j] + a[l]); j++; } else { G[i].push_back(G[r][k] + a[r]); k++; } } if (j == G[l].size()) for (int p = k; p < G[r].size(); p++) G[i].push_back(G[r][p] + a[r]); else for (int p = j; p < G[l].size(); p++) G[i].push_back(G[l][p] + a[l]); } dep >>= 1; } for (int i = 1; i <= n; i++) { P[i].push_back(G[i][0]); for (int j = 1; j < G[i].size(); j++) { P[i].push_back(P[i][j - 1] + G[i][j]); } } int x, y; lint h; while (q--) { cin >> x >> h; if (h == 0) { cout << 0 << endl; continue; } lint ans = solve(x, h); while (x > 1) { if (a[x] < h) { ans += h - a[x]; h -= a[x]; } else break; y = (x >> 1) << 1; if (y == x) y++; x = (x >> 1); if (y > n) continue; if (a[y] < h) ans += solve(y, h - a[y]); } cout << ans << endl; } return 0;}

View Code

Ralph and Mushrooms

按照题解把代码写出来了，运行超时，大方向差不多，不想再调了。

#pragma comment(linker, "/STACK:102400000,102400000")#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 //#include
                 
                  using namespace std;typedef long long lint;class Tarjan_Algorithm {public: int n; vector
                  
                    dfn, low; vector
                   
                     inStack; vector
                    
                     
                       > * G; int dep; stack
                      
                        pStack; vector
                       
                        
                          > Scc; vector
                         
                           color; vector
                          
                           
                             > bridge; vector
                            
                              component; void init(vector
                             
                              
                                > * G, int size); void dfs(int x); void runTarjan();};void Tarjan_Algorithm::init(vector
                               
                                
                                  > * Graph, int size) { if(size < 0) return; G = Graph, n = size; dfn.clear(), low.clear(), inStack.clear(), Scc.clear(), color.clear(), bridge.clear(); dfn = vector
                                 
                                  (n + 1, 0); low = vector
                                  
                                   (n + 1, 0); inStack = vector
                                   
                                    (n + 1, false); color = vector
                                    
                                     (n + 1, 0); dep = 0; while(!pStack.empty()) pStack.pop();}void Tarjan_Algorithm::dfs(int x) { if(x > n) return; inStack[x] = true; dfn[x] = low[x] = ++dep; pStack.push(x); for(int i = 0; i < (*G)[x].size(); i++) { int u = (*G)[x][i]; if(dfn[u] == 0) { dfs(u); low[x] = min(low[x], low[u]); if(dfn[x] < low[u]) { bridge.push_back(make_pair(x, u)); } } else { if(inStack[u]) low[x] = min(low[x], dfn[u]); } } if(low[x] == dfn[x]) { component.clear(); while(!pStack.empty()) { int u = pStack.top(); pStack.pop(); component.push_back(u); color[u] = Scc.size(); inStack[u] = false; if(u == x) break; } Scc.push_back(component); }}void Tarjan_Algorithm::runTarjan() { for(int i = 1; i <= n; i++) { if(!dfn[i]) dfs(i); }}int cmp(const void * x, const void * y) {#define datatype int datatype dx = *((datatype *)(x)), dy = *((datatype *)(y)); //x < y return dx > dy ? 1 : -1;#undef datatype}vector
                                     
                                      
                                        > G(1000005, vector
                                       
                                        ()), P(1000005, vector
                                        
                                         ());vector
                                         
                                          
                                            > DAG(1000005, vector
                                           
                                            ()), DAGP(1000005, vector
                                            
                                             ());queue
                                             
                                               q;lint dp[1000005];lint s[1000005];bool flag[1000005];Tarjan_Algorithm tja;lint calc(int x) { int ll = 0, rr = 20000; while(ll < rr) { int mm = (ll + rr + 1) / 2; if(mm * (mm + 1) / 2 > x)rr = mm - 1; else ll = mm; } return x * (lint)(ll + 1) - (lint)ll * (ll + 1) * (ll + 2) / 6;}int main() {#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin);#endif std::ios::sync_with_stdio(0), cin.tie(0); int n, m, x, y, c; while(cin >> n >> m) { for(int i = 1; i <= n; i++) G[i].clear(), P[i].clear(); for(int i = 0; i < m; i++) { cin >> x >> y >> c; G[x].push_back(y); P[x].push_back(c); } tja.init(&G, n); tja.runTarjan(); int nn = tja.Scc.size(); for(int i = 0; i < nn; i++) DAG[i].clear(), DAGP[i].clear(); memset(s, 0, sizeof(s)); for(int i = 1; i <= n; i++) { x = tja.color[i]; for(int j = 0; j < G[i].size(); j++) { int u = G[i][j]; y = tja.color[u]; if(x != y) { DAG[x].push_back(y); DAGP[x].push_back(P[i][j]); } else { s[x] += calc(P[i][j]); } } } memset(dp, 0, sizeof(dp)); int start; cin >> start; start = tja.color[start]; dp[start] = s[start]; while(!q.empty()) q.pop(); memset(flag, false, sizeof(flag)); q.push(start); flag[start] = true; while(!q.empty()) { int u = q.front(); q.pop(); flag[u] = false; for(int i = 0; i < DAG[u].size(); i++) { int v = DAG[u][i]; if(dp[v] < dp[u] + DAGP[u][i] + s[v]) { dp[v] = dp[u] + DAGP[u][i] + s[v]; if(!flag[v]) { q.push(v); flag[v] = true; } } } } lint ans = 0; for(int i = 0; i < nn; i++) ans = max(ans, dp[i]); cout << ans << endl; } return 0;}