把一个长为n的正整数序列划分为一些连续的段落, 使得每一段元素之和单调递增, 求最多段数. (1≤n≤10^5, 1≤wi≤10^4)

Read More

求每行每列恰有两个1的n*n 0-1矩阵的数目. 输出前缀和对998244353取模的结果.

Read More

在列车上打的......A题一时不会做. TAT C题卡住了. 感觉是个数位DP, 但是拿什么作状态呢? 虽然数位和的所有可能值很少呢......跳过了这题, 发现后面是三道基本数据结构练习题. F没时间写了. 比赛时完成ABDE. C题最后用数位DP写出来了, 但是有更妙的方法. 题解: 6/6.

Read More

有多少个 (a位0-1串, b位0-1串), 满足前者的1多于后者? 输出十进制下最后k位. (1≤a,b≤10^15, b≤a≤b+10^4, 1≤k≤9, 每个测试点数据组数不多于10, 时限1.5s)

Read More

给一个n行m列的矩阵, 求上下,左右均对称的正方形区域的数目. (n,m≤10^4, 矩阵中的数≤10^9)

Read More

8种物品, 同一种物品之间不可区分, 求总共n件物品, 每种物品分别满足以下数量限制的方案数模10007: - 偶数 - 0或1 - 0,1,或2 - 奇数 - 4的倍数 - 0,1,2,或3 - 不超过1 - 3的倍数

(1≤n≤10^500)

Read More

维护一个序列, 支持:

• 插入 在p位置和p+1位置之间插入整数a,a+1,...,b-1,b; 若p=0, 插在最前面
• 删除 删除a,a+1,...,b-1,b位置的元素
• 查询 查询p位置的元素

(1≤n≤2*10^4, 1≤m≤2*10^4, 涉及的所有数在int内) 题面中还说: 在任何情况下，保证序列中的元素总数不超过100000. 其实数据并不满足这个限制.

Read More

二维平面上有n个点, 不存在两个点有相同的横/纵坐标. S是点集的一个子集, 把S中的点按横坐标依次连线, 求增减性变化(k-1)次的S的数目模10^5+7. (n≤5*10^4, 0<k≤10)

Read More

矩形区域 (0,0) - (x,y) 上有n个条形区域, 第i个宽度为hi, 在上面滑动的速率为vi. 路线自拟, 不能离开矩形区域, 求 (0,0) 到 (x,y) 的最短用时. (n≤100, x≤10^3, vi<v(i+1) for 1≤i<n)

疑惑: 如果光发生全反射, 题目该怎么解呢? 欢迎指教或讨论......

Read More

一棵有根树. 若个不同的点 i,j 到它们 LCA 的距离分别x,y, 则 A[i][j] = x xor y. 对k=0,1,..., 求出 A[i][j]=k 的 (i,j) 的数目. (i,j),(j,i)算作同一个. (节点数n≤10^5, 最大深度h≤500)

Read More

求[L,R)中满足0 <= 十进制各个数位之积 <= n的数的个数. (0<L<R<10^18, n≤10^9)

Read More

一个初始长度为len的字符串, 一个长度为n的序列a, m个操作:

• 头部插入 在字符串开头添加一个字符 (强制在线)
• 单点修改 令a[x] = pos
• 区间查询 求min{ suffix(a[i]) | l≤i≤r }, 输出i即可; 多解输出最小的i

(1≤n≤5*10^5, 1≤m≤8*10^5, 插入约占1/5, 修改,查询约各占2/5, 保证a[i]合法)

Read More

同学问我替罪羊树和带插入的区间k小, 我说没有太大兴趣, 结果立了个flag...... 本文不加证明地介绍了替罪羊树, 这种简洁高效, 不用旋转的重量平衡树. link: - cls的集训队论文 <重量平衡树和后缀平衡树在信息学奥赛中的应用> - vfk的论文 <对无旋转操作的平衡树的一些探究> - 发明人的论文 Scapegoat Trees - neither_nor神犇对发明人论文的翻译

Read More

定义:

1. 是一个数; 如果 是数, 那么 也是数

给一个长度为 的全 序列 , 个操作:

• 赋值 给出参数 , 执行
• 询问 给出参数 , 求 最大值的下标; 多个最大值, 输出最小下标.

Read More

一棵点带权的有根树, 要求支持: - 单点加 - 子树加 - 查询以u为lca的不同两点的点权之和的期望

(1≤节点数,操作数≤3*10^5, 0≤|权值|,|加数|≤2*10^4)

Read More