网络上太不给力啊,找不到一份像样的题解,让弱弱为大家服务,写一份完整的有AC代码的详细解题报告。感谢群巨给我的帮助,尤其是xiaoxin巨巨提供的思路以及题解。源代码和思路在此:          http://paste.ubuntu.com/10566645/


A.奇怪的排序:中文题,不存在看不懂题意的情况,。细节点,数的个数为B-A+1,按照新产生的数排序完毕之后,需要输出的是原来的数

#include<stdio.h>
#include<string.h>
struct aa
{
	int num,diff;
};
int change(int n)
{
	int m=0;
	while(n>0)
	{
		m=m*10+n%10;
		n=n/10;
	}
	return m;
}
int main()
{
	int n,a,b,i,j;
	aa x[60],ch;
	scanf("%d",&n);
	while(n--)
	{
		memset(x,0,sizeof(x));
		scanf("%d%d",&a,&b);
		for(i=a;i<=b;i++)
		{
			x[i-a].diff=change(i);
			x[i-a].num=i;
		}
		for(i=0;i<=(b-a);i++)
			for(j=0;j<=(b-a);j++)
				if (x[i].diff<x[j].diff)
					{
						ch=x[i];
						x[i]=x[j];
						x[j]=ch;
					}
		for(i=0;i<(b-a);i++)
			printf("%d ",x[i].num);
		printf("%d\n",x[b-a].num);
	}
	return 0;
}

B.最强的DE战斗力

这道题小学数学竞赛好的,或者是对数字敏感的,或者是看到n=1000敢打表的,都是大数模版题

数学结论如下:想分解n,使得乘积最大,那么尽可能多分解为3

所以,n%3=0时,全部分解为3,n%3=1时,分解为两个2,剩下的都是3,n%3=2时,分解为一个2,剩下的都是3


注意,n最大为1000,那么答案会到3^333,肯定超过unsigned long long,必须大数模版(或者模拟)

n=1或者n=2的时候特判一下

#include<stdio.h>
#include<string.h>
const int M=400; 
int a[M];
void pow(int n)
{
	int i;
	while(n--)
	{
		for(i=0;i<M;i++)
			a[i]=a[i]*3;
		for(i=0;i<M;i++)
			if (a[i]>=10)
			{
				a[i+1]+=a[i]/10;
				a[i]%=10;
			}
	}
}
int main()
{
	int n,i,j,m;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&m);
		memset(a,0,sizeof(a));
		a[0]=1;
		if (m==1) printf("%d\n",m);
		else
		{
			if (m%3==1) pow(m/3-1);
				else    pow(m/3);
			if (m%3==1)
			{
				for(i=0;i<M;i++)
					a[i]=a[i]*4;
				for(i=0;i<M;i++)
					if (a[i]>=10)
					{
						a[i+1]+=a[i]/10;
						a[i]%=10;
					}
			}
		else if (m%3==2)
			{
				for(i=0;i<M;i++)
					a[i]=a[i]*2;
				for(i=0;i<M;i++)
					if (a[i]>=10)
					{
						a[i+1]+=a[i]/10;
						a[i]%=10;
					}
			}
		for(j=M-1;j>=1;j--)
			if (a[j]) break;
		for(i=j;i>=0;i--)
			printf("%d",a[i]);
		printf("\n") ;
		}
	} 
	return 0;
}

C.试制品

这道题我认为是倒数第二难的题,思路大家都知道,但是就是不敢写,乱七八糟的情况太多

难点整理如下:

1.如何处理数据,即:每个方程的生成物,反应物如何保存

2.当前的方程式是不是已经反应过

3.如果一个方程反应发生了,产生了一种生成物,那么这种生成物对其他方程式可能产生的影响怎么表示(是图论建图还是并查集建树,我当时是这样考虑的)

4.n=400意味着随意暴力,只需要把各种情况分析清楚

大家学习学习xiaoxin巨巨的代码吧,前面已经贴出的ubuntu的。赞一个的。


D.遥控器

这届比赛怎么这么多模拟题啊,简直不能忍

难点整理如下:

1.上键和下键的使用问题:只要上键或者下键至少存在一个,那么必定有解

2.这题“显然”的贪心思想:能够直接到(一位数直接一次到,两位数三次到),必然直接到

3.如果要绕路,必然只绕一次

先贴我的代码,再说说xin巨巨的代码比我好在哪里,同样的,模拟题一定要自己写出来,代码肯定都看得懂

#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 t,ans;
int num[20];
int up,down;
int target,initial,choose;

void init(){
	memset(num,0,sizeof(num));
	choose=up=down=target=initial=0;
	ans=9999;
}

int CalcUp(int x,int y){
	//暴力按上键需要多少次 
	return (y+100-x)%100;
}

int CalcDown(int x,int y){
	//暴力按下键需要多少次
	return (x+100-y)%100;
}

int main(){
	//freopen("input.txt","r",stdin);
	
	int i,j,k;
	scanf("%d",&t);
	while(t--){
		init();
		
		//读取数据
		scanf("%d%d%d%d",&num[1],&num[2],&num[3],&up);
		scanf("%d%d%d%d",&num[4],&num[5],&num[6],&down);
		scanf("%d%d%d",&num[7],&num[8],&num[9]);
		scanf("%d%d",&choose,&num[0]);
		scanf("%d%d",&initial,&target);
		
		//判断不需要走 
		if (initial==target){
			puts("0");
			continue;
		}
		
		//判断无解情况
		//上下键都用不了,直接去也去不了 
		if (!up&&!down&&((target<10&&!num[target])||(target>=10&&num[target/10]+num[target%10]+choose<3))){
			puts("-1");
			continue;
		}
		
		//上下键用不了
		//由之前的无解情况知,必然能“直接” 到
		if (!up&&!down){
			if (target>=10) ans=3;
			else ans=1;
			printf("%d\n",ans);
			continue;
		}
		
		//暴力走 
		if (up) ans=min(ans,CalcUp(initial,target));
		if (down) ans=min(ans,CalcDown(initial,target));
		
		//枚举所有的两位数作为新起点,再暴力 
		for(i=0;i<=9;i++)
			if (num[i]){
				if (up) ans=min(ans,1+CalcUp(i,target));
				if (down) ans=min(ans,1+CalcDown(i,target));
			}
		
		if (!choose){
			printf("%d\n",ans);
			continue;
		}
		
		//枚举所有的一位数作为新起点,再暴力
		for(i=1;i<=9;i++)
			if (num[i])
				for(j=0;j<=9;j++)
					if (num[j]){
						int x=i*10+j;
						if (up) ans=min(ans,3+CalcUp(x,target));
						if (down) ans=min(ans,3+CalcDown(x,target));
					}
			
		printf("%d\n",ans);
	}
	return 0;
}

我的优点:分类细致,在找新的问题或者错误或者细节之类的可以方便找和Debug

跟xin巨巨的差距:xin巨巨的check判断能否“直接”从起点到终点减少了很多重复代码,我就是不断的暴力。。。差距太大


T5.奇妙的图案   不说话,我是计算几何渣,坐等bin神写题解

bin神就是bin神,利用计算几何+区间DP秒杀此题,弱还没懂,贴贴题解和代码就好

http://paste.ubuntu.com/10572491/


T6.Metric Martrice

英文签到题:注意题中的一个单词lowest

意味着我只需要判断条件4是否成立,再判断3,如果4和3同时成立的话,那么保留的就是“较小”的3

剩下的就是暴力for循环

代码如下:

#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 int maxn=100;
int a[maxn][maxn];
int t,n;

int main(){
	//freopen("input.txt","r",stdin);
	int i,j,k;
	int flag=0;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				scanf("%d",&a[i][j]);
		int flag=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if (i!=j)
				for(k=1;k<=n;k++)
					if (i!=k&&j!=k)
						if (a[i][j]+a[j][k]<a[i][k]) flag=4;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if (a[i][j]!=a[j][i]) flag=3;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if (i!=j)
					if (a[i][j]<=0) flag=2;
		for(i=1;i<=n;i++)
			if (a[i][i]!=0) flag=1;
		printf("%d\n",flag);
	}
	return 0;
}

T7.Divideing Jewels

这题的题意理解有点费劲。意思是说,价值为1到价值为10的10种珠宝数目是输入给定的10个整数,问是否存在某种分配方案,使得可以将其所有珠宝的价值平分

思路:暴力/dfs/DP

考虑暴力的情况是可以猜想的,如:左边拿一个,右边拿一个之后,谁小谁继续拿,但是可能有反例,如1个2,2个9,2个10

dfs/DP:找是否存在平均分配方案,即找:有没有可能找到某种方案,拼出总价值一半。

那么转化为DP的完全背包问题。即:给你很多很多种物品(把题中的价值考虑为体积),数目是物品的个数,是否能够装满背包

代码如下:

#include<stdio.h>
#include<math.h>
#include<algorithm>
#define maxn 100000
using namespace std;
int mm[10009];
int f(int w,int s)
{
    if(w==0) return 1;
    if(w<0||w>0 &&s==0) return 0;
    if(f(w-mm[s],s-1)) return 1;
    return f(w,s-1);
}
int main(){
	//freopen("T7.IN","r",stdin);
	int n=0,i,j,k,a[11];
	while(++n){
		int sum=0,geshu=0;
		for(i=1,j=0;i<=10;i++){
			scanf("%d",&a[i]);
			for(k=0;k<a[i];k++){
				mm[j++]=i;
				
			}
			sum+=i*a[i];
			geshu+=a[i];
		}
		if(sum==0)break;
		if(n!=1)
		puts("");
		if(sum&1){
			printf("#%d:Can't be divided.\n",n);
		}
		else{
		sum/=2;
//		for(i=0;i<10;i++){
//			printf("%d  ",a[i]);
//		}
		
		if(f(sum,geshu)){
			printf("#%d:Can be divided.\n",n);
			
		}
		else printf("#%d:Can't be divided.\n",n);
		}
		
	}
	return 0;
}

T8.Interesting Punch-Bowl

这题考阅读啊!!!看了好久

题意:给你个矩阵,往其中灌水能够存多少。把每个数看作高度,那么中间就会有凸有凹,凹的地方是可以存水的

样例分析:(2,2)的2处可以存3个单位的水,(2,3)的1处存4个单位,(3,2)的1处存4个单位,(4,3)的6处存1个单位,ans=12个单位

做法:优先队列,xiaoxin巨巨的paste解释得很清楚

我讲讲,为什么可以这么做

求存水多少,我不妨从边界上注水。当矩阵里面的数小于外面的数时,就可能存水。所以,我从外面的最低的地方注水进去,如果里面的木板高于我,我就注不进去,相当于加了一个新的边界,如果可以注进去,那么ans加上高度差,然后将注水的木板改成跟边界一样的高度值。之所以用优先队列,可以保证每次弹出的队首元素就是还没有处理过的最小高度值,我从这里开始尝试注水。

代码不贴了,paste

细节:B的范围,需要用long long   n和m的意思,n是宽度,n是长度,与平时的习惯是反的