Google-KickStart-Round-E
Google KickStart Round E
这次做的有点菜😓
High Buildings
题意:构造一个以a[1]
为首且长度为a
的最长不下降序列,以a[n]
为尾且长度为b
的最长不上升序列,这两个序列的公共部分长度为c
。
考场上不知道哪里的边界情况没处理好,而且没利用好不下降/不上升的一个性质:$a[i]\leq a[i+1]$,可以构造为$a[i]=a[i+1]$。以下代码参考自榜1。
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;
typedef long long ll;
void solve()
{
int n, a, b, c;
cin >> n >> a >> b >> c;
int lena = a - c;
int lenb = b - c;
if (lena + lenb + c > n || (lena + lenb + c == 1 && n >= 2))
{
printf("IMPOSSIBLE\n");
return;
}
if (n == 1)
{
printf("1\n");
return;
}
if (n == 2)
{
if (c == 2)
printf("1 1\n");
else if (a == 2)
printf("1 2\n");
else if (b == 2)
printf("2 1\n");
return;
}
vector<int> ans;
for (int i = 1; i <= lena; i++)
ans.push_back(2);
for (int i = 1; i <= c; i++)
ans.push_back(3);
for (int i = 1; i <= lenb; i++)
ans.push_back(2);
int extra = n - lena - lenb - c;
if (extra)
ans.insert(ans.begin() + 1, extra, 1);
for (int i = 0; i < n; i++)
printf("%d ", ans[i]);
printf("\n");
}
int main()
{
int T;
cin >> T;
cin.ignore();
for (int caseNum = 1; caseNum <= T; caseNum++)
{
printf("Case #%d: ", caseNum);
solve();
}
return 0;
}
Toys
这题想了一会正解,没想出来,又懒得写暴力,所以就没做了。看了正解之后发现,其实我已经想到一大半了……
如果一个toy不能无限玩:$R_i>\sum_{j\neq i}E_j=\sum_j E_j-E_i$,所以能无限玩的toy满足:$R_i+E_i\leq SUM$, where $SUM$ is the sum of all selected toys $E_i$.
最优解:每次尝试移除$R_i+E_i$最大的toy,因为如果移除其他的toy,such as $j$, $R_i+E_i>SUM$依然成立。