Warning: session_start(): open(/tmp/sess_b951b74e3ea84643678d5f95ffbb05aa, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 2020.05.17-2020.05.23 周报 ====== ===== 团队训练 ===== ^ 比赛时间 ^ 比赛名称 ^ 赛中过题 ^ 总计过题 ^ 总题目数 ^ 排名 ^ | 2020.05.23 | [[neerc2016 | NEERC 2016]] | 5 | 10 | 13 | 47 / 215 | ===== 团队会议 ===== ===== 个人训练 - nikkukun ===== ==== 比赛 ==== 无 ==== 学习总结 ==== 主要在做字符串专题的相关练习，把板子和不熟悉的知识点都过了一遍。 ==== 本周推荐 ==== === NEERC 2016 B - Binary Code === [[https://codeforces.com/gym/281394|题目链接]] 2-SAT 好题，题意与题解[[neerc2016#B_-_Binary_Code|见此]]。 ===== 个人训练 - qxforever ===== ==== 比赛 ==== === 2020.05.17 Educational Codeforces Round 87 === ^ 题目 ^ A ^ B ^ C1 ^ C2 ^ D ^ E ^ F ^ G ^ | 通过 | √ | √ | √ | √ | √ | √ | | | | 补题 | | | | | | | | | ==== 学习总结 ==== ==== 本周推荐 ==== === === [[|题目链接]] ===== 个人训练 - Potassium ===== ==== 比赛 ==== 无 ==== 学习总结 ==== 2020.5.19 [[.:potassium:lyndon|字符串1 - Lyndon 分解]] ==== 本周推荐 ==== === 2015 ACM/ICPC Asia Regional Shanghai Online C Typewriter === [[http://acm.hdu.edu.cn/showproblem.php?pid=5470|题目链接]] **题意**：有一个字符串 $s$ ，给定打印每一种字母的代价。你可以花费单个字母的代价进行一次打字，或花费 $len\times A+2\times B$ 的代价粘贴一段已经打印过的、长度为 $len$ 的字符串。求把这个字符串打印出来的代价最小值。 **题解**：很明显有 DP ：设 $f(i)$ 表示打印前 $i$ 个字符的代价，则有递推式 $$ f(i)=\min\{f(i-1)+val(s_i),\min_{j #include #include #include #include #include #include #include #include #include #include typedef long long ll; using namespace std; #define pii pair #define pll pair #define pb push_back #define mp make_pair #define fi first #define se second #define N 100010 #define P 26 ll val[P]; char s[N]; // SAM struct SAM{ int tr[N<<1][P],len[N<<1],fa[N<<1]; int last,tot; void init(){ tot=0; last=tot=newnode(); } int newnode(){ ++tot; memset(tr[tot],0,sizeof(tr[tot])); fa[tot]=len[tot]=0; return tot; } void insert(int c){ int p=last,np=newnode(); last=np; len[np]=len[p]+1; while(p&&!tr[p][c])tr[p][c]=np,p=fa[p]; if(!p)fa[np]=1; else{ int q=tr[p][c]; if(len[q]==len[p]+1)fa[np]=q; else{ int nq=newnode(); len[nq]=len[p]+1; memcpy(tr[nq],tr[q],sizeof(tr[q])); fa[nq]=fa[q]; fa[q]=fa[np]=nq; while(tr[p][c]==q)tr[p][c]=nq,p=fa[p]; } } } }sam; // monotone queue ll f[N]; int hd,tl; pll Q[N]; void insert(int p,ll v){ while(hdv)tl--; Q[tl++]=mp(p,v); } ll get(int p){ while(hd=tl)return 1e18; else return Q[hd].se; } int main(){ int T,i,j,cas=0; ll A,B; scanf("%d",&T); while(T--){ hd=tl=0; scanf("%s",s+1); int n=strlen(s+1); for(i=0;i<26;i++)scanf("%lld",&val[i]); scanf("%lld%lld",&A,&B); sam.init(); j=0; int cur=1; // [j+1...i-1] for(i=1;i<=n;i++){ //int F=sam.fa[cur]; while(j+1<=i-1&&!sam.tr[cur][s[i]-'a']){ // correct if(sam.len[sam.fa[cur]]>=i-1-(j+1))cur=sam.fa[cur]; sam.insert(s[++j]-'a'); while(sam.fa[cur]&&sam.len[sam.fa[cur]]>=i-1-j)cur=sam.fa[cur]; // correct 2 /*if(sam.len[F]>=i-1-(j+1))cur=F,F=sam.fa[cur]; sam.insert(s[++j]-'a');*/ // wrong /*if(sam.len[sam.fa[cur]]>=i-1-(j+1))cur=sam.fa[cur]; sam.insert(s[++j]-'a');*/ } if(sam.tr[cur][s[i]-'a']){ cur=sam.tr[cur][s[i]-'a']; }else{ cur=1; hd=tl=0; sam.insert(s[++j]-'a'); } f[i]=min(f[i-1]+val[s[i]-'a'],get(j)+1LL*i*A); insert(i,f[i]-1LL*i*A+2*B); } printf("Case #%d: %lld\n",++cas,f[n]); } return 0; }