A. Hello, A + B
題意
每行僅含四個(gè)整數(shù)A, B, C, D (-10^9 ≤ A, B, C, D ≤ 10^9).
0 0 0 0代表輸入結(jié)束, 你不應(yīng)該處理它.
對(duì)于每組數(shù)據(jù), 輸出A+B-C*D.
思路
+/-1e9的數(shù)字用int夠裝
那么1e9*1e9呢揍鸟？
所以要么用long long類(lèi)型（VC++中為int64_t）
足矣摔蓝，如果要用int裝數(shù)尘喝，在計(jì)算和輸出時(shí)候注意
轉(zhuǎn)型long long。//(+/- 9e18)
C代碼實(shí)現(xiàn)
#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元.
那么對(duì)于貨幣而言, 要湊夠x (1 ≤ x ≤ 10^18) 元至少需要多少?gòu)堚n票?
輸入包含多組測(cè)試數(shù)據(jù).
第一行為一個(gè)整數(shù)n (1 ≤ n ≤ 200000). 表示測(cè)試數(shù)據(jù)的數(shù)量
緊接著為n行, 每行一個(gè)數(shù)字x (1 ≤ x ≤ 10^18).
對(duì)于每組測(cè)試數(shù)據(jù), 輸出湊夠x (1 ≤ x ≤ 10^18) 元至少需要鈔票的數(shù)量.
思路
可以先從最大的鈔票一直往下拿译仗，就可以得到最小了，不出意外，你就WA了
（這種思路本身也是算是一種貪心策略玻褪，不過(guò)本題有特殊情況）
本題算是取巧做出來(lái)的，你至少手動(dòng)分配7-28元這段范圍的鈔票應(yīng)該怎么拿公荧，
然后分析带射，才能理解為什么我這樣寫(xiě)。
出題師兄的代碼實(shí)現(xiàn)方法是DP（動(dòng)態(tài)規(guī)劃）
略修改循狰，可以解決任意貨面值組合的最少取鈔的求解窟社。
用遞歸可以實(shí)現(xiàn)（要優(yōu)化，不要重復(fù)計(jì)算）
C代碼實(shí)現(xiàn)
#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盞燈, 依次被標(biāo)記為1, 2, 3, 4, 5, …, N.
開(kāi)始時(shí)所有燈都被關(guān)閉. Edward先按下所有編號(hào)為A的倍數(shù)的燈對(duì)應(yīng)的開(kāi)關(guān), 所有編號(hào)為A的倍數(shù)的燈都將亮起. 然后再按下所有編號(hào)為B的倍數(shù)的燈對(duì)應(yīng)的開(kāi)關(guān), 其中關(guān)著的燈將會(huì)亮起, 開(kāi)著的燈將被關(guān)閉. 最終, Edward的房間亮起了多少盞燈?
輸入包含多組測(cè)試數(shù)據(jù). 每組數(shù)據(jù)為三個(gè)數(shù)字N, A, B (1 ≤ A, B ≤ N ≤ 10^18). 輸入以EOF結(jié)束.
對(duì)于每組測(cè)試數(shù)據(jù), 輸出最終Edward的房間亮起的燈的數(shù)量.
思路
數(shù)據(jù)long long可裝，
有n/a+n/b次開(kāi)關(guān)燈操作
n/（a和b的最小公約數(shù)）次重復(fù)（也就是操作了兩次检眯，應(yīng)為關(guān)燈的狀態(tài)）
這里的唯一坑點(diǎn)俯逾，就只有a和b的最小公倍數(shù)了，它會(huì)導(dǎo)致數(shù)值溢出匣吊。
看數(shù)據(jù)a和b小于n沒(méi)錯(cuò)盗扒，所以能用long long裝下，但是缀去，當(dāng)a和b足夠大
并且他們的最小公約數(shù)足夠小時(shí)侣灶。那么這個(gè)數(shù)值會(huì)大于n，也會(huì)大于longlong的范圍
那么不夠裝缕碎，只能截取這個(gè)數(shù)的64個(gè)位（二進(jìn)制的位）了褥影，所以，得到的值可能會(huì)是
比n小的數(shù)咏雌，也可能是一個(gè)負(fù)數(shù)凡怎。這也是溢出的意思。
由于此題的特殊性赊抖，若是這個(gè)最小公倍數(shù)大于n统倒，其實(shí)也就沒(méi)有重復(fù)。
p是最小公倍數(shù)氛雪，所以
從v=n/(a*b/p)我們可以改為
v=n/b/(a/p);這樣就有效防止了溢出房匆，
也不需要用所謂的大數(shù)（高精度）處理
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}, 求它的最大連續(xù)子序列的和, 它的開(kāi)始位置和結(jié)束位置..
輸入包含多組測(cè)試數(shù)據(jù). 輸入以EOF結(jié)束.
第一行為整數(shù)n (1 ≤ n ≤ 100000).
第二行包含n個(gè)整數(shù). 這n個(gè)整數(shù)的范圍在 -100000 到 100000之間.
對(duì)于每組輸入, 你應(yīng)輸出一行. 格式為: ”Case %T: %SUM %BEG %END”.其中%T為測(cè)試數(shù)據(jù)的編號(hào). %SUM為測(cè)試數(shù)據(jù)的最大連續(xù)子序列的和. %BEG為子序列的開(kāi)始位置. %END為子序列的結(jié)束位置. 可能有多個(gè)連續(xù)子序列的和相等, 不過(guò)你應(yīng)該返回第一個(gè)子序列的開(kāi)始和結(jié)束位置.
思路
只要一路加上去，要求i~j的和
只要a[j]-a[i-1]就可以得到
參考數(shù)列Sn=a1+a2+....+an
接下來(lái)就是選點(diǎn)了报亩。
假設(shè)右邊某一點(diǎn)是序列的結(jié)尾浴鸿，再按以上思路，
只需要通過(guò)記錄和不斷判斷找到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);
}
}
