Codeforces Round #526 (Div. 1)

毕竟是上紫之后的第一场div1，还是太菜了啊，看来我要滚回去打div2了。

A. The Fair Nut and the Best Path

这题本来是傻逼贪心dfs，结果我越写越麻烦，然后就只有150了。。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<vector>

#include<cmath>

#include<cctype>

using namespace std;

typedef long long ll;

const int Maxn=610000;

int to[Maxn],nxt[Maxn],first[Maxn],tot=1;

int n,u,v;

ll a[Maxn],ans,w[Maxn],wi;

queue<int>q;

inline void add(int u,int v,ll wi) {

	to[tot]=v;

	nxt[tot]=first[u];

	w[tot]=wi;

	first[u]=tot++;

	to[tot]=u;

	nxt[tot]=first[v];

	w[tot]=wi;

	first[v]=tot++;

}

ll dfs(int root,int fa) {

	ll mx=0,cd=0,sxz=a[root];

	for(int i=first[root];i;i=nxt[i])

		if(to[i]!=fa) {

			ll temp=dfs(to[i],root)-w[i];

			if(temp>mx) cd=mx,mx=temp;

			else cd=max(cd,temp);

		}

	sxz+=mx;

	ans=max(ans,sxz+cd);

	return sxz;

}

int main() {

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%I64d",&a[i]);

	for(int i=1;i<n;i++) {

		scanf("%d%d%I64d",&u,&v,&wi);

		add(u,v,wi);

	}

	dfs(1,1);

	printf("%I64d\n",ans);

	return 0;

}

B - The Fair Nut and Strings

这道题开始时看上去很毒瘤，但是仔细一想会发现这里面有个树的结构，具体讲不太明白，自己看看代码就好了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<vector>

#include<cmath>

#include<cctype>

using namespace std;

typedef long long ll;

const int Maxn=610000;

int n,k;

char a[Maxn],s[Maxn];

int main() {

	scanf("%d%d",&n,&k);

	scanf("%s",a);

	scanf("%s",s);

	if(k==1||strcmp(a,s)==0) {

		printf("%d\n",n);

		return 0;

	}

	int temp=0;ll sxz=2,ans=0;

	while(a[temp]==s[temp]) temp++;ans+=temp;ans+=2;

	for(int i=temp+1;i<n;i++) {

		sxz<<=1;

		if(a[i]=='b') sxz--;

		if(s[i]=='a') sxz--;

		if(sxz>=k) {

			ans+=1ll*(n-i)*k;

			break;

		}

		ans+=sxz;

	}

	printf("%I64d\n",ans);

	return 0;

}

还是自己太菜啊。。