传送

A Drinks Choosing

题意： 给出 $n$ 个元素，一共有 $k$个不同元素，请你给出$⌈n/2⌉$ 个二元组，每个二元组中的两个元素相同，使你给出的所有元素中与原元素相同个数最多。请你给出最多的相同个数。

思路：很水的题目，，，显然对于每个不同的元素，如果有偶数个，那么全部可以满足，剩下的所有元素（假设有M个），最多满足 $⌈M/2⌉$ 个

Code Below

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef bitset<35> sta;

int n,k,c[1005],ans;

int main(){
    cin>>n>>k;
    for (int i=1;i<=n;++i){
        int x; scanf("%d",&x);
        c[x]++;
    }
    n=(n+1)/2;
    for (int i=1;i<=1000;++i){
        ans+=(c[i]/2)*2; n-=c[i]/2; c[i]%=2; 
    }
    for (int i=1;i<=1000;++i){
        if (n>0 && c[i]) ans++,n--;
    }
    cout<<ans<<endl;
    return 0;
}

B Sport Mafia

题意： 有一个盒子，珂朵莉每次可以做两个操作：

1. 吃一块黄油蛋糕；
2. 放入比上一次放入的个数多一个的黄油蛋糕。

当盒子为空时，珂朵莉只能执行第2个操作。第1次操作永远是放入一个蛋糕。 现在给出操作数$n$和操作后蛋糕数量$k$，求出珂朵莉吃了多少块蛋糕。

题目保证有解。

思路：显然是个数学题（别问我为什么）

设放入$x$次，则有$$\frac{x*(x+1)}{2}=n-x+k$$

因此$$x= \frac{-3+\sqrt{9+8(n+k)}}{2} $$直接求解即可，注意要舍去非法解

Code Below

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef bitset<35> sta;

ll n,k;

int main(){
    cin>>n>>k;
    ll t=2*(n+k);
    ll ans1=(-3+(ll)(sqrt(9+4*t)+0.5))/2;
    ll ans2=(-3-(ll)(sqrt(9+4*t)+0.5))/2;
    if (ans1>=1 && ans1<=n) cout<<n-ans1<<endl;
    else cout<<n-ans2<<endl;
    return 0;
}

C Basketball Exercise

题意： 给定一个 $2×n$ 的矩阵 h，现从中选择若干数，且任意两个数不上下或左右相邻，求这些数的和最大是多少？

思路：好睿智的DP。。。可以发现每一行至多去一个，状态转移无后效性

$F_{i,j}$表示前i行，最后一行状态为j的最大和（j=0表示 第i行 不取， j=1表示 第i行 取上面的一个， j=2表示 第i行 取下面的一个 ）有

$$F_{i,j}=max(F_{i-1,k}+a_{i,j},k \neq j)$$

Code Below

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef bitset<35> sta;

int n,a[100005][3];
ll f[100005][3];

int main(){
    cin>>n;
    for (int i=1;i<=n;++i){
        scanf("%d",&a[i][1]);
    }
    for (int i=1;i<=n;++i){
        scanf("%d",&a[i][2]);
    }
    for (int i=1;i<=n;++i){
        f[i][0]=max({f[i-1][0],f[i-1][1],f[i-1][2]});
        f[i][1]=max({f[i-1][0],f[i-1][2]})+a[i][1];
        f[i][2]=max({f[i-1][0],f[i-1][1]})+a[i][2];
    }
    cout<<max({f[n][0],f[n][1],f[n][2]})<<endl;
    return 0;
}

E OpenStreetMap

题意： 给定一个 $ n\times m $ 的矩阵 $ h $ ,求出所有大小为 $ a\times b $ 的子矩形中的最小值的和.
矩阵的给定方式: 给定 $ g_0,x,y,z $ ,它们表示一个序列 $ g_i=(g_{i-1}\cdot x+y)\bmod z $ ,而 $ h_{i,j}=g_{(i-1)\cdot m+j-1} $.

思路： 单调队列模板题

首先生成这个矩阵（这应该不用我说了吧。。。）

由于矩阵是二维的，不能直接用单调队列，因此可以先预处理出每行的情况$f_{i,j}$表示$h_{i,j} – h_{i,j+a-1}$中的最小值（很明显用单调队列）

这样就把原来的a*b的矩阵转换成了1*b的矩阵，然后再求出每个1*b矩阵中的最小值，求和即可（还是用单调队列）

单调队列具体实现方法：

以第一次操作为例，对于每一行

1. 首先建立一个双端队列(STL deque)，双端队列中存一个int类型，表示该元素对应是第i行的第几个。然后扫描该行，设扫到该行第j个元素
2. 首先检查对头的元素与j的距离是否大于a（如果大于说明这个最小值已经“过期”，弹出队头，并再次检查）
3. 最后剩下的队头就是$j-a+1 – j-1$之间的最小值，与当前的$h_{i,j}$取个min即得到了一个最小值，累加到答案中
4. 检查队尾元素值是否大于$h_{i,j}$，如果大于，弹出队尾并重复这一步（因为这些元素在j之前就被加入，且值比j大，未来肯定没用，为了维护队列的单调性，直接弹出即可）
5. 把j插入到队尾

为什么这样可行？原因在于维护了一个队列，其中队列中每个下标对应的元素值递增，这样每次取出队头就得到了该次的最小值。每个元素平均出队/入队1次，因此复杂度为$O(nm)$

Code Below

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef bitset<35> sta;

int n,m,a,b;
ll ans,t[3005][3005],h[3005][3005],g[9000005],x,y,z;

int main(){
    cin>>n>>m>>a>>b;
    cin>>g[0]>>x>>y>>z;
    for (int i=1;i<=n*m;++i){
        g[i]=(g[i-1]*x+y)%z;
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            t[i][j]=h[i][j]=g[(i-1)*m+j-1];
        }
    }
    for (int i=1;i<=n;++i){
        deque <int> q;
        q.clear();
        for (int j=1;j<=m;++j){
            while (!q.empty() && q.front()<j-b+1) q.pop_front();
            while (!q.empty() && h[i][q.back()]>=h[i][j]) q.pop_back();
            q.push_back(j);
            if (j>=b) t[i][j]=h[i][q.front()];
        }
    }
    for (int j=b;j<=m;++j){
        deque <int> q;
        q.clear();
        for (int i=1;i<=n;++i){
            while (!q.empty() && q.front()<i-a+1) q.pop_front();
            while (!q.empty() && t[q.back()][j]>=t[i][j]) q.pop_back();
            q.push_back(i);
            if (i>=a) ans+=t[q.front()][j];
        }
    }
    cout<<ans<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/cf574-div2-1195/