路径之谜
小明冒充X星球的骑士，进入了一个奇怪的城堡。
城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 n x n 个方格。【如图1.png】所示。
按习俗，骑士要从西北角走到东南角。
可以横向或纵向移动，但不能斜着走，也不能跳跃。
每走到一个新方格，就要向正北方和正西方各射一箭。
（城堡的西墙和北墙内各有 n 个靶子）
同一个方格只允许经过一次。但不必做完所有的方格。
如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？
有时是可以的，比如图1.png中的例子。
本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
输入：
第一行一个整数N(0<N<20)，表示地面有 N x N 个方格
第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）
输出：
一行若干个整数，表示骑士路径。
为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3....
比如，图1.png中的方块编号为：
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
示例：
用户输入：
4
2 4 3 4
4 3 3 3
程序应该输出：
0 4 5 1 2 3 7 11 10 9 13 14 15
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
1 #include <bits/stdc++.h> 2 3 /** 4 @author:d g w 5 */ 6 using namespace std; 7 typedef long long LL ; 8 9 const int maxn=1e3; 10 11 int map1[maxn][maxn]; 12 bool inq[maxn][maxn]={0}; 13 int X[4]={0,0,-1,1}; 14 int Y[4]={1,-1,0,0}; 15 int n; 16 int bei[4],xi[4];//记录边界数 17 int beisum=0,xisum=0; 18 int res[maxn]={0},alen=0; 19 20 void dfs(int x,int y){ 21 if(x==n-1&&y==n-1){ 22 if(beisum==0&&xisum==0){ 23 for(int i=0;i<alen;i++){ 24 cout<<res[i]<<" "; 25 } 26 } 27 } 28 for(int i=0;i<4;i++){ 29 int newx=x+X[i]; 30 int newy=y+Y[i]; 31 if(newx>=0&&newx<n&&newy>=0&&newy<n&&inq[newx][newy]==0&&bei[newy]>0&&xi[newx]>0){ 32 inq[newx][newy]=1; 33 beisum--; 34 xisum--; 35 bei[newy]--; 36 xi[newx]--; 37 res[alen]=map1[newx][newy]; 38 alen++; 39 dfs(newx,newy); 40 alen--; 41 inq[newx][newy]=0; 42 beisum++; 43 xisum++; 44 bei[newy]++; 45 xi[newx]++; 46 } 47 } 48 49 50 } 51 52 int main() 53 { 54 int k=0; 55 for(int i=0;i<4;i++){ 56 for(int j=0;j<4;j++){ 57 map1[i][j]=k++; 58 } 59 } 60 cin>>n; 61 for(int i=0;i<n;i++){ 62 cin>>bei[i]; 63 beisum+=bei[i]; 64 } 65 for(int i=0;i<n;i++){ 66 cin>>xi[i]; 67 xisum+=xi[i]; 68 } 69 inq[0][0]=1; 70 beisum--; 71 xisum--; 72 bei[0]--; 73 xi[0]--; 74 res[alen]=map1[0][0]; 75 dfs(0,0); 76 system("pause"); 77 return 0; 78 }
平方末尾
能够表示为某个整数的平方的数字称为“平方数”
比如，25,64
虽然无法立即说出某个数是平方数，但经常可以断定某个数不是平方数。
因为平方数的末位只可能是：[0, 1, 4, 5, 6, 9] 这6个数字中的某个。
所以，4325435332必然不是平方数。
如果给你一个2位或2位以上的数字，你能根据末位的两位来断定它不是平方数吗？
请计算一下，一个2位以上的平方数的最后两位有多少种可能性？
注意：需要提交的是一个整数，表示2位以上的平方数最后两位的不同情况数。
不要填写任何多余内容（比如，说明解释文字等）
1 #include <bits/stdc++.h> 2 3 /** 4 @author:d g w 5 */ 6 using namespace std; 7 typedef long long LL ; 8 9 const int maxn=1e5; 10 set<string> st; 11 int main() 12 { 13 int ans=0; 14 stringstream ss; 15 //[0, 1, 4, 5, 6, 9] 16 for(int i=10;i<100;i++){ 17 int a=i*i; 18 ss<<a; 19 string s; 20 ss>>s; 21 ss.clear(); 22 int len=s.length(); 23 string p=s.substr(len-2,len); 24 st.insert(p); 25 } 26 cout<<st.size(); 27 system("pause"); 28 return 0; 29 }
反幻方
我国古籍很早就记载着
2 9 4
7 5 3
6 1 8
这是一个三阶幻方。每行每列以及对角线上的数字相加都相等。
下面考虑一个相反的问题。
可不可以用 1~9 的数字填入九宫格。
使得：每行每列每个对角线上的数字和都互不相等呢？
这应该能做到。
比如：
9 1 2
8 4 3
7 5 6
你的任务是搜索所有的三阶反幻方。并统计出一共有多少种。
旋转或镜像算同一种。
比如：
9 1 2
8 4 3
7 5 6
7 8 9
5 4 1
6 3 2
2 1 9
3 4 8
6 5 7
旋转或镜像算同一种等都算作同一种情况。
请提交三阶反幻方一共多少种。这是一个整数，不要填写任何多余内容。
1 #include <bits/stdc++.h> 2 3 /** 4 @author:d g w 5 */ 6 using namespace std; 7 typedef long long LL ; 8 9 const int maxn=1e3; 10 11 12 int m[10]; 13 int main() 14 { 15 16 int a[9]={1,2,3,4,5,6,7,8,9},ans=0; 17 do{ 18 bool flag=true; 19 m[0]=a[0]+a[1]+a[2]; 20 m[1]=a[3]+a[4]+a[5]; 21 m[2]=a[6]+a[7]+a[8]; 22 m[3]=a[0]+a[4]+a[8]; 23 m[4]=a[2]+a[4]+a[6]; 24 m[5]=a[0]+a[3]+a[6]; 25 m[6]=a[1]+a[4]+a[7]; 26 m[7]=a[2]+a[5]+a[8]; 27 28 for(int i=0;i<8;i++){ 29 for(int j=i+1;j<8;j++){ 30 if(m[i]==m[j]){ 31 flag=false; 32 break; 33 } 34 } 35 if(!flag){ 36 break; 37 } 38 } 39 if(flag){ 40 ans++; 41 } 42 }while(next_permutation(a,a+9)); 43 cout<<ans/8; //旋转有四种 镜像两种 所以 4*2 44 system("pause"); 45 return 0; 46 } 47 48 /* 49 5 50 5 51 8 3 52 12 7 16 53 4 10 11 6 54 9 5 3 9 4 55 */
赢球票
某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。
主持人拿出 N 张卡片（上面写着 1~N 的数字），打乱顺序，排成一个圆圈。
你可以从任意一张卡片开始顺时针数数: 1,2,3.....
如果数到的数字刚好和卡片上的数字相同，则把该卡片收入囊中，从下一个卡片重新数数。
直到再无法收获任何卡片，游戏结束。囊中卡片数字的和就是赢得球票的张数。
比如：
卡片排列是：1 2 3
我们从1号卡开始数，就把1号卡拿走。再从2号卡开始，但数的数字无法与卡片对上，
很快数字越来越大，不可能再拿走卡片了。因此这次我们只赢得了1张球票。
还不算太坏！如果我们开始就傻傻地从2或3号卡片数起，那就一张卡片都拿不到了。
如果运气好，卡片排列是 2 1 3
那我们可以顺利拿到所有的卡片！
本题的目标就是：已知顺时针卡片序列。
随便你从哪里开始数，求最多能赢多少张球票（就是收入囊中的卡片数字之和）
输入数据：
第一行一个整数N(N<100)，表示卡片数目
第二行 N 个整数，表示顺时针排列的卡片
输出数据：
一行，一个整数，表示最好情况下能赢得多少张球票
比如：
用户输入：
3
1 2 3
程序应该输出：
1
比如：
用户输入：
3
2 1 3
程序应该输出：
6
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
answer：重点在于循环模拟进退位，还要注意打表后环位
1 #include <bits/stdc++.h> 2 3 /** 4 @author:d g w 5 */ 6 using namespace std; 7 typedef long long LL ; 8 9 const int maxn=1e3; 10 11 int m[maxn],pnum=0; 12 int inq[maxn]; 13 int n; 14 15 int f() 16 { int ans=0; 17 18 for(int i=0; i<n; i++) 19 { 20 for(int i=0; i<n; i++) 21 { 22 inq[i]=m[i]; 23 } 24 int re=0; 25 int cnt=1; 26 int start=i; 27 while(1) 28 { 29 bool flag=true; 30 for(int j=0; j<n; j++) 31 { 32 if(inq[j]>=cnt) 33 { 34 flag=false; 35 break; 36 } 37 } 38 if(flag) 39 break; 40 int k=start%n; 41 if(inq[k]==cnt) 42 { 43 inq[k]=-1; 44 re+=cnt; 45 cnt=1; 46 } 47 else if(inq[k]!=-1) 48 { 49 cnt++; 50 } 51 start++; 52 } 53 54 ans=max(ans,re); 55 } 56 return ans; 57 } 58 59 int main() 60 { 61 cin>>n; 62 for(int i=0; i<n; i++) 63 { 64 cin>>m[i]; 65 } 66 67 cout<< f(); 68 system("pause"); 69 return 0; 70 } 71 72 /* 73 5 74 5 75 8 3 76 12 7 16 77 4 10 11 6 78 9 5 3 9 4 79 */
打印数字
小明写了一个有趣的程序，给定一串数字。
它可以输出这串数字拼出放大的自己的样子。
比如“2016”会输出为：
22222 00000 1 6666
2 2 0 0 1 1 6
2 0 0 1 666666
2 0 0 1 6 6
2 0 0 1 6 6
2 2 0 0 1 6 6
2222222 00000 1111 66666
请仔细分析代码，填写划线部分缺少的内容。
#include <stdio.h>
#include <string.h>
#define ZIW 8
#define ZIH 7
void f(int n)
{
char cc[100];
int i,j;
char di[][ZIH][ZIW] =
{{" 00000 ",
"0 0",
"0 0",
"0 0",
"0 0",
"0 0",
" 00000 "},
{" 1 ",
" 1 1 ",
" 1 ",
" 1 ",
" 1 ",
" 1 ",
" 1111"},
{" 22222 ",
"2 2",
" 2",
" 2 ",
" 2 ",
" 2 2",
"2222222"},
{" 33333 ",
"3 3",
" 3",
" 3333 ",
" 3",
"3 3",
" 33333 "},
{" 44 ",
" 4 4 ",
" 4 4 ",
"4 4 ",
"4 4 ",
"4444444",
" 4 "},
{" 55555 ",
" 5 ",
"555555 ",
" 5",
" 5",
"5 5",
" 55555 "},
{" 6666 ",
"6 ",
"666666 ",
"6 6",
"6 6",
"6 6",
" 66666 "},
{"7777777",
"7 7 ",
" 7 ",
" 7 ",
" 7 ",
" 7 ",
" 7 "},
{" 88888 ",
"8 8",
"8 8",
" 88888 ",
"8 8",
"8 8",
" 88888 "},
{" 99999 ",
"9 9",
"9 9",
" 999999",
" 9",
"9 9",
" 99999 "}};
sprintf(cc, "%d", n);
for(i=0; i<ZIH; i++){
for(j=0; j<strlen(cc); j++){
printf("%s ", _______________________ ); //填空位置
}
printf("\n");
}
}
int main()
{
f(2016);
return 0;
}
注意：只提交划线部分缺少的代码，不要添加任何题面已有代码或符号。
也不要提交任何说明解释文字等。
1 #include <stdio.h> 2 #include <string.h> 3 #define ZIW 8 4 #define ZIH 7 5 void f(int n) 6 { 7 char cc[100]; 8 int i,j; 9 char di[][ZIH][ZIW] = 10 { 11 {" 00000 ", 12 "0 0", 13 "0 0", 14 "0 0", 15 "0 0", 16 "0 0", 17 " 00000 "}, 18 {" 1 ", 19 " 1 1 ", 20 " 1 ", 21 " 1 ", 22 " 1 ", 23 " 1 ", 24 " 1111"}, 25 {" 22222 ", 26 "2 2", 27 " 2", 28 " 2 ", 29 " 2 ", 30 " 2 2", 31 "2222222"}, 32 {" 33333 ", 33 "3 3", 34 " 3", 35 " 3333 ", 36 " 3", 37 "3 3", 38 " 33333 "}, 39 {" 44 ", 40 " 4 4 ", 41 " 4 4 ", 42 "4 4 ", 43 "4 4 ", 44 "4444444", 45 " 4 "}, 46 {" 55555 ", 47 " 5 ", 48 "555555 ", 49 " 5", 50 " 5", 51 "5 5", 52 " 55555 "}, 53 {" 6666 ", 54 "6 ", 55 "666666 ", 56 "6 6", 57 "6 6", 58 "6 6", 59 " 66666 "}, 60 {"7777777", 61 "7 7 ", 62 " 7 ", 63 " 7 ", 64 " 7 ", 65 " 7 ", 66 " 7 "}, 67 {" 88888 ", 68 "8 8", 69 "8 8", 70 " 88888 ", 71 "8 8", 72 "8 8", 73 " 88888 "}, 74 {" 99999 ", 75 "9 9", 76 "9 9", 77 " 999999", 78 " 9", 79 "9 9", 80 " 99999 "}}; 81 82 sprintf(cc, "%d", n); 83 //printf("%s ", cc[0] ); 84 85 for(i=0; i<ZIH; i++){ 86 for(j=0; j<strlen(cc); j++){ 87 printf("%s ", di[cc[j]-'0'][i] ); //填空位置 88 } 89 printf("\n"); 90 } 91 } 92 93 int main() 94 { 95 f(2016); 96 return 0; 97 }