A

题意

有 $k$ 种饮料，每两个种类相同的饮料组成一组。每种饮料都有无限组。有 $n$ 个同学。每个同学有一种想喝的饮料。选择 $\lceil \frac{n}{2} \rceil$ 种饮料。问最多能有多少个同学喝到自己想喝的饮料。 $1\le n,k \le 10000$

solve

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

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.向盒子中放入 $x$ 个糖。其中 $x$ 表示当前是第 $x$ 次向盒子中放糖。
2.从盒子中取出 $1$ 个糖。要求盒子中必须有糖才能进行此操作。
现在给出操作数 $n(1 \le n \le 10^9)$ 和最终剩余的糖果数量 $k(0 \le k \le 10^9)$ ，问总共可以取出几个糖(即进行操作2的次数)。保证有解。

solve

设 $a$ 为进行操作 $1$ 的次数。那么放入的糖果数就是 $\frac{a \times (a + 1)}{2}$ ,取出的糖果数就是 $n-a$
所以 $\frac{a \times (a + 1)}{2} - (n - a) = k$
$a$ 是 $\sqrt{k}$ 级别的，枚举即可。

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

题意

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

solve

$f[i][0/1/2]$ 表示前 $i$ 个同学中第 $i$ 个位置选的是第一排(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

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

题意

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

如：

$f(1111,2222)=12121212$ $f(7777,888)=7787878$ $f(33,44444)=4443434$ $f(555,6)=5556$ $f(111,2222)=2121212$

现在给出 $n(1\le n \le 10^5)$ 个数字,记第 $i$ 个数字为 $a_i$
求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^nf(a_i,a_j) mod\ 998244353$

solve

考虑某个数字某一位的贡献。
设 $r$ 为位数大于等于当前位置 $k$ 的数字个数， $y$ 为当前位置的数字,这些数字所造成的贡献就是 $r\times y \times (10 ^ {2k} + 10^{2k+1})$

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

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

题意

有一个 $n\times m$ 的矩阵，询问其中所有大小为 $a \times b$ 的子矩阵的最小值之和。 $1\le n,m \le 3000$

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;
}

CF1195 解题报告

A

题意

solve

code

B

题意

solve

code

C

题意

solve

code

D1 & D2

题意

solve

code

E

题意

solve

code