A题 悬崖 (脑筋急转弯)
脑筋急转弯题,就不翻译题目了,没必要。
当 时,可以一直跳到两个墙合并,答案为 。
当 时,至多跳一次就掉下去,但是还是有跳跃距离的,答案为 。
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long x, n, ans;
cin >> x >> n;
ans = n > x ? x : n * x;
cout << ans << endl;
return 0;
}
B题 数数 (签到)
给定一个函数:
void dfs(int cnt) { //cnt从1开始 如同dfs(1) for(int i = 1;i <= cnt;i++) ans++; dfs(cnt + 2); }
问函数递归到第 层时, 的值为多少?(从 开始, 是全局变量,初始值为 0)
样例: 时,
不难发现,第 层会让答案增加 ,所以 。
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n;
cin >> n;
cout << n * n;
return 0;
}
C题 山楂 (数学,贪心)
已知现在有不少等级不同的糖果,我们可以每次选择将 3 或 4 个 级的糖果合成为一个 级的糖果,并获得 点积分。当若干个 8 级糖果被合成为一个 9 级糖果后,这个糖果会消失,不再能够被继续合成。
现在给定前八级糖果的数量 ,问我们能够合成的最高积分是多少?
糖果只能从低级向高级合成,所以我们贪心的考虑,先低级后高级。
我们假设 级糖果的数量为 ,那么 时无法合成, 时可以将三个糖果合并, 时则将四个全部合并。
时候,有一个不是很显然的性质: 一定能够被表示为 的形式(可以同余证明,或者去参考 小凯的疑惑),这意味着这一级的糖果必然能被全部合成,即给积分贡献 。那么,我们必然要最大化合成的 级糖果数量,显然数量为 。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL a[10];
const LL v[6] = {0, 0, 0, 3, 4, 4};
int main()
{
for (int i = 1; i <= 8; ++i)
cin >> a[i];
LL ans = 0;
for (int k = 1; k <= 8; ++k) {
LL n = a[k];
ans += k * (n > 5 ? n : v[n]);
a[k + 1] += n / 3;
}
cout << ans;
return 0;
}
D题 切糕 (思维,前缀和)
给定一个括号串,可以可以将其切上几刀或者不切,将其变为若干个合法括号串,问有多少种切的方式?
合法括号串:串内左右括号数量相等,且任意前缀内左括号数量不少于右括号。
,答案对 取模
若干个合法括号串的拼接必然也是一个合法括号串,所以我们直接对原括号串扫一遍,看看合不合法。
如果合法,我们重新开始,每找到能切的地方就标记一下,最后记标记的总数量为 ,那么最后答案就是 。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1000010;
const LL mod = 1e9 + 7;
int n = 0, a[N], sum[N];
int main()
{
//read
string s;
cin >> s;
for (char c : s) a[++n] = c == '(' ? 1 : -1;
//solve
bool NoSolution = false;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + a[i];
if (sum[i] == 0 && i != n) cnt++;
if (sum[i] < 0) NoSolution = true;
}
if (sum[n] != 0) NoSolution = true;
if (NoSolution) {
cout << -1;
return 0;
}
LL ans = 1;
for (int i = 0; i < cnt; ++i)
ans = ans * 2 % mod;
cout << ans;
return 0;
}
E题 筑巢 (树形DP)
给定一棵树,树上的点和边都拥有一个舒适值。
现在想要在树上选择一个连通块,使得连通块内部的点和边的舒适值之和最大。
我们考虑一手树形 DP,从根节点 1 开始,那么显然,这个连通块要么包含自己,要么在它的某一棵子树中。
那么,我们尝试设立状态 ,表示点 在选或者不选下的所得连通块最大值,那么有 DP 方程:
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 100010;
int n, w[N];
struct Edge { int to, val; };
vector<Edge> tree[N];
LL dp[N][2];
void dfs(int x, int fa) {
dp[x][0] = -1e18, dp[x][1] = w[x];
for (Edge e : tree[x]) {
int y = e.to, v = e.val;
if (y != fa) {
dfs(y, x);
dp[x][0] = max(dp[x][0], max(dp[y][0], dp[y][1]));
dp[x][1] = dp[x][1] + max(dp[y][1] + v, 0LL);
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> w[i];
for (int i = 1; i < n; ++i) {
int x, y, v;
cin >> x >> y >> v;
tree[x].push_back((Edge){y, v});
tree[y].push_back((Edge){x, v});
}
dfs(1, 0);
cout << max(dp[1][0], dp[1][1]);
return 0;
}
F题 交换
题面很详细且简洁,就不翻译了。
我们记排列长度 。
对于每次询问,我们考虑枚举所有可能的区间并进行操作,总复杂度为 。
我们参考这场的前缀和训练题 牛牛的猜球游戏,来对区间操作进行优化,可以将复杂度降到 。不过显然,枚举的复杂度降不了了,必须得进行优化。
(我一开始以为这个答案长度可以二分,等比赛结束了才发现这个不符合二分性质)
注意到一个性质:对于 ,排列的所有可能仅有 种,这意味着我们可以直接从排列中枚举,将复杂度降到 。但问题是, 的规模, 和 是一个数量级的,也没啥用啊?
我们换一个角度考虑,在每次询问中,我们已经知道了原排列,需要将其变为一个按照升序来的新排列,那么,我们不难构造出这个操作序列是咋样的,之后直接在所有排列中查找这个操作序列是否存在即可。
Trie树
Trie树是为了实现字符串的快速检索,同样的,它也可以实现排列的检索。
不过这个Trie树应该开多大是应该先算好的(毕竟空间有限),我们可以,手建一棵排列长度为 4 的Trie树,计算一下大小看看。
我们记一个排列长度为 的Trie树的大小为 (按照节点数的数量来算),找规律发现:。
这是一个阶乘增长的函数(查表发现 ),递推可得 ,就离谱(我们得开一个将近 规模的 int 数组,还好内存限制是 512M,再加上很多叶子节点不需要向下扩展,所以实际上很多空间是未被使用的,所以不会被记入使用范围)
#include<bits/stdc++.h>
using namespace std;
const int N = 2010, SIZE = 1e7 + 10;
struct State {
int a[11];
State(){}
State(int k, int *arr) {
for (int i = 1; i <= k; ++i) a[i] = arr[i];
for (int i = k + 1; i <= 10; ++i) a[i] = i;
}
void Swap(int x, int y) { swap(a[x], a[y]); }
};
//
int Trie[SIZE][11], V[SIZE], tot = 0;
void insert(State s, int val) {
int p = 0, *arr = s.a;
for (int i = 1; i <= 10; ++i) {
int x = arr[i];
if (!Trie[p][x]) Trie[p][x] = ++tot, V[tot] = val;
p = Trie[p][x];
V[p] = min(V[p], val);
}
}
int search(int k, State s) {
int p = 0, *arr = s.a;
for (int i = 1; i <= k; ++i) {
p = Trie[p][arr[i]];
if (!p) return -1;
}
return ***}
int n, m, x[N], y[N];
State opt[N][2];
int main()
{
//read
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d%d", &x[i], &y[i]);
//init
for (int i = 1; i <= 10; ++i)
opt[0][0].a[i] = i;
insert(opt[0][0], 0);
for (int i = 1; i <= n + 1; ++i)
opt[i][0] = opt[0][0];
for (int len = 1; len <= n; ++len) {
for (int i = 1; i + len - 1 <= n; ++i) {
opt[i][len % 2] = opt[i + 1][(len - 1) % 2];
opt[i][len % 2].Swap(x[i], y[i]);
insert(opt[i][len % 2], len);
}
}
//query
while (m--) {
int k, a[11];
scanf("%d", &k);
for (int i = 1; i <= k; ++i)
scanf("%d", &a[i]);
State s(k, a);
printf("%d\n", search(k, s));
}
return 0;
}
康托展开+哈希
显然,我们可以将排列通过康托展开来映射为一个数,然后开一个哈希表来进行 查找。
int calc(int n, int *arr) {
int vis[20];
memset(vis, 0, sizeof(vis));
int res = 1;
for (int i = 1; i < n; ++i) {
int x = arr[i], cnt = 0;
vis[x] = 1;
for (int j = 1; j < x; ++j) if (!vis[j]) cnt++;
//f[k]=k!
res += cnt * f[n - i];
}
return res;
}
不过比较尴尬的是,我们构造出来的操作序列往往不止一种,很有可能是若干种(例如将排列 变为 ,那么构造的操作序列应为 ,即后四位不固定)。那么,我们总不能一个个枚举来查吧?
康托展开有一个比较让人平和的性质:假设一个排列的前 位确定了,后 位不确定,那么记后 位从小到大排序,所得康托展开值为 ,那么其从大到小排序所得的展开值为 ,且所有可能排列的区间值均在 之间。
我们可以开一棵线段树当哈希表,然后每次查询看看区间有没有符合要求的值即可。
//代码略,有空去参考下别的dalao写的代码