725D
刚拿到题目一脸懵逼
10万个数字长度十万？？？？？？
哦……字符总数小于十万
妈的吓死了，还以为输入要超时了
构造一个回文串，显然的是，我们可以把两个相反的字符串加到一个回文串的两侧，构成新的回文串。
就这个思路，直接开map离散字符串，然后找一下，如果大于0就加上去，以及：可以在中间放一个本身是回文串的字符串
然后，对于多个相同的字符串的处理方法，显然越大越好
所以我们先对所有输入排序，然后挂链表
嗯……数组模拟链表
然后就可以做了，不知道为什么联想到当前弧优化（逃
以及一个有趣的问题：如果有两个是回文串的字符串，我们是加到两侧还是加一个到中间？
听起来要很多特判的样子。。。
其实不用
我们开一个变量ans1存中间那个字符串的贡献
例如xyz -1,xyz 2这样，我们可以直接把他们放在两侧，然后ans1=max(ans1,-(-1))
为什么？这样相当于把一个去掉，然后把另外一个放到中间去
可以保证中间只有一个
然后。。我WA了两次
至今不知道发生了什么= =？？？理论上没区别啊
？？？
算了。。。OI的世界是玄学的
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<string> #include<map> #include<cstring> #include<ctime> #include<vector> #define inf 1e9 #define ll long long #define For(i,j,k) for(int i=j;i<=k;i++) #define Dow(i,j,k) for(int i=k;i>=j;i--) using namespace std; struct node { string s; int v; }t[100001]; map<string,int> mp; inline bool cmp(node x,node y){return x.v<y.v;} int f[300001],nxt[300001],poi[300001],ans,ans1,n,k,tot,cnt; int main() { ios::sync_with_stdio(false); cin>>n>>k; For(i,1,n) cin>>t[i].s>>t[i].v; sort(t+1,t+n+1,cmp); For(i,1,n) { if(!mp[t[i].s]) { mp[t[i].s]=++tot; poi[++cnt]=t[i].v;nxt[cnt]=0;f[tot]=cnt; } else { int tmp=mp[t[i].s]; poi[++cnt]=t[i].v;nxt[cnt]=f[tmp];f[tmp]=cnt; } } Dow(i,1,n) { string ts; Dow(j,0,k-1) ts+=t[i].s[j]; if(ts==t[i].s) { int tmp=mp[ts]; if(tmp&&f[tmp]&&nxt[f[tmp]]) { int v=poi[f[tmp]]+poi[nxt[f[tmp]]]; if(v>0) ans+=v,ans1=max(ans1,-poi[nxt[f[tmp]]]),f[tmp]=nxt[nxt[f[tmp]]]; else ans1=max(ans1,poi[f[tmp]]); }else if(tmp&&f[tmp]) { ans1=max(ans1,poi[f[tmp]]); } } else { int tmp=mp[ts],tmp1=mp[t[i].s]; if(tmp&&f[tmp]&&f[tmp1]) { int v=poi[f[tmp1]]+poi[f[tmp]]; if(v>0) ans+=v,f[tmp]=nxt[f[tmp]],f[tmp1]=nxt[f[tmp1]]; } } } printf("%d",ans1+ans); }