比赛链接：https://codeforces.com/contest/1341

A - Nastya and Rice

有 n 堆米，每堆质量在 [a-b,a+b] 之间，这些米的总质量是否可能在 [c-d,c+d] 之间。

n 堆米的最小总质量为 n*(a-b)，最大总质量为 n*(a+b)，即判断区间 [n*(a-b),n*(a+b)] 是否与 [c-d,c+d] 相交。

#include
using namespace std;

void solve() {
int n, a, b, c, d; cin >> n >> a >> b >> c >> d;
int mi = n * (a - b);
int mx = n * (a + b);
if (c + d < mi or c - d > mx)
cout << "No" << "\n";
else
cout << "Yes" << "\n";
}

int main() {
int t; cin >> t;
while (t--) solve();
}

B - Nastya and Door

有一数组 a，定长 k 最多能完整覆盖多少 a[i-1] < a[i] 且 a[i] > a[i+1] 的长为 3 的区间，不考虑数组两端。

前缀和记录每个端点为止的符合条件的区间数量，之后枚举定长的起始点，覆盖区间的右端点需要再减一来错峰。

#include
using namespace std;

void solve() {
int n, k; cin >> n >> k;
int a[n + 1]= {};
for (int i = 1; i <= n; i++) { cin >> a[i];
}
int cnt[n + 1] = {};
for (int i = 1; i <= n; i++) { cnt[i] += cnt[i - 1]; if (a[i] > a[i - 1] and a[i] > a[i + 1])
++cnt[i];
}
int mx = 1, st = 1;
for (int i = 1; i + k - 1 <= n; i++) { int l = i, r = i + k - 2; int sub = cnt[r] - cnt[l] + 1; if (sub > mx) mx = sub, st = l;
}
cout << mx << ' ' << st << "\n";
}

int main() {
int t; cin >> t;
while (t--) solve();
}

记录所有符合条件区间的左右端点，对于每个枚举的起始点二分查找最近的区间左右端点。

#include
using namespace std;

void solve() {
int n, k; cin >> n >> k;
int a[n + 1]; for (int i = 1; i <= n; i++) cin >> a[i];
vector l, r;
for (int i = 2; i <= n - 1; i++) { if (a[i - 1] < a[i] and a[i] > a[i + 1]) {
l.push_back(i - 1);
r.push_back(i + 1);
}
}
int mx = 1, st = 1;
for (int i = 1; i <= n; i++) { int lf = lower_bound(l.begin(), l.end(), i) - l.begin(); int rt = upper_bound(r.begin(), r.end(), i + k - 1) - r.begin(); if (rt > 0 and rt - lf + 1 > mx) {
mx = rt - lf + 1;
st = i;
}
}
cout << mx << ' ' << st << "\n";
}

int main() {
int t; cin >> t;
while (t--) solve();
}

C - Nastya and Strange Generator

[1,2,3,…,n] 中每次可从一点起向右连续选取所有未选取的位置并依次放置 1 ~ n，问所有可能的放置中是否有当前排列。

因为是连续放置的所以 a[i - 1] + 1 = a[i] 或 a[i - 1] > a[i]，即 a[i] - a[i - 1] ≤ 1。

#include
using namespace std;

void solve() {
int n; cin >> n;
int a[n]; for (int &i : a) cin >> i;
for (int i = 0; i + 1 < n; i++) { if (a[i + 1] - a[i] > 1) {
cout << "No" << "\n";
return;
}
}
cout << "Yes" << "\n";
}

int main() {
int t; cin >> t;
while (t--) solve();
}

D - Nastya and Scoreboard

有一液晶数字板，其中亮着一些段，问再点亮 k 段所能构成的最大数字。

先确定每位可以用掉几段，ok[i][j] 表示第 i 位可以用掉 j 段，之后从后向前构造，dp[i][j] 表示构造到第 i 位时用 j 段是否可行，dp[0][k] 可行即有解（构造 n-1 → 0 位）。因为在 dp 的过程中每一位每一种可行的情况都是与之后一系列的位相关联的，所以当输出第一位的最大可行数字后后面一系列的位就已经确定了。

#include
using namespace std;

const int M = 2200;

string str[10] = {"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
int a[M], s[10];
bool ok[M][8], dp[M][M];

int main() {
for (int i = 0; i < 10; i++) { for (int j = 0; j < 7; j++) { s[i] = 2 * s[i] + str[i][j] - '0'; } } int n, k; cin >> n >> k;
for (int i = 0; i < n; i++) { int a_i = 0; for (int j = 0; j < 7; j++) { char c; cin >> c;
a_i = 2 * a_i + c - '0';
}
a[i] = a_i;
for (int j = 0; j < 10; j++) { if ((a[i] & s[j]) == a[i]) { int cnt = __builtin_popcount(a[i] ^ s[j]); ok[i][cnt] = true; } } } dp[n][0] = true; for (int i = n - 1; i >= 0; i--)
for (int j = 0; j < M; j++)
if (dp[i + 1][j])
for (int k = 0; k <= 7; k++)
if (ok[i][k])
dp[i][j + k] = true;
if (!dp[0][k]) cout << "-1";
else {
for (int i = 0; i < n; i++)
for (int j = 9; ; j--)
if ((a[i] & s[j]) == a[i]) {
int cnt = __builtin_popcount(a[i] ^ s[j]);
if (dp[i + 1][k - cnt]) {
k -= cnt; cout << j;
break;
}
}
}
}