A. Restoring Three Numbers
题意
给出四个数:a+b、a+c、b+c、a+b+c,要求输出a、b、c
关键词
数学
思路
四个数中,最大的数一定是a+b+c
用这个数减去其他三个数的结果,就是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
题意
给定一个长度为n的数组,可以对数组中每一个数都加上或减去同一个数D,如果存在使得数组所有数都相等的D则输出D,否则输出-1。
关键词
数学
思路
用set来保存数组中有多少个不同的数,并对set的大小size分成3种情况进行讨论:
- size=3:如果三个数构成等差数列,则结果为等差数列的差,否则无解。
- size=2:这种情况一定有解,如果两数之差为奇数,则结果就为他们的差,如果为偶数,则可以再除以二。
- size=1:显然,这种情况数组中的数已经是相等的,结果为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三种食物的数量,并规定一周中每天吃的食物:
周一 | 周二 | 周三 | 周四 | 周五 | 周六 | 周日 |
---|---|---|---|---|---|---|
a | b | c | a | c | b | a |
可以从任意一天开始,求最多能连续吃多少天。
关键词
贪心、暴力
思路
显然一周中,需要消耗a3份,b2份,c2份。
对于给定的食物数量,按照这个比例可以求出能完整地吃多少周。
再求出无法连续吃一周时,剩余每种食物的数量。
从周一到周日开始暴力枚举,求出这些剩余的食物最长能连吃多少天。
代码
#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
题意
给定一个拥有一个普通电池(用完就不可以再使用)和一个太阳能电池(在一定条件下可充电)的机器人。
两块电池开始时电量都是满的,且容量分别为b(普通电池)、a(太阳能电池)。且每走一段路程都需要消耗一个单位的电量。
给定n段路程,当该段路程可以给太阳能电池充电时,用1表示,位于该段路程中,可以通过使用普通电池行走,使太阳能电池的电量+1,但不能超过其容量。
求机器能最长能走多远。
关键词
贪心、构造
思路
在不能给太阳能电池充电时或可以充电但太阳能电池的电量已满时,优先使用太阳能电池。其他情况使用普通电池。
代码
#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
题意
给一个长度为n的学生初始队伍,按照每次选择初始队伍中数值最大的学生和他左右最多各k个学生,分配到另外两个队伍。
要求打印分配结果。
关键词
构造、排序、数据结构、双向链表
思路
记录每一个数值的学生所在的位置,并使用数组(方便根据数值直接拿到学生的位置)维护一个类似双向链表的数据结构。
对于每一个初始队伍中的学生,维护他左边和右边相邻第一个学生的坐标。
从初始队伍移除学生时,使用这个学生维护其左右相邻学生的相邻学生坐标。类似于双向链表中删除某个节点时,更新前后节点指针的操作。
对学生排序。
每次移除数值最高的,并向左右继续移除最多k个学生。
代码
#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件物品的价格,每种物品只有一件,以及m种优惠。
每种优惠的都可以表示为,一次恰好购买x件物品时,最便宜的y件都免费。不限制优惠的使用次数。
问不限制购买次数且每次都可以购买任意物品的情况下,购买k个物品最少需要花多少钱。
关键词
dp、贪心
思路
类似于背包问题的解法:
使用dp[i]表示恰好购买i件物品花费的最少金额,显然一定是最便宜的i件。
- 先对价格排序,并求累加和sum
(sum(i)表示物品位置在[1, i]的价格累加和,sum(a, b)表示物品位置在[a, b]的价格的累加和) - 初始值:dp[i] = sum(i),dp[0] = 0。
- 对于每个数量i、每种优惠的x、y,状态转移方程为:
dp[i] = min(dp[i], dp[i-x] + sum(i-x+y+1, i))。
状态转移方程的含义:
对于购买当前数量i的物品所花费最小金额的状态,都可以通过在dp[i-x]状态的基础上使用某种优惠来达到,使用该优惠的花费为sum(i-x+y+1, i)。
对于状态i,取所有使用的优惠中,花钱最少的那种即可。
代码
#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个数,求出其中任意两个数的最小公倍数的最小值为多少。
关键词
暴力、贪心、数论
思路
显然,至少出现过2次的最小那个的数,一定是最优的结果。
对于其他情况:
枚举一个公因子i,如果给定的数中存在i的两个不同的倍数,则通过i计算这两个数的公倍数去维护最终结果尽可能小。
即:
对于i,如果存在两个数A、B满足A=a*i、B=b*i(a和b为不同整数,这意味着i为A、B的公因子),则ans = min(ans, A*B/i) = min(ans, a*b*i)。
需要注意的是,如果整数a、b不互质,则意味着i不是最大公因子,此时A*B/i并不会是A、B的最小公倍数,而是一个大于最小公倍数的值。
但是这并不影响最终结果,因为,在后面对i的枚举中,早晚会枚举到A、B的最小公倍数,最终结果会维护为最小的值。
例如,i=2,A=4、B=8,此时的a=2,b=4。算出来的公倍数为A*B/i = 16,并不是A、B的最小公倍数。
但是在接下来枚举到i=4的时候,对于A=4、B=8就有a=1,b=2。此时算出来的就是最小公倍数A*B/i = 8。
因为最终结果会取每次枚举结果的最小值,这里为8,所以前面i=2时虽然不是最优解,但不会影响后面真正的最优解的求解。
代码
#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; }