Educational Codeforces Round 169 (Rated for Div. 2)

2024-08-24 10:52

本文主要是介绍Educational Codeforces Round 169 (Rated for Div. 2),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

       电脑显示屏一闪一闪地感觉要拿去修了,比赛时重启了好几次。

        手速场,E 题没学过 Sprague-Grundy 吃了亏,好在前四题都一发过才不至于掉分。

        Standings:1214

        题目链接:Dashboard - Educational Codeforces Round 169 (Rated for Div. 2) - Codeforces

A. Closest Point

        题意:

        给一个集合表示数轴上的一些点,你需要在数轴上加入一个不同于集合内任何元素的整数点,使得这个点是所有集合内的点最近点,也就是这个点到所有点的路上不能有其他点。

        思路:

        显然只有 n = 2 时且两个点不是相邻的整数才有解。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;int T,n,a[105];int main()
{scanf("%d",&T);while (T --){scanf("%d",&n);for (int i = 1;i <= n;++ i) scanf("%d",&a[i]);sort(a + 1,a + n + 1);int flag = 1;for (int i = 2;i <= n;++ i)if(a[i] - a[i - 1] <= 1){flag = 0;break;}if(n > 2) flag = 0;if(flag) printf("YES\n");else printf("NO\n"); }return 0;
}

B. Game with Doors

        题意:

        有 100 个房间排成一排,相邻房间有门连接,告诉你两个人可能所在的房间区间(是一段连续的子区间),求最少锁上多少间房门能让这两个人所在的房间不能互通。

        思路:

        分类讨论即可,懒得写了。

#include<cstdio>
#include<cstring>
using namespace std;int T,l,r,x,y;int main()
{scanf("%d",&T);while (T --){scanf("%d%d%d%d",&l,&r,&x,&y);int tmp,ans;if(l > x || l == x && r < y) tmp = l,l = x,x = tmp,tmp = r,r = y,y = tmp;if(r < x) ans = 1;else if(r >= x && y >= r) ans = (r - x) + (y > r) + (l < x);else if(r >= x && y < r) ans = (y - x) + (r > y) + (l < x);printf("%d\n",ans);}return 0;
}

C. Splitting Items

        题意:

        给一串数字作为分值,两个人轮流取,总得分分别记作 A 和 B,你可以对原数列进行操作,给任意数量的数字增加一个数,增加的总和不能超过 k ,求 A - B 的最小值。

        思路:

        显然贪心,从大到小排序后,A 肯定会取奇数位上的数字,尽可能地增加偶数位上的数字使 B 更大,但是不能超过前一位 A 取的数,否则这个数就会被 A 拿走。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;#define N 200005int T,n,k,a[N];
long long ans;int cmp(int x,int y) { return x > y ; }int main()
{scanf("%d",&T);while (T --){scanf("%d%d",&n,&k);for (int i = 1;i <= n;++ i) scanf("%d",&a[i]);sort(a + 1,a + n + 1,cmp);ans = 0ll;for (int i = 1;i <= n;++ i){if(i & 1) ans += 1ll * a[i];else{int now = a[i - 1] - a[i];if(k >= now) a[i] = a[i - 1],k -= now;else a[i] += k,k = 0;ans -= 1ll * a[i];}}printf("%lld\n",ans);}return 0;
}

D. Colored Portals

        题意:

        给 n 个城市,城市 i 和 j 之间的距离是 |i - j| ,每个城市有两种传送门,可以通过相同的传送门在城市之间穿梭,有若干个询问找出城市 x 到城市 y 的最短距离。

        思路:

        显然要么直达,要么只中转一次,要么无法到达。

        中转的情况分情况讨论二分查找使得总距离最短的那个城市即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;#define N 200005int T,n,q,ans,a[6][N],c[6],id[N],inv[6];
char s[5];int min(int x,int y) { return x < y ? x : y ; }int find(int k,int x,int y)
{int l,r,mid,now,tmp;l = 1,r = c[k],now = 0;while (l <= r){mid = (l + r) >> 1;if(a[k][mid] > x) now = a[k][mid],r = mid - 1;else l = mid + 1;}if(x < now && now < y) return y - x ;l = 1,r = c[k],now = 0,tmp = 1e9;while (l <= r){mid = (l + r) >> 1;if(a[k][mid] < x) now = a[k][mid],l = mid + 1;else r = mid - 1;}if(now) tmp = min(tmp,x - now + y - now);l = 1,r = c[k],now = 0;while (l <= r){mid = (l + r) >> 1;if(a[k][mid] > y) now = a[k][mid],r = mid - 1;else l = mid + 1;}if(now) tmp = min(tmp,now - x + now - y);return tmp;
}int main()
{for (int i = 0;i < 6;++ i) inv[i] = 5 - i;scanf("%d",&T);while (T --){memset(c,0,sizeof c);scanf("%d%d",&n,&q);for (int i = 1;i <= n;++ i){cin >> s + 1;if(s[1] == 'B' && s[2] == 'G') a[0][++ c[0]] = i,id[i] = 0;if(s[1] == 'B' && s[2] == 'R') a[1][++ c[1]] = i,id[i] = 1;if(s[1] == 'B' && s[2] == 'Y') a[2][++ c[2]] = i,id[i] = 2;if(s[1] == 'G' && s[2] == 'R') a[3][++ c[3]] = i,id[i] = 3;if(s[1] == 'G' && s[2] == 'Y') a[4][++ c[4]] = i,id[i] = 4;if(s[1] == 'R' && s[2] == 'Y') a[5][++ c[5]] = i,id[i] = 5;}while (q --){int x,y,tmp,ix,iy;scanf("%d%d",&x,&y),ans = 1e9;if(x > y) tmp = x,x = y,y = tmp;ix = id[x],iy = id[y];if(ix == inv[iy]){for (int i = 0;i < 6;++ i){if(i == ix || i == iy) continue;ans = min(ans,find(i,x,y));}}else ans = y - x;if(ans == 1e9) printf("-1\n");else printf("%d\n",ans);}}return 0;
}

E. Not a Nim Problem

        题意:

        常规的取石子游戏变形,限制就是只能取和当前堆数互质的数目。

        思路:

        经典的博弈论题目,要用到 Sprague-Grundy 函数,比赛后恶补了一下,发现还挺有意思。

        感觉瞪眼法很难看出有什么规律,打个表就很显而易见了:

        1. sg(1) = 1

        2. 若 x 为偶数,则 sg(x) = 0

        3. 其他情况,设 x 的最小质因子为 p ,则 sg(x) = p 在质数中从小到大的排位(记作num)

        证明:

        1 和 2 是显然的,这里我们主要考虑 3 ,用数学归纳法证明。

        假设 1 ~ x - 1 都满足上述条件,考虑 sg(x) 的值,要证 x 的后继中有 0 ~ num - 1 但是不能有num。

        对于 x ,我们肯定可以取 1 个或者 x - 1 个石子,这样后继就是 sg(x - 1) 和 sg(1) ,分别对应 0 和 1。接着,肯定也可以取到剩下小于 p 个石子,即 2 ~ p - 1,那么后继就是 sg(2) , sg(3), ... , sg(p - 1),根据前面的条件都满足,这些后继肯定包含了 2 ~ num - 1 的值。综上,后继中一定有 0 ~ num - 1。

        那么后继能不能有 num 呢?反证。假设有,那么意思是后继中也有某一堆石子数,满足其最小质因子为 p ,这样这堆就和原来的互质了,违背题意。

        因此,sg(x) = num 。

#include<cstdio>
#include<cstring>
using namespace std;#define N 10000007int T,n,check[N],prime[N],p[N],num[N],cnt,tmp,ans;void ola()
{check[1] = 1,cnt = 0;for (int i = 2;i < N;++ i){if(!check[i]) prime[++ cnt] = i,p[i] = i;for (int j = 1;j <= cnt;++ j){if(i * prime[j] >= N) break;check[i * prime[j]] = 1,p[i * prime[j]] = prime[j];if(!(i % prime[j])) break;}}for (int i = 1;i <= cnt;++ i) num[prime[i]] = i;return;
}int main()
{ola();scanf("%d",&T);while (T --){scanf("%d",&n),ans = 0;for (int i = 1,x;i <= n;++ i){scanf("%d",&x);if(x == 1) tmp = 1;else if(!(x & 1)) tmp = 0;else tmp = num[p[x]];ans ^= tmp;}if(ans) printf("Alice\n");else printf("Bob\n");}return 0;
}

F. Make a Palindrome

        题意:

        给一个长度为 n 的整数序列 a ,定义 f(b) 表示使得序列 b 回文的最少操作数,每次操作可以选择序列的任意一端,要么合并这一端的两个数;要么让端点的这个数拆分成两个数,使得这两个数之和与原来相等。计算序列 a 的所有子序列的 f 值之和。

        思路:

        首先不难发现,合并和拆分操作的意义是一样的,即当你选择一次合并操作的时候,也一定可以使用一次拆分操作满足相同的回文要求,只是序列中的数字不一样而已。

        我们考虑某个序列 p ,我们用最小的操作使序列两端的数字之和相等,这样的条件是序列的某个前缀和与后缀和相等,然后我们只用合并操作就可以达到这一条件。那么得到剩下的不合法序列就是一个子序列,我们可以用分治考虑它。

        我们记某一段区间 [l,r] 的前缀和为 s ,考虑它需要的操作数:

        找出最大的子区间 [x,y] 使得 s_{x - 1} - s_{l-1} = s_y - s_r , 即 s_r+s_{l-1} = s_y + s_{x-1},因此我们发现所有 s_r+s_{l-1} 相等的区间都是一组,并且一定是包含关系(因为前缀和是单调的,一个增加另一个必须减少,即区间左端点右移的时候,区间右端点一定左移)。于是每两个相邻区间都会有一个操作数的差值,我们先统计假设所有组的区间都以最大长度的那个区间计算时需要的操作数,再减去所有多计算的操作数即可。

#include<cstdio>
#include<cstring>
#include<map>
using namespace std;#define N 2005int T,n,a[N],pre[N],ans;
map< int, int > mpl,mpr;int main()
{scanf("%d",&T);while (T --){scanf("%d",&n),pre[0] = ans = 0;for (int i = 1;i <= n;++ i) scanf("%d",&a[i]),pre[i] = pre[i - 1] + a[i];map< int, int > mp;for (int i = 0;i < n;++ i)for (int j = i;j <= n;++ j)ans += j - i - 1,++ mp[pre[i] + pre[j]];for (auto [x,y] : mp) ans -= y * (y - 1);for (int i = 0;i <= n;++ i) ans += mp[2 * pre[i]]; printf("%d\n",ans);}return 0;
}

总结

        这套比赛主要是博弈论的 E 题没有学过吃了亏,但是这是无关紧要的,遇到不会的知识点时去填坑就好了,主要还是像 F 这种难度的计数题比较难想,需要大量做题大量思考来引起质变。

这篇关于Educational Codeforces Round 169 (Rated for Div. 2)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1102276

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor

创建一个大的DIV,里面的包含两个DIV是可以自由移动

创建一个大的DIV,里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单,不做解释 C 对于 x y 两个方向,每一个方向至少需要 x / k 向上取整的步数,取最大值。 由于 x 方向先移动,假如 x 方向需要的步数多于 y 方向的步数,那么最后 y 方向的那一步就不需要了,答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>

CF#271 (Div. 2) D.(dp)

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/474/problem/D We s

CF #278 (Div. 2) B.(暴力枚举+推导公式+数学构造)

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/488/problem/B There