首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >“玲珑杯”ACM比赛 Round #12题解&源码

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

作者头像
Angel_Kitty
发布2018-04-08 15:30:25
7320
发布2018-04-08 15:30:25
举报

我能说我比较傻么!就只能做一道签到题,没办法,我就先写下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

“玲珑杯”ACM比赛 Round #12

题目链接: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 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-03-18 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档