codeTONround6

[CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)](https://codeforces.com/contest/1870)

（2023年9月18日晚）

C. Colorful Table

题意

给出n个数$a_1 ,a_2,...,a_n$ ，以及一个数k，所有数满足 $1\le a_i \le k$ ,数组b是一个nxn的二维数组，其中 $b_{i,j} = min(a_i,a_j)$ ,对于每一个数 $1 \le x \le k$ ，求出面积最小的矩阵，使得矩阵中涵盖了b数组中的所有的$x$，输出矩阵的两边之和（例如矩阵为3x3就输出6（6=3+3），矩阵为2x5就输出7（7=2+5））。

思路

例如a数组为（k = 4）：

1	2	3	4	1

那么b数组为：

$b[i,j]$	$a_1 = 1$	$a_2 = 2$	$a_3 = 3$	$a_4 = 4$	$a_5 = 1$
$a_1 = 1$	1	1	1	1	1
$a_2 = 2$	1	2	2	2	1
$a_3 = 3$	1	2	3	3	1
$a_4 = 4$	1	2	3	4	1
$a_5 = 1$	1	1	1	1	1

这样就可以得出我们应该输出

10，6，4，2

我们可以按照$a_i$由大到小地填充b表格，每次填充$a_i$对应的行和列，并且直接覆盖之前填充好的数据，最终就能得出b数组。


可以发现，大数会被更小的数”蚕食“
以3为例，起初3占满了所有行和列，但由于有更小的数1和2，在填充1和2时，1，2数字所在的行列（1,2,5)都被覆盖掉了。导致只剩下第3，4行存在3。因此面积最小应该为2x2 ，输出4。

由此推广出来，一个数$x$会这些行留下自己的身影：$i,(x \le a_i)$, 因此对于任何一个数x，我们只需要找到 区间$[l,r]$ 使得对于任意的 $a_i >= x$ 都有$l \le i \le r$ 。 也就是 $[l,r]$涵盖了所有的大于等于x的数，此时这个最小矩阵的边长就是undefinedr-l+1)$,需要输出$2*(l-r+1)$ 。

特判：当一个数在a中不存在时，需要输出0。

代码

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int t ;
    cin>>t;
    while(t--){
        int n,k;
        scanf("%d %d",&n,&k);
        vector<bool> isok(k+5);//记录某个数是否出现过，请注意这里的数组大小应该是k而不是n 
        vector<int> v(n+5);//原始数据
        vector<int> qz(n+5);//前缀, qz[i]表示前i个数中的最大值
        vector<int> hz(n+5);//后缀，hz[i]表示后i个数中的最大值
        for(int i = 1;i<=n;i++){
            scanf("%d",&v[i]);
            isok[v[i]] = true;
        }
        qz[0] = hz[n+1] = 0;
        for(int i = 1;i<=n;i++){
            qz[i] = max(qz[i-1],v[i]);
        }
        for(int i = n;i>=1;i--){
            hz[i] = max(hz[i+1],v[i]);
        }
        int l = 1,r = n;
        for(int i = 1;i<=k;i++){
            if(!isok[i]) {cout<<0<<" ";continue;}
            while(qz[l]<i) l++;//跳过所有小于i的值
            while(hz[r]<i) r--;
            cout<<(r-l+1)*2<<" ";
        }
        puts("");
    }
    return 0;
}

D - Prefix Purchase

题意

给出一个n个数的数组a. 起初 $a_1 = a_2 =...= a_n = 0$ ,再给出一个n个数的数组c, 现在你手上有k个金币，可以进行如下操作任意次：
从数组c中选择一个数$c_i$ ，花费 $c_i$个金币，使得数组a的前i项加一，即 $a_j+=1,(1\le j \le i)$

问如何操作才能使得最终的数组a 的字典序尽可能大。

思路

首先我们知道，选择越靠后，他的“价值”就越高。因此如果存在 $c_i \ge c_j 且 i < j$ ，那么选择$c_j$ 就一定优于 $c_i$ ,因此我们可以将这种情况下的$c_i$ 的值改为$c_j$ 。在这种操作之后，我们会得到一个单调递增的c数组。 之后进行如下操作
首先尽可能地购买$c_1$ ，此时可能手上剩余一些钱（设为left），由于越靠后”价值“越高，所以我们可以继续花费left来升级（升级指的就是 将一部分$c_i$ 变为$c_{i+1}$ ， 显而易见，我们应当尽可能地花费剩余的钱去升级。因此有如下递推式 $a_i = min(a_{i-1},\frac{left}{c_i - c_{i-1}})$ 。

最终得到的a数组就是我们所需要的a数组

代码

#include<iostream>
#include<vector>
using namespace std;
void solve(){
    int n;
    scanf("%d",&n);
    vector<int> c(n+5);//c数组
    for(int i = 1;i<=n;i++){
        scanf("%d",&c[i]);
    }
    int k;
    scanf("%d",&k);//k
    //对c数组进行预处理
    int mn = 1e9;
    for(int i = n;i>=1;i--){
        mn = min(mn,c[i]);
        c[i] = mn;
    }
    vector<int> a(n+5);//a数组
    a[1] = k / c[1];
    int left = k % c[1];
    for(int i = 2;i<=n;i++){//递推
        int cha = c[i] - c[i-1];
        if(cha == 0){
            a[i] = a[i-1];
            continue;
        }
        a[i] = min(a[i-1],left/cha);
        left -= cha * a[i];
    }
    for(int i = 1;i<=n;i++){
        printf("%d%c",a[i]," \n"[i==n]);
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}