AGC008
B
题目大意
给出一个序列，一开始全是白色，一次操作可以染黑或染白一段长度为 \(K\) 的区间，要让最后序列中黑色格子上数的和最大，求这个最大值。
解题思路
考虑找结论。
发现我们一定要尽可能地把正数涂黑，负数涂白，由于对操作次数没有限制，因此对一个正数我们只要将其放在区间首位涂黑，再把后面的数涂白即可实现单独将其涂黑。
但是我们发现如果这么做最后的 \(K\) 个数就无法实现，同理，如果逆转从后往前涂那么前 \(K\) 个数就无法实现。
考虑一段从前往后，一段从后往前，中间就会有 \(K\) 个数无法实现，而其他正数都能取到。
因此我们可以枚举这个无法实现的区间，如果它求和大于 \(0\) 就加上，否则不加，然后将剩下的所有正数求和加上。
代码上，我们可以维护两个前缀和，一个是序列的前缀和 \(s_1\)，一个是正数的前缀和 \(s_2\)。
答案即为：
\[\max_{i=1}^{n-k+1}{(s_2[i - 1] + s_2[n] - s_2[i + k - 1] + \max(0, s_1[i + k - 1] - s_1[i - 1]))} \]代码
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n, k;
ll s1[N], s2[N], ans;
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> s1[i];
s2[i] = s2[i - 1];
if (s1[i] > 0)
{
s2[i] += s1[i];
}
s1[i] += s1[i - 1];
}
for (int i = 1; i <= n - k + 1; i++)
{
ans = max(ans, s2[i - 1] + s2[n] - s2[i + k - 1] + max(0ll, s1[i + k - 1] - s1[i - 1]));
}
cout << ans << endl;
return 0;
}
D
题目大意
构造一个序列 \(a\)，使得：
-
\(a\) 的长度为 \(N^2\)，并且满足数字 \(1,2, \cdots, N\) 都各出现恰好 \(N\) 次。
-
对于 \(1 \le i \le N\)，数字 \(i\) 在 \(a\) 中第 \(i\) 次出现的位置是 \(X_i\)。
解题思路
考虑贪心。
题意即为：对于 \(1 \le i \le N\)，位置 \(X_i\) 上的数为 \(i\)，前面有 \(i-1\) 个 \(i\)，后面有 \(n -i\) 个。
考虑先满足前一个条件，我们可以对 \(X_i\) 从小到大排序，然后放在 \(X_i\) 前面空位即可，放不下就必定无解。
但是我们为了顾及后面一个条件，那么就需要尽可能少地占用后面的空位，因此我们填数时在最前面的空位一定是最优的。
于是后面一个条件只需从大到小遍历，找后面的空位放即可（不一定要选取最后面，但为了编写方便，不妨就选最后的空位）。
代码
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
const int N = 510;
struct node
{
int id, x;
} b[N];
int n;
int a[N * N];
bool cmp(node x, node y)
{
return x.x < y.x;
}
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> b[i].x;
a[b[i].x] = i;
b[i].id = i;
}
sort(b + 1, b + n + 1, cmp);
for (int i = 1, p = 1; i <= n; i++)
{
for (int j = 1; j < b[i].id; j++)
{
while (p <= b[i].x && a[p] != 0)
{
p++;
}
if (p > b[i].x)
{
cout << "No" << endl;
return 0;
}
a[p++] = b[i].id;
}
}
for (int i = n, p = n * n; i >= 1; i--)
{
for (int j = b[i].id + 1; j <= n; j++)
{
while (p >= b[i].x && a[p] != 0)
{
p--;
}
if (p < b[i].x)
{
cout << "No" << endl;
return 0;
}
a[p--] = b[i].id;
}
}
cout << "Yes" << endl;
for (int i = 1; i <= n * n; i++)
{
cout << a[i] << " ";
}
return 0;
}