CodeForces 比赛笔记（1）

本文主要是介绍CodeForces 比赛笔记（1），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics)

A

注意最多只能跳一次。

 1 const int N = 110;
 2 int t, n, l, r, a[N];
 3 
 4 int main()
 5 {
 6     read(t);
 7     while (t--)
 8     {
 9         read(n); l = 1, r = n;
10         for (int i = 1; i <= n; ++i) read(a[i]);
11         while (l < n && a[l + 1]) ++l;
12         while (r > 1 && a[r - 1]) --r;
13         print(l > r ? 0 : r - l), pc('\n');
14     }
15     fwrite(pbuf, 1, pp - pbuf, stdout); return 0;
16 }

B

考虑踢球次数最多的人没踢完的话剩下的球都得自己踢，踢完了剩下的人传着踢就行。

所以答案就是最大的 $a[i]$ 减去其他 $a[i]$ 后的值跟 $1$ 取 $\max$，注意特判全为 $0$ 的情况。

 1 const int N = 1e5 + 10;
 2 int t, n, a[N];
 3 
 4 int main()
 5 {
 6     read(t);
 7     while (t--)
 8     {
 9         read(n);
10         for (int i = 1; i <= n; ++i) read(a[i]);
11         nth_element(a + 1, a + 1, a + n + 1, greater<int>());
12         if (!a[1]) { pc('0'), pc('\n'); continue; }
13         for (int i = 2; i <= n; ++i)
14         {
15             a[1] -= a[i];
16             if (a[1] < 1) break;
17         }
18         if (a[1] < 1) pc('1'), pc('\n');
19         else print(a[1]), pc('\n');
20     }
21     fwrite(pbuf, 1, pp - pbuf, stdout); return 0;
22 }

C

由于是曼哈顿距离，直接将答案拆成行和列的分别求解即可。

 1 const int N = 1e5 + 10;
 2 int n, m;
 3 ll ans, cnt[N], sum[N];
 4 vector<int> a[320];
 5 
 6 int main()
 7 {
 8     read(n, m);
 9     for (int x, i = 1; i <= n; ++i)
10     {
11         a[i].emplace_back(0);
12         for (int j = 1; j <= m; ++j)
13             read(x), a[i].emplace_back(x);
14     }
15     for (int i = 1; i <= n; ++i)
16     {
17         for (int j = 1; j <= m; ++j)
18             ans += cnt[a[i][j]] * i - sum[a[i][j]];
19         for (int j = 1; j <= m; ++j)
20             ++cnt[a[i][j]], sum[a[i][j]] += i;
21     }
22     memset(cnt, 0, sizeof(cnt));
23     memset(sum, 0, sizeof(sum));
24     for (int j = 1; j <= m; ++j)
25     {
26         for (int i = 1; i <= n; ++i)
27             ans += cnt[a[i][j]] * j - sum[a[i][j]];
28         for (int i = 1; i <= n; ++i)
29             ++cnt[a[i][j]], sum[a[i][j]] += j;
30     }
31     print(ans);
32     fwrite(pbuf, 1, pp - pbuf, stdout); return 0;
33 }

D

直接暴力枚举 $y$ 和 $\lfloor\dfrac{x}{y}\rfloor$，判断数组中是否存在 $x$ 但不存在 $\lfloor\dfrac{x}{y}\rfloor$ 即可。

由于枚举的是倍数关系，$\dfrac{n}{1}+\dfrac{n}{2}+\dfrac{n}{3}+\cdots+\dfrac{n}{n}=O(n\log{n})$，所以时间复杂度是正确的。

 1 const int N = 1e6 + 10;
 2 int t, n, c, a[N], cnt[N];
 3 
 4 inline bool check(int y)
 5 {
 6     for (int k = 1; k * y <= c; ++k)
 7     {
 8         int l = k * y - 1, r = Min(k * y + y - 1, c);
 9         if (cnt[r] - cnt[l] && !(cnt[k] - cnt[k - 1])) return false;
10     }
11     return true;
12 }
13 
14 int main()
15 {
16     read(t);
17     while (t--)
18     {
19         read(n, c); bool flag = true;
20         for (int i = 1; i <= n; ++i) read(a[i]), ++cnt[a[i]];
21         for (int i = 1; i <= c; ++i) cnt[i] += cnt[i - 1];
22         sort(a + 1, a + n + 1);
23         for (int i = 1; i <= n; ++i)
24             if (a[i] != a[i - 1] && !check(a[i])) { flag = false; break; }
25         puts(flag ? "Yes" : "No");
26         for (int i = 1; i <= c; ++i) cnt[i] = 0;
27     }
28     fwrite(pbuf, 1, pp - pbuf, stdout); return 0;
29 }

E

F

To be continued...

这篇关于CodeForces 比赛笔记（1）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！