首页 > 其他 > 详细

GDUT决赛题解

时间:2017-07-31 09:46:22      阅读:194      评论:0      收藏:0      [点我收藏+]

决赛,我自我认为题目难度更大,反而我的心态更好了。

由于放轻松的时候反而效果更好,跟昨天的观点一样,凡是可以1A的,才算这题做得好。


A.数目不大,关键是看懂题(我自己连输入输出是什么都不清楚。。。。

然后管理员就把题下掉了。

。。批评批评啊。

。。

)bin神的代码膜拜了下。知道是状态压缩,题中说了最多6个,要么1<<6枚举,要么6!枚举。代码:

/* ***********************************************
Author        :kuangbin
Created Time  :2015/3/15 14:17:30
File Name     :GDUT\A.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int dp[1000];
int st[6410],cost[6410];
int num[6410];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		int cnt = 0;
		for(int i = 0;i < n;i++){
			int m;
			int nn;
			int p;
			scanf("%d%d",&m,&nn);
			while(m--){
				int k;
				scanf("%d",&k);
				st[cnt] = 0;
				num[cnt] = nn;
				while(k--){
					scanf("%d",&p);
					st[cnt] |= (1<<p);
				}
				scanf("%d",&cost[cnt]);
				cnt++;
			}
		}
		for(int i = 0;i < (1<<6);i++)dp[i] = INF;
		dp[0] = 0;
		for(int i = 0;i < (1<<6);i++){
			if(dp[i] == INF)continue;
			for(int j = 0;j < cnt;j++){
				if( (i&(1<<num[j])) != 0)continue;
				if( (i|st[j]) != i )continue;
				dp[i|(1<<num[j])] = min(dp[i|(1<<num[j])],dp[i]+cost[j]);
			}
		}
		int tot = (1<<6)-1;
		if(dp[tot] == INF)dp[tot] = -1;
		printf("%d\n",dp[tot]);
	}
    return 0;
}

B.区间DP,因为是随意地方插入0或者1,那么单位长度显然ans为0。两个长度作为初始化推断。然后区间DP

代码:

/* ***********************************************
Author        :kuangbin
Created Time  :2015/3/15 13:05:55
File Name     :GDUT\B.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
char str[1010];
int a[1010];

int dp[1010][1010];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T;
	int n;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		scanf("%s",str);
		for(int i = 0;i < n;i++)
			a[i] = str[i]-'0';
		memset(dp,0,sizeof(dp));
		for(int i = 0;i < n;i++)
			dp[i][i] = 1;
		for(int i = n-1;i >= 0;i--)
			for(int j = i+1;j < n;j++){
				dp[i][j] = j-i+1;
				if(a[i] != a[j])
					dp[i][j] = min(dp[i][j],dp[i+1][j-1]);
				dp[i][j] = min(dp[i][j],dp[i+1][j]+1);
				dp[i][j] = min(dp[i][j],dp[i][j-1]+1);
			}
		printf("%d\n",dp[0][n-1]);
	}
    return 0;
}


另外,另一种非常好的思路。依照题意来,取反,翻转。那么反复的不须要加入0或者1。转换为最多反复多少个,所以转换为LCS(Longest Common Sequence)代码不须要写吧,O(n^2)的算法。n=1000妥妥的


C.这道题表述上事实上是没有问题的,可是大家会陷于自己生活中的误区,菜怎么可能炒到一半就换种菜?这个题的第一组数据是个非常经典的小学竞赛问题:2个锅,要做出来3个饼,每一个饼须要2分钟做好,问你最少几分钟能够做好?答案是3.过程是这样:第一分钟,做第1和2个饼;第二分钟,做第2和3个饼。第三分钟,做1和3个饼。

那么,非常明显:利用的贪心思想。

把全部的饼尽可能的分到不同的锅里去。

那么就是取平均值的上整数值。可是一个菜不能分成多份,那么就是要统计出最大值,于是,求得就是平均值的上整数值和最大值的较大值。绕口,可是代码非常好懂

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 99999999
#define pi 3.1415926535897932384626433832795028841971

int main(){
	int t,n,m;
	int Max,aver,num;
	scanf("%d",&t);
	while(t--){
		aver=Max=0;
		scanf("%d%d",&n,&m);
		while(n--){
			scanf("%d",&num);
			Max=max(Max,num);
			aver+=num;
		}
		aver=(aver+m-1)/m;
		printf("%d\n",max(aver,Max));
	}
	return 0;
}

D.数学题。

假设GCD(a,b)==n   LCM(a,b)==m   那么 m/n  是a b 的互质因子乘积    那就是枚举  1到m/n 互质的对数吧。sqrt(n)的复杂度。明显能够接受
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<set>
#include<iostream>
using namespace std;
typedef long long LL;

LL n, m;
LL Gcd(LL x, LL y)
{
	if (!y) return x;
	else
		return Gcd(y, x%y);
}
LL solve(LL n)
{
	LL sum = 0;
	LL i, j;
	for (i = 1; i <= (double)sqrt(n*1.0); i++)
	{
		if (n%i==0)
		{
			j = n / i;
			if (Gcd(i, j) == 1) ++sum;
		}
	}
	return sum;
}
int main()
{
	int T, i, Case = 0, j, k;
	//freopen("data.txt", "r", stdin);
	scanf("%d", &T);
	while (T--)
	{
		scanf("%lld%lld", &n, &m);
		if (m%n)
		{
			printf("0\n"); continue;
		}
		LL temp = m / n;
		printf("%lld\n", solve(temp));
	}
	return 0;
}


第五题。并查集基础。我当时煞笔WA了五次。。。

原因就是太过于自信。我的找爸爸直接用的fa[i]而不是getf[i]。

。。。。哭死。

。。

有些细节问题,不要一直提交的啊。。能够先做做别的题冷静冷静,或者自己写几个測试数据,检測下。20分钟罚时非常多的啊

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 99999999
#define pi 3.1415926535897932384626433832795028841971

const long long maxn=1000050;
int t;
long long n,m;

long long fa[maxn];

void init(){
	for(long long i=0;i<=n;i++) fa[i]=i;
}

long long getf(long long x){
	if (fa[x]==x) return x;
	return fa[x]=getf(fa[x]);
}

int main(){
	input;
	long long i,j,k;
	scanf("%d",&t);
	while(t--){
		scanf("%lld%lld",&n,&m);
		init();
		while(m--){
			scanf("%lld",&i);
			scanf("%lld",&j);
			long long fi=getf(i);
			long long fj=getf(j);
			if (fi!=fj) fa[fi]=fj;
		}
		k=0;
		long long f1=getf(1);
		for(i=2;i<=n;i++){
			int fi=getf(i);
			if (fi!=f1){
				fa[fi]=f1;
				k++;
			}
		}
		printf("%lld\n",k);
	}
	return 0;
}


F.模拟。这道题没难度的哈。

依照题目的意思来呗。

要你干啥就干啥。推断n和m仅仅有100怎么循环都只是分的

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 99999999
#define pi 3.1415926535897932384626433832795028841971

int vis[200];
int num[200];
int main(){
	//input;
	int t;
	int n,m;
	int i,j,k;
	scanf("%d",&t);
	while(t--){
		memset(vis,0,sizeof(vis));
		scanf("%d%d",&n,&m);
		for(i=1;i<=m;i++) scanf("%d",&num[i]);
		
		for(i=1;i<=m;i++)
			for(j=1;j<=n;j++){
				if (vis[j]) continue;
				if (j>=num[i]) vis[j]=num[i];
			}
		
		for(i=1;i<=n;i++) printf("%d%c",vis[i],i==n?'\n':' ');
	}
	return 0;
}

关键的细节问题是:每一个灯最多被关一次。意味着假设曾经訪问过这个点,那么之后不管大小关系,都不会理它了


G.数学题。意思是说求(1+n)*n/2这个数列之中。告诉你n,有多少个数被3整除。


看到那么大的n心里就不要慌啊,肯定是有规律的啊。肯定是不能打表的啊,肯定是小数据猜过程猜结论的啊
或者写出这个数列:1 3 6 10 15 21 28 36 45 55 66 78……
看到规律了吗?每三个数一组,每组的第一个不是3的倍数,第二个和第三个是3的倍数。程序大家自己写吧

H.DP。我最高兴的是这道题我的思路跟bin神是一样的啊,说明有些题是能够做的啊,不要自己吓自己的,比方BC33的第3题。我看着是状态压缩。。赛后理解就是个复杂一点的背包。。(扯远了。。)
定义:dp[i][j][k]代表第一个手指在i处。第二个手指在j处,当前已经完毕k格走过的最短距离。0<=i<=4,0<=j<=4,1<=k<=n。

依据题中数据,n最大10000。

放心的一次循环解决。
初始值为-1意味着当前情况取不到(非经常见的思路啊,用-1标记不可达,用正数标记最短路),初始情况呢,dp[0][0][0]=0

递推的思路也非常easy:假设新节点没去过(值为-1),去呗。去过的话,取小值呗
代码例如以下:

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 99999999
#define pi 3.1415926535897932384626433832795028841971

int dp[10][10][10050];
int t,n;
int num[10050];

int main(){
	int i,j,k,dis;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(i=1;i<=n;i++) scanf("%d",&num[i]);
		memset(dp,-1,sizeof(dp));
		dp[0][0][0]=0;
		for(k=1;k<=n;k++)
			for(i=0;i<=4;i++)
				for(j=0;j<=4;j++){
					if (dp[i][j][k-1]==-1) continue;
					dis=abs(i-num[k]);
					if (dp[num[k]][j][k]==-1) dp[num[k]][j][k]=dp[i][j][k-1]+dis;
					else dp[num[k]][j][k]=min(dp[num[k]][j][k],dp[i][j][k-1]+dis);
					dis=abs(j-num[k]);
					if (dp[i][num[k]][k]==-1) dp[i][num[k]][k]=dp[i][j][k-1]+dis;
					else dp[i][num[k]][k]=min(dp[i][num[k]][k],dp[i][j][k-1]+dis);
				}
		int ans=100000000;
		for(i=0;i<=4;i++)
			for(j=0;j<=4;j++)
				if (dp[i][j][n]!=-1&&dp[i][j][n]<ans) ans=dp[i][j][n];
		printf("%d\n",ans);
	}
	return 0;
}

再次感谢bin神,axp巨巨,Tonny巨巨和群巨和广大acm爱好者的支持。

GDUT决赛题解

原文:http://www.cnblogs.com/cynchanpin/p/7261382.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!