AtCoder Beginner Contest 120 解题报告-白红宇

AtCoder Beginner Contest 120 解题报告

阅读量：4584 次

发布时间：2019-06-09

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

为啥最近都没有arc啊...

A - Favorite Sound

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define ll long long#define inf 0x3f3f3f3f#define il inlinenamespace io {#define in(a) a = read()#define out(a) write(a)#define outn(a) out(a), putchar('\n')#define I_int llinline I_int read() { I_int x = 0, f = 1; char c = getchar(); 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;}char F[200];inline void write(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]);}#undef I_int}using namespace io;using namespace std;#define N 100010int a, b, c;int main() { in(a), in(b), in(c); printf("%d\n", min(b / a, c));}

B - K-th Common Divisor

显然，就是求gcd的第k小的因子。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define ll long long#define inf 0x3f3f3f3f#define il inlinenamespace io {#define in(a) a = read()#define out(a) write(a)#define outn(a) out(a), putchar('\n')#define I_int llinline I_int read() { I_int x = 0, f = 1; char c = getchar(); 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;}char F[200];inline void write(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]);}#undef I_int}using namespace io;using namespace std;#define N 100010int a, b, k, d[N], tot;int main() { in(a), in(b), in(k); int g = __gcd(a, b); for(int i = 1; i * i <= g; ++i) { if(g % i == 0) { d[++tot] = i; if(g / i != i) d[++tot] = g / i; } } sort(d+1, d + tot + 1); reverse(d + 1, d + tot + 1); printf("%d\n", d[k]);}

C - Unification

栈的经典题。。。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define ll long long#define inf 0x3f3f3f3f#define il inlinenamespace io {#define in(a) a = read()#define out(a) write(a)#define outn(a) out(a), putchar('\n')#define I_int llinline I_int read() { I_int x = 0, f = 1; char c = getchar(); 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;}char F[200];inline void write(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]);}#undef I_int}using namespace io;using namespace std;#define N 100010char s[N];int n, st[N];int main() { scanf("%s", s + 1); n = strlen(s + 1); int ans = 0, top = 0; for(int i = 1; i <= n; ++i) s[i] -= '0'; for(int i = 1; i <= n; ++i) { if(top && s[top] ^ s[i]) {++ans, --top; continue;} s[++top] = s[i]; } printf("%d\n", ans * 2);}

D - Decayed Bridges

正着计数太麻烦了。

考虑最后一条边断掉之后答案肯定是\(n(n-1)/2\)。

用个经典的套路，把删边弄成倒着连边。

那么每次多连一条边，联通的点数就多了\(siz_x*siz_y\)

用\(n(n-1)/2\)减去\(siz_x*siz_y\)即可。

注意longlong。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define ll long long#define inf 0x3f3f3f3f#define il inlinenamespace io {#define in(a) a = read()#define out(a) write(a)#define outn(a) out(a), putchar('\n')#define I_int llinline I_int read() { I_int x = 0, f = 1; char c = getchar(); 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;}char F[200];inline void write(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]);}#undef I_int}using namespace io;using namespace std;#define N 100010int n, m;int a[N], b[N], f[N];ll siz[N];ll ans = 0, sum = 0, res[N];int find(int x) { if(f[x] == x) return x; else return f[x] = find(f[x]);}int main() { in(n), in(m); sum = (ll)(n * (n - 1ll) / 2ll); for(int i = 1; i <= m; ++i) in(a[i]), in(b[i]); for(int i = 1; i <= n; ++i) f[i] = i, siz[i] = 1ll; for(int i = m; i; --i) { res[i] = sum - ans; int x = find(a[i]), y = find(b[i]); if(x != y) { ans += (ll)siz[x] * siz[y]; siz[x] += siz[y]; f[y] = x; } } for(int i = 1; i <= m; ++i) printf("%lld\n", res[i]);}