第一个问题：
Energy Conversion
魔法师百小度也有遇到难题的时候——如今。百小度正在一个古老的石门面前，石门上有一段古老的魔法文字，读懂这样的魔法文字须要耗费大量的能量和大量的脑力。
过了许久。百小度最终读懂魔法文字的含义：石门里面有一个石盘，魔法师须要通过魔法将这个石盘旋转X度。以使上面的刻纹与天相相应。才干打开石门。
可是，旋转石盘须要N点能量值，而为了解读密文。百小度的能量值仅仅剩M点了！破坏石门是不可能的，由于那将须要很多其它的能量。
只是，幸运的是，作为魔法师的百小度能够耗费V点能量，使得自己的能量变为如今剩余能量的K倍（魔法师的世界你永远不懂，谁也不知道他是怎么做到的）。比方，如今百小度有A点能量,那么他能够使自己的能量变为(A-V)*K点（能量在不论什么时候都不能够为负。即：假设A小于V的话。就不能够运行转换）。 然而。在解读密文的过程中，百小度预支了他的智商。所以他如今不知道自己能否够旋转石盘。打开石门。你能帮帮他吗？
输入数据第一行是一个整数T，表示包括T组測试例子。接下来是T行数据。每行有4个自然数N,M,V,K（字符含义见题目描写叙述）；数据范围：T<=100N,M,V,K <= 10^8
对于每组数据，请输出最少做几次能量转换才可以有足够的能量点开门；假设无法做到，请直接输出-1。
4 10 3 1 2 10 2 1 2 10 9 7 3 10 10 10000 0
3 -1 -1 0
解题思路：
直接模拟就可以，注意走一步后的能量要比之前的要大，负责会陷入死循环。
代码：
//#include<CSpreadSheet.h>#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);ll n,m,v,k;int t;scanf("%d",&t);while(t--){scanf("%I64d%I64d%I64d%I64d",&n,&m,&v,&k);int ans=0;if(m>=n){printf("0\n");continue;}ll la=m;while((m-v)*k<n&&m>=v&&(m-v)*k>la) //要推断后面的比前面打{ans++;m=(m-v)*k;la=m;}if((m-v)*k>=n)printf("%d\n",ans+1);elseprintf("-1\n");}return 0;
}第二题
Problem Description
有非常多从磁盘读取数据的需求，包含顺序读取、随机读取。为了提高效率，须要人为安排磁盘读取。然而，在现实中。这样的做法非常复杂。我们考虑一个相对简单的场景。
磁盘有很多轨道，每一个轨道有很多扇区，用于存储数据。当我们想在特定扇区来读取数据时。磁头须要跳转到特定的轨道、详细扇区进行读取操作。
为了简单，我们如果磁头能够在某个轨道顺时针或逆时针匀速旋转，旋转一周的时间是360个单位时间。
磁头也能够任意移动到某个轨道进行读取，每跳转到一个相邻轨道的时间为400个单位时间，跳转前后磁头所在扇区位置不变。一次读取数据的时间为10个单位时间，读取前后磁头所在的扇区位置不变。
磁头同一时候仅仅能做一件事：跳转轨道。旋转或读取。
如今。须要在磁盘读取一组数据，如果每一个轨道至多有一个读取请求，这个读取的扇区是轨道上分布在 0到359内的一个整数点扇区，即轨道的某个360等分点。磁头的起始点在0轨道0扇区，此时没有数据读取。在完毕全部读取后。磁头须要回到0轨道0扇区的始点位置。请问完毕给定的读取所需的最小时间。
Input
输入的第一行包括一个整数M（0<M<=100）。表示測试数据的组数。
对于每组測试数据，第一行包括一个整数N（0<N<=1000），表示要读取的数据的数量。
之后每行包括两个整数T和S（0<T<=1000。0<= S<360），表示每一个数据的磁道和扇区。磁道是按升序排列，而且没有反复。
Output
对于每组測试数据，输出一个整数，表示完毕所有读取所需的时间。
Sample Input
3
1
1 10
3
1 20
3 30
5 10
2
1 10
2 11
Sample Output
830
4090
1642
解题思路：
dp
双调欧几里得旅行商问题。等价成两个人从起点開始走。
dp[i][j]表示一个人走到第i个位置，一个人走到第j个位置时的最小花费。
保证i>j 且前i个位置都走遍了。
dp[i][j]=min(dp[i][j],dp[i-1][j]+dis(i-1,i)) ;要么给快人从i-1走到了i
dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+dis(j,i); 要么给慢人从j走到了i
代码：
//#include<CSpreadSheet.h>#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;#define Maxn 1100
int dis[Maxn][Maxn],save[Maxn];
int n,dp[Maxn][Maxn];int cal(int a,int b)
{return min(abs(save[a]-save[b]),360-abs(save[a]-save[b]));
}int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int T,Max;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++) //离散化{int a,b;scanf("%d%d",&a,&b);save[i]=b;Max=a;}save[0]=0;for(int i=0;i<=n;i++) //预处理出距离{for(int j=i+1;j<=n;j++)dis[i][j]=cal(i,j);}for(int i=0;i<=n;i++) //初始化for(int j=0;j<=n;j++)dp[i][j]=INF;dp[1][0]=dis[0][1];for(int i=2;i<=n;i++) //第i个位置一定有人走for(int j=0;j<i;j++){dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+dis[j][i]);//慢人从j到idp[i][j]=min(dp[i][j],dp[i-1][j]+dis[i-1][i]); //快人从i-1走到i}int res=INF;for(int i=0;i<n;i++)res=min(res,dp[n][i]+dis[i][n]);printf("%d\n",res+Max*400*2+10*n); //加上轨道的偏移 和取数据花的时间}return 0;
}第三题：
Problem Description
Zeus 和 Prometheus 做了一个游戏，Prometheus 给 Zeus 一个集合，集合中包括了N个正整数，随后 Prometheus 将向 Zeus 发起M次询问。每次询问中包括一个正整数 S ，之后 Zeus 须要在集合其中找出一个正整数 K ，使得 K 与 S 的异或结果最大。Prometheus 为了让 Zeus 看到人类的伟大，随即允许 Zeus 能够向人类求助。你能证明人类的智慧么？
Input
输入包括若干组測试数据。每组測试数据包括若干行。
输入的第一行是一个整数T（T< 10），表示共同拥有T组数据。
每组数据的第一行输入两个正整数N。M（<1=N,M<=100000），接下来一行，包括N个正整数，代表Zeus 的获得的集合，之后M行，每行一个正整数S，代表Prometheus 询问的正整数。全部正整数均不超过2^32。
Output
对于每组数据。首先须要输出单独一行”Case #?:”，当中问号处应填入当前的数据组数。组数从1開始计算。
对于每一个询问。输出一个正整数K，使得K与S异或值最大。
Sample Input
2
3 2
3 4 5
1
5
4 1
4 6 5 6
3
Sample Output
Case #1:
4
3
Case #2:
4
解题思路：字典树
把每一个数当成33位。从高往低位依次压到字典树中，对于每一个查询X。从高位往低位，取出当前位的反，假设存在的话继续往下找，假设不存在仅仅能从本身往后找。
代码：
//#include<CSpreadSheet.h>#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;#define Maxn 110000
struct Node
{struct Node* next[2];
}root,node[Maxn*50];
int n,m,pp;void inse(ll cur)
{Node * p=&root;for(int i=32;i>=0;i--){if(cur&((ll)1<<(ll)i)){if(p->next[1]==NULL){++pp;memset(node[pp].next,NULL,sizeof(node[pp].next));p->next[1]=&node[pp];}p=p->next[1];}else{if(p->next[0]==NULL){++pp;memset(node[pp].next,NULL,sizeof(node[pp].next));p->next[0]=&node[pp];}p=p->next[0];}}
}
ll qure(ll cur)
{ll res=0;Node * p=&root;for(int i=32;i>=0;i--){if(p->next[0]==NULL&&p->next[1]==NULL)return res;if(cur&((ll)1<<(ll)i)) //当前位是1{if(p->next[0]) //找0{p=p->next[0];res=res*2+0;} else //不存在0 仅仅能找1{p=p->next[1];res=res*2+1;}}else //为0 {if(p->next[1]) //找1{p=p->next[1];res=res*2+1;//printf("01: ");}else //不存在 仅仅能找0{p=p->next[0];res=res*2+0;//printf("00: ");}}//printf("i:%d res:%I64d\n",i,res);//system("pause");}return res;
}int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int t;scanf("%d",&t);for(int ca=1;ca<=t;ca++){memset(root.next,NULL,sizeof(root.next));scanf("%d%d",&n,&m);pp=0;for(int i=1;i<=n;i++){ll temp;scanf("%I64d",&temp);inse(temp);//system("pause");}printf("Case #%d:\n",ca);while(m--){ll temp;scanf("%I64d",&temp);printf("%I64d\n",qure(temp));}}return 0;
}第四题：
Labyrinth
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 519 Accepted Submission(s): 174
度度熊是一仅仅喜欢探险的熊，一次偶然落进了一个m*n矩阵的迷宫，该迷宫仅仅能从矩阵左上角第一个方格開始走，仅仅有走到右上角的第一个格子才算走出迷宫，每一次仅仅能走一格。且仅仅能向上向下向右走曾经没有走过的格子，每个格子中都有一些金币（或正或负。有可能遇到强盗拦路抢劫，度度熊身上金币能够为负，须要给强盗写欠条），度度熊刚開始时身上金币数为0，问度度熊走出迷宫时候身上最多有多少金币？
输入的第一行是一个整数T（T < 200）。表示共同拥有T组数据。
每组数据的第一行输入两个正整数m，n（m<=100，n<=100）。接下来的m行，每行n个整数。分别代表对应格子中能得到金币的数量，每一个整数都大于等于-100且小于等于100。
对于每组数据，首先须要输出单独一行”Case #?:”，当中问号处应填入当前的数据组数，组数从1開始计算。
每组測试数据输出一行，输出一个整数，代表依据最优的打法，你走到右上角时能够获得的最大金币数目。
2 3 4 1 -1 1 0 2 -2 4 2 3 5 1 -90 2 2 1 1 1 1
Case #1: 18 Case #2: 4
解题思路：
dp
显然仅仅能往右走m次，所以用dp[i][j]表示第i列且在第i行往右走 ，能达到的最大值。
枚举列。在枚举行依次找出dp[i][j]的最大值。
dp[i][j]=max(dp[i-1][k]+dis[k][j])
注意边界情况。
代码：
//#include<CSpreadSheet.h>#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;#define Maxn 220
int dp[Maxn][Maxn],save[Maxn][Maxn],n,m;
int sum[Maxn][Maxn];int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int t;scanf("%d",&t);for(int ca=1;ca<=t;ca++){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)scanf("%d",&save[i][j]);}if(m==1){printf("Case #%d:\n%d\n",ca,save[1][1]);continue;}for(int i=1;i<=m;i++){sum[i][0]=0;for(int j=1;j<=n;j++)sum[i][j]=sum[i][j-1]+save[j][i]; //预处理出每一列的前i行和}memset(dp,-INF,sizeof(dp));//printf("%d\n",dp[0][0]);dp[0][0]=0;for(int i=1;i<m;i++){for(int j=1;j<=n;j++){if(i==1){dp[i][j]=sum[1][j];continue;}int temp=-INF;for(int k=1;k<=n;k++){int Max=max(k,j),Min=min(k,j);temp=max(temp,dp[i-1][k]+sum[i][Max]-sum[i][Min-1]);}dp[i][j]=temp;}}int ans=dp[m-1][1]+save[1][m];for(int i=2;i<=n;i++) //最后一列单独拿出来考虑ans=max(ans,dp[m-1][i]+sum[m][i]);printf("Case #%d:\n%d\n",ca,ans);}return 0;
}版权声明：本文博主原创文章，博客，未经同意不得转载。
