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 <stdio.h>
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
题意
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 <stdio.h>
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 <stdio.h>
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 <stdio.h>
#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);
}
}
