橙队的题就不写题意了qwq
T1
一些闲话
题面上出现的人都没想出正解，橙队好奶
菜菜子也出现在题面上了qwq
很惨，考试时就乱搞，期望得分是 0
但有 10 分还是出题人手软了，赞美出题人！
题解
$O(nm)$ 的 DP，设 $f[i][j]$ 为 A 串与 B 串第 i 和 j 相匹配
考虑转移
$$
f[i][j]=\begin{cases}
min(f[i-1][j-1]+dis(a[i],b[j]))\qquad j\ge1,i\ge1\\
min(f[i][j-1]+b[j])\qquad j\ge1\\
min(f[i-1][j]+a[i])\qquad i\ge1
\end{cases}
$$
然后就做完了(
代码
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=2005;
const int inf=0x3f3f3f3f;
char s[maxn],ss[maxn];
int len1,len2,f[maxn][maxn],ans,tot;
signed main(void)
{
scanf("%s",s+1),scanf("%s",ss+1);
len1=strlen(s+1),len2=strlen(ss+1);
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(register int i=0;i<=len1;++i)
for(register int j=0;j<=len2;++j)
{
if(i&&j)f[i][j]=f[i-1][j-1]+min(abs(s[i]-ss[j]),10-abs(s[i]-ss[j]));
if(j)f[i][j]=min(f[i][j],f[i][j-1]+ss[j]-'0');
if(i)f[i][j]=min(f[i][j],f[i-1][j]+s[i]-'0');
}
printf("%d\n",f[len1][len2]);
return 0;
}
T2
一些闲话
屑出题人，明明数据不会超 $long\space long$ ，取模
菜菜子没取模 100->30
菜菜子就是菜！
题解
按照 b 升序为第一关键词，a 降序为第二关键词
每次贪心的选，把已经选好的放进 set 里，满足 b 后，再尽量让已经选了的更大即可
吐槽一下，标称左偏树不难打吗(
代码
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1000005;
const int inf=0x3f3f3f3f;
int n,a[maxn],b[maxn],pos[maxn];
ll ans;
multiset<int>s;
inline bool cmp(const int &x,const int &y){return b[x]^b[y]?b[x]<b[y]:a[x]>a[y];}
inline int read(void)
{
int num,sign=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')sign=0;
num=c-'0';
while(isdigit(c=getchar()))num=(num<<1)+(num<<3)+c-'0';
return sign?num:-num;
}
signed main(void)
{
n=read();
for(register int i=1;i<=n;++i)a[i]=read(),pos[i]=i;
for(register int i=1;i<=n;++i)b[i]=read();
sort(pos+1,pos+1+n,cmp);
int la=0;
for(register int t,i=1;i<=n;i=i)
{
t=b[pos[i]];
while(la<t+1&&b[pos[i]]==t)ans=(ans+a[pos[i]])%910666,s.insert(a[pos[i]]),++i,++la;
while(b[pos[i]]==t)
{
int res=*s.begin();
if(res<a[pos[i]])s.erase(s.begin()),s.insert(a[pos[i]]),ans=(ans+a[pos[i]]-res)%910666,++i;
else break;
}
while(b[pos[i]]==t)++i;
}
cout<<ans<<endl;
}
T3
还是闲话
我是傻逼 ，思路和题解一模一样，就不写题解之接粘代码了
傻逼了一下，fail 树建好后重复遍历导致答案累加 100->0 ，明明 vis 数组都记录好了，就是不用
代码
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1000005;
const int inf=0x3f3f3f3f;
int n,len[maxn];
char s[maxn*100];
struct anstree
{
int tot,vis[maxn],head[maxn],cnt_edge,edd[maxn],ru[maxn];
ll ans[maxn],cnt[maxn],sum;
struct node
{
int ch[26],fail,pos,fa,cnt;
ll si;
}tr[maxn],ntr[maxn];
struct edge
{
int v,last;
}e[maxn];
inline void addedge(int u,int v){e[++cnt_edge].last=head[u],e[cnt_edge].v=v,head[u]=cnt_edge;++ru[v];}
inline void insert(char *s,int id)
{
len[id]=strlen(s);
int u=0;
for(register int i=0;i<len[id];++i)
{
int c=s[i]-'a';
if(!tr[u].ch[c])tr[u].ch[c]=++tot;
tr[tr[u].ch[c]].fa=u;
u=tr[u].ch[c];
}
tr[u].pos=id,edd[id]=u;
tr[u].si=len[id],tr[u].cnt=1;
}
inline void get_fail(void)
{
queue<int>q;
for(register int i=0;i<=tot;++i)ntr[i]=tr[i];
for(register int i=0;i<26;++i)if(tr[0].ch[i])q.push(tr[0].ch[i]);
while(!q.empty())
{
int u=q.front();
q.pop();
for(register int i=0;i<26;++i)
if(tr[u].ch[i])
tr[tr[u].ch[i]].fail=tr[tr[u].fail].ch[i],q.push(tr[u].ch[i]);
else
tr[u].ch[i]=tr[tr[u].fail].ch[i];
}
}
inline void dfs(int u)
{
if(vis[u])return;
vis[u]=true;
for(register int i=head[u];i;i=e[i].last)
{
int v=e[i].v;
dfs(v);
tr[u].si+=tr[v].si;
tr[u].cnt+=tr[v].cnt;
}
}
inline void getans(int u,int id)
{
while(u)
{
ans[id]+=tr[u].si;
cnt[id]+=tr[u].cnt;
u=tr[u].fa;
}
}
inline void getcon(void)
{
for(register int i=1;i<=tot;++i)addedge(i,tr[i].fail);
for(register int i=1;i<=tot;++i)if(!ru[i])dfs(i);
for(register int i=1;i<=n;++i)getans(edd[i],i);
}
inline void get_w_ans(void)
{
for(register int i=1;i<=n;++i)ans[i]=cnt[i]*len[i]-ans[i],sum+=ans[i];
printf("%lld\n",sum);
for(register int i=1;i<=n;++i)printf("%lld\n",ans[i]);
}
}ccz;
signed main(void)
{
cin>>n;
for(register int i=1;i<=n;++i)
{
scanf("%s",s);
ccz.insert(s,i);
}
ccz.get_fail();
ccz.getcon();
ccz.get_w_ans();
return 0;
}
总结
但凡出题人给了 T2,T3 大样例，也不至于这样
总的来说，很多时候 dp 想不到，多练习dp思维…
注意读题，明明出题人都把模数写在那么显眼的位置还用了粗体标注，甚至括号告知取模，都没取模，争取以后不当瞎子
代码打完过了记得检查一遍，很明显的错误，但神奇的样例确实把他放过了(
以后别犯这么傻逼的错了(
