总结

T1

这题我一看，哇！好简单啊！

直接建立每一个字母的映射就可以了。

我很快就打完了程序，跳到下一题。

等到比赛快结束时，我才发现了一个可怕的数据：

1

abcdefghijklmnopqrstuvwxyz

zyxwvutsrqponmlkjihgfedcba

这样每次无论把哪一种字母进行操作，代码中都会出现两个相同的字母——这意味着在以后的操作中，它们都会一起被修改。

我不知怎么办，只好估分0分，重交一次。

然而，出题人忽略了这种情况。

某DL特地判了这种情况，只拿了10分。

最后，我只拿了10分（What the hell?），搞了半天，发现原来是我打错了一个地方——我的映射数组只开到了[0..25]，每次映射字母时，ASCLL码都要减去97，但是我某个地方却没有减97。

以后打题时，哪怕一道题目有多简单，都要打一下对拍，多测几个数据。不能再犯这样的错误了！

T2

比赛时打了个二分+SPFA，每一次把温度大于二分结果的路径删去，再跑一次SPFA计算最小温度和。结果TLE 50分了（数据真心毒）。

其实可以新建一个空图，将所有的边按温度排序。

每一次在图中加入一条新的边，并把所有与它温度相同的边加入到图中，直到起点和终点连通。

然后我们就得到了一个最小生成图，在图上跑一遍SPFA即可。

T3

比赛时打了\(w_i=0\)的情况的表，水了10分。

可以设\(f_{i,j}\)表示从i出发，走到i的子树中，再返回到i，用了j的时间的最大和；\(g_{i,j}\)表示从i出发，走到i的子树中不返回，用了j的时间的最大和；\(h_{i,j}\)表示从i的某个子树中出发，经过i（可多次经过），到达i的其它子树，用了j的时间的最大和。如下图，考虑加入红色子树（下面所说的原树都不包含红色子树）。

我们先考虑h的转移：

\(h_{i,j}\)可以通过在原来的树中用k的时间走，再用j-k-t的时间在红色子树中走的和更新（为了方便，i与红色子树之间的连边长度设为t）。状态转移方程显然为h[i][j]=max(h[i][j],h[now][k]+f[son][j-k-2*t]);
相似地，可以得出方程h[i][j]=max(h[i][j],f[i][k]+h[son][j-k-2*t])
其实可以从原树的某子树出发，经过点i，再到达红色子树（不返回），状态转移方程就为h[i][j]=max(h[i][j],g[i][k]+g[son][j-k-t])为什么都用g？因为无论顺着走一条路或是倒着走一条路，其权值和都不会变。

可以发现，其他方法都不会更优（包括h+h的做法）

相似地，我们可以写出g和f的转移方程：

g[i][j]=max(g[i][j],g[i][k]+f[son][j-k-2*t]);

g[i][j]=max(g[i][j],f[i][k]+g[son][j-k-t]);

f[i][j]=max(f[i][j],f[i][k]+f[son][j-k-2*t])

注意一下DP的顺序（先h再g最后f），不然会WA（因为我们所用的\(f_{i,j}\)、\(g_{i,j}\)都是原树中的，若是先求出则会把红色子树也计算在内，搞不好会加两次红色子树，从而使答案出错）

标程

T1

#include<cstdio>

#include<cstring>

using namespace std;

#define minus 'a'

char a[1010],b[1010],turn[26];

int main()

{

	freopen("copycat.in","r",stdin);

	freopen("copycat.out","w",stdout);

	int t,i,j,n,m;

	char ch;bool bk;

	scanf("%d\n",&t);

	while(t--)

	{

		gets(a+1),gets(b+1);

		n=strlen(a+1),m=strlen(b+1);

		if(n!=m)

		{

			puts("0");

			continue;

		}

		for(i=0;i<26;i++) turn[i]='\0';

		for(i=1,bk=0;i<=n;i++) if(a[i]!=b[i])

		{

			if(b[i]<'a'||b[i]>'z'||a[i]<'a'||a[i]>'z')

			{

				bk=1;

				break;

			}

			if(turn[a[i]-minus])

			{

				if(turn[a[i]-minus]!=b[i])

				{

					bk=1;

					break;

				}

			}

			else turn[a[i]-minus]=b[i];

		}

		if(bk) puts("0");

		else puts("1");

	}

	return 0;

}

T2

#include<algorithm>

#include<cstdio>

#include<queue>

using namespace std;

#define ll long long

#define N 500010

#define M 1000010

#define inf 100000000000010ll

struct edge

{

	ll end,lenth,temp,next;

}a[M<<1];

struct readIn

{

	ll start,end,temp,lenth;

}input[M];

queue<ll>data;

ll first[N],dis[N],f[N],n,m,s,S,T,num;

char ch;bool exist[N];

ll getfather(ll k)

{

	if(f[k]==k) return k;

	return f[k]=getfather(f[k]);

}

bool cmp(readIn x,readIn y){return x.temp<y.temp;}

inline void read(ll &x)

{

	while(ch=getchar(),ch<'0'||ch>'9');

	x=ch-48;

	while(ch=getchar(),ch>='0'&&ch<='9') x=x*10+ch-48;

}

inline void inc(ll x,ll y,ll z,ll t)

{

	a[++s]=(edge){y,z,t,first[x]};

	first[x]=s;

	a[++s]=(edge){x,z,t,first[y]};

	first[y]=s;

}

inline void spfa()

{

	ll i,u,v;

	dis[S]=0;data.push(S);

	while(!data.empty())

	{

		u=data.front();

		exist[u]=1;

		data.pop();

		for(i=first[u];i;i=a[i].next)

		{

			v=a[i].end;

			if(a[i].temp<=num&&dis[v]>dis[u]+a[i].lenth)

			{

				dis[v]=dis[u]+a[i].lenth;

				if(exist[v])

				{

					exist[v]=0;

					data.push(v);

				}

			}

		}

	}

}

inline void Kruskal()

{

	ll i,j;

	for(i=0,j=1;getfather(S)!=getfather(T);i++)

	{

		for(;j<=m&&input[j].temp==i;j++)

		{

			inc(input[j].start,input[j].end,input[j].lenth,input[j].temp);

			f[getfather(input[j].start)]=getfather(input[j].end);

		}

		if(j>m) break;

	}

	num=i;

	if(num) num--;

}

int main()

{

	freopen("running.in","r",stdin);

	freopen("running.out","w",stdout);

	ll i,j;

	read(n),read(m);

	for(i=1;i<=n;i++) f[i]=i,dis[i]=inf,exist[i]=1;

	for(i=1;i<=m;i++)

	{

		read(input[i].start),read(input[i].end),

		read(input[i].temp),read(input[i].lenth);

		input[i].lenth*=input[i].temp;

	}

	read(S),read(T);

	sort(input+1,input+m+1,cmp);

	Kruskal();spfa();

	printf("%lld %lld\n",num,dis[T]);

	return 0;

}

T3

#include<cstdio>

#include<cstring>

using namespace std;

#define N 305

struct edge

{

	int end,lenth,next;

}a[N<<1];

int first[N],t[N],w[N],f[N][N],g[N][N],h[N][N],n,m,s,ans;

inline void inc(int x,int y,int z)

{

	a[++s]=(edge){y,z,first[x]};

	first[x]=s;

	a[++s]=(edge){x,z,first[y]};

	first[y]=s;

}

inline int max(int x,int y){return x>y?x:y;}

void dfs(int now,int from)

{

	f[now][t[now]]=g[now][t[now]]=h[now][t[now]]=w[now];

	int i,j,k,t;

	for(i=first[now];i;i=a[i].next)

		if(a[i].end!=from)

		{

			dfs(a[i].end,now);

			for(j=m;j>=a[i].lenth;j--)

				for(k=j-a[i].lenth;k>=0;k--)

				{

					if(j-k-2*a[i].lenth>=0)

						h[now][j]=max(h[now][j],h[now][k]+f[a[i].end][j-k-2*a[i].lenth]);

					h[now][j]=max(h[now][j],g[now][k]+g[a[i].end][j-k-a[i].lenth]);

					if(j-k-2*a[i].lenth>=0)

						h[now][j]=max(h[now][j],f[now][k]+h[a[i].end][j-k-2*a[i].lenth]),

						g[now][j]=max(g[now][j],g[now][k]+f[a[i].end][j-k-2*a[i].lenth]);

					g[now][j]=max(g[now][j],f[now][k]+g[a[i].end][j-k-a[i].lenth]);

					if(j-k-2*a[i].lenth>=0)

						f[now][j]=max(f[now][j],f[now][k]+f[a[i].end][j-k-2*a[i].lenth]);

				}

		}

}

int main()

{

	freopen("toyuq.in","r",stdin);

	freopen("toyuq.out","w",stdout);

	int i,j,x,y,z;

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

	for(i=1;i<=n;i++) scanf("%d",&w[i]);

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

	{

		scanf("%d",&t[i]);

		if(t[i]>300) t[i]=301;

	}

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

	{

		scanf("%d%d%d",&x,&y,&z);

		inc(x,y,z);

	}

	memset(f,192,sizeof(f));

	memset(g,192,sizeof(g));

	memset(h,192,sizeof(h));

	dfs(1,0);

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

		for(j=0;j<=m;j++)

			ans=max(ans,max(f[i][j],max(g[i][j],h[i][j])));

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

	return 0;

}

巴特西

2018.08.15【2018提高组】模拟A组比赛总结

总结

T1

T2

T3

标程

T1

T2

T3

最新文章

热门文章

巴特西

2018.08.15【2018提高组】模拟A组 比赛总结

总结

T1

T2

T3

标程

T1

T2

T3

最新文章

热门文章

2018.08.15【2018提高组】模拟A组比赛总结