唉 不——开——心——
有些话就不说了。T1打假了，打了T3、T4的特殊样例(共10分)，原本是抱着爆0的心态的，结果没想到T1数据水到直接给了我70分——但T3T4爆掉了， 总分70分 。差点爆0，不——开————心——————
T1【二分图匹配】
题目大意：
给出两个长度分别为n,m(1<=n<=1e3,1<=m<=1e6)的字符串A,B，字符串仅由字符'A'~'Z'组成。 翻译一通后： 求A,B最长公共子串的长度。
解题思路：
我们都知道
一大坨代码
#incIude <bits/stdc++.h>
using namespace std;
const int N=2e3+10;
const int M=1e6+5;
int n,m;
int a[M],b[M],box[100];
int f[N][N];//f[i][j]:匹配i个、s1匹配到下标j，s2所匹配到的地方
int nxt[M][30];//nxt[i][j]:b[i]后第一个值为j的位置
string s1,s2;
int ans;
void init()
{
memset(box,0x3f,sizeof box);
memset(nxt,0x3f,sizeof nxt);
}
int main()
{
init();
cin>>n>>m>>s1>>s2;
for (int i=0;i<n;i++) a[i+1]=(int)(s1[i]-'A');
for (int i=0;i<m;i++) b[i+1]=(int)(s2[i]-'A');
for (int i=m;i>=0;i--)//倒序枚举，box记录上一个j值所出现的位置
{
for (int j=0;j<=25;j++)
{
nxt[i][j]=box[j];
if (b[i]==j) box[j]=i;
}
}
for (int i=1;i<=n;i++) f[i][0]=m+1;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
f[i][j]=min(f[i][j-1],nxt[f[i-1][j-1]][a[j]]);//不匹配第i个，与匹配第i个
}
}
for (int i=n;i>=1;i--)
{
if (f[i][n]<=m)//没有跳出去 即可行
{
cout<<i;
break;
}
}
return 0;
}
T2【虚图】
题目大意：
给出由n个节点、m条变组成的无向图，给出T个“关键点”，求任意两个关键点距离的最小值。
解题思路：
两大坨代码
#incIude <bits/stdc++.h>
#define pii pair<int,int>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,T;
struct node { int nxt,val; };
vector <node> e[N];
struct node2 { int uu,vv,ww; } b[N];
int p[N];
int ans=0x3f3f3f3f3f3f3f3f;
int dis[N],c[N];
bool vis[N];
priority_queue < pii,vector <pii>,greater<pii> > q;
void read()
{
scanf("%lld%lld%lld",&n,&m,&T);
for (int i=1;i<=m;i++)
{
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
e[u].push_back({v,w});
e[v].push_back({u,w});
b[i]={u,v,w};
}
for (int i=1;i<=T;i++) scanf("%lld",&p[i]);
}
void dijstra()
{
memset(dis,0x3f,sizeof dis);
for (int i=1;i<=T;i++)
{
q.push(make_pair(0,p[i]));
dis[p[i]]=0;
c[p[i]]=p[i];//记录是从哪个关键点到的
}
while (!q.empty())
{
pii t=q.top();
q.pop();
int u=t.second;
if (vis[u]) continue;
vis[u]=true;
for (int i=0;i<e[u].size();i++)
{
int v=e[u][i].nxt,w=e[u][i].val;
if (dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
c[v]=c[u];
q.push(make_pair(dis[v],v));
}
}
}
}
signed main()
{
read();
dijstra();
for (int i=1;i<=m;i++)
{
int u=b[i].uu,v=b[i].vv,w=b[i].ww;
if (c[u]==0||c[v]==0) continue;
if (c[u]!=c[v]) ans=min(ans,dis[u]+dis[v]+w);//若是出现u->v->u的情况，那么不要取
}
printf("%lld",ans);
return 0;
}