网络上太不给力啊，找不到一份像样的题解，让弱弱为大家服务，写一份完整的有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是长度，与平时的习惯是反的
京公网安备 11010502036488号