Difference between revisions of "2018 ACM-ICPC Asia Nanjing Regional Contest"

From EOJ Wiki
Jump to navigation Jump to search
Line 85: Line 85:
 
题意:给出两个字符串$s$,$t$,求有多少的数对$(i,j,k)$满足$s_i,\cdots ,s_j,t_1,\cdots ,t_k$是回文串,且$j-i+1>k$。
 
题意:给出两个字符串$s$,$t$,求有多少的数对$(i,j,k)$满足$s_i,\cdots ,s_j,t_1,\cdots ,t_k$是回文串,且$j-i+1>k$。
  
题解:可以把$s$串倒转成$s$',然后我们拿$t$在$s$'上匹配,假设$t_1,\cdots ,t_k=s$'$_1,\cdots ,s$'$_k$
+
题解:可以把$s$串倒转成$s$',然后我们拿$t$在$s$'上匹配,假设$t_1,\cdots ,t_k=s$'$_i,\cdots ,s$'$_j(j-i+1=k)$,这种情况下的方案个数就是以$s$‘$_{i-1}$为结尾的回文串个数。
 +
 
 +
首先用Manacher算法处理一下以每个位置$i$为结尾的回文串个数$ans_i$,就是在当前位置和最远位置分别打上tag,然后扫一遍,统计一下。
 +
 
 +
接着我们需要$s$‘的每一位最多与$t$匹配了多少位,这个可以用拓展KMP来处理每个位置$i$与最多$t$匹配成功的位数$a_i$,那么答案就是$\sum_{i=1}^{|s|}ans_{i-1}*a_i$。

Revision as of 12:03, 14 October 2018

Replay

oxx1108:

dreamcloud:

Xiejiadong:

  • 热身赛受到对面南大队伍碾压。听说他们少过了一题,正式赛能多过一题?那我们正式赛一定能多过两题,比他们多一题(flag)。
  • flag立住了(他们应该看不到这个吧,怂)。
  • 开场开题,博弈题,数学题...挂机预定。
  • 感觉B题很可做啊。搞了至少两个小时的$N^2$的优化,躺在地上看队友各种过题,差点零贡献领奖。
  • 打印差评,送的慢,甚至中间有一段连打三份一份都不送,导致占着电脑debug,强制减少oxx上机时间。
  • 比赛结束后,背后一生大吼,东南一队好强啊,随机seed用某人生日把K过去了。
  • 冠军是dls,xls,小火车梦之队,心服口服。不过冠军没有奖杯,那这场冠军真是亏了。
  • M题差评,由于原题,金牌题强行变成银牌题。K题差评,场上过的绝大部分都是随机。
  • 比赛最后二十分钟,划水观看oxx提交了127发E题随机代码,比赛就是20min才得到了全部WA的feedback,差点以为要Au了。

Problem A

Solved by oxx1108.

Problem B

Unsolved.

IOI2014原题。

Problem C

Unsolved.

Problem D

Solved by Redbook.

题意:三位一体求最小覆盖。

题解:红书原题,甚至数据范围小了很多。

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Solved by oxx1108.

Problem H

Unsolved.

Problem I

Solved by dreamcloud.

Problem J

Solved by oxx1108.

Problem K

Unsolved.

Problem L

Unsolved.

Problem M

Solved by Xiejiadong && dreamcloud.

题意:给出两个字符串$s$,$t$,求有多少的数对$(i,j,k)$满足$s_i,\cdots ,s_j,t_1,\cdots ,t_k$是回文串,且$j-i+1>k$。

题解:可以把$s$串倒转成$s$',然后我们拿$t$在$s$'上匹配,假设$t_1,\cdots ,t_k=s$'$_i,\cdots ,s$'$_j(j-i+1=k)$,这种情况下的方案个数就是以$s$‘$_{i-1}$为结尾的回文串个数。

首先用Manacher算法处理一下以每个位置$i$为结尾的回文串个数$ans_i$,就是在当前位置和最远位置分别打上tag,然后扫一遍,统计一下。

接着我们需要$s$‘的每一位最多与$t$匹配了多少位,这个可以用拓展KMP来处理每个位置$i$与最多$t$匹配成功的位数$a_i$,那么答案就是$\sum_{i=1}^{|s|}ans_{i-1}*a_i$。