# “玲珑杯”ACM比赛 Round #12题解&源码

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

 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 }

下面给出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 }

 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 }

 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 }

  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 }

0 条评论

• ### UVA 1030 - Image Is Everything【模拟+思维+迭代更新】

题目链接：uva 1030 - Image Is Everything 题目大意：有一个最大为n*n*n的立方体的一个不规整立体，由若干个1*1*1的小正方体构...

• ### “玲珑杯”ACM比赛 Round #13 题解&源码

A ? 题目链接：http://www.ifrog.cc/acm/problem/1111 分析：容易发现本题就是排序不等式， 将A数组与B数组分别排序之后，...

• ### 零基础学贪心算法

本文在写作过程中参考了大量资料，不能一一列举，还请见谅。 贪心算法的定义： 贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上...

• ### agc027D - Modulo Matrix(构造 黑白染色)

构造一个$n * n$的矩阵，要求任意相邻的两个数$a,b$,使得$max(a,b) % min(a,b) \not = 0$

• ### 贪心算法

贪心算法：分阶段的工作，在每个阶段做出当前最好的选择，从而希望得到结果是最好或最优的算法。

• ### 颜色聚合向量

package com.imageretrieval.features; /** * 颜色聚合向量<br> * 参考链接：http://www.docin...

• ### POJ 2594 Treasure Exploration(最小路径覆盖+Floyd)

题意是有n个点，m条单向边，然后在边上放机器人，问最少放多少个机器人能遍历到所有的点。

• ### BZOJ2707: [SDOI2012]走迷宫(期望 tarjan 高斯消元)

显然有$$f[x] = \sum_{y} \frac{f[y]}{deg[x]} + 1$$

• ### 弱校联盟10.3

n对括号最多需要1+2+..+n次交换，当它是)))..(((的形式时，)))(((需要6次，然后把中间两个交换一下，))()((就还需要5次，再交换一次靠近左...

• ### 【USACO 3.2】Magic Squares

4*2个格子分别为 1234 8765 的魔板有3种操作，A：上下两排互换，B：最后一列放到第一列前面，C：中间四个顺时针旋转1格。 现在给出目标状态，...