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