(ps: 写题请到Problems
页面)
可能算详解?代码部分随缘写。
题解
A. NO GAMES NO LIFE
题目描述
共有$n$(偶数)堆棋子,第$i$堆初始为$1 \leq a_i \leq 100$,玩家每次必须选$\frac{n}{2}$堆棋子并使之减少正整数个,每次每堆减少的值可以不同。
Bai
先手,Kong
后手。玩家无法选择时失败。
基准思路:
- 谁先导致场上出现被取完的堆必定输掉游戏
- 如果选了
1
则必须减少到0
考虑数字1
的数量,令$cnt[i]$为数字$i$的个数。
- $cnt[1] > \frac{n}{2}$时玩家必选到
1
,必输 - $1 \leq cnt[1] \leq \frac{n}{2}$可以增加
1
的数量使下家面临第一个局面,必胜 - $cnt[1] = 0$时考虑
2
的数量- $cnt[2] > \frac{n}{2}$玩家必选到
2
,必然产生1
,且个数不大于$\frac{n}{2}$,必输 - $1 \leq cnt[2] \leq \frac{n}{2}$可以增加
2
的数量使下家面临上一个局面,必胜 - $cnt[2] = 0$时考虑
3
的数量- $\dots$
- $cnt[2] > \frac{n}{2}$玩家必选到
显然,问题只与最小值的数量有关。
B. 整除数
题目描述
找到最小的$n$位能被$m$整除的自然数
- $n=1$时,直接输出
0
- 找到最小的$n$位整数$10^{n-1}$,求最少还需多少使得其能被$m$整除,即$(m - 10^{n-1} % m) \mod m$,如果加上后位数不变则为答案,否则无解。
C. 网格图
题目描述
从$(0,0)$,每次你只可以往正东走,或者往正北走(即x,y坐标增大的方向)。但是你每次走的长度可以是任意正实数。这个网格上有$\mathit n$个景点,你可以经过任意个景点,问:以每个景点为终点时,分别能走出多少条不同路线。(当且仅当经过的景点不同时才被视为不同路线) 取模$1e9+7$.
由于是走正实数,某点左下方的所有景点都可以直接到达该点。
比较特殊的是与之处在同一行列的点,这里就只需加上到最近的那个点的方案数。
思路,按照$(x,y)$从小到大排序,只要保证到某点时,所有处于其左下方的点都已经更新答案,那么该点的方案就是它们求和再+1(从$(0,0)$直达)。
同时要维护行列点数目,每次更新答案后再更新即可。
D. 修机器
题目描述
$n$个机器,总时间为$T$,修理某机器的时间为$y_i$,收益为$\textrm{修完后剩余时间} \times x_i$,求可能的最大收益。
首先可以明确本题是一个01背包问题,关键在于怎样安排顺序会影响物品价值。
先考虑一个子问题:在恰好能修完的条件下选择$k$个机器,求如何安排其顺序,使之收益最大?
- $k=0,1$收益为$0$。
- $k=2$时,为$\max{x_a \times y_b}$,即取$\frac{x}{y}$更大的在前。
- $k>2$时,每次只考虑最后一个位置,情况可以递推过去,即最后一定是比值最小的。
按照比值$\frac{x}{y}$排序,然后按照背包的基本思路去写就好了。
E. squares
题目描述
找出坐标$(0,0)$到$(n,m)$之间由整点构成的正方形的数量,取模$1e9+7$。
简单的思维题,推导在下面的图片上,懒得制图就手写了。
F. 拍照
题目描述
给定一个$n\times m$的矩阵和一个长$s$的序列$h$,所有元素在$0$到$9$。在矩阵中找连续的长为$s$的连续数组其元素与$h$对应元素的和均不超过$9$。
数字都很小,考虑枚举所有可能的对应序列,使用hash
或者kmp
查询数量。
G. 递增数组2
题目描述
给出一个长度为$N$的严格递增的数组$A$,一共$K$次操作,每次选择$[L,R]$区间,加上$C$,询问否存在某个$A_i=i(1\leq i \leq n)$。
数据范围
$1\leq N\leq 10^7,1\leq K\leq 500$
我们把加上相同值的最长连续区间称为一段操作,由于$K$极小,所以最终并不会产生很多的段。
又因为初始的数组是有序的,我们只要二分查询每一段中是否有$A_i+C=i$即可。
|
|
H. function
题目描述
令$F(x)$为数字$x$的数位和,给定$n$,求满足$F(x)+x=n$的所有$n$,升序输出。
由于数位和最大为$9\times \textrm{位数}$,所以可以知道满足条件的$x$很少,直接暴力枚举即可。
I. 数字游戏
题目描述
给定两个由数字$0~9$构成的序列$s,t$,每次选定$s$的一个连续区间并将其转成升序,在有限步(可以为$0$)后是否能使得$s,t$相同
将一个连续区间变成升序后是不可逆的,那么每次就只选择两个相邻的数字变成升序以减少影响。
考虑去模拟这个过程,注意不要真的去移动实际值,那样的复杂度是不可接受的。
由于数字的种类有限,直接记录每个数字所在的位置,就可以判断当前位置上的所需要的数字是否可以移动到该位置上。
判断方式也很简单,两位置之间没有比它更小的数存在即可移动到所需位置。
所以每次只需要知道该位置(包含在内)之后的每个数字第一次出现的位置,就可以了,考虑使用栈去维护。
|
|
J. lazy tree
题目描述
给出数列${a_n}$,有两种操作
- 选定区间$[l,r]$所有元素加上$v$
- 区间$[l,r]$询问$\sum_{i=l}^{r}\sum_{j=i+1}^{r}a_i\times a_j$,取模$1e9+7$
所求为区间中不重复的两个位置的数对的乘积之和。
$$Query=\frac{(\sum_{i=l}^{r}a_i)^2-\sum_{i=l}^{r}a_i^2}{2}$$
线段树直接维护即可。
|
|
总结
虽然侥幸拿了Rank-2,但是鉴于运气成分有点多,还是得加油。
个人认为自己赛中暴露出的问题:
心态不稳
。前面一段时间一直发懵(30min才交第一发),结束前修机器那题应该能过的,但后面有点自暴自弃最后一小时基本放弃思考了。动态规划
和贪心
这块太薄弱了。- 手速太慢了。。。