这次比赛zz的不行，本来预计100+100+15+15+100+100=430的。。
但是T2的错误和T5的错误实在是好笑。。。
T1：
模拟
code:
#include<bits/stdc++.h>
using namespace std;
int n,a[1010],b[1010];
char s1[1010],s2[1010];
int ans;
int main(){
scanf("%d%s%s",&n,s1+1,s2+1);
for(int i=1;i<=n;i++){
a[i]=s1[i]-'0';
b[i]=s2[i]-'0';
int x=abs(a[i]-b[i]);
// printf("%d %d\n",a[i],b[i]);
int y=10-a[i]+b[i];
int z=10-b[i]+a[i];
ans+=min(x,min(y,z));
}
printf("%d",ans);
return 0;
}T2:
没有上司的舞会改版。。但是要注意map细节。。。
使用map来离散这些人名，然后跑树形DP即可
code:
#include<bits/stdc++.h>
using namespace std;
int n,root,g[100010];
int f[100010][2],cnt;
string x,y;
map<string,int> mp;
vector<int> edge[100010];
void tree_dp(int u,int pre){
for(int i=0;i<edge[u].size();i++){
int v=edge[u][i];
if(v==pre) continue;
tree_dp(v,u);
f[u][0]+=max(f[v][0],f[v][1]);
f[u][1]+=f[v][0];
}
return;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>x;
if(!mp[x]) mp[x]=++cnt;
scanf("%d",&f[mp[x]][1]);
cin>>y;
if(!mp[y]) mp[y]=++cnt;
// f[mp[y]][1]=temp;
if(y=="NOBODY") root=mp[x];
g[mp[x]]=1;
edge[mp[x]].push_back(mp[y]);
edge[mp[y]].push_back(mp[x]);
}
// for(int i=1;i<=cnt;i++)if(!g[i]) root=i;
tree_dp(root,0);
printf("%d",max(f[root][1],f[root][0]));
return 0;
}T3:
不会。。打个15分的骗分吧。。
T4：
60分的算法有些问题。。我的只有50分。。。
正常的奇偶性贪心是错误的
@larryzhong @wujinzhao @siyuan 求教各位大佬哪里错了。。
code:
#include<bits/stdc++.h>
using namespace std;
int f[10010][10010][2][2];
int n,a[200010],m;
int main(){
scanf("%d%d",&n,&m);
if(m>n/2){
puts("Error!");
return 0;
}
// memset(f,-127,sizeof(f));
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
f[1][1][1][1]=a[1];
for(int i=2;i<=n;i++)
for(int j=1;j<=m;j++){
f[i][j][0][0]=max(f[i-1][j][0][0],f[i-1][j][1][0]);
f[i][j][0][1]=max(f[i-1][j][0][1],f[i-1][j][1][1]);
f[i][j][1][0]=f[i-1][j-1][0][0]+a[i];
if(i!=2) f[i][j][1][1]=f[i-1][j-1][0][1]+a[i];
}
// for(int i=1;i<=n;i++)
// for(int j=1;j<=m;j++)printf("%d %d %d %d\n",i,j,f[i][j][0],f[i][j][1]);
int ans=0;
ans=max(max(f[n][m][1][0],f[n][m][0][0]),f[n][m][0][1]);
printf("%d",ans);
return 0;
}T5:
一道图论题。。。
发现最后求的答案肯定位于原图最小生成树上（环切性质）
先处理处最小生成树，然后每次做LCA求一下即可
code:
#include<bits/stdc++.h>
#define pb push_back
#define mk make_pair
#define fi first
#define se second
using namespace std;
struct node{
int x,y,z;
}edge[100010];
int fa[100010];
int n,m,q;
int u,v,ans;
int f[100010][30],g[100010][30];
int dep[100010];
vector<pair<int,int> > e[100010];
int cmp(node a,node b){return a.z<b.z;}
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
void dfs(int u,int d,int pre,int cnt){
f[u][0]=pre;
g[u][0]=cnt;
dep[u]=d;
for(int i=0;i<e[u].size();i++){
int v=e[u][i].fi;
if(v==pre) continue;
if(dep[v]) continue;
dfs(v,d+1,u,e[u][i].se);
}
return;
}
int main(){
// memset(g,127,sizeof(g));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
sort(edge+1,edge+m+1,cmp);
int sum=0;
for(int i=1;i<=m;i++){
if(sum==n-1) break;
int fx=getfa(edge[i].x),fy=getfa(edge[i].y);
if(fx!=fy){
e[edge[i].x].pb(mk(edge[i].y,edge[i].z));
e[edge[i].y].pb(mk(edge[i].x,edge[i].z));
fa[fx]=fy;
sum++;
}
}
scanf("%d",&q);
dfs(1,1,0,0);
for(int j=1;j<=25;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1],g[i][j]=max(g[i][j-1],g[f[i][j-1]][j-1]);
for(int ij=1;ij<=q;ij++){
scanf("%d%d",&u,&v);
ans=0;
if(dep[u]<dep[v]) swap(u,v);
for(int i=25;i>=0;i--)
if(dep[u]>=dep[v]+(1<<i)) ans=max(ans,g[u][i]),u=f[u][i];
if(u==v){printf("%d\n",ans);continue;}
for(int i=25;i>=0;i--)
if(f[u][i]!=f[v][i]){
ans=max(ans,max(g[u][i],g[v][i]));
u=f[u][i];v=f[v][i];
}
ans=max(ans,max(g[u][0],g[v][0]));
printf("%d\n",ans);
}
return 0;
}T6:
发现每次移动其实不管移动多少，我们只关心前缀最小和和后缀最小和
于是枚举k，然后判断是否可行即可
code:
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[1000010],b[1000010];
int c[1000010],d[1000010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int tot=a[1];b[1]=a[1];
for(int i=2;i<=n;i++){
tot+=a[i];
b[i]=min(tot,b[i-1]);
}
c[n]=a[n],d[n]=a[n];
for(int i=n-1;i>=1;i--){
c[i]=min(a[i],c[i+1]+a[i]);
d[i]=d[i+1]+a[i];
}
for(int i=1;i<=n;i++)
if(c[i]>=0&&d[i]+b[i]>=0) ans++;
printf("%d",ans);
return 0;
}
