CF574 div2 1195

Author Avatar
Axell 7月 28, 2019
  • 在其它设备中阅读本文章

传送

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://axell.wind-flower.cn/archives/cf574-div2-1195/