Can I say I’m stupid?! Can only do A sign-in problem, no way, I will first write A problem solution & source bar, the official problem solution posted out!

 

                                    A — Niro plays Galaxy Note 7                   

Time Limit: 1 s

The Memory Limit: 128 mbyte

DESCRIPTION

       

           

Niro, a lovely girl, has bought a Galaxy Note 7 and wants to destroy cities. There are N cities numbered 1… N on a line and each pair of adjacent cities has distance 1. Galaxy Note 7 has its explosion radius R. Niro puts her Galaxy Note 7 in city X and city, I will be destroyed if (I | | X – R) or less

.You must tell Niro how many cities wil be destroyed.

                   

   

       

INPUT

       

           

The first line contains a positive integer T , the number of test cases.

Each of the following T lines contains three integers N, R, X.

OUTPUT

            

Tlines.Each line contains one integer, the answer.

      

SAMPLE INPUT

           

3

May 23 100

100 8 36

100 9 99

SAMPLE OUTPUT

            

11

17

11

    

HINT

           

1 T or less, N 100 or less

0 R 100 1 X or less or less or less or less N * * * *

       

SOLUTION

“Linglong Cup” ACM Round #12

Title link: www.ifrog.cc/acm/problem…

Analysis: Max (1,X− I),min(X+ I,N) = min(X+ I,N)− Max (1,X− I)+1 It’s essentially a point that extends R units to the left and R units to the right, and ends if it’s more than N or less than zero!

Here is the AC code:

1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int T; 6 int n,r,x; 7 int a[1010]; 8 while(scanf("%d",&T)! =EOF) 9 { 10 while(T--) 11 { 12 scanf("%d%d%d",&n,&r,&x); 13 memset(a,0,sizeof(a)); 14 int ans=0; 15 if(x<=n) 16 { 17 for(int i=x; i<=x+r; i++) 18 { 19 if(i<=n) 20 { 21 a[i]=1; 22 } 23 } 24 for(int i=x; i>=x-r; i--) 25 { 26 if(i>=0) 27 { 28 a[i]=1; 29 } 30 } 31 for(int i=1; i<=n; i++) 32 if(a[i]) 33 ans++; 34 printf("%d\n",ans); 35 } 36 } 37 } 38 return 0; 39}Copy the code

The official STL solution is given:

1 #include <cstdio> 2 #include <algorithm> 3 int T, N, R, X; 4 int main() 5 { 6 for (scanf("%d", &T); T--; ) 7 { 8 scanf("%d%d%d", &N, &R, &X); 9 printf("%d\n", std::min(N, X + R) - std::max(1, X - R) + 1); 10 } 11 return 0; 12}Copy the code

 

 

Title link: www.ifrog.cc/acm/problem…

Answer key:

Here is the AC code:

1 #include <cstdio> 2 #include <queue> 3 #include <vector> 4 #include <algorithm> 5 const int INF = 1000000000; 6 class Heap 7 { 8 private : 9 std::priority_queue < int, std::vector < int >, std::greater < int > > inc, dec; 10 void BaseClear() 11 { 12 while (! dec.empty() && inc.top() == dec.top()) 13 { 14 inc.pop(); 15 dec.pop(); 16 } 17 } 18 public : 19 int top() 20 { 21 BaseClear(); 22 return inc.top(); 23 } 24 void del(int x) 25 { 26 dec.push(x); 27 } 28 void push(int x) 29 { 30 inc.push(x); 31 } 32 void clear() 33 { 34 while (! inc.empty()) 35 inc.pop(); 36 while (! dec.empty()) 37 dec.pop(); 38 } 39 bool empty() 40 { 41 BaseClear(); 42 return inc.empty(); 43 } 44 } 45 Q0, Q1; 46 int TC, f0[200001], f1[200001], *F0 = f0 + 100000, *F1 = f1 + 100000, N, C0, C1, N0, N1, E0, E1, TAG0, TAG1; 47 void forward(char option) 48 { 49 if (option == '0') 50 { 51 F0--; 52 F0[1] = (Q1.empty() ? INF : Q1.top()) + TAG1 - TAG0; 53 E0++; 54 Q0.push(F0[1]); 55 while (E0 >= N0) 56 Q0.del(F0[E0--]); 57 E1 = 0; 58 Q1.clear(); 59 } 60 else if (option == '1') 61 { 62 F1--; 63 F1[1] = (Q0.empty() ? INF : Q0.top()) + TAG0 - TAG1; 64 E1++; 65 Q1.push(F1[1]); 66 while (E1 >= N1) 67 Q1.del(F1[E1--]); 68 E0 = 0; 69 Q0.clear(); 70 } 71 else 72 { 73 F0--; 74 F0[1] = (Q1.empty() ? INF : Q1.top()) + TAG1 - TAG0; 75 E0++; 76 F1--; 77 F1[1] = (Q0.empty() ? INF : Q0.top()) + TAG0 - TAG1; 78 E1++; 79 Q0.push(F0[1]); 80 Q1.push(F1[1]); 81 while (E0 >= N0) 82 Q0.del(F0[E0--]); 83 while (E1 >= N1) 84 Q1.del(F1[E1--]); 85 TAG0 += C0; 86 TAG1 += C1; 87 } 88 } 89 int main() 90 { 91 for (scanf("%d", &TC); TC--; ) 92 { 93 F0 = f0 + 100000; 94 F1 = f1 + 100000; 95 TAG0 = TAG1 = 0; 96 Q0.clear(); 97 Q1.clear(); 98 E0 = E1 = 0; 99 scanf("%d%d%d%d%d", &N, &C0, &C1, &N0, &N1); 100 char c = getchar(); 101 while (c ! = '0' && c ! = '1' && c ! = '? ') 102 c = getchar(); 103 if (c == '0') 104 { 105 F0[E0 = 1] = 0; 106 Q0.push(0); 107 } 108 else if (c == '1') 109 { 110 F1[E1 = 1] = 0; 111 Q1.push(0); 112 } 113 else 114 { 115 F0[E0 = 1] = C0; 116 F1[E1 = 1] = C1; 117 Q0.push(C0); 118 Q1.push(C1); 119 } 120 for (int i = 1; i < N; i++) 121 forward(getchar()); 122 int ans = 1000000001; 123 if (! Q0.empty()) 124 ans = std::min(ans, Q0.top() + TAG0); 125 if (! Q1.empty()) 126 ans = std::min(ans, Q1.top() + TAG1); 127 printf("%d\n", ans); 128 } 129 return 0; 130}Copy the code

Title link: www.ifrog.cc/acm/problem…

Answer key:

Here is the AC code:

1 #include <bits/stdc++.h> 2 const int MOD = 1234321237; 3 int F[100001], N, G, a[1000], w[1000]; 4 int gcd(int x, int y) 5 { 6 int r; 7 while (y) 8 { 9 r = x % y; 10 x = y; 11 y = r; 12 } 13 return x; 14 } 15 void DP(int x, int y) 16 { 17 std::vector < int > Div; 18 for (int i = 1; i * i <= x; i++) 19 if (x % i == 0) 20 { 21 Div.push_back(i); 22 if (i * i < x) 23 Div.push_back(x / i); 24 } 25 std::sort(Div.begin(), Div.end()); 26 int L = Div.size(); 27 std::vector < int > Use(L, 0); 28 for (int i = L - 1; ~i; i--) 29 { 30 Use[i] = y / Div[i]; 31 for (int j = i + 1; j < L; j++) 32 if (Div[j] % Div[i] == 0) 33 Use[i] -= Use[j]; 34 } 35 for (int i = G; ~i; i--) 36 { 37 F[i] = 0; 38 for (int j = 0; j < L && Div[j] <= i; j++) 39 F[i] = (F[i] + (long long)F[i - Div[j]] * Use[j]) % MOD; 40 } 41 } 42 int main() 43 { 44 scanf("%d%d", &N, &G); 45 for (int i = 0; i < N; i++) 46 scanf("%d", a + i); 47 for (int i = 0; i < N; i++) 48 scanf("%d", w + i); 49 F[0] = 1; 50 for (int i = 0; i < N; i++) 51 DP(a[i], w[i]); 52 printf("%d\n", F[G]); 53 return 0; 54}Copy the code

Title link: www.ifrog.cc/acm/problem…

Answer key:

Here is the AC code:

1 #include <cstdio> 2 const long long MOD = 1234321237; 3 long long POWER(long long a, long long b) 4 { 5 long long r = 1; 6 for (; b; b >>= 1) 7 { 8 if (b & 1) 9 r = r * a % MOD; 10 a = a * a % MOD; 11 } 12 return r; 13 } 14 long long N; 15 int T; 16 int main() 17 { 18 for (scanf("%d", &T); T--; ) 19 { 20 scanf("%lld", &N); 21 long long F = POWER(4, N - 1) * 3 - POWER(3, N - 1) * 2; 22 long long G = POWER(4, N - 1) * (((N % MOD * 9) - 69) % MOD) + POWER(3, N - 1) * (((N % MOD * 8) + 52) % MOD); 23 G %= MOD; 24 F %= MOD; 25 G %= MOD; 26 F += MOD; 27 G += MOD; 28 F %= MOD; 29 G %= MOD; 30 if (G & 1) 31 G += MOD; 32 G >>= 1; 33 printf("%lld %lld\n", F, G); 34 } 35 return 0; 36}Copy the code

Title link: www.ifrog.cc/acm/problem…

Answer key:

Here is the AC code:

1 #include <cstdio> 2 #include <vector> 3 #include <algorithm> 4 std::vector < int > E[100001], col[100001]; 5 std::vector < std::pair < int, int > > inc[100002], dec[100002]; 6 int N, q[100001], left[100001], right[100001], size[100001], BeiZeng[17][100001], *fa = BeiZeng[0], LOG; // left : DFN; right maximum DFN in its subtree 7 std::vector < int >::iterator ue[100001]; 8 void DFS() 9 { 10 int D = 1, TIME = 1; 11 q[1] = 1; 12 ue[1] = E[1].begin(); 13 left[1] = right[1] = 1; 14 while (D) 15 { 16 if (ue[D] ! = E[q[D]].end() && *ue[D] == fa[q[D]]) 17 ue[D]++; 18 if (ue[D] ! = E[q[D]].end()) 19 { 20 int To = *ue[D]++; 21 fa[To] = q[D]; 22 left[To] = right[To] = ++TIME; 23 q[++D] = To; 24 ue[D] = E[To].begin(); 25 } 26 else 27 { 28 if (D > 1) 29 right[q[D - 1]] = right[q[D]]; 30 D--; 31 } 32 } 33 for (int i = 1; i <= N; i++) 34 size[i] = right[i] - left[i] + 1; 35 while (2 << LOG < N) 36 LOG++; 37 for (int i = 1; i <= LOG; i++) 38 for (int j = 1; j <= N; j++) 39 BeiZeng[i][j] = BeiZeng[i - 1][BeiZeng[i - 1][j]]; 40 } 41 int lowest(int u, int v) 42 { 43 for (int i = LOG; ~i; i--) 44 if (BeiZeng[i][u] && size[BeiZeng[i][u]] < size[v]) 45 u = BeiZeng[i][u]; 46 return u; 47 } 48 inline void bar(int u, int d, int l, int r) 49 { 50 inc[u].push_back(std::make_pair(l, r)); 51 if (d < N) 52 dec[d + 1].push_back(std::make_pair(l, r)); 53 } 54 void conflict(int u, int v) 55 { 56 if (size[u] < size[v]) 57 std::swap(u, v); 58 if (left[u] <= left[v] && right[v] <= right[u]) // u is v's ancestor 59 { 60 int lw = lowest(v, u); 61 if (left[lw] > 1) 62 { 63 bar(left[v], right[v], 1, left[lw] - 1); 64 bar(1, left[lw] - 1, left[v], right[v]); 65 } 66 if (right[lw] < N) 67 { 68 bar(left[v], right[v], right[lw] + 1, N); 69 bar(right[lw] + 1, N, left[v], right[v]); 70 } 71 } 72 else 73 { 74 bar(left[u], right[u], left[v], right[v]); 75 bar(left[v], right[v], left[u], right[u]); 76 } 77 } 78 int MIN[262145], TAG[262145], NUM[262145]; // NUM[] : the number of elements which reach MIN[] 79 void INC(int p, int l, int r, int L, int R, int w) 80 { 81 if (L <= l && r <= R) 82 { 83 MIN[p] += w; 84 TAG[p] += w; 85 return; 86 } 87 if (TAG[p]) 88 { 89 MIN[p + p] += TAG[p]; 90 MIN[p + p + 1] += TAG[p]; 91 TAG[p + p] += TAG[p]; 92 TAG[p + p + 1] += TAG[p]; 93 TAG[p] = 0; 94 } 95 int m = (l + r) >> 1; 96 if (L <= m) 97 INC(p + p, l, m, L, R, w); 98 if (R > m) 99 INC(p + p + 1, m + 1, r, L, R, w); 100 MIN[p] = std::min(MIN[p + p], MIN[p + p + 1]); 101 NUM[p] = (MIN[p + p] == MIN[p] ? NUM[p + p] : 0) + (MIN[p + p + 1] == MIN[p] ? NUM[p + p + 1] : 0); 102 } 103 inline int ZERONUM() 104 { 105 return MIN[1] == 0 ? NUM[1] : 0; 106 } 107 long long ANS; 108 void Treeinit(int p = 1, int l = 1, int r = N) 109 { 110 NUM[p] = r - l + 1; 111 if (l < r) 112 { 113 int m = (l + r) >> 1; 114 Treeinit(p + p, l, m); 115 Treeinit(p + p + 1, m + 1, r); 116 } 117 } 118 int main() 119 { 120 scanf("%d", &N); 121 for (int i = 1, u, v; i < N; i++) 122 { 123 scanf("%d%d", &u, &v); 124 E[u].push_back(v); 125 E[v].push_back(u); 126 } 127 for (int i = 1, c; i <= N; i++) 128 { 129 scanf("%d", &c); 130 col[c].push_back(i); 131 } 132 DFS(); 133 for (int i = 1; i <= N; i++) 134 for (std::vector < int >::iterator x = col[i].begin(); x ! = col[i].end(); x++) 135 for (std::vector < int >::iterator y = x + 1; y ! = col[i].end(); y++) 136 conflict(*x, *y); 137 Treeinit(); 138 for (int i = 1; i <= N; i++) 139 { 140 for (std::vector < std::pair < int, int > >::iterator j = inc[i].begin(); j ! = inc[i].end(); j++) 141 INC(1, 1, N, j -> first, j -> second, 1); 142 for (std::vector < std::pair < int, int > >::iterator j = dec[i].begin(); j ! = dec[i].end(); j++) 143 INC(1, 1, N, j -> first, j -> second, -1); 144 ANS += ZERONUM(); 145 } 146 printf("%lld\n", (ANS - N) >> 1); 147 return 0; 148}Copy the code