Codeforces Round 706 D Lets Go Hiking @ Wings            分类 ACM
发布于 星期四, 三月 11 日, 2021 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

给出 $1 \sim n$ 的排列, 开始时A, B各选一个点, 然后轮流移动, 每次移动只能移动到相邻的位置, 且不能碰到另一个人. 并且, A只能走更小的数字, B只能走更大的数字. A先走, 不能走的人输. 问A必胜的选点有多少个.

$2 \le n \le 10^5$

题解

可以发现, 和排列没什么关系. 看成折线图, 发现, A一定要选峰, 否则在坡上, B只需要卡他下坡路, A就无了.

所以现在需要看某个峰是不是必胜.

考虑仅有一个峰, 首先能够发现, 如果AB相对走的话, 距离为奇数, A败; 距离为偶数, A胜. 更多地(当时这么思考的), 如果下落长度为奇数, 那么B只要放在底下(或者离峰距离为奇数的地方), A必败. 所以此时A一定不会走是奇数的一边, 那么他只能走另一边. 如果另一边是奇数, 那无论如何必败.

这启示我们考虑两边的下落距离奇偶性.

还可以发现, 如果有一边很长, 另一边较短, B可以放在较长的边上, 这样A走另一边不能胜利. 走这一边还需要看B放的位置到峰是不是奇数.

这启示我们考虑两边下落的距离差.

所以这样讨论:

  1. 2奇: 必败
  2. 1奇1偶:
    1. 奇>偶: B放奇边底端, A必败
    2. 偶>奇: B放偶边(长边)等于奇边的位置, A必败
  3. 2偶:
    1. 不相等: B放较长边的 (较短边+1) 的位置, A必败
    2. 相等: A必胜

画图即可. 由于重点不在证明而在思考方式, 所以不画(证)了.

然后还需要注意一点, 如果有多个峰, 或者说多个"下落"(边界点不是峰, 但是有下落), 那么仅有 “拥有最大落差的峰” 才可能成为必胜点. 否则, B只爬走最大坡, A一定没B走得远. 所以结论是, 当且仅当落差最大的峰唯一, 且左右两边落差相等且为偶数, A的必胜点且仅有一个(这个峰).

太菜了, 考场想1h+也没想出来, 逻辑混乱, 头脑混沌, 不知所措. 后来还是和 littlechai 讨论了半天才解决.

思维题还是要多练, 没有形成一种有用的思考方式.

复杂度$O(n)$

代码
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
#define lowbit(x) (x&(-x))
#define LCH(x) (x<<1)
#define RCH(x) (x<<1|1)
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int INTINF = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;

const int MAXN = 1e5+10;

int n, p[MAXN], ans = 0, f[MAXN], g[MAXN], mx = 0;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", p + i);
	for (int i = 2; i <= n; i++)
		f[i] = p[i] > p[i-1] ? f[i-1] + 1 : 0;
	for (int i = n-1; i; i--)
		g[i] = p[i+1] < p[i] ? g[i+1] + 1 : 0;
	for (int i = 1; i <= n; i++)
		mx = max(mx, max(f[i], g[i]));
	if ((mx&1)^1) {
		for (int i = 1; i <= n; i++)
			if (f[i] == mx && g[i] != mx || g[i] == mx && f[i] != mx) {
				ans = 0;
				break;
			}
			else if (!ans && f[i] == mx && g[i] == mx)
				ans++;
			else if (ans && (f[i] == mx || g[i] == mx)) {
				ans = 0;
				break;
			}
	}
	printf("%d\n", ans);
	return 0;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球
  • 三阶速拧20s

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch