A

题意

有种饮料，每两个种类相同的饮料组成一组。每种饮料都有无限组。有个同学。每个同学有一种想喝的饮料。选择种饮料。问最多能有多少个同学喝到自己想喝的饮料。

solve

统计出每种饮料有多少个同学想喝。找出有奇数个人喜欢的饮料个数。答案就是

code

/*
* @Author: wxyww
* @Date:   2019-07-17 22:34:23
* @Last Modified time: 2019-07-17 22:42:55
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;

ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int a[1010];
int main() {
    int n = read(),k  =read();

    for(int i = 1;i <= n;++i) {
        a[read()]++;
    }
    int ans = 0;
    for(int i = 1;i <= 1000;++i) {
        ans += a[i] & 1;
    }    
    n -= ans / 2;
    cout<<n;

    return 0;
}

B

题意

有一个盒子，两种操作:
1.向盒子中放入个糖。其中表示当前是第次向盒子中放糖。
2.从盒子中取出个糖。要求盒子中必须有糖才能进行此操作。
现在给出操作数和最终剩余的糖果数量，问总共可以取出几个糖(即进行操作2的次数)。保证有解。

solve

设为进行操作的次数。那么放入的糖果数就是,取出的糖果数就是
所以
是级别的，枚举即可。

code

/*
* @Author: wxyww
* @Date:   2019-07-17 23:05:03
* @Last Modified time: 2019-07-18 07:53:04
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;

ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

int main() {
    ll n = read(),k = read();
    for(ll i = 0;i <= n;++i) {
        if(i * (i + 3) == 2 * k + 2 * n) {
            cout<<n - i<<endl;return 0;
        }
    }
    return 0;
}

C

题意

有两排同学，每排都有个。每个同学都有一个高度,从中选出任意多个人。满足每排相邻的两个人不能被选中。求高度和最大为多少。

solve

表示前个同学中第个位置选的是第一排(0),第二排(1),没选(2)的最大高度。转移即可。

code

/*
* @Author: wxyww
* @Date:   2019-07-17 23:13:00
* @Last Modified time: 2019-07-18 07:53:31
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll f[N][3],a[N],b[N];
int main() {
    int n = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    for(int i = 1;i <= n;++i) b[i] = read();
    for(int i = 1;i <= n;++i) {
        f[i][0] = max(f[i - 1][1],f[i - 1][2]) + a[i];
        f[i][1] = max(f[i - 1][0],f[i - 1][2]) + b[i];
        f[i][2]=  max(f[i - 1][0],f[i - 1][1]);
    }
    cout<<max(f[n][0],max(f[n][1],f[n][2]));
    return 0;
}

D1 & D2

为的特殊情况，只描述解法

题意

定义一个函数,是把和从个位开始往上依次排列得到新的数字。

如：

现在给出个数字,记第个数字为
求

solve

考虑某个数字某一位的贡献。
设为位数大于等于当前位置的数字个数，为当前位置的数字,这些数字所造成的贡献就是

然后再考虑位数小于当前位置k的数字造成的贡献。假设与一个位数为的数字进行操作之后，会使得当前位置的数字到了位置上，那么当前位置的数字的贡献就是，然后求个前缀和即可快速计算出所有小于等于它的数字造成的贡献。

code

/*
* @Author: wxyww
* @Date:   2019-07-17 23:34:49
* @Last Modified time: 2019-07-18 07:54:18
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int mod = 998244353;
#define int ll
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
const int N = 1000000;
ll s[N],sum[N],a[N];
ll qm(ll x,ll y) {
    ll ret = 1;
    for(;y;y >>= 1,x = x * x % mod) 
        if(y & 1) ret = ret * x % mod;
    return ret;
}
signed main() {
    int n = read();
    for(int i = 1;i <= n;++i) {
        a[i] = read();
        int x = a[i];
        int js = 0;
        while(x) ++js,x /= 10;
        s[js]++;
        sum[js] += qm(10,js);
        sum[js] %= mod;
    }
    for(int i = 1;i <= 100;++i) {
        sum[i] += sum[i - 1];
        s[i] += s[i - 1];
        sum[i] %= mod;
    }
    ll ans = 0;
    for(int i = 1;i <= n;++i) {
        int x = a[i];
        int js = 0;
        while(x) {
            int y = x % 10;
            ll l = s[js],K = sum[js],r = n - l;
            ans += (y * r % mod * (qm(10,js << 1) + qm(10,js << 1 | 1)) % mod) % mod;
            ans %= mod;
            ans += 2ll * y * sum[js] % mod * qm(10,js) % mod;

            ans %= mod;
            x /= 10;
            ++js;
        }
    }
    cout<<ans;

    return 0;
}

E

题意

有一个的矩阵，询问其中所有大小为的子矩阵的最小值之和。

solve

先对于每一行用单调队列跑出来每a个数字中的最小值。然后在对于求出的最小值中每一列用单调队列求出来最小值，然后求和。

code

/*
* @Author: wxyww
* @Date:   2019-07-18 14:37:59
* @Last Modified time: 2019-07-18 14:55:00
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 3010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll ans;
int t[N * N],a[N][N],b[N][N],q[N];
int main() {
    int n = read(),m = read(),nn = read(),mm = read();
    t[0] = read();int x = read(),y = read(),mod = read();
    for(int i = 1;i <= n * m;++i) t[i] = (1ll * t[i - 1] * x % mod+ y) % mod;

    for(int i = 1;i <= n;++i) {
        int head = 1,tail = 0;
        for(int j = 1;j <= m;++j) {
            a[i][j] = t[(i - 1) * m + j - 1];
            while(tail >= head && a[i][q[tail]] >= a[i][j]) --tail;
            q[++tail] = j;
            while(tail >= head && q[head] <= j - mm) ++head;
            if(j >= mm) b[i][j - mm + 1] = a[i][q[head]];
        }
    }



    for(int j = 1;j <= m - mm + 1;++j) {
        int head = 1,tail = 0;
        for(int i = 1;i <= n;++i) {
            while(tail >= head && b[q[tail]][j] >= b[i][j]) --tail;
                q[++tail] = i;
            while(tail >= head && q[head] <= i - nn) ++head;
            if(i >= nn) ans += b[q[head]][j];
        }
    }

    cout<<ans<<endl;

    return 0;
}