我能说我比较傻么!就只能做一道签到题,没办法,我就先写下A题的题解&源码吧,把官方给出的题解贴出来!
A -- Niro plays Galaxy Note 7
Time Limit:1s
Memory Limit:128MByte
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 (|X−i|≤R)
.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
100 5 23
100 8 36
100 9 99
SAMPLE OUTPUT
11
17
11
HINT
1≤T,N≤100
0≤R≤100 1≤X≤N
SOLUTION
题目链接:http://www.ifrog.cc/acm/problem/1106?contest=1014&no=0
分析:这道题就是所谓的签到题,不是很难,能够摧毁的城市是区间 [max(1,X−i),min(X+i,N)],直接输出min(X+i,N)−max(1,X−i)+1即可,题解的那种方式看不太懂,可能是因为我自己没学C++STL,其实就是以一个点为中心,向左区间和右区间分别延伸R个单位,如果超过N或小于0终止!
下面给出AC代码:
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 }
给出官方的STL解法:
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 }
题目链接:http://www.ifrog.cc/acm/problem/1107?contest=1014&no=1
题解:
下面给出AC代码:
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 }
题目链接:http://www.ifrog.cc/acm/problem/1108?contest=1014&no=2
题解:
下面给出AC代码:
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 }
题目链接:http://www.ifrog.cc/acm/problem/1109?contest=1014&no=3
题解:
下面给出AC代码:
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 }
题目链接:http://www.ifrog.cc/acm/problem/1110?contest=1014&no=4
题解:
下面给出AC代码:
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 }