atcoder 泛做

2024-10-07 15:58:05

https://atcoder.jp/contests/arc060/tasks/arc060_b

先考虑一些特殊情况：

$$n>s$$

$$n=s$$

$b$小于$sqrt(N)$可以枚举，如何找到大于$sqrt(N)$的$b$是关键。

在$x$(x>sqrt(N))进制下有：

$$a*x+b=n$$

$$a+b=s$$

即

$$n-s=(x-1)*a$$

$x-1$一定是$n-s$的因子

枚举$n-s$的因子然后检验即可

https://atcoder.jp/contests/arc060/tasks/arc060_c

预处理倍增数组$f[i][j]$表示从i开始走$2^j$步到哪个点，询问的时候在倍增数组上跑就行了

https://atcoder.jp/contests/arc061/tasks/arc061_a

dfs

https://atcoder.jp/contests/arc061/tasks/arc061_b

只枚举黑块周围的部分

https://atcoder.jp/contests/arc061/tasks/arc061_c

++++拆点建图

(x,c)表示在c号地铁线上的x点。

(x,c)<—0—>(y,c)

(x,c)<—1—>x

01边权图最短路bfs即可，最后答案 /= 2

https://atcoder.jp/contests/arc061/tasks/arc061_d

关键点在于如何O(1)由

$\sum_{i=a}^b C_n^i$

求

$\sum_{i=a}^b C_{n+1}^i$

看着杨辉三角推一下很容易看出来

题解(有些错误)

https://www.cnblogs.com/henry-1202/p/9691319.html

类似题目：

http://acm.hdu.edu.cn/showproblem.php?pid=6333

https://atcoder.jp/contests/arc062/tasks/arc062_a

每次二分一下就好了。

https://atcoder.jp/contests/arc062/tasks/arc062_b

每次权值相同，贪心，能赢就赢。

https://atcoder.jp/contests/arc062/tasks/arc062_c

差评，需要一定的枚举思路，但是立方体题目涉及空间想象，无意义费脑，而且卡常，需要常数优化。

https://atcoder.jp/contests/arc062/tasks/arc062_d

polya定理，不会

https://atcoder.jp/contests/abc130/tasks/abc130_f

单峰函数，可以三分，注意边界值和常量的设置

https://atcoder.jp/contests/arc063/tasks/arc063_b

难度一般的贪心，只有价格差最大的时候商人才会买卖，处理一下这些点即可。

https://atcoder.jp/contests/arc063/tasks/arc063_c

https://blog.csdn.net/weixin_30740581/article/details/95124509

有意思的思维题，贪心，dp，线段树合并(雾)都可以搞

贪心：确定的点值最小的点周围的点可以直接确定，每次从最小的点向外延伸一层。

dp：可以求出每个点点权的上下界和奇偶性。

https://atcoder.jp/contests/arc063/tasks/arc063_d

https://zsnuo.github.io/arc063f/

https://atcoder.jp/contests/abc143/tasks/abc143_e

双关键字$dijkstra$

https://atcoder.jp/contests/abc143/tasks/abc143_f

双指针，从大到小求解，求解每次拿$i$个时，将出现次数小于等于$i$的看做随意放置的填充物，出现次数大于$i$的每种每次拿一个。

最新文章

热门文章