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);
    }
}