JOISC2017F 鉄道旅行 (Railway Trip) 做题记录

给定长 nn 的序列 aia_i,满足 a1=an=max{ai}a_1=a_n=\max\{a_i\}

构建一个 nn 个点的无向图 GG 如下:

  • 1i<jn\forall 1\le i<j\le n,若存在某个正整数 kk 满足 ai,ajka_i,a_j\ge ki<p<j\forall i<p<j 都有 ap<ka_p<k,则 GG 中存在边 (i,j)(i,j)

qq 次询问,每次询问点 xix_iyiy_i 之间的最短路长度减一

1n,q1051\le n,q\le 10^51ain1\le a_i\le n

阅读全文 »

CF1637F Towers 做题记录

给定一棵 nn 个点的树,每个点有一个权值 aia_i

一个长度为 nn 的序列 bb 合法当且仅当 1un\forall 1\le u\le n,都存在两个整数 x,yx,y 满足:

  • 1x,yn1\le x,y\le n
  • x=yx\not=y
  • uuxxyy 的简单路径上;
  • min(bx,by)au\min(b_x,b_y)\ge a_u

输出所有合法的 bb 中最小的 bi\sum b_i

2n2×1052\le n\le 2\times 10^51ai1091\le a_i\le 10^9

阅读全文 »

CF1770F Koxia and Sequence 做题记录

给定非负整数 n,x,yn,x,y,对于所有满足 i=1nai=x\sum \limits_{i=1}^n a_i=x,所有 aia_i 按位或和为 yy 的序列 aa,求出 i=1nai\oplus_{i=1}^n a_i 的异或和。

1n2401\le n\le 2^{40}0x<2600\le x< 2^{60}0x<2200\le x< 2^{20}

阅读全文 »

ABC228G Digits on Grid 做题记录

给定一个 H×WH\times W 的矩阵 cc 和一个整数 nn

起初在任意格子上放置一个棋子,接下来操作 nn 次,第 ii 次操作:

  • ii 是奇数,则把棋子移动到当前所在中任意一个格子(可以不动);
  • ii 是偶数,则把棋子移动到当前所在中任意一个格子(可以不动);

把每次操作完后棋子所在的格子上的数依次写下,形成一个长度为 2n2n 的序列 bb,请你求出有多少种可能的序列 bb,对 998244353998244353 取模。

1H,W101\le H,W\leq101n3001\le n\leq 3001ci,j91\le c_{i,j}\le 9

阅读全文 »

CF1270H Number of Components 做题记录

给定一个长 nn 的元素两两不同的序列 aa1i<jn\forall 1\le i<j\le n,若 ai<aja_i<a_j,则让 iijj 连一条无向边。

qq 次修改数组某个位置的值,每次修改后输出图中连通块个数。

1n,q5×1051\le n,q\le 5\times 10^51ai1061\le a_i\le 10^6,保证任意时刻数组中元素两两不同。

阅读全文 »

CF1519F Chests and Keys 做题记录

给定 n,mn,m 表示存在 nn 个宝箱和 mm 把钥匙,第 ii 把钥匙需要 bib_i 元,第 ii 个宝箱内部有 aia_i 元。

现在进行一场游戏,Bob 是本场游戏的玩家,而 Alice 则是场景布置者,Alice 可以给每个宝箱上一些锁(第 jj 种锁需要第 jj 种钥匙打开)

如果 Bob 可以购买一些钥匙,然后打开一些宝箱,使得 Bob 的收益大于 00,那么 Bob 就赢得了游戏,反之 Alice 获得了胜利。

现在 Alice 打算布置宝箱上的锁,第 ii 个宝箱上放置第 jj 种锁的花费为 ci,jc_{i,j},请帮助 Alice 找到一种布置锁的方案,使得花费最小,且 Alice 将取得胜利。

注意:一个箱子上可以放置若干把锁,Bob 需打开所有锁才能获得内部的钱。

n,m6,ai,bi4,ci,j107n,m\le 6,a_i,b_i\le 4,c_{i,j}\le 10^7

阅读全文 »

CF1446D1&2 Frequency Problem 做题记录

给定长 nn 的序列 a[1,n]a_{[1,n]}

输出最长的满足不同的众数(出现次数最多的数)至少有两个的区间的长度。

D1:1n2×1051\le n\le 2\times 10^51aimin(100,n)1\le a_i\le \min(100,n)

D2:1n2×1051\le n\le 2\times 10^51ain1\le a_i\le n

阅读全文 »