L- We are the Lights
题意
一天，波波在参加一个国际灯光展时，注意到一个 n × m n \times m n×m 的网格灯排列成 n n n 行和 m m m 列。起初，所有的灯都熄灭了。
波波注意到，每行每列都有两个按钮，一个用于打开，另一个用于关闭。这意味着他可以执行以下四个操作：
第二排开启：开启第二排所有灯。第二排熄灭：将第二排的所有灯熄灭。第二列打开：打开第二列中的所有灯。第二列关闭：关闭第二列中的所有灯。
顽皮的波波当然不会错过这个机会。你得到了波波执行的q次操作。在按顺序执行 q q q 次操作后，您需要确定打开的灯的数量。
题解
经典的矩阵覆盖问题，由于后面的操作会覆盖前面已经执行过的操作，因此我们可以从后往前递推结果。
用两个数组分别记录哪些行 r o w row row 和 哪些列 c o l col col 已经被操作覆盖过， r o w s rows rows 和 c o l s cols cols 分别表示当前行和列已经被操作覆盖的数量。
如果当前行 r o w row row 没有被覆盖且当前的执行操作为 o n on on，则对答案的贡献为 m − c o l s m-cols m−cols。
如果当前行 c o l col col 没有被覆盖且当前的执行操作为 o n on on，则对答案的贡献为 n − r o w s n-rows n−rows。
最后输出累加的答案即可。
时间复杂度为 O ( q ) O(q) O(q)。
AC_Code
void solve(){int n , m , q ;cin >> n >> m >> q ;vector< string > s(q) ;vector< string > t(q) ;vector< int > num(q) ;vector< bool > row(n,false) ;vector< bool > col(m,false) ;for( int i = 0 ; i < q ; ++ i ){cin >> s[i] >> num[i] >> t[i] ;}int res = 0 ;int r = 0 , c = 0 ;for( int i = q-1 ; i >= 0 ; -- i ){int x = num[i] ;if( s[i] == "row" ){if( !row[x] ){row[x] = true ;if( t[i] == "on" ){res += m-c ;}r ++ ;}}else {if( !col[x] ){col[x] = true ;if( t[i] == "on" ){res += n-r ;}c ++ ;}}}cout << res << "\n" ;return ;}
F- Election of the King
题意
在遥远的博博兰，每五年举行一次国王选举。今年是博博兰再次举行国王选举的时候了。博博兰的每个城市都提名了nn国王候选人，编号为 1 ⋯ n 1 \cdots n 1⋯n。这些 n n n 个候选人有明显的政治倾向 a 1 , a 2 , ⋯ , a n ( 1 ≤ a i ≤ 1 0 9 ) a_1,a_2, \cdots,a_n(1 \leq a_i \leq 10^9) a1,a2,⋯,an(1≤ai≤109) 代表第二位候选人的政治倾向，其中较大的数字意味着更右翼的倾向， 1 1 1 代表极左翼， 1 0 9 10^9 109 代表极右翼。然后，将在候选人中进行以下内部投票机制，以决定最终的国王：
将进行 n − 1 n-1 n−1 轮投票，每轮只淘汰一名候选人，直到只剩下一名候选人为止，他将成为最终的国王。
每一轮的投票规则如下：每个候选人都可以投票给除自己之外的任何其他候选人。得票最多的候选人将被淘汰。如果有多个候选人拥有相同的最高票数，其中最右翼的候选人将被淘汰。
在观察了博博兰历届国王选举后，您发现每一位候选人都坚持以不同意见攻击对手的原则，并将在每一轮投票中执行以下策略：
在所有剩余的候选人中，投票给政治倾向与自己最不相同的候选人（即第 i i i 位候选人，如果他们没有被淘汰，将投票给第 j j j 位候选人，他们的票数差最大的 ∣ a j − a i ∣ |a_j-a_i| ∣aj−ai∣ , 指尚未被淘汰的人）。如果有多个候选具有相等的 a j − a i a_j-a_i aj−ai, 他们将投票给他们当中倾向最右翼的人。
题解
通过分析我们可以知道，每次投票的选择只会在最左翼倾向和最右翼倾向的候选人中产生。因此我们可以将候选人的倾向 a i a_i ai 从小到大排序，然后判断被选择出局的人。
将 a i a_i ai 从小到大排序之后，每次投票后的出局人在剩余候选人中的最左边或者最右边，而决定这两者谁会被投票出局的关键在于最中间的人。因为如果一个候选者投最右边的人，那么其左边的候选者都会投右边（ i f i ≥ x , ∣ a j − a x ∣ ≥ ∣ a j − a i ∣ if \ i \geq x,|a_j-a_x| \geq |a_j-a_i| ifi≥x,∣aj−ax∣≥∣aj−ai∣），同理如果一个候选者投最左边的人，那么其右边的候选者都会投左边。
因此我们判断谁出局的依据，只需要看投右边的人数有没有到达一半即可。
时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。
AC_Code
void solve(){int n ;cin >> n ;vector< int > a(n) ;vector< int > b(n) ;for( int i = 0 ; i < n ; ++ i ){cin >> a[i] ;b[i] = a[i] ;}sort( a.begin() , a.end() ) ;int l = 0 ;int r = n-1 ;while( l < r ){int mid = l+r >> 1 ;if( a[mid]-a[l] <= a[r]-a[mid] ){r -- ;}else {l ++ ;}}for( int i = 0 ; i < n ; ++ i ){if( a[l] == b[i] ){cout << i+1 << "\n" ;return ;}}return ;}
A- Bobo String Construction
题意
波波正在学习编码，以便给他最好的朋友oboB发送信息。他最近开发了一种“波波编码”，本质上是一种二进制编码。然而，与直接二进制编码不同，“波波编码”由三个部分组成：开头的“开始识别字符串” t t t ，用于传输信息的“消息字符串” s s s，和与“开始识别串”相同的“结束识别字符串”” t t t 。给定需要传输的“消息串” s s s 和识别字符串 t t t，这个“消息字符串” s s s的Bobo编码是 t + s + t t+s+t t+s+t，其中 + + + 表示字符串串联。在发送信息时，波波将他想要发送的消息字符串加密为“波波编码”，并将其逐一发送给oboB。oboB一旦发现识别字符串在接收到的字符串中出现两次，就会停止接收信息，这表明他已经接收到“开始识别字符串”和“结束识别字符串”。请注意，识别字符串可能重叠，例如，如果识别字符串为 t = 101 t=101 t=101，oboB接收 10101 10101 10101，oboB会认为识别字符串已经出现两次，并停止接收信息。
现给定一个 01 01 01 字符串 t t t，和一个正整数 n n n，求构造一个 01 01 01 字符串 s s s，使得 t + s + t t+s+t t+s+t 可以成立。
题解
构造 s s s 为全 0 0 0 字符串或者全 1 1 1 字符串即可，然后判断两者谁满足题意即可。
时间复杂度 O ( T n ) O(Tn) O(Tn)。
AC_Code
void solve(){int n ;cin >> n ;string t ;cin >> t ;int tlen = t.size() ;string s = "" ;for( int i = 1 ; i <= n ; ++ i ){s += "1" ;}string ans = t+s+t ;if( ans.find( t , 1 ) == n+tlen ){cout << s << "\n" ;}else {for( int i = 1 ; i <= n ; ++ i ){cout << 0 ;}cout << "\n" ;}return ;}
J- Qu’est-ce Que C’est?
题意
作为一名记者，波波被要求写一篇关于波波兰的长篇报道。波波最初想写一份既赞扬又批评的报告，但他担心恶意的人可能会断章取义，把他的话变成对波波兰的批评。长度为 n n n 的报告可以看作是一个整数序列 a 1 , … , a n a_1, \dots,a_n a1,…,an， − m ≤ a i ≤ m -m \leq a_i \leq m −m≤ai≤m ，表示被称赞程度为 a i a_i ai。如果报告中有 k k k 个连续的声明总赞度小于 0 0 0，并且满足 k ≥ 2 k \geq 2 k≥2，那么这 k k k 段声明可能会被恶意人员断章取义，攻击波波。波波不希望这种情况发生，他想知道在不断章取义的情况下，他能写多少不同的报告。
形式上，您需要计算长度为 n n n 的整数序列 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1,a2,…,an，满足：
对于所有的 1 ≤ i ≤ n 1 \leq i \leq n 1≤i≤n，保证 − m ≤ a i ≤ m -m \leq a_i \leq m −m≤ai≤m。
对于所有的 1 ≤ l ≤ r ≤ n 1 \leq l \leq r \leq n 1≤l≤r≤n，保证 ∑ i = l r a i ≥ 0 \sum_{i=l}^{r}a_i \geq 0 ∑i=lrai≥0。
由于答案可能很大，您需要对 998244353 998244353 998244353 取模。
题解
动态规划求解，定义 d p i , j dp_{i,j} dpi,j 表示前 i i i 个数，当前的数为 j j j 的满足题意的数量，定义 p r e i , j pre_{i,j} prei,j 表示第 i i i 个数， ∑ x = 0 j d p i , x \sum_{x=0}^{j}dp_{i,x} ∑x=0jdpi,x。
那么状态转移方程就是：
d p i , j { p r e i , 2 m − p r e i , 2 m − j − 1 i f j < m p r e i , 2 m − p r e i , j − m − 1 i f j ≥ m dp_{i,j} \begin{cases} pre_{i,2m}-pre_{i,2m-j-1} &if \ j \lt m \\ pre_{i,2m}-pre{i,j-m-1} &if \ j \geq m \end{cases} dpi,j{prei,2m−prei,2m−j−1prei,2m−prei,j−m−1ifj<mifj≥m
同时更新 p r e i , j pre_{i,j} prei,j，最后答案即为 a n s = ∑ x = 0 2 m d p n , x ans = \sum_{x=0}^{2m}dp_{n,x} ans=∑x=02mdpn,x，注意在运算过程中取模。
时间复杂度为 O ( n m ) O(nm) O(nm)。
AC_Code
int pre[5005][10005] ;int dp[5005][10005] ;void solve(){int n , m ;cin >> n >> m ;for( int i = 0 ; i <= (m<<1) ; ++ i ){dp[1][i] = 1 ;pre[1][i] = pre[1][i-1] + dp[1][i] ;}for( int i = 2 ; i <= n ; ++ i ){for( int j = 0 ; j <= (m<<1) ; ++ j ){if( j < m ){dp[i][j] = ( ( pre[i-1][(m<<1)]-pre[i-1][ (m<<1)-j-1 ] )%Max +Max ) %Max ;}else {dp[i][j] = ( ( pre[i-1][(m<<1)]-pre[i-1][j-m-1] )%Max +Max) %Max ;}pre[i][j] = ( pre[i][j-1]+dp[i][j] )%Max ;}}int res = 0 ;for( int i = 0 ; i <= (m<<1) ; ++ i ){res = ( res + dp[n][i] ) %Max ;}cout << res << "\n" ;return ;}
