“学佳澳杯”湖北文理学院第一届程序设计竞赛 个人题解

G-密码专家

看数据一眼区间Dp，转移注意边界。

#include
#define int long long
using namespace std;
const int N=305;int n,dp[N][N],w[10][10],a[N];
string str;int check(int i,int j,int k){int ans=0;if(k-1>=i) ans+=dp[i][k-1];if(k+1<=j) ans+=dp[k+1][j];if(i-1>=1) ans+=w[a[i-1]][a[k]];if(j+1<=n) ans+=w[a[j+1]][a[k]];return ans;
}void solve(){for(int i=1;i<=5;++i){for(int j=1;j<=5;++j){cin>>w[i][j];}}cin>>n;cin>>str;for(int i=1;i<=n;++i) a[i]=str[i-1]-'a'+1;memset(dp,0x3f,sizeof(dp));for(int len=1;len<=n;++len){for(int i=1;i+len-1<=n;++i){int j=i+len-1;for(int k=i;k<=j;++k){dp[i][j]=min(dp[i][j],check(i,j,k));}}}cout<ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;cin>>T;while(T--){solve(); } return 0;
}

H-戏团演出

这是个好题，树链剖分后转化为序列上的差分操作，然后用一个map存当前dfs序位置要修改的操作，然后再一个数组记下颜色的数量，然后再套个线段树求最大值即可。

#include
#define pb emplace_back
#define pii pair
#define mk make_pair
#define F first
#define S second 
using namespace std;
const int N=1e5+7;
inline int read(){int x=0;char ch=getchar();while(!isdigit(ch)) ch=getchar();while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x;
}
int n,m,ans[N];
vectorG[N];
int sz[N],fa[N],son[N],dep[N];
int dfn[N],idfn[N],idx=0,bel[N],cnt[N];
unordered_mapmp[N];
#define mid ((l+r)>>1)
#define inf (1e9+7)
int tot=0,rt;
struct Tr{int ls,rs,mx,mxid;
}tr[N<<5];
void update(int &p,int l,int r,int pos,int val){if(!p) p=++tot;if(l==r){tr[p].mx+=val;tr[p].mxid=pos;return;}tr[p].mx=tr[p].mxid=0;if(pos<=mid) update(tr[p].ls,l,mid,pos,val);else update(tr[p].rs,mid+1,r,pos,val);if(tr[p].ls&&tr[tr[p].ls].mx>tr[p].mx){tr[p].mx=tr[tr[p].ls].mx;tr[p].mxid=tr[tr[p].ls].mxid;}if(tr[p].rs&&tr[tr[p].rs].mx>tr[p].mx){tr[p].mx=tr[tr[p].rs].mx;tr[p].mxid=tr[tr[p].rs].mxid;}
}inline void dfs1(int x,int f){sz[x]=1;for(auto to:G[x]){if(to==f) continue;fa[to]=x;dep[to]=dep[x]+1;dfs1(to,x);sz[x]+=sz[to];if(sz[son[x]]dfn[x]=++idx;idfn[idx]=x;bel[x]=tp;if(son[x]) dfs2(son[x],tp);for(auto to:G[x]){if(to==son[x]||to==fa[x]) continue;dfs2(to,to);} 
}void modify(int x,int y,int z){mp[x][z]++;mp[y+1][z]--;  //使用map来差分颜色 
}bool cmp(const pii lf,const pii rg){if(lf.S!=rg.S) return lf.Srg.F;
}signed main(){n=read();m=read();for(int i=1,u,v;iu=read();v=read();G[u].pb(v);G[v].pb(u); }dfs1(1,0);dfs2(1,1);for(int i=1,u,v,w;i<=m;++i){u=read();v=read();w=read(); while(bel[u]!=bel[v]){if(dep[bel[u]]//for(auto it=mp[i].begin();it!=mp[i].end();++it) now[(it->F)]+=(it->S);for(auto it=mp[i].begin();it!=mp[i].end();++it) update(rt,1,inf,(it->F),(it->S)); ans[idfn[i]]=(tr[1].mxid);cnt[idfn[i]]=(tr[1].mx);//	cout<if(!cnt[i]) puts("0");else printf("%d\n",ans[i]);}return 0;
} 

I-寻宝任务

感觉题意不是很清楚，就是求最短路，然后选一个能够到达的位置并且获得的权值是最大的。

#include
using namespace std;
const int N=505;
const int dx[]={-1,-1,-1,0,1,1,1,0},dy[]={-1,0,1,1,1,0,-1,-1};int n,m,sx,sy,ep,ans=0,vis[N][N],mp[N][N];struct Nod{int x,y,d;bool operator <(const Nod& p)const{return d>p.d; }
};void dijkstra(){memset(vis,-1,sizeof(vis));priority_queueq;q.emplace((Nod){sx,sy,0});while(q.size()){Nod fro=q.top();q.pop();if(vis[fro.x][fro.y]!=-1) continue;if(fro.d>ep) break;if(mp[fro.x][fro.y]>0){ans=max(ans,mp[fro.x][fro.y]);continue;}vis[fro.x][fro.y]=fro.d;for(int i=0;i<8;++i){int nx=fro.x+dx[i],ny=fro.y+dy[i];if(nx<1||ny<1||nx>n||ny>m) continue;q.emplace((Nod){nx,ny,fro.d+(i+1)});	}	}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m>>sx>>sy>>ep;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cin>>mp[i][j];}}dijkstra();cout<