A. Restoring Three Numbers
題意
給出四個(gè)數(shù)：a+b、a+c寨辩、b+c、a+b+c歼冰，要求輸出a靡狞、b、c
關(guān)鍵詞
數(shù)學(xué)
思路
四個(gè)數(shù)中隔嫡，最大的數(shù)一定是a+b+c
用這個(gè)數(shù)減去其他三個(gè)數(shù)的結(jié)果甸怕，就是a、b腮恩、c梢杭。
代碼
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 300005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
int num[4];
for (int i = 0; i < 4; ++i)
{
cin>>num[i];
}
sort(num,num+4);
int a, b, c;
b = num[3]-num[1];
a = num[3] -num[2];
c = num[3] -num[0];
cout<<a<<" "<<b<<" "<<c<<endl;
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
B. Make Them Equal
題意
給定一個(gè)長(zhǎng)度為n的數(shù)組，可以對(duì)數(shù)組中每一個(gè)數(shù)都加上或減去同一個(gè)數(shù)D秸滴，如果存在使得數(shù)組所有數(shù)都相等的D則輸出D武契，否則輸出-1。
關(guān)鍵詞
數(shù)學(xué)
思路
用set來保存數(shù)組中有多少個(gè)不同的數(shù)荡含，并對(duì)set的大小size分成3種情況進(jìn)行討論：
- size=3：如果三個(gè)數(shù)構(gòu)成等差數(shù)列咒唆，則結(jié)果為等差數(shù)列的差，否則無解释液。
- size=2：這種情況一定有解全释，如果兩數(shù)之差為奇數(shù)，則結(jié)果就為他們的差误债，如果為偶數(shù)浸船，則可以再除以二妄迁。
-
size=1：顯然，這種情況數(shù)組中的數(shù)已經(jīng)是相等的李命，結(jié)果為
0登淘。
代碼
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 1000
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int n;
int arr[MAXN];
set<int> se;
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
cin>>n;
for (int i = 0; i < n; ++i)
{
cin>>arr[i];
se.insert(arr[i]);
}
int sum = 0;
vector<int> vt;
for (int i : se)
{
vt.pb(i);
}
if(se.size() == 3)
{
int a = vt[0];
int b = vt[1];
int c = vt[2];
if(c-b != b-a)
{
cout<<-1<<endl;
} else
cout<<b-a<<endl;
}else if(se.size() == 2)
{
int ans = vt[1] - vt[0];
if(ans % 2 == 0 )
ans /= 2;
cout<<ans<<endl;
}else if(se.size() == 1)
{
cout<<0<<endl;
} else
{
cout<<-1<<endl;
}
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
C. Gourmet Cat
題意
給出a、b项戴、c三種食物的數(shù)量形帮，并規(guī)定一周中每天吃的食物：
| 周一 | 周二 | 周三 | 周四 | 周五 | 周六 | 周日 |
|---|---|---|---|---|---|---|
| a | b | c | a | c | b | a |
可以從任意一天開始，求最多能連續(xù)吃多少天周叮。
關(guān)鍵詞
貪心辩撑、暴力
思路
顯然一周中，需要消耗a3份仿耽，b2份合冀，c2份。
對(duì)于給定的食物數(shù)量项贺，按照這個(gè)比例可以求出能完整地吃多少周君躺。
再求出無法連續(xù)吃一周時(shí)，剩余每種食物的數(shù)量开缎。
從周一到周日開始暴力枚舉棕叫，求出這些剩余的食物最長(zhǎng)能連吃多少天。
代碼
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 700000005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
int a, b, c;
cin >> a >> b >> c;
ll ans = 7 * min(a / 3, min(b / 2, c / 2));
if (ans)
{
a -= ans / 7* 3;
b -= ans / 7* 2;
c -= ans / 7* 2;
}
int ta = a, tb= b, tc = c;
int d[] = {1, 2, 3, 1, 3, 2, 1};
int m = 0;
for (int i = 0; i < 7; ++i)
{
int t = 0;
int ta = a, tb= b, tc = c;
for (int j = i, k = 0; k < 7; ++k, j = (i+k)%7)
{
if (d[j] == 1)
{
if (ta)
{
ta--;
t++;
} else
{
break;
}
} else if (d[j] == 2)
{
if (tb)
{
tb--;
t++;
} else
break;
} else
{
if (tc)
{
tc--;
t++;
} else
break;
}
}
m = max(m, t);
}
ans += m;
cout << ans << endl;
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
D. Walking Robot
題意
給定一個(gè)擁有一個(gè)普通電池（用完就不可以再使用）和一個(gè)太陽能電池（在一定條件下可充電）的機(jī)器人奕删。
兩塊電池開始時(shí)電量都是滿的俺泣，且容量分別為b（普通電池）、a（太陽能電池）完残。且每走一段路程都需要消耗一個(gè)單位的電量伏钠。
給定n段路程，當(dāng)該段路程可以給太陽能電池充電時(shí)谨设，用1表示熟掂，位于該段路程中，可以通過使用普通電池行走扎拣，使太陽能電池的電量+1赴肚，但不能超過其容量。
求機(jī)器能最長(zhǎng)能走多遠(yuǎn)二蓝。
關(guān)鍵詞
貪心尊蚁、構(gòu)造
思路
在不能給太陽能電池充電時(shí)或可以充電但太陽能電池的電量已滿時(shí)，優(yōu)先使用太陽能電池侣夷。其他情況使用普通電池横朋。
代碼
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 200005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int arr[MAXN];
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
int n, b, a;
cin >> n >> b >> a;
int c = a;
int ans = 0;
for (int i = 1; i <= n; ++i)
{
cin >> arr[i];
if (arr[i])
{
if (c && c == a)
{
c--;
} else if (b)
{
b--;
c++;
} else if (c)
{
c--;
} else
{
ans = i;
break;
}
} else
{
if (c)
{
c--;
} else if (b)
{
b--;
} else
{
ans = i;
break;
}
}
}
if( ans == 0)
ans = n;
else
ans --;
cout << ans << endl;
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
E. Two Teams
題意
給一個(gè)長(zhǎng)度為n的學(xué)生初始隊(duì)伍，按照每次選擇初始隊(duì)伍中數(shù)值最大的學(xué)生和他左右最多各k個(gè)學(xué)生百拓，分配到另外兩個(gè)隊(duì)伍琴锭。
要求打印分配結(jié)果晰甚。
關(guān)鍵詞
構(gòu)造、排序决帖、數(shù)據(jù)結(jié)構(gòu)厕九、雙向鏈表
思路
記錄每一個(gè)數(shù)值的學(xué)生所在的位置，并使用數(shù)組（方便根據(jù)數(shù)值直接拿到學(xué)生的位置）維護(hù)一個(gè)類似雙向鏈表的數(shù)據(jù)結(jié)構(gòu)地回。
對(duì)于每一個(gè)初始隊(duì)伍中的學(xué)生扁远，維護(hù)他左邊和右邊相鄰第一個(gè)學(xué)生的坐標(biāo)缚俏。
從初始隊(duì)伍移除學(xué)生時(shí)溶锭，使用這個(gè)學(xué)生維護(hù)其左右相鄰學(xué)生的相鄰學(xué)生坐標(biāo)幅聘。類似于雙向鏈表中刪除某個(gè)節(jié)點(diǎn)時(shí)汰聋，更新前后節(jié)點(diǎn)指針的操作。
對(duì)學(xué)生排序盐类。
每次移除數(shù)值最高的俗批，并向左右繼續(xù)移除最多k個(gè)學(xué)生痕貌。
代碼
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 200005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr,v) memset((arr),(v),sizeof(arr))
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int sk[MAXN], le[MAXN], ri[MAXN];
int arr[MAXN];
int ans[MAXN];
void remove (int x)
{
le[ri[x]] = le[x];
ri[le[x]] = ri[x];
}
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
int n, k;
MSET(ans, 0);
cin >> n >> k;
for (int i = 1; i <= n; ++i)
{
cin >> arr[i];
sk[arr[i]] = i;
le[i] = i - 1;
ri[i] = i + 1;
}
int team = 1;
for (int i = n; i >= 0; --i)
{
int index = sk[i];
if(ans[index])
continue;
remove(index);
ans[index] = team;
int l = le[index], r = ri[index];
for (int cnt = 0; cnt < k && l>0; ++cnt, l = le[l])
{
if(!ans[l])
{
remove(l);
ans[l] = team;
}
}
for (int cnt = 0; cnt < k && r<=n; ++cnt, r = ri[r])
{
if(!ans[r])
{
remove(r);
ans[r] = team;
}
}
team = 3 - team;
}
for (int i = 0; i < n; ++i)
{
cout<<ans[1+i];
}
cout<<endl;
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
F. Shovels Shop
題意
給定n件物品的價(jià)格溜徙，每種物品只有一件湃缎，以及m種優(yōu)惠。
每種優(yōu)惠的都可以表示為蠢壹，一次恰好購(gòu)買x件物品時(shí)嗓违，最便宜的y件都免費(fèi)。不限制優(yōu)惠的使用次數(shù)图贸。
問不限制購(gòu)買次數(shù)且每次都可以購(gòu)買任意物品的情況下蹂季，購(gòu)買k個(gè)物品最少需要花多少錢。
關(guān)鍵詞
dp求妹、貪心
思路
類似于背包問題的解法：
使用dp[i]表示恰好購(gòu)買i件物品花費(fèi)的最少金額，顯然一定是最便宜的i件佳窑。
- 先對(duì)價(jià)格排序制恍，并求累加和
sum
（sum(i)表示物品位置在[1, i]的價(jià)格累加和，sum(a, b)表示物品位置在[a, b]的價(jià)格的累加和） - 初始值：
dp[i] = sum(i)神凑，dp[0] = 0净神。 - 對(duì)于每個(gè)數(shù)量
i、每種優(yōu)惠的x溉委、y鹃唯，狀態(tài)轉(zhuǎn)移方程為：
dp[i] = min(dp[i], dp[i-x] + sum(i-x+y+1, i))。
狀態(tài)轉(zhuǎn)移方程的含義：
對(duì)于購(gòu)買當(dāng)前數(shù)量i的物品所花費(fèi)最小金額的狀態(tài)瓣喊，都可以通過在dp[i-x]狀態(tài)的基礎(chǔ)上使用某種優(yōu)惠來達(dá)到坡慌，使用該優(yōu)惠的花費(fèi)為sum(i-x+y+1, i)。
對(duì)于狀態(tài)i藻三，取所有使用的優(yōu)惠中洪橘，花錢最少的那種即可跪者。
代碼
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 200015
#define MAXM 200
#define MAXK 10000010
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int n, m, k;
int arr[MAXN];
Pair pur[MAXN];
ll dp[MAXN] = {0};
ll sum[MAXN] = {0};
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i)
{
cin >> arr[i];
}
for (int i = 0; i < m; ++i)
{
cin >> pur[i].first >> pur[i].second;
}
sort(arr+1, arr + n+1);
for (int i = 1; i <= n; ++i)
{
sum[i] = sum[i - 1] + arr[i];
dp[i] = sum[i];
}
dp[0] = 0;
for (int i = 0; i <= k; ++i)
{
for (int j = 0; j < m; ++j)
{
int x = pur[j].first;
int y = pur[j].second;
if(i+x > k)
continue;
dp[i + x] = min(dp[i + x], dp[i] + sum[i + x] - sum[i + y]);
}
}
cout << dp[k] << endl;
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
F. Minimum Possible LCM
題意
給定n個(gè)數(shù)，求出其中任意兩個(gè)數(shù)的最小公倍數(shù)的最小值為多少熄求。
關(guān)鍵詞
暴力渣玲、貪心、數(shù)論
思路
顯然弟晚，至少出現(xiàn)過2次的最小那個(gè)的數(shù)忘衍，一定是最優(yōu)的結(jié)果。
對(duì)于其他情況：
枚舉一個(gè)公因子i卿城，如果給定的數(shù)中存在i的兩個(gè)不同的倍數(shù)枚钓，則通過i計(jì)算這兩個(gè)數(shù)的公倍數(shù)去維護(hù)最終結(jié)果盡可能小。
即：
對(duì)于i藻雪，如果存在兩個(gè)數(shù)A秘噪、B滿足A=a*i、B=b*i（a和b為不同整數(shù)勉耀，這意味著i為A指煎、B的公因子），則ans = min(ans, A*B/i) = min(ans, a*b*i)便斥。
需要注意的是至壤，如果整數(shù)a、b不互質(zhì)枢纠，則意味著i不是最大公因子像街，此時(shí)A*B/i并不會(huì)是A、B的最小公倍數(shù)晋渺，而是一個(gè)大于最小公倍數(shù)的值镰绎。
但是這并不影響最終結(jié)果，因?yàn)槟疚鳎诤竺鎸?duì)i的枚舉中畴栖，早晚會(huì)枚舉到A、B的最小公倍數(shù)八千，最終結(jié)果會(huì)維護(hù)為最小的值吗讶。
例如，
i=2恋捆，A=4照皆、B=8，此時(shí)的a=2沸停，b=4膜毁。算出來的公倍數(shù)為A*B/i = 16，并不是A、B的最小公倍數(shù)爽茴。
但是在接下來枚舉到i=4的時(shí)候葬凳，對(duì)于A=4、B=8就有a=1室奏，b=2火焰。此時(shí)算出來的就是最小公倍數(shù)A*B/i = 8。
因?yàn)?strong>最終結(jié)果會(huì)取每次枚舉結(jié)果的最小值胧沫，這里為8昌简，所以前面i=2時(shí)雖然不是最優(yōu)解，但不會(huì)影響后面真正的最優(yōu)解的求解绒怨。
代碼
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 10000005
#define MAXM 200
#define MAXK 10000010
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);s
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int n;
ll arr[MAXN];
int index[MAXN] = {0};
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
// SYNC
cin >> n;
ll mi = LONG_LONG_MAX;
int a, b;
for (int i = 1; i <= n; ++i)
{
cin >> arr[i];
// If the smallest number appears twice, this number will be the optimal solution.
if (index[arr[i]] && arr[i] < mi)
{
mi = arr[i];
a = index[arr[i]];
b = i;
}
index[arr[i]] = i;
}
for (int i = 1; i < MAXN; ++i)
{
int aa = 0, bb = 0;
ll x, y;
for (int j = i; j < MAXN; j += i)
{
if (index[j] && aa > 0)
{
y = j;
bb = index[y];
break;
} else if (index[j])
{
x = j;
aa = index[x];
}
}
if(!aa || !bb)
continue;
ll lcm = x * y / i;
if (lcm < mi)
{
mi = lcm;
a = aa;
b = bb;
}
}
if (a > b)
swap(a, b);
cout << a << " " << b << endl;
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
}
