[18.11.14]GPNU新生热身赛题解 [18.11.14]GPNU新生热身赛题解

A. Hello, A + B 题意
每行仅含四个整数A, B, C, D (-10^9 ≤ A, B, C, D ≤ 10^9).
0 0 0 0代表输入结束, 你不应该处理它.
对于每组数据, 输出A+B-C*D.
思路 +/-1e9的数字用int够装
那么1e9*1e9呢？
所以要么用long long类型（VC++中为int64_t）
足矣，如果要用int装数，在计算和输出时候注意
转型long long。//(+/- 9e18)
C代码实现

#include int main() { long long a,b,c,d; while (1) { scanf("%lld%lld%lld%lld",&a,&b,&c,&d); if (!(a || b || c || d)) break; printf("%lld\n",a+b-c*d); } return 0; }

B. Money 题意
【[18.11.14]GPNU新生热身赛题解】1元, 3元, 7元, 10元, 30元, 70元, 100元, 300元, 700元, 1000元, 3000元, 7000元, 10000元.
那么对于货币而言, 要凑够x (1 ≤ x ≤ 10^18) 元至少需要多少张钞票?
输入包含多组测试数据.
第一行为一个整数n (1 ≤ n ≤ 200000). 表示测试数据的数量
紧接着为n行, 每行一个数字x (1 ≤ x ≤ 10^18).
对于每组测试数据, 输出凑够x (1 ≤ x ≤ 10^18) 元至少需要钞票的数量.
思路可以先从最大的钞票一直往下拿，就可以得到最小了，不出意外，你就WA了
（这种思路本身也是算是一种贪心策略，不过本题有特殊情况）
本题算是取巧做出来的，你至少手动分配7-28元这段范围的钞票应该怎么拿，
然后分析，才能理解为什么我这样写。
出题师兄的代码实现方法是DP（动态规划）
略修改，可以解决任意货面值组合的最少取钞的求解。
用递归可以实现（要优化，不要重复计算）
C代码实现

#include const long long tx[17]={-1000,10000,7000,3000,-100,1000,700,300,-10,100,70,30,-1,10,7,3,1}; int main(void) { long long n,x,s,p; int i; scanf("%lld",&n); while (n--) { scanf("%lld",&x); s=0; for (i=0; i<17; i++) if (tx[i]>0) { s+=x/tx[i]; x%=tx[i]; }else { p=x/(-tx[i]); if (p>13 && p%10>3 && p%10<6) { s+=2; x-=(-tx[i])*14; } } printf("%lld\n",s); } return 0; }

C. Light 题意
Edward的房间有N盏灯, 依次被标记为1, 2, 3, 4, 5, …, N.
开始时所有灯都被关闭. Edward先按下所有编号为A的倍数的灯对应的开关, 所有编号为A的倍数的灯都将亮起. 然后再按下所有编号为B的倍数的灯对应的开关, 其中关着的灯将会亮起, 开着的灯将被关闭. 最终, Edward的房间亮起了多少盏灯?
输入包含多组测试数据. 每组数据为三个数字N, A, B (1 ≤ A, B ≤ N ≤ 10^18). 输入以EOF结束.
对于每组测试数据, 输出最终Edward的房间亮起的灯的数量.
思路数据long long可装，
有n/a+n/b次开关灯操作
n/（a和b的最小公约数）次重复（也就是操作了两次，应为关灯的状态）
这里的唯一坑点，就只有a和b的最小公倍数了，它会导致数值溢出。
看数据a和b小于n没错，所以能用long long装下，但是，当a和b足够大
并且他们的最小公约数足够小时。那么这个数值会大于n，也会大于longlong的范围
那么不够装，只能截取这个数的64个位（二进制的位）了，所以，得到的值可能会是
比n小的数，也可能是一个负数。这也是溢出的意思。
由于此题的特殊性，若是这个最小公倍数大于n，其实也就没有重复。
p是最小公倍数，所以
从v=n/(a*b/p)我们可以改为
v=n/b/(a/p); 这样就有效防止了溢出，
也不需要用所谓的大数（高精度）处理
C源代码

#include long long gcd(long long a,long long b) { return (b==0) ? a : gcd(b,a%b); } int main(void) { long long n,a,b,p,v,v1,v2,sum; while (~scanf("%lld%lld%lld",&n,&a,&b)) { p=(a>b)?gcd(a,b):gcd(b,a); v1=n/a; v2=n/b; v=n/b/(a/p); sum=v1-v+v2-v; printf("%lld\n",sum); } return 0; }

D. Max Sum of Subsequence 题意
给定序列{a1, a2, a3, … , an}, 求它的最大连续子序列的和, 它的开始位置和结束位置..
输入包含多组测试数据. 输入以EOF结束.
第一行为整数n (1 ≤ n ≤ 100000).
第二行包含n个整数. 这n个整数的范围在 -100000 到 100000之间.
对于每组输入, 你应输出一行. 格式为: ”Case %T: %SUM %BEG %END”.其中%T为测试数据的编号. %SUM为测试数据的最大连续子序列的和. %BEG为子序列的开始位置. %END为子序列的结束位置. 可能有多个连续子序列的和相等, 不过你应该返回第一个子序列的开始和结束位置.
思路只要一路加上去，要求i~j的和
只要a[j]-a[i-1]就可以得到
参考数列Sn=a1+a2+....+an
接下来就是选点了。
假设右边某一点是序列的结尾，再按以上思路，
只需要通过记录和不断判断找到a[i-1]最小的位置就行了。
C源代码

#include #define inf 1e18 long long a[100003]; int main(void) { long long t=0,mx,n,i,j,x,y,mn; while (~scanf("%lld",&n)) { for (i=1; i<=n; i++) { scanf("%lld",a+i); a[i]+=a[i-1]; } t++; mx=-inf; x=1; y=1; mn=0; for (i=1; i<=n; i++) { if (a[i]-a[mn]>mx) { mx=a[i]-a[mn]; x=mn+1; y=i; } if (a[mn]>a[i]) mn=i; } printf("Case %lld: %lld %lld %lld\n",t,mx,x,y); } }