Atcoder 刷题

1973. Iroha's Obsession

题意：给你一个小于1e4的正整数n，和一个合法digit集合（保证至少有一个非0 digit合法）。称一个数字合法，当且仅当它所包含digit都合法，让你找出一个不小于n的最小合法数字。

观察：因为至少有一个合法的非0digit，那么至少 11111, 22222, ...., 99999 当中有一个合法，所以，答案不会超过 99999。

方法：

1. 直接暴力枚举ans，然后判断ans是否可行即可。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define mp make_pair
 5 #define pb push_back
 6 
 7 typedef long long ll;
 8 typedef pair<int, int> ii;
 9 typedef pair<ll, ll> l4;
10 
11 
12 bool valid[10];
13 inline bool solve(int n)
14 {
15   while (n)
16     {
17       if (!valid[n%10])
18     return false;
19       n /= 10;
20     }
21   return true;
22 }
23 int main()
24 {
25   int n, k;
26   scanf("%d %d", &n, &k);
27   memset(valid, 1, sizeof(valid));
28   for (int i = 0; i < k; ++i)
29     {
30       int x;
31       scanf("%d", &x);
32       valid[x] = false;
33     }
34   while (!solve(n))
35     ++n;
36   printf("%d
", n);
37 }

View Code

2. 其实可以从高位到低位找到第一个不合法的位置，更改这个位置之后，它后面的数位都变成了0，那么一定都会取最小的合法digit。所以只需要找出这个位置就好了。注意可能会有向前进位的情况，处理一下。如果预处理出nxt[i] = 不小于i的最小合法digit, 0 <= i <= 9, 那么算法就是O(length of n)。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define mp make_pair
 5 #define pb push_back
 6 
 7 typedef long long ll;
 8 typedef pair<int, int> ii;
 9 typedef pair<ll, ll> l4;
10 
11 
12 
13 vector<char> vs;
14 char s[100001];
15 int k;
16 deque<char> dq;
17 int nxt[10];
18 bool forbid[10]={0};
19 int main()
20 {
21   scanf("%s %d", s, &k);
22   for (int i = 0; i < k; ++i)
23     {
24       int x;
25       scanf("%d", &x);
26       forbid[x] = true;
27     }
28   //preprocess nxt[10]
29   {
30     int p = 0;
31     for (int i = 0; i < 10; ++i)
32       {
33     if (p < i)
34       p = i;
35     while (p < 10 && forbid[p])
36       ++p;
37     if (p == 10)
38       nxt[i] = -1;
39     else
40       nxt[i] = p;
41       }
42   }
43   int len = strlen(s);
44   for (int i = 0; i < len; ++i)
45     dq.push_back(s[i]);
46   for (int i = 0; i < dq.size(); ++i)
47     {
48       if (nxt[dq[i]-'0'] == -1)
49     {
50       int pos = i;
51       --i;
52       while (i >= 0)
53         {
54           if (dq[i] < '9' && nxt[dq[i]-'0'+1]!=-1)
55         {
56           dq[i] = nxt[dq[i]-'0'+1]+'0';
57           break;
58         }
59           --i;
60         }
61       if (i < 0)
62         {
63           for (int j = 0; j < dq.size(); ++j)
64         dq[j] = '0'+nxt[0];
65           dq.push_front(nxt[1]+'0');
66         }
67       else
68         {
69           for (int j = i+1; j < dq.size(); ++j)
70         dq[j] = nxt[0]+'0';
71         }
72       break;
73     }
74       else if (nxt[dq[i]-'0']+'0' > dq[i])
75     {
76       dq[i] = nxt[dq[i]-'0']+'0';
77       for (int j = i+1; j < dq.size(); ++j)
78         dq[j] = nxt[0]+'0';
79       break;
80     }
81     }
82   for (int i = 0; i < dq.size(); ++i)
83     putchar(dq[i]);
84   puts("");
85 }

View Code

1974. Iroha and Haiku

题意：给你一个h*w的board和左下角一个a*b的禁止区域(1 <= a < h, 1 <= b < w, 1 <= w, h, <= 1e5)，从左上角出发，每次只能向下或向右走，不能走出棋盘。走到右下角的方法数mod 1e9+7。

观察：可以把board分成(h-a)* w 和 a*(w-b) 两个长方形，这样在只需要考虑从第一个长方形进入第二个长方形的位置，在两个长方形内的路线方法数就是C(长+宽-2，长-1）。

方法：

把board分成(h-a)* w 和 a*(w-b) 两个长方形，然后枚举第一个长方形和第二个长方形相邻的部分，分别计算两个长方形内到达这个相邻位置的方法数，然后相乘，累加到答案

注意！：factorial的大小可能超过1e5!!!!

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define mp make_pair
 5 #define pb push_back
 6 
 7 typedef long long ll;
 8 typedef pair<int, int> ii;
 9 typedef pair<ll, ll> l4;
10 
11 
12 const int maxn = 2e5+1, mod = 1e9+7;
13 ll f[maxn], inv[maxn];
14 ll power(ll base, ll p)
15 {
16   ll ret = 1;
17   while (p)
18     {
19       if (p&1)
20     ret = ret * base % mod;
21       base = base * base % mod;
22       p >>= 1;
23     }
24   return ret;
25 }
26 ll h, w, a, b;
27 ll cb(ll n, ll k)
28 {
29   return f[n] * inv[k] % mod * inv[n-k] % mod;
30 }
31 inline void add(ll &a, ll b)
32 {
33   a = a + b;
34   if (a > mod)
35     a %= mod;
36 }
37 int main()
38 {
39   f[0] = 1;
40   for (ll i = 1; i < maxn; ++i)
41     f[i] = f[i-1] * i % mod;
42   inv[maxn-1] = power(f[maxn-1], mod-2);
43   for (ll i = maxn-1; i >= 1; --i)
44     inv[i-1] = inv[i] * i % mod;
45   scanf("%lld %lld %lld %lld", &h, &w, &a, &b);
46   ll ret = 0;
47   for (ll i = b+1; i <= w; ++i)
48     add(ret, cb(h-a+i-2, h-a-1)*cb(a+w+1-i-2, a-1)%mod);
49   printf("%lld
", ret);
50 }

View Code

1975. Iroha and Haiku

题意：不是很好解释。大体就是，给定x, y, z (1<= x, z <= 5, 1<= y <= 7)，对于一个只由1-10构成的数列，如果存在某个连续子数列，使得可以把这个子数列分成三部分，并且从左到右各部分的元素和为x, y, z，那么就说这个数列是好的。比如x = 5, y = 7, z = 5, 那么数列1, 2, 3, 3, 4, 5就是好的，因为它从第二个元素到最后一个元素的子数列满足2+3 = 5, 3+4 = 7, 5 = 5。下面就是给你n<=40, x, y, z，让你求出好的数列的个数mod 1e9+7。

观察：比较容易想到反向求解，求不好的数列，然后再用好数列的个数 = 10^n - 不好数列的个数，得到答案。而且对于字符串有一类题目，给定禁止串，求长度为n的串有多少种之类的，和这题的限制很像，我们可以想到定义状态dp(len, tail)，表示当前长度为len，尾部的若干各元素是tail的不好的数列的个数（这里的tail是一个数列）。但是tail的表示和合法性判断都不是很好做。

方法：（看了题解，但是是日文的，看的不是很懂，如果有理解不对的地方，或是可以改进的地方，请大家指出）

学到了！用二进制数 1 表示 1， 10 表示 2 ,..., 10000表示5, ..., 1000000000 表示10。即一个数i可以用1加上i-1各0表示，就把这种方法成为特殊表示把。那么可以发现，任意几个相邻的数的特殊表示相连，一定包含了这几个数和的特殊表示。比如 2和3相邻，特殊表示为：10100, 5的特殊表示为10000，被10100包含。所以就可以把tail通过这种特殊表示用二进制数来储存，并且可以快速判断是否合法（是否包含x, y, z)。同时注意到x+y+z <= 17，可以只考虑特殊表示的最后18位，2^18不会内存爆炸。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define mp make_pair
 5 #define pb push_back
 6 
 7 typedef long long ll;
 8 typedef pair<int, int> ii;
 9 typedef pair<ll, ll> l4;
10 
11 
12 const int maxn = 20;
13 int x, y, z;
14 int dp[2][1<<maxn] = {0};
15 int f = 0;
16 const int mod = 1e9+7;
17 inline void add(int &a, int b)
18 {
19   a += b;
20   if (a >= mod)
21     a %= mod;
22 }
23 int n;
24 int mask;
25 bool work[1<<maxn] = {0};
26 int main()
27 {
28   scanf("%d", &n);
29   scanf("%d %d %d", &x, &y, &z);
30   int bit = ((((1<<x)+1)<<y)+1)<<(z-1);
31   mask = (1<<(x+y+z))-1;
32   for (int i = 0; i <= mask; ++i)
33     {
34       work[i] = true;
35       int tmp = i;
36       while (tmp)
37     {
38       if ((tmp&bit)==bit)
39         {
40           work[i] = false;
41           break;
42         }
43       tmp >>= 1;
44     }
45     }
46   f = 0;
47   dp[f][0] = 1;
48   for (int i = 0; i < n; ++i)
49     {
50       f ^= 1;
51       memset(dp[f], 0, (mask+1)*sizeof(int));
52       for (int j = 0; j <= mask; ++j)
53     if (work[j])
54       for (int d = 1; d <= 10; ++d)
55         {
56           int nxt = ((j<<1)|1)<<(d-1);
57           nxt &= mask;
58           if (work[nxt])
59         add(dp[f][nxt], dp[f^1][j]);
60         }
61     }
62   int ans = 0;
63   for (int i = 0; i <= mask; ++i)
64     add(ans, dp[f][i]);
65   ll tot = 1;
66   for (int i = 0; i < n; ++i)
67     tot = tot * 10 % mod;
68   tot -= ans;
69   tot %= mod;
70   if (tot < 0)
71     tot += mod;
72   ans = tot;
73   printf("%d
", ans);
74   
75     
76       
77 }

View Code

1976. Iroha Loves Strings

题意：

观察：

方法：

1977. Iroha and Haiku (ABC Edition)

题意：给你三个数a, b, c，让你判断可不可以通过重新排列顺序使三个数变成5, 7, 5

方法：直接暴力。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define mp make_pair
 5 #define pb push_back
 6 
 7 typedef long long ll;
 8 typedef pair<int, int> ii;
 9 typedef pair<ll, ll> l4;
10 
11 
12 int main()
13 {
14   vector<int> v(3);
15   for (auto &e : v)
16     scanf("%d", &e);
17   sort(v.begin(), v.end());
18   vector<int> ans({5, 5, 7});
19   puts(ans==v?"YES":"NO");
20 }

View Code

1978. Iroha Loves String (ABC Edition)

题意：给你n<=100个长度均为L<=100的string，记录为s[1-n]，让你把他们重新排列，使得str = s[1] + s[2] +...+ s[n]的字典序最小。

观察：经典的考虑两个相邻位置的交换是否可以使答案更优。

方法：

考虑答案中相邻的两个string, s[i] 和 s[i+1]。如果s[i]+s[i+1] > s[i+1]+s[i]，那么把两者交换之后答案的字典恤会更变得更小。因为每个s[j] 的长度都是L，所以s[i]+s[i+1] > s[i+1]+s[i] 和 s[i] > s[i+1] 是等价的。所以只需要把s[] 排一边序，然后一个个输出就好了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define mp make_pair
 5 #define pb push_back
 6 
 7 typedef long long ll;
 8 typedef pair<int, int> ii;
 9 typedef pair<ll, ll> l4;
10 
11 
12 int main()
13 {
14   ios::sync_with_stdio(false);
15   cin.tie(0);
16   int n, l;
17   cin >> n >> l;
18   vector<string> vs(n);
19   for (auto &e : vs)
20     cin >> e;
21   sort(vs.begin(), vs.end());
22   for (auto &e : vs)
23     cout << e;
24   cout << '
';
25 }

View Code

1979. BBQ easy

题意：给你n<=100对木棒，每个木棒的长度都是不超过100的正整数。下面让你把这2*n个木棒配对，每一对木棒所能承载的肉量等于两根中较短那根木棒的长度，问你最优配对下一共能承载多少肉。

观察：贪心

方法：排序，然后贪心即可。

贪心的证明可以先证明最小的两根配对比不会比不让最小的两根配对差，然后问题规模n变为n-1, 数学归纳就好了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define mp make_pair
 5 #define pb push_back
 6 
 7 typedef long long ll;
 8 typedef pair<int, int> ii;
 9 typedef pair<ll, ll> l4;
10 
11 int main()
12 {
13   int n;
14   scanf("%d", &n);
15   vector<int> L(2*n);
16   for (auto &e : L)
17     scanf("%d", &e);
18   sort(L.begin(), L.end());
19   int ans = 0;
20   for (int i = 0; i < 2*n; i += 2)
21     ans += L[i];
22   printf("%d
", ans);
23 }

View Code

1980. Mysterious light

题意：从一个正三角形的某个位置向其内部发出光线，光线遇到正三角形的边或者自己过去的轨迹都会反射，直到光线射回初始点。让你求光路的长度。

观察：模拟一下，可以发现存在子问题。

方法：可以发现存在一个可以递归求解的子问题，就是光在一个平行四边形区域内走的路程。然后一个类似于Euclidean GCD的函数。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define mp make_pair
 5 #define pb push_back
 6 
 7 typedef long long ll;
 8 typedef pair<int, int> ii;
 9 typedef pair<ll, ll> l4;
10 
11 
12 ll solve(ll x, ll n)
13 {
14   if (n%x==0)
15     {
16       return 2*n-x;
17     }
18   else
19     {
20       ll ret = (n/x)*x*2+solve(n%x, x);
21       return ret;
22     }
23 }
24 
25 ll n, x;
26 ll solve()
27 {
28   return n + solve(x, n-x);
29 }
30 
31 int main()
32 {
33   scanf("%lld %lld", &n, &x);
34   printf("%lld
", solve());
35 }

View Code

题解指出有一个公式：ans = 3*(n-gcd(n, x))，还没有看懂。

1981. Shorten Diameter

题意：给你一颗大小为n<=2000的树，同时给你一个k。问你最少删多少点，可以让剩下的图是一个直径不超过k的树。

观察：n比较小，可以枚举直径的中心位置。分k奇偶讨论。k为偶数的时候，枚举中心点，然后保留的点到中心点的距离都不能超过k/2；如果为奇数，就枚举中心边。

方法：枚举中心元素，dfs就好了，O(n^2)

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <vector>
 7 #include <unordered_map>
 8 //#include <bits/stdc++.h>
 9 #include <cassert>
10 #include <map>
11 #include <bitset>
12 using namespace std;
13 
14 #define pb push_back
15 #define mp make_pair
16 typedef long long ll;
17 typedef unsigned long long ull;
18 typedef pair<int, int> ii;
19 
20 const int maxn = 2e3+1;
21 int n, k;
22 vector<int> g[maxn];
23 int dfs(int cur, int pa, int dis, int k)
24 {
25   int ret = 1;
26   if (dis < k)
27     for (auto nxt : g[cur])
28       if (nxt != pa)
29     ret += dfs(nxt, cur, dis+1, k);
30   return ret;
31 }
32 
33 int main()
34 {
35   scanf("%d %d", &n, &k);
36   for (int i = 0; i < n-1; ++i)
37     {
38       int u, v;
39       scanf("%d %d", &u, &v);
40       g[u].pb(v);
41       g[v].pb(u);
42     }
43   int ans = n;
44   if (k%2 == 0)
45     {
46       for (int i = 1; i <= n; ++i)
47     {
48       int tmp = dfs(i, 0, 0, k/2);
49       tmp = n-tmp;
50       if (tmp < ans)
51         ans = tmp;
52 
53     }
54     }
55   else
56     {
57       for (int i = 1; i <= n; ++i)
58     for (auto nxt : g[i])
59       if (nxt > i)
60         {
61           int tmp = dfs(i, nxt, 0, k/2) + dfs(nxt, i, 0, k/2);
62           tmp = n-tmp;
63           if (tmp < ans)
64         ans = tmp;
65         }
66     }
67   printf("%d
", ans);
68 }

View Code

这道题n比较大的时候（比如1e5）该怎么做呢？

1982. Arrays and Palindrome

题意：

观察：

方法：

1983.

1984.

1995. Range Product

题意：给你两个int a, b，a <= b, 问你把a, a+1, ...., b-1, b都乘起来，乘积是正是负还是0。

观察：当且仅当[a, b] 有0的时候乘积才会是0，不然只有当区间内负数个数为奇数的时候，乘积为负，不然就是正。

方法：直接判断

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <vector>
 7 #include <unordered_map>
 8 //#include <bits/stdc++.h>
 9 #include <cassert>
10 #include <map>
11 #include <bitset>
12 using namespace std;
13 
14 #define pb push_back
15 #define mp make_pair
16 typedef long long ll;
17 typedef unsigned long long ull;
18 typedef pair<int, int> ii;
19 
20 
21 int cal(int x)
22 {
23   if (x >= 0)
24     return 0;
25   return -x;
26 }
27 
28 int main()
29 {
30   int a, b;
31   scanf("%d %d", &a, &b);
32   if (a <= 0 && 0 <= b)
33     puts("Zero");
34   else
35     {
36       int cnt = cal(a)-cal(b+1);
37       if (cnt%2==0)
38     puts("Positive");
39       else
40     puts("Negative");
41     }
42 }

View Code

想了下其实可以通过负数边界的奇偶性来判断负数个数的奇偶性。

1996. Box and Ball

题意：给你n <- 1e5个盒子。初始时第一个盒子装了一个红球，剩下的盒子每个盒子装了一个白球。下面给你m<=1e5次操作，每次从一个盒子x中随机取一个球放到盒子y中。问你最终有多少个盒子可能装了红球。

观察：因为问的是“可能”，我们每次把红球放进一个盒子，就可以看作把这个盒子里所有的球都染成了红色。

方法：用has[] 标记该盒子里是否可能有红球。直接模拟做就好了，注意一个盒子被掏空时，要把has[]设为false。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <vector>
 7 #include <unordered_map>
 8 //#include <bits/stdc++.h>
 9 #include <cassert>
10 #include <map>
11 #include <bitset>
12 using namespace std;
13 
14 #define pb push_back
15 #define mp make_pair
16 typedef long long ll;
17 typedef unsigned long long ull;
18 typedef pair<int, int> ii;
19 
20 const int maxn = 1e5+1;
21 int n, m;
22 int cnt[maxn];
23 bool has[maxn];
24 int main()
25 {
26 
27   int n, m;
28   scanf("%d %d", &n, &m);
29   fill(cnt+1, cnt+n+1, 1);
30   has[1] = 1;
31   for (int i = 0; i < m; ++i)
32     {
33       int x, y;
34       scanf("%d %d", &x, &y);
35       if (has[x])
36     has[y] = true;
37       --cnt[x];
38       ++cnt[y];
39       if (cnt[x] == 0)
40     has[x] = 0;
41     }
42   int ans = 0;
43   for (int i = 1; i <= n; ++i)
44     ans += has[i];
45   printf("%d
", ans);
46 }

View Code

1997. Knot Puzzle

题意：给你n (2 <= n<= 1e5)段绳子，第i段绳子长度为a[i] <= 1e9。一开始，绳子通过结点顺序链接行程绳索，即第i根的右端通过结点连着第i+1根的左端。告诉你，当一根绳索长度不小于L(<=1e9)的时候，你可以断开该绳子上任意一个结点，使得绳索分为两段新的绳索。下面问你，是否能将绳索分为原来的n段绳子。如果可以，请给出方案。

观察：可以想到，如果有两段相邻的绳子长度之和不小于L，那么我们就可以这两段绳子为基准，一步步断开最外侧的结点，最后再断开这两段绳子间的结点。那么这个条件是否是必要的呢？通过思考得到，应该是必要的。反证，如果任意两段相邻的绳子长度之和都小于L，而且能够达成题意的目标，那么最后一步我们一定会得到一段绳索，它是由两个相邻绳子组成，那么我们将无法切断它，因为相邻两段绳子的长度之和小于L，所以无法达成目标，与假设相悖。

方法：枚举找出上述方法中的基准，然后从外层向内一个个切断，最后再把基准切开。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <vector>
 7 #include <unordered_map>
 8 //#include <bits/stdc++.h>
 9 #include <cassert>
10 #include <map>
11 #include <bitset>
12 using namespace std;
13 
14 #define pb push_back
15 #define mp make_pair
16 typedef long long ll;
17 typedef unsigned long long ull;
18 typedef pair<int, int> ii;
19 
20 
21 
22 const int maxn = 1e5+1;
23 int n, a[maxn], l;
24 
25 int main()
26 {
27   scanf("%d %d", &n, &l);
28   for (int i = 0; i < n; ++i)
29     {
30       scanf("%d", a+i);
31     }
32   int tar = -1;
33   for (int i = 0; i < n-1; ++i)
34     if (a[i]+a[i+1]>=l)
35       {
36     tar = i;
37     break;
38       }
39   if (tar == -1)
40     {
41       puts("Impossible");
42       return 0;
43     }
44   puts("Possible");
45   tar += 1;
46   for (int i = 1; i < tar; ++i)
47     printf("%d
", i);
48   for (int i = n-1; i > tar; --i)
49     printf("%d
", i);
50   printf("%d
", tar);
51 }

View Code

1998. Stamp Rally

题意：给一个n<=1e5个点，m<=1e5条边的无向图。q<=1e5个询问，每次形如x, y, z （1<= x, y, z <= n)，表示从x或者从y沿边扩展到大小为z的子图中（包含x和y的大小为z的子图，而且每个点在子图中必须与x或者y联通），所包含的路径最大编号最小可以是多少。

观察：最优性问题转化成判定性问题，即只考虑前i条边，是否可以满足存在一个由x，y扩展的大小为z的子图。我们只需要维护dsu，不断加边，如果一个时刻，x和y所在联通分量的大小之和不小于z，那么就存在一个大小刚好为z的子图。如果只有一个询问，把边按照从小到大的顺序加进去，并且每次加完检查是否存在合法子图就好，这样单次查询O(n)。但是询问多组，我们想到如果可以快速的二分答案，那么这样总时间就是O(q*log(n))。但是每次二分判定需要特殊的数据结构记录下每一个时刻（即加完一条边）dsu的情况（可持久化？），不容易实现。所以我们想到整体来做，大体就是整体二分的思想。

方法：考虑一个函数 solve({q}, ansl, ansr, depth) 表示当前{q}中询问的答案所在的范围是[ansl, ansr]（depth是二分的深度，辅助接下来的解释用的），那么另ansmid = (ansl+ansr)/2。我们把ansmid之前的边merge一下，然后对于{q}中的每个询问，检查一下当前x,y,z是否有解；有解的话把该询问放到{qleft}, 不然放到{qright}。然后递归求解solve({qleft}, ansl, ansmid, depth+1), solve({qright}, ansmid+1, ansr, depth+1)。注意在同一个depth（二分树的同一个深度），所有边只需被merge一次，所以我们可以按照深度顺序来处理solve()函数，大致就是bfs。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <vector>
  7 #include <unordered_map>
  8 //#include <bits/stdc++.h>
  9 #include <cassert>
 10 #include <map>
 11 #include <bitset>
 12 using namespace std;
 13 
 14 #define pb push_back
 15 #define mp make_pair
 16 typedef long long ll;
 17 typedef unsigned long long ull;
 18 typedef pair<int, int> ii;
 19 
 20 
 21 const int maxn = 1e5+1;
 22 int n, m, qcnt;
 23 vector<int> g[maxn];
 24 int p[maxn], cnt[maxn];
 25 void clear()
 26 {
 27     for (int i = 1; i <= n; ++i)
 28         p[i] = i, cnt[i] = 1;
 29 }
 30 int pa(int id)
 31 {
 32     return id==p[id]?id:p[id]=pa(p[id]);
 33 }
 34 void merge(int x, int y)
 35 {
 36     x = pa(x);
 37     y = pa(y);
 38     if (x != y)
 39     {
 40         cnt[y] += cnt[x];
 41         p[x] = y;
 42     }
 43 }
 44 struct Query
 45 {
 46     int l, r, z, id;
 47     inline void read(int i)
 48     {
 49         scanf("%d %d %d", &l, &r, &z);
 50         id = i;
 51     }
 52 } q[maxn];
 53 int ans[maxn];
 54 ii e[maxn];
 55 int main()
 56 {
 57     scanf("%d %d", &n, &m);
 58     for (int i = 1; i <= m; ++i)
 59     {
 60         scanf("%d %d", &e[i].first, &e[i].second);
 61     }
 62     scanf("%d", &qcnt);
 63     for (int i = 0; i < qcnt; ++i)
 64         q[i].read(i);
 65     queue<Query> que;
 66     que.push((Query){0, qcnt-1, 1, m});
 67     int tot = 0;
 68     while (!que.empty())
 69     {
 70         clear();
 71         int sz = que.size();
 72         int ptr = 1;
 73 //        cerr << "level " << ++tot << endl;
 74         for (int t = 0; t < sz; ++t)
 75         {
 76             auto cur = que.front();
 77             que.pop();
 78 //            cerr << "solve " << " " << cur.l << " " << cur.r << " " << cur.z << " " << cur.id << endl;
 79             if (cur.z == cur.id)
 80             {
 81                 for (int i = cur.l; i <= cur.r; ++i)
 82                     ans[q[i].id] = cur.z;
 83                 continue;
 84             }
 85             int tm = (cur.z+cur.id)>>1;
 86             while (ptr <= tm)
 87             {
 88                 merge(e[ptr].first, e[ptr].second);
 89                 ++ptr;
 90             }
 91             int l = cur.l, r = cur.r;
 92 //            cerr << "till " << tm << endl;
 93             for (int i = l; i <= r; ++i)
 94             {
 95                 int a = q[i].l, b = q[i].r;
 96                 if ((pa(a)==pa(b) && cnt[pa(a)] >= q[i].z) || (pa(a) != pa(b) && cnt[pa(a)]+cnt[pa(b)]>=q[i].z))
 97                 {
 98 //                    cerr << a << " " << b << " cnt >= " << q[i].z << endl;
 99                 }
100                 else
101                 {
102 //                    cerr << a << " " << b << " cnt < " << q[i].z << endl;
103                     swap(q[i--], q[r--]);
104                 }
105             }
106             if (cur.l <= r)
107                 que.push((Query){cur.l, r, cur.z, tm});
108             if (r+1<=cur.r)
109                 que.push((Query){r+1, cur.r, tm+1, cur.id});
110         }
111     }
112     for (int i = 0; i < qcnt; ++i)
113         printf("%d
", ans[i]);
114 }

View Code

1999.

2000.

2001. Wanna go back home

题意：给你一个长度不超过1000的string，由NWSE组成，意思为向某个方向走任意positive长度的距离。问你有没有可能回到原地。

观察：因为向一个方向走的距离可以任选，所以只要一个维度上正反两个方向都出现过，那就一定可以走回0。

方法：统计各个方向是否出现，同一个维度上两个方向必须同时出现或者同时不出现，否则无法走回原地。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define mp make_pair
 5 #define pb push_back
 6 
 7 typedef long long ll;
 8 typedef pair<int, int> ii;
 9 typedef pair<ll, ll> l4;
10 
11 bool vis[300] = {0};
12 char str[1001];
13 int main()
14 {
15   char *s = str;
16   scanf("%s", s);
17   while (*s)
18     {
19       vis[*s] = true;
20       ++s;
21     }
22   puts((vis['N']^vis['S'])||(vis['E']^vis['W'])?"No":"Yes");
23 }

View Code

2002. Simplified mahjong

题意：告诉你n<=1e5种牌，每种牌的个数A[i] <=1e9。然后如果牌号之差不超过1，那么两个牌可以组成一个对子。问你最多可以租多少个对子。

观察：贪心可行，从牌号最小的牌开始，剩下的牌就留着和下个编号的牌配对。证明也是可以反证，找到编号最小的未配对的牌，假设有比他小1的未配对的牌，那么可以产生新的对子；如果有和他编号相同但是和比他大一号的牌配对的牌，那么拆散他俩，让两个编号相同的牌配对，不会使原来的对数减少。如果有比他编号大的牌，进行类似的操作。然后会发现我们的配对方式不会使答案变差。

方法：按照思路实现即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define mp make_pair
 5 #define pb push_back
 6 
 7 typedef long long ll;
 8 typedef pair<int, int> ii;
 9 typedef pair<ll, ll> l4;
10 
11 int n;
12 int main()
13 {
14   ll ans = 0, last = 0, a;
15   scanf("%d", &n);
16   for (int i = 0; i < n; ++i)
17     {
18       scanf("%lld", &a);
19       ll take = min(last, a);
20       ans += take;
21       a -= take;
22       ans += a/2;
23       last = a%2;
24     }
25   printf("%lld
", ans);
26 
27 }

View Code

3xxx. Multiple Gift

题意：给你1<= x <= y <= 1e18，让你找出一个最长的序列A，使得 x <= A[i] <= y 并且 A[i+1] % A[i] == 0。

观察：可以贪心。

方法：去x, 2*x, 4*x, ... 直到突破天际。复杂度是log2(y) 的。浪一点可以推个公式，答案是满足x * 2^n > y 最小的n，即floor(log2(y/x)+1)

3xxx. Wide Flip

题意：给你一个长度为n<= 1e5的01串。对于一个K，你可以反转任意长度大于等于k区间内的数字。问你能使原来01串全变成0的最大k是多少。

观察：有点难搞，猜测答案存在单调性以至于可以二分。单调性比较明显，因为对于任意的k = k1, 如果可以达到目标，那么k = k2 < k1 也一定能达到目标，因为k = k1 所对应的操作集合是k = k2对应操作集合的子集。下面就是考虑该如何短时间内判定。设当前k = mid, 01串从1开始编号（1-indexed) ，那么对于[1, n-mid+1] 的位置，我们从左到右贪心的反转，那么每次反转多长的区间呢？我使用的长度为mid的区间, 即[i, i+mid-1]，但好像用最长的区间也没有关系，即[i, n]。下面对于[n-mid+2, n]的位置，我们希望可以在不改变之前元素的前提下，改变他们的值。根据第一个样例可以发现，有一种特殊的操作，任意可以更改“靠后”位置的值且不影响其他值，比如你想改变第j位的值，那么先反转[j-mid, j]，再反转[j-mid, j-1]。所以，当且仅当 j-mid>=1 时，我们可以任意改变j的值。所以就是检查[n-mid+2, n]里面的值，如果有1的话，看看可不可以通过特殊操作“任意改变”。或者直接看[n-mid+2, mid] 这个区间里是否有1，有1的话就还原不了，没有的话就可以还原。

3xxx. Papple Sort

题意：给你一个长度为n<=2e5的字符串s，只由小写字母组成。下面问你，可否指通过交换相邻的两个字母，把s变成一个回文串。如果可以的话，最少要交换几次？

观察：首先，判断是否能达成比较简单，只需统计各个字母出现次数就好了，能达成回文的充要条件是，至多只有一个字母出现奇数次。下面我们考虑，怎样构造才能使交换次数最小。比赛的时候自己没有证明，想到这么几个点。首先，同一种字母的相对顺序是不会变的；其次，好像先确定最外层元素会容易一点，因为确定了外层元素之后，确定了的元素对未确定的元素就没有影响了。然后取得时候我贪心的取最外层的元素，但是没有证明。题解中给了证明，说两种字符A，B之间的相对位置，只有当ABBA的时候要先取A，BAAB的时候先取B，其他时候都无所谓。

方法：

3xxx. Christmas Tree