题解:
第一题:字符连通块
这道题还是比较好想的，首先把每个连通块标记出来，并用第一次扫到的点标记为这个连通块的父节点，接下来要做的就是把一个‘*’周围的连通块连通起来。不过要注意一点，在连通标记的时候不要用memset，memset的复杂度是m/8（m是数组大小），会很慢，直接循环标记就好了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 1050
#define FOR(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;++i)
#define DOR(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;--i)
using namespace std;
char pic[M][M];
int n,m;
char s[M];
bool mark[M][M];
int tmp;
int drx[]= {0,1,-1,0},dry[]= {1,0,0,-1};
struct node{
int x,y;
}Fa[M][M];
int size[M][M];
void DFS(int x,int y,int fax,int fay){
Fa[x][y].x=fax;
Fa[x][y].y=fay;
tmp++;
mark[x][y]=true;
FOR(i,0,3){
int nx=x+drx[i],ny=y+dry[i];
if(nx<=n&&nx>0&&ny<=m&&ny>0&&!mark[nx][ny]&&pic[nx][ny]=='.')
DFS(nx,ny,fax,fay);
}
}
bool Mark[M][M];
int create(int i,int j){
int res=0;
FOR(k,0,3){
int nx=i+drx[k],ny=dry[k]+j;
if(nx>0&&nx<=n&&ny>0&&ny<=m){
if(!Mark[Fa[nx][ny].x][Fa[nx][ny].y]){
Mark[Fa[nx][ny].x][Fa[nx][ny].y]=1;
res+=size[Fa[nx][ny].x][Fa[nx][ny].y];
}
}
}
FOR(k,0,3){
int nx=i+drx[k],ny=dry[k]+j;
Mark[Fa[nx][ny].x][Fa[nx][ny].y]=0;
}
return res+1;
}
struct AC{
void solve(){
FOR(i,1,n){
FOR(j,1,m)if(pic[i][j]=='.'&&!mark[i][j]){
tmp=0;
DFS(i,j,i,j);
size[i][j]=tmp;
}
}
int ans=0;
FOR(i,1,n){
FOR(j,1,m)if(pic[i][j]=='*'){
if(create(i,j)>ans)ans=create(i,j);
}
}
cout<<ans<<endl;
}
}AK;
int main() {
cin>>n>>m;
FOR(i,1,n) {
scanf("%s",s+1);
FOR(j,1,m)pic[i][j]=s[j];
}
AK.solve();
return 0;
}
第二题：回文子序列
这道题比较玄学，我用的是区间dp来写的，但是其他人收到完美队形的启发，秒A，我辛辛苦苦写了半天，什么数据都对上了（包括给的大数据），但就是错了。浑身难受。
这道题可以这么认为，有一个区间有两种情况，要么是首尾相同，要么首尾不同，首尾不同的情况，可以用容斥原理解释，dp［i］［j］=dp［i］［j-1］+dp［i+1］［j-1］-dp［i+1］［j-1］。首尾相同的话，就可以把之前的所有情况都给转移过来了，即dp［i］［j］＝dp［i+1］［j］＋dp［i］［j-1］+1，还要加上只有这两个点的情况。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 2050
#define FOR(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;++i)
#define DOR(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;--i)
using namespace std;
const int P=100007;
int dp[M];//dp[i]
int n;
int flag[M][M];//flag[L][R]
char A[M];
char B[M];
void Add(int &x,int y) {
x+=y;
if(x>=P)x%=P;
}
void create() {
FOR(i,1,n)flag[i][i]=1;
FOR(j,1,n)DOR(i,j-1,1) {
if(A[i]==A[j])Add(flag[i][j],flag[i+1][j]+flag[i][j-1]+1);
else Add(flag[i][j],flag[i+1][j]+flag[i][j-1]-flag[i+1][j-1]+P);
}
}
int main() {
scanf("%s",A+1);
n=strlen(A+1);
create();
cout<<flag[1][n]<<endl;
return 0;
}
第三题：删边最小生成树
这道题我打了个暴力就不打了，去写第二题了，其实不难看出，这道题只要在最小生成树上操作就可以了。若在最小生成树上的边被删去了，那么非树边就会与原来的树形成一个环，只要删除这个环中最小的边就可以了，如果这条边不在最小生成树上，就从这两个点不断往上走，更新每条树边被删去后的最小边。还是比较简单的，毕竟都是随机生成树，还有并查集压边的方法，请见YZK大佬的题解。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define M 200050
#define N 50050
#define INF 1000000009
#define FOR(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;++i)
#define DOR(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;--i)
using namespace std;
struct node {
int fr,to,co,id;
bool operator<(const node&a)const {
return co<a.co;
}
} A[M<<1],B[M];
int Fa[N];
void checkmin(int &x,int y){x=x<y?x:y;}
void checkmax(int &x,int y){x=x>y?x:y;}
bool mark[M<<1];
int degree[N];
int Min;
int n,m;
int ans[M];
int fa[M][2],dep[N];
void Init_ans(){
FOR(i,1,m)ans[i]=INF;
}
void Init() {
FOR(i,1,n)Fa[i]=i;
}
int Find(int x) {
return x==Fa[x]?x:Fa[x]=Find(Fa[x]);
}
bool same(int x,int y) {
return Find(x)==Find(y);
}
void unite(int x,int y) {
Fa[Find(x)]=Find(y);
}
struct Node{
int to,id,co;
};
vector<Node>edge[N];
Node makenode(int to,int id,int co){
Node tmp;
tmp.id=id;
tmp.to=to;
tmp.co=co;
return tmp;
}
void dfs(int x,int f){
dep[x]=dep[f]+1;
fa[x][0]=f;
FOR(i,0,edge[x].size()-1){
int y=edge[x][i].to;
if(y==f)continue;
dfs(y,x);
fa[y][1]=edge[x][i].id;
}
}
int Kruskal(int x) {
int res=0;
Init();
FOR(i,1,m) {
node e=A[i];
if(mark[e.id])continue;
if(!same(e.fr,e.to)) {
unite(e.fr,e.to);
mark[e.id]=true;
edge[e.fr].push_back(makenode(e.to,e.id,e.co));
edge[e.to].push_back(makenode(e.fr,e.id,e.co));
res+=e.co;
}
}
return res;
}
int circle[M];
void up(int x,int y,int co){
if(dep[x]>dep[y])swap(x,y);
while(dep[y]!=dep[x]){
checkmin(circle[fa[y][1]],co);
y=fa[y][0];
}
while(x!=y){
checkmin(circle[fa[y][1]],co);
checkmin(circle[fa[x][1]],co);
x=fa[x][0],y=fa[y][0];
}
}
int main() {
cin>>n>>m;
Init_ans();
FOR(i,1,m)scanf("%d%d%d",&A[i].fr,&A[i].to,&A[i].co),A[i].id=i;
sort(A+1,A+m+1);
fill(circle+1,circle+m+1,INF);
int _=1;
int Min=Kruskal(_);
dfs(1,0);
FOR(i,1,m)if(!mark[A[i].id])up(A[i].fr,A[i].to,A[i].co);
FOR(i,1,m){
if(!mark[A[i].id])ans[A[i].id]=Min;
else {
if(circle[A[i].id]==INF)ans[A[i].id]=-1;
ans[A[i].id]=Min-A[i].co+circle[A[i].id];
}
}
FOR(i,1,m){
if(ans[i]>=INF)puts("-1");
else printf("%d\n",ans[i]);
}
return 0;
}
总结：
这次考得很一般，虽然保底分都拿过来了，但是时间分配出了点问题，第一题卡的时间也太长了，不能完全以水分为目的，而且第一个代码可能什么分都水不到。导致分配给第二题和第三题的时间很少，下次都要注意。
