第二次模拟赛-总结
总分
140
复盘：
T1
做法：一个很朴素的哈希
把1~i的正串和反串都用哈希处理出来，然后进行比较，如果相同的话肯定就是回文串喽，dp[i]=dp[i/2]+1
写挂了*1 考场思路错误（题没读懂+原本就不是很会
WA 10
T2
做法:在dijk过程中进行一个dp， dp[i][j] 表示目前在i号点还剩j次免费机会时最小值时多少
写挂了 死因：补充题意里的双向边没看
加了双向边直接AC
AC 100 → WA 0
T3
最大半连通子图
做法：Tarjan缩点，去重边，重新建图，跑一个拓扑，用dp在拓扑过程中记录f[i] 为第i个半连通块的大小，g[i]表示有多少个这样的半连通块
细节比较多，写挂了
至今仍未知死因
WA 0
T4
种树
一个简单的差分约束
记a为前缀和数组 注意3种建边
1：a[i+1]-a[i]>=0\\
\\
2.a[r]-a[l-1]>=k\\
\\
3.a[i]-a[i-1]<=a\\
建边后跑一遍最长路，输出答案。
AC 100
T5
一道DP题（式子还没推出来就不说了
当时第五第六题只留了30分钟，打了两个暴力上去
绿题
WA 0
T6
一道推式子然后DP的题
j[r]-j[l-1]==o[r]-o[l-1]==l[r]-l[l-1];\\
\\
移项\\
\\
j[r]-j[l-1]-o[r]+o[l-1]==l[r]-l[l-1]-j[r]+j[l-1]==0\\
设 x[i]=o[i]-j[i],y[i]=l[i]-j[i];\\
\\
所以\\
\\
x[l-1]-x[r]==y[r]-r[l-1]==0;\\
x[r]==x[l-1];\\
y[r]==y[l-1];\\
\\
所以\\
\\
x[r]==x[l-1] 且 y[r]==y[l-1]\\
（这个只是推导过程，详情见代码）
//AC代码\\
#include<bits/stdc++.h>
using namespace std;
string s;
int j[1000005],o[1000005],l[1000005],x[1000005],y[1000005];
map<int,map<int,int>> dp;
int ans=0,len;
int main(){
cin.tie(0);
cin>>len>>s;
s=" "+s;
for(int i=1;i<=len;i++){
if(s[i]=='J'){
j[i]++;
x[i]--;;
y[i]--;
}else if(s[i]=='O'){
o[i]++;
x[i]++;
}else if(s[i]=='I'){
l[i]++;
y[i]++;
}
j[i]+=j[i-1];
o[i]+=o[i-1];
l[i]+=l[i-1];
x[i]+=x[i-1];
y[i]+=y[i-1];
}
for(int i=1;i<=len;i++){
/*
j[r]-j[l-1]==o[r]-o[l-1]==l[r]-l[l-1];
移项
j[r]-j[l-1]-o[r]+o[l-1]==l[r]-l[l-1]-j[r]+j[l-1]==0
设 x[i]=o[i]-j[i],y[i]=l[i]-j[i];
所以
x[l-1]-x[r]==y[r]-r[l-1]==0;
x[r]==x[l-1];
y[r]==y[l-1];
所以
x[r]==x[l-1]&&y[r]==y[l-1]
答案长度为
*/
if(!dp[x[i]][y[i]]){
dp[x[i]][y[i]]=i;
}else{
int num=dp[x[i]][y[i]];
ans=max(ans,i-dp[x[num]][y[num]]);
}
}
for(int i=1;i<=len;i++){
if(j[i]==o[i]&&o[i]==l[i]){
ans=max(ans,i);
}
}
cout<<ans;
return 0;
}
考场上没写出来，赛后问大佬 @cym
WA 0
寄
