A.Nastya and Rice

题意：

给定个物品，每个物品的重量都限制在，询问是否存在一种方案使得这个物品的重量合在之间

题解：

极限情况判断大小，比较和与和即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n, a, b, c, d;
    scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
    if (n * (a + b) < c - d || n * (a - b) > c + d)
        puts("No");
    else
        puts("Yes");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Nastya and Door

题意：

给定个点和一条长度为的线段，要求区间内的极大值点（峰点）尽可能多。

题解：

统计所有极大值点之后扫描一遍。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int a[maxn];
bool check[maxn];
void solve()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    check[1] = check[n] = false;
    for (int i = 2; i < n; i++)
        check[i] = (a[i] > a[i - 1]) && (a[i] > a[i + 1]);
    int sum = 0;
    for (int i = 1; i < k; i++)
        sum += check[i];
    int ans = -1, l = 0;
    for (int i = k; i <= n; i++)
    {
        if (check[i - k + 1])
            sum--;
        if (ans < sum)
        {
            ans = sum;
            l = i - k + 1;
        }
        sum += check[i];
    }
    printf("%d %d\n", ans + 1, l);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Nastya and Strange Generator

题意：

有一个生成器，会按照以下条件从到从小到大每次赋一个值构造序列：

  • 规定为最小的大于等于的且未被赋值的下标。
  • 规定为中的个数。
  • 选取任意一个值进行赋值。

现在给出一个序列，问是否可以通过这个生成器生成。

题解：

注意到初始状态下所有的都是自己，所以所有的都为。但是每确定一个数字后，当前确定的下标的就会增加。所以在一个数字确定后，接下来的数字一定是连续到串结束或者已被赋值的点。根据第一个数字的下标不断进行扫描即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int p[maxn], idx[maxn];
bool vis[maxn];
void solve()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &p[i]);
        idx[p[i]] = i;
        vis[i] = false;
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            for (int j = idx[i]; j <= n; j++)
            {
                if (vis[p[j]])
                    break;
                if (p[j] - j == i - idx[i])
                    vis[p[j]] = true;
                else
                {
                    puts("No");
                    return;
                }
            }
    puts("Yes");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Nastya and Scoreboard

题意：

给定个记分板，每个记分板由根火柴棒组成（为表示不亮，为表示亮），最终结果为各位上上亮的部分，问加根火柴棒以后能拼出的最大数字。
图片说明
图片说明

题解：

首先可以肯定优先将高位变成最大的肯定比变低位来的优，因此将每一位的状态用二进制的形式表示，从最高位依次dfs暴力搜一遍能到达的最大值即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
const int maxn = 3e3 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int tab[10] = {119, 18, 93, 91, 58, 107, 111, 82, 127, 123};
int n, k, a[maxn], ans[maxn];
bool vis[maxn][maxn];
string s;
void dfs(int i, int x)
{
    if (x > k || vis[i][x])
        return;
    vis[i][x] = 1;
    if (i == n)
    {
        if (x == k)
        {
            for (int j = 0; j < n; j++)
                printf("%d", ans[j]);
            exit(0);
        }
        return;
    }
    for (int j = 9; j >= 0; j--)
    {
        ans[i] = j;
        if ((tab[j] & a[i]) == a[i])
            dfs(i + 1, x + __builtin_popcount(tab[j] ^ a[i]));
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        for (char j : s)
            a[i] = a[i] * 2 + (j - '0');
    }
    dfs(0, 0);
    puts("-1");
    return 0;
}