比赛链接
T1
\(100 \to 10\)。
错因：
-
01 背包转移方程写错，没有取 \(\max\)。
-
并查集合并错写成将
u,v而非fnd(u),fnd(v)合并。
#include<bits/stdc++.h>
using namespace std;
int n,m,w;
int c[10031],d[10031];
int fa[10031];
int dp[10031];
int fnd(int x){ return (fa[x]==x?x:fa[x]=fnd(fa[x])); }
int main(){
//freopen("T1.in","r",stdin);
//freopen("T1.out","w",stdout);
cin>>n>>m>>w;
for(int i=1;i<=n;i++) cin>>c[i]>>d[i],fa[i]=i;
for(int i=1,u,v;i<=m;i++) cin>>u>>v,fa[fnd(u)]=fnd(v);
for(int i=1;i<=n;i++) if(i!=fnd(i)) c[fnd(i)]+=c[i],d[fnd(i)]+=d[i],c[i]=d[i]=0;
for(int i=1;i<=n;i++) for(int j=w;j>=c[i];j--) dp[j]=max(dp[j],dp[j-c[i]]+d[i]);
cout<<dp[w];
return 0;
}
T2
\(100 \to 80\)。
错因：
- 存边数组
e开小，应为4N。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,n,t,tot,etot,ans;
int a[531][531];
int fa[250031],cnt[250031],v[250031];
struct E{ int u,v,w; }e[500031];
int dx[]={1,0},dy[]={0,1};
int fnd(int x){
return (fa[x]==x?x:fa[x]=fnd(fa[x]));
}
void mrg(int x,int y){
fa[x]=y,cnt[y]+=cnt[x],v[y]+=v[x];
cnt[x]=v[x]=0;
}
int get(int x,int y){
return (x-1)*n+y;
}
bool cmp(E x,E y){ return x.w<y.w; }
signed main(){
cin>>m>>n>>t;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>v[get(i,j)];
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
for(int k=0;k<2;k++){
int ii=i+dx[k],jj=j+dy[k];
if(ii>=1&&ii<=m&&jj>=1&&jj<=n)
e[++etot]={get(i,j),get(ii,jj),abs(a[i][j]-a[ii][jj])};
}
for(int i=1;i<=250005;i++) fa[i]=i,cnt[i]=1;
sort(e+1,e+etot+1,cmp);
for(int i=1;i<=etot;i++){
int x=fnd(e[i].u),y=fnd(e[i].v);
if(x!=y){
if(cnt[x]+cnt[y]>=t){
if(cnt[x]<t) ans+=v[x]*e[i].w;
if(cnt[y]<t) ans+=v[y]*e[i].w;
}
mrg(x,y);
}
}
cout<<ans;
return 0;
}
T3
\(100 \to 10\)。
错因：
- 没开
long long。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans,tot;
int a[2031],fa[2031];
struct E{
int u,v,w;
}e[4000031];
bool cmp(E x,E y){ return x.w>y.w; }
int fnd(int x){ return (fa[x]==x?x:fa[x]=fnd(fa[x])); }
void kruskal(){
for(int i=1;i<=tot;i++){
int x=fnd(e[i].u),y=fnd(e[i].v);
if(x!=y){
fa[x]=y,ans+=e[i].w;
//if(cnt==n-1) return;
}
}
}
signed main(){
//freopen("T3.in","r",stdin);
//freopen("T3.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
e[++tot].u=i,e[tot].v=j,e[tot].w=a[i]^a[j];
sort(e+1,e+tot+1,cmp);
kruskal();
cout<<ans;
return 0;
}
T4
\(100 \to 20\)。
错因：
- 统计到达点数的计数器 \(s\) 初值设错为 \(1\) 而非 \(0\)。
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
vector<int> G[4531];
int dp[131][131];
void floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dp[i][k]&&dp[k][j])
dp[i][j]=1;
}
int main(){
//freopen("T4.in","r",stdin);
//freopen("T4.out","w",stdout);
cin>>n>>m;
//for(int i=1;i<=n;i++) dp[i][i]=0;
for(int i=1,u,v;i<=m;i++) cin>>u>>v,dp[u][v]=1;
floyd();
for(int i=1;i<=n;i++){
int s=0;
for(int j=1;j<=n;j++)
if(j!=i) s+=(dp[i][j]||dp[j][i]);
if(s==n-1) ans++;
}
cout<<ans;
return 0;
}
T5
\(100\)。
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int t[231];
int dp[231][231];
void upd(int k){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
int main(){
//freopen("T5.in","r",stdin);
//freopen("T5.out","w",stdout);
cin>>n>>m;
memset(dp,0x3f,sizeof(dp));
for(int i=0;i<n;i++) dp[i][i]=0;
for(int i=0;i<n;i++) cin>>t[i];
for(int i=0,u,v,w;i<m;i++)
cin>>u>>v>>w,
dp[u][v]=dp[v][u]=w;
cin>>q;
int cur=0;
for(int i=0,x,y,tt;i<q;i++){
cin>>x>>y>>tt;
for(;t[cur]<=tt;cur++) upd(cur);
if(t[x]>tt||t[y]>tt) cout<<"-1\n";
else if(dp[x][y]==0x3f3f3f3f) cout<<"-1\n";
else cout<<dp[x][y]<<'\n';
}
return 0;
}
T6
\(100\)。
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int dp[10031],in[10031],len[10031];
vector<int> G[10031];
void topo(){
queue<int> q;
for(int i=1;i<=n;i++)
if(!in[i]) q.push(i),dp[i]=len[i];
while(!q.empty()){
int now=q.front(); q.pop();
for(int i:G[now]){
dp[i]=max(dp[i],dp[now]+len[i]),in[i]--;
if(!in[i]) q.push(i);
}
}
}
int main(){
//freopen("T6.in","r",stdin);
//freopen("T6.out","w",stdout);
cin>>n;
for(int i=1,u,v;i<=n;i++){
cin>>u>>len[i];
while(cin>>v&&v) G[u].push_back(v),in[v]++;
}
topo();
int ans=-1e9;
for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
cout<<ans;
return 0;
}
T7
\(100 \to 80\)。
错因：
dp转移时机出错，应当在点入队时转移而非枚举邻接点时转移。
#include<bits/stdc++.h>
using namespace std;
int n,m,id;
int dp[131],in[131],iin[131];
bool vis[131],p[131];
string path;
vector<int> G[631];
void check(){
for(int i='A';i<='Z';i++){
//cout<<dp[i]<<' ';
if(dp[i]==n&&p[i]) cout<<"Sorted sequence determined after "<<id<<" relations: "<<path<<".",exit(0);
}
for(int i='A';i<='Z';i++){
//cout<<vis[i]<<' ';
if(!vis[i]&&p[i]) cout<<"Inconsistency found after "<<id<<" relations.",exit(0);
}
}
void topo(){
queue<int> q;
for(int i='A';i<='Z';i++)
if(!iin[i]&&p[i]) q.push(i),dp[i]=vis[i]=1;
while(!q.empty()){
int now=q.front(); q.pop(),path+=(char)(now);
for(int i:G[now]){
dp[i]=dp[now]+1,iin[i]--;
if(!iin[i]) q.push(i),vis[i]=1;
}
}
}
int main(){
//freopen("T6.in","r",stdin);
//freopen("T6.out","w",stdout);
cin>>n>>m;
for(id=1;id<=m;id++){
char u,v,op;
cin>>u>>op>>v,G[u].push_back(v);
if(u==v) cout<<"Inconsistency found after "<<id<<" relations.",exit(0);
in[v]++,p[u]=p[v]=1;
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
memcpy(iin,in,sizeof(iin));
path="";
topo(),check();
}
cout<<"Sorted sequence cannot be determined.";
return 0;
}
总结：
- 本次挂分巨大，下次每题写完后应当及时静态差错并对拍。