A. 数字塔（2016 GC小甲 2）
Description
FJ农场里每一只奶牛的脖子上挂着一个胸牌，胸牌上面印着一个倒三角数字塔，例如奶牛Bessie脖子上的胸牌印着：
74932
1325
457
92
1
你发现什么规律了吗？除了第一行的数字外，其他行的数字都等于其正上方的数字 + 其右上方数字的和，再除以10之后的余数。看不懂？除了第一行之外，我们用a[i][j]表示第i行第j列的数字，那么a[i][j] = (a[i-1][j]+a[i-1][j+1])%10。我们规定i从上到下是递增的，j从左往右是递增的。
所有奶牛的胸牌都符合这个规律！！除了第一行之外，a[i][j] = (a[i-1][j]+a[i-1][j+1])%10。
奶牛John是个粗心的家伙，它在玩耍的过程中，胸牌上面的数字大部分都弄丢了，John胸牌的每一行都只剩下一个数字！其他数字都丢失了。假如我们用‘?’来表示一个丢失的数字，那么John的胸牌可能变成这样了：
4??
?2
1
农夫知道后非常生气，打算不给John发圣诞礼物，除非John可以还原胸牌。John希望你能帮助它还原胸牌，你能做到呢？
Input Format
第一行，一个整数N，表示数字塔共有N行，第1行有N个数字，第2行有N-1个数字，第3行有N-2个数字,......第i行有N-i+1个数字，最后一行只有一个数字。这些数字都是0至9的数字。丢失的数字用?来代替。
Output Format
输出John的胸牌，也就是你要输出一个倒三角数字塔。请放心，答案肯定唯一。
输入数据 1
3
4??
?2
1输出数据 1
457
92
1Hint
【输入样例2】
4
???2
??2
?2
2
【输出样例2】
0002
002
02
2
【数据范围】
对于100%的数据，1<=N<=50。
思路
本题考察二维数组的应用，可以从下往上推导，最后一行肯定是有数字的，那么倒数第二行，可以扫描一遍
代码
#include<bits/stdc++.h>
using namespace std;
int a[55][55];
int n, m, x, y, ans;
int main() {
cin>>n;
for(int i=1; i<=n; i++)
for(int j=1; j<=n-i+1; j++) {
char c;
cin>>c;
if(c=='?') a[i][j]=-1;//标记
else a[i][j]=(int) (c-'0');
}
for(int i=n-1; i>=1; i--)
for(int j=1; j<=(n-i+1); j++)
for(int k=1; k<=(n-i+1); k++)
if(a[i][k]==-1) {//被标记，需要填写数字
if(a[i][k+1]!=-1 && k!=(n-i+1)) {
//如果是右边有数字
a[i][k]=(10+a[i+1][k]-a[i][k+1])%10;
break;
} else if(a[i][k-1]!=-1 && k!=1) {
//如果是左边有数字
a[i][k]=(10+a[i+1][k-1]-a[i][k-1])%10;
break;
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n-i+1; j++)
printf("%d",a[i][j]);
printf("\n");
}
return 0;
}
B. 路程（2016 GC小甲 3）
Description
奶牛Bessie要从家里出发，去超市购买一些圣诞礼物，但是Bessie之前没去过超市，怎么办呢？农夫FJ给出了M条指令，指令的格式是：X Y，指令的意义是沿着X方向走Y米。上面指令的X是一个字符，‘N’表示向北、‘S’表示向南、‘W’表示向西、‘E’表示向东。
当Bessie执行完FJ给出的M条指令后，就到达超市了。Bessie是个聪明的奶牛，知道两点之间走直线的距离最短，所以在返程时，Bessie从超市走直线回到家。
那么Bessie总共走过的路程总和是多少？
Input Format
第一行，一个整数M。
接下来有M行，每行的格式是：X和Y，其中X是‘N’、‘S’、‘W’、‘E’四种字符之一。 Y是一个正整数。
Output Format
一个实数。答案四舍五入保留6位小数。
输入数据 1
3
N 1
E 3
S 3Copy
输出数据 1
10.605551Hint
【样例解释】
【输入样例2】
4
N 15
N 15
S 25
S 5
【输出样例2】
60.000000
【数据范围】
1<=M<=50， 1<=Y<=50。
【提示】
C++语言保留6位小数的做法：cout<<fixed<<setprecision(6)<<a<<endl; //变量a四舍五入保留6位小数，a是小数
思路
这道题主要考了勾股定理，要做这道题要先知道勾股定理的公式：
（字母a、b、c分别代表三条边,c代表斜边）：
代码
#include<bits/stdc++.h>
using namespace std;
char z1;
double x,y,jl;//jl累加 x,y坐标
int n,z2;
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>z1>>z2;
if(z1=='N')
x+=z2;
else if(z1=='S')
x-=z2;
else if(z1=='W')
y+=z2;
else if(z1=='E')
y-=z2;
jl+=z2;
}
jl+=sqrt((x*x)+(y*y));//勾股定理
//sqrt开根号（一定不要写成sprt）
cout<<fixed<<setprecision(6)<<jl<<endl;
return 0;
}
C. 整点（2016 GC小甲 4）
Description
在http://smoj.nhedu.net/网站里，ID是1094的题目是这样的：
在一条数轴上，从0至N共有N+1个整点，分别是：0,1,2,3,4,...N。有K头奶牛，每头奶牛选择一个整点作为它们的家，但它们不能选择相同的整点。为了方便联络，住得最远的那两头奶牛的距离必须等于D。问有多少种不同的方案？
出题人觉得这题不错，于是把这题给大家做，但为了降低难度，于是把上面的题目做了一个改变：K=3，即只有3头奶牛。
Input Format
一行，两个正整数，N 和 D。
Output Format
一个整数。
输入数据 1
2 2Copy
输出数据 1
6Copy
Hint
【样例解释】
方案1：奶牛A选择整点0，奶牛B选择整点1，奶牛C选择整点2。
方案2：奶牛A选择整点0，奶牛C选择整点1，奶牛B选择整点2。
方案3：奶牛B选择整点0，奶牛A选择整点1，奶牛C选择整点2。
方案4：奶牛B选择整点0，奶牛C选择整点1，奶牛A选择整点2。
方案5：奶牛C选择整点0，奶牛A选择整点1，奶牛B选择整点2。
方案6：奶牛C选择整点0，奶牛B选择整点1，奶牛A选择整点2。
【输入样例2】5 3
【输出样例2】36
【输入样例3】500000 20000
【输出样例3】57597239994
【数据范围】
1、对于50%的数据， 1<=N<=100，2<=D<=N。
2、对于100%的数据，1<=N<=500000，2<=D<=N。
【温馨提示】
答案可能较大，建议读入的变量N、D以及程序中你用到的其他变量，都定义为long long类型。
这道题有一点难，我的思路如下：
#include<bits/stdc++.h>
using namespace std;
long long n,d;
int main(){
cin>>n>>d;//输入N、D
cout<<(n-d+1)*(d-1)*6;
return 0;
}/*
这些是思路：
d=3,n=5:
0 1 2 3
1.a b c
2.a b c
2*6=12
n=5:n-3+1=3（有3个区间）
3*12=36
d=5:
0 1 2 3 4 5
1.a b c
2.a b c
3.a b c
4.a b c
5-1=4(种):4种方案
*/
D. 拔河比赛（2018 GC小乙 6）
【题目描述】
今天小Q班的体育课，是进行拔河比赛。同学们个个兴奋极了。体育老师一声令下，就抢着拉绳子占好了位置，谁也不肯让谁。
每位同学都一个力量值，为了让两边队伍实力均衡，体育老师想找一个合适的“中点”，将队伍分成两边，使得两个队伍力量总值相差最小。你来帮体育老师想想办法？
【输入格式】
第一行有两个正整数。一个整数N（ 2 <= N <= 500000），表示小Q班上的人数。
第二行有N个整数，依次表示队伍中每位同学的力量值P(0<=p<=1000)。
【输出格式】
输出两个数x和y。 表示在x和y之间设置“中点”，可以使队伍两边的力量总值相差最小（如果有多个中点，则以x大优先）。
【输入样例】
10
65 50 80 85 120 95 85 55 75 120
【输出样例】
5 6
【样例解释】
前5个人的力量和为400，后5个人的力量和为430，最小差值为30。
数据范围:
对于60%的数据 N<10000;
对于100%的数据 N<500000;
一、题目考察点
这道题主要考察以下几个方面：
对数组的运用和操作。
循环结构和条件判断的结合使用。
数学计算和逻辑推理能力。
二、代码思路
首先从用户输入中读取学生人数 n。
接着使用一个循环读取每个学生的力量值 a，并同时计算前缀和数组 s，其中 s[i] 表示前 i 个学生的力量总和。
然后再使用一个循环遍历所有可能的分割点 i，计算以 i 为分割点时两边队伍力量总和的差值的绝对值，与已记录的最小差值 minn 进行比较，如果当前差值更小，则更新 minn 和对应的分割点 x。
最后输出找到的分割点 x 和 x + 1。
三、代码
#include <bits/stdc++.h>
using namespace std;
long long n,a,s[1000005],minn=10000005,x;// n 表示学生人数，a 临时存储每个学生的力量值，s 是前缀和数组，minn 存储最小差值，x 存储最优分割点
int main(){
cin>>n;// 读取学生人数
for(int i=1;i<=n;i++){
cin>>a;// 读取每个学生的力量值
s[i]=s[i-1]+a;// 计算前缀和
}
for(int i=1;i<=n;i++){
if(abs(s[n]-s[i]*2)<minn){// 如果当前分割点的两边队伍力量总和差值的绝对值小于已记录的最小差值
minn=abs(s[n]-s[i]*2);// 更新最小差值
x=i;// 更新最优分割点
}
}
cout<<x<<" "<<x+1;// 输出分割点和分割点的下一个位置
return 0;
}
E. 排序（2016 GC小甲 5）
Description
有N*M只奶牛，每只奶牛的头上都印有一个唯一的标识ID，第i头奶牛的ID是正整数i。农夫FJ有一块大农田，FJ把农田划分成N行M列的格子，每个格子都必须有且仅有一头奶牛在里面工作。由于奶牛是无序动物，所以它们随机的各自选取了一个格子就开始工作了。但FJ希望他的奶牛是有序的，FJ希望第1行的奶牛从左往右的ID依次是：1,2,3，......M；第二行的奶牛从左往右的ID依次是：M+1,M+2,M+3,....2*M；...最后一行的奶牛从左往右的ID一次是：(N-1)*M+1,(n-1)*M+2,.....N*M。
所以农夫FJ决定对奶牛进行排序。FJ只能对奶牛使用两种指令：
任意交换两行奶牛。
任意交换两列奶牛。
上述的两种指令，FJ可以任用无限次。
那么FJ可以达到目标吗？如果可以，输出“Possible”，否则输出“Impossible”。
Input Format
第一行，一个整数R，表示总共有R组测试数据。 1<=R<=10。
每组测试数据格式如下：
第一行，两个整数：N和M。 1<=N,M<=50。
接下来是N行M列的格子，第i行第j列是一个正整数，表示一开始在该格子工作的奶牛的ID。
Output Format
共R行，每行输出“Possible”，或者输出“Impossible”，双引号不用输出。
输入数据 1
5
2 2
1 2
3 4
2 2
3 4
1 2
2 2
4 3
1 2
1 10
4 5 1 2 9 8 3 10 7 6
3 5
10 6 8 9 7
5 1 3 4 2
15 11 13 14 12 输出数据 1
Possible
Possible
Impossible
Possible
Possible题意
给定一个矩阵，问是否通过任意次交换两行或两列的得到题目所示的矩阵。
思路
可以先对结果矩阵找规律，可以看出每一列%m都是相等的；把数轴上的点以m为分割点化成若干个区间，每一行的数都在同一个区间里，即/m是相等的。这样出现一个问题是每一行最后一个数和前面的数/m是不相等的。 举个例子，比如1 2 3，n=3，那么3得到的结果是0 0 1，但是我们想让他相等，这样比较好判断，就可以让每个数都-1，这样会发现变成了0 1 2，3 后变成了0 0 0 ，符合题意。 所以我们也就找到了能够使得题目条件成立的矩阵的特征。再来考虑做的变换，因为每次变换都是两行或两列的换，所以如果说原始的数组不满足特征的话，再怎么变换也不符合题意；如果满足特征的话，一定能够变换成符合题意的矩阵。
代码
本题要理解二维数组的遍历。
#include<bits/stdc++.h>
using namespace std;
int r,n,m,i,j,t,a[1005][1005],b[1005][1005],c[1005][1005];
int main(){
scanf("%d",&r);
while(r--){
int count=0,flag=1;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
scanf("%d",&a[i][j]);
b[i][j]=a[i][j]%m,c[i][j]=(a[i][j]-1)/m;
}
for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)for(t=1;t<=m;t++)
if(b[i][t]!=b[j][t]){
flag=0;
break;
}
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
for(t=1;t<=n;t++)
if(c[t][i]!=c[t][j]){
flag=0;
break;
}
if(flag==1)printf("Possible\n");
else printf("Impossible\n");
}
return 0;
}
F. 累加和（2016 GC小甲 6）
Description
1、老师在黑板上写下一个正整数，记为X1。
2、删除X1的最后一位数字后，得到的正整数记为X2。
3、删除X2的最后一位数字后，得到的正整数记为X3。
。。。。
进行若干次操作后，剩下的正整数只有1位数字了，记为Xn。
令Y = X1 + X2 + X3 + ....+ Xn。
例如：老师刚开始在黑板写下的正整数是509，那么:
X1 = 509
X2 = 50
X3 = 5
那么此时的Y = 509+50+5 = 564。
现在给出Y，你的任务是求出X1。数据能保证对于Y，X1不会有多个解，如果找不到X1,那么输出-1。
Input Format
一行，一个正整数Y。(1<=Y<=10^16)
Output Format
一行，一个整数X1,或者输出-1。
输入数据 1
565Copy
输出数据 1
-1Copy
Hint
输入样例二：
137174210616796
输出样例二：
123456789555123
【数据范围】
1、对于20%的数据，1 <= Y <= 1000000。
2、对于100%的数据，1 <= Y <= 1000000000000000000。
思路
本题因为要查找的数字X肯定在1-Y之间是有序的，可以使用二分答案
代码
#include<bits/stdc++.h>
#define ll long long//定义ll 为long long
using namespace std;
ll work(ll k) {//拆分数字K
ll s=0;
while(k>0) {
s+=k;
k/=10;
}
return s;
}
int main() {
ll n;
cin>>n;
ll L=0, R=n;
while(L<=R) {
ll mid =(L+R)>>1;
if(work(mid)==n) {//找到这个数字
cout<<mid;
return 0;
}
if(work(mid)>n)//要查找的数字在左边
R=mid-1;
else//要查找的数字在右边
L=mid+1;
}
cout<<-1;
return 0;
}