A.Berland Poker

题意：

有张牌，其中张joker,将这张牌平均分给个人，询问拿到joker牌数最多和剩下的所有人中拿到joker牌数最多的之差最大为多少

题解：

让joker尽可能多的在一个手上，如果，那就让这张都到一个人手里，否则一个人拿张joker，剩下的人均分

#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;
void solve()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    if (m <= n / k)
        printf("%d\n", m);
    else
        printf("%d\n", n / k - (int)ceil((1.0 * m - n / k) / (k - 1)));
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.New Theatre Square

题意：

给出一个只由"."和"*"组成的的矩阵，消除一个的"."花费为，消除一个的"."花费为。求恰好将"."消除的最小费用。(注意的可以一次消除，的无法一次消除)

题解：

因为只有和两种方法，所以只需要考虑每行，对于相邻两个"."考虑和的大小，只有一个"."用即可

#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;
void solve()
{
    int n, m, x, y, ans = 0;
    scanf("%d%d%d%d", &n, &m, &x, &y);
    while (n--)
    {
        string s;
        cin >> s;
        for (int i = 0; i < m; i++)
        {
            if (s[i] == '.' && s[i + 1] == '.' && 2 * x > y)
            {
                ans += y;
                s[i + 1] = '*';
            }
            else if (s[i] == '.')
                ans += x;
        }
    }
   printf("%d\n",ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Mixing Water

题意：

热水和冷水的温度分别为，。
以 一杯热水->一杯冷水->一杯热水->一杯冷水->…的顺序加入一个容器内，
询问最少加多少杯，可以最接近温度。

题解：

  1. ,
  2. ,
  3. 得，带入式子比较和与的差即可
    #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;
void solve()
{
 ll h, c, t;
 scanf("%lld%lld%lld", &h, &c, &t);
 if (h == t)
     puts("1");
 else if (h + c >= 2 * t)
     puts("2");
 else
 {
     ll x = (h - t) / (2 * t - h - c);
     ll y = x + 1;
     if (abs((2 * x + 1) * t - (x + 1) * h - x * c) * (2 * y + 1) <= abs((2 * y + 1) * t - (y + 1) * h - y * c) * (2 * x + 1))
         printf("%lld\n", 2 * x + 1);
     else
         printf("%lld\n", 2 * y + 1);
 }
}
int main()
{
 int t;
 for (scanf("%d", &t); t >= 1; t--)
     solve();
}

D.Yet Another Yet Another Task

题意：

给定个数，求一段区间之和-区间内最大值的最大值

题解：

因为答案最小为
所以可以从到$304枚举可能的区间最大值
然后遍历寻找最大子段和即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int main()
{
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    int ans = 0;
    for (int i = 1; i <= 30; i++)
    {
        int res = 0;
        for (int j : arr)
        {
            res += j;
            if (j > i)
                res = 0;
            res = max(res, 0);
            ans = max(ans, res - i);
        }
    }
    printf("%d\n", ans);
    return 0;
}

E.Modular Stability

题意：

给定和，要求在中找出不同的个数，使得,其中为的每种排列

题解：

从中选取一个基数，再从中找的这个基数的倍数即可，最终结果都为。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll fac[maxn];
ll qpow(ll a, ll b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init()
{
    fac[0] = 1;
    for (int i = 1; i < maxn; i++)
        fac[i] = fac[i - 1] * i % mod;
}
ll c(int x, int y)
{
    if (x < 0 || y < 0 || x < y)
        return 0;
    return fac[x] * qpow(fac[y] * fac[x - y] % mod, mod - 2) % mod;
}
int main()
{
    init();
    ll n, k;
    scanf("%lld%lld", &n, &k);
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        ans = (ans + c(n / i - 1, k - 1)) % mod;
    printf("%lld\n", ans);
    return 0;
}