2021 集训队作业 题解
题目链接:
Problem E, 2018 ACM-ICPC World Finals
Problem J, 2017 ACM-ICPC World Finals
Problem H, 2015-2016 ACM-ICPC Northeastern European Regional Contest (NEERC 15)
欢迎任何建议
题目链接:
Problem E, 2018 ACM-ICPC World Finals
Problem J, 2017 ACM-ICPC World Finals
Problem H, 2015-2016 ACM-ICPC Northeastern European Regional Contest (NEERC 15)
欢迎任何建议
找不到对于第二种做法的详细描述,看到的都只有一个式子. 于是来写一下.
有 \(n\) 只变色龙,你会扔 \(k\) 次球,球会被随机的一只变色龙吃掉. 球是蓝色或者红色的,初始时所有变色龙都是蓝色的,当一只变色龙吃下的红球和蓝球数量不同时它会变成较多的那种颜色.
你可以决定每次扔下球的颜色,求有多少种方案有可能使所有变色龙都变红. 两种方案不同当且仅当某一次扔下的球的颜色不同.
\(1\le n,k \le 5\times 10^5\)
好久没更了,水平下降严重 = =
AtCoder Japanese Student Championship 2019 Qualification E
有 \(n\) 个写着数字的卡片放在 \(h\times w\) 的网格上,第一次你可以在每一行选择至多一张卡片取走,第二次在每一列选择至多一张卡片取走,要求最大化取走卡片上的数字总和。
同一个位置可能有多个卡片。
\(n,h,w\le 10^5\)
Codeforces 1060G. Balls and Pockets
有一个从 \(0\) 到 \(\infty\) 的序列,第 \(a_1,a_2,\dotsc,a_n\) 个位置上各有一个口袋
每秒每个口袋会吃掉当前位置上的数,较大的数会向较小的方向移动以填补空位
\(m\) 次询问在 \(k_i\) 秒后一个位置 \(x_i\) 上的数是什么
\(a_1< a_2< \cdots< a_n\)
\(n,m\le 10^5, a_i,k_i,x_i\le 10^9\)
好久没更了 = =
现在看到什么题都感觉一脸不可做,水平太低了
给出仅包含小写字母的长度为 \(n\) 的字符串 \(s\)
每次取出 \(s\) 的一个子串 \(t_i\)(可以为空),执行 \(m\) 次,顺次拼接成一个大字符串 \(t=t_1 t_2\dots t_m\),求可以得到多少种本质不同的 \(t\)
\(q\) 次询问,每次给出一个 \(m\)
\(n,q\le 10^5, m\le 10^{10}\)
给定一个长为 \(n\) 的序列 \(A_1,\dotsc,A_n\),求一个长为 \(n\) 的不下降序列 \(B_1,\dotsc,B_n\),使得 \(\sum_{i=1}^n (A_i-B_i)^2\) 最小,只需要输出最小值
以及 \(m\) 次互相独立的修改,每次会更改一个位置的值,要求输出修改后的答案
模 \(998244353\)
\(n,m\le 10^5\)
Codeforces 1090H. Linearization
定义一个长度为 \(n(n=2^k,k\in N)\) 的 01 串 \(s\)(从 0 开始标号)是线性的,当且仅当存在整数 \(x\) 和 二进制数位 \(b\),使得 \(\forall i\in [0,n),s_i=P(i~{\rm and}~x)~{\rm xor}~b\),其中 \(P(a)\) 表示 \(a\) 的二进制表示中 \(1\) 的数量的奇偶性
定义一个 01 串的线性化难度为,进行最少的取反一个区间的操作,使之成为线性的操作次数
给定一个长度为 \(m\) 的 01 串 \(t\),\(q\) 次询问指定一个子串,要求计算其线性化难度
\(m,q\le 2\times 10^5\)