题解 CF1476 A&B&D

如果写错了求求不要 $\text{hack}$ 啊呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜

云浅太菜啦/kel，只做了ABD/kel

珂能更好的阅读体验

$\mathbf{A.}\ \ \text{K-divisible Sum}$

Description

题目 Link

• 给两个正整数 $n,k$
• 要求构造一个长为 $n$ 的正整数数列 $A$ 使得 $k\left|\left(\sum\limits_{i=1}^nA_i\right)\right.$，且使得 $\max\limits_{1\le i\le n}A_i$ 最小，输出 $\max\limits_{1\le i\le n}A_i$。
• $1\le n,k\le 10^9$
• $t$ 组数据， $1\le t\le 10^4$

Solution

首先考虑一下这个数列中所有数之和最小值，显然是 $\forall i,A_i=1$ 的情况，即 $\sum\limits_{i=1}^nA_i$ 最小为 $n$。

最大肯定是可以想搞多大搞多大的qwq

然后显然若 $x\ge n$ 且 $x\in \mathbb N_+$，那么必定可以构造出长为 $n$ 的正整数数列使得这个数列中所有数的和为 $x$。

那么分类一下：

如果 $n<k$，那么肯定可以构造出数列 $A$ 使得 $\sum\limits_{i=1}^nA_i=k$。

然后让最大值最小，那其实就是差不多让这个数列中的数平均一点嘛qwq。

那最大值就是 $\left\lceil\dfrac{k}{n}\right\rceil$。

如果 $n>k$，当 $k|n$ 时，直接放 $n$ 个 $1$ 即可。

当 $k\nmid n$ 时，考虑放 $k-(n\mod k)$ 个 $2$，剩下的全放 $1$，此时有 $\sum\limits_{i=1}^nA_i=\left\lceil\dfrac{n}{k}\right\rceil\cdot k$，能被 $k$ 整除。

不难证明 $2$ 就是此时的最优解。所以直接输出 $2$。

PS：其实 $n>k$ 时还可以把 $k$ 直接硬改成 $k_2=n+(n\mod k)$，然后 $n<k_2$，转回第一种情况qwq。

总之这题方法挺多的，总之这题比较水qwq。

Code：

#include<cstdio>
#include<cstdlib>
#include<cstring>

using namespace std;

int n,k;
int T;

int ceill(int a,int b){
    if(a%b==0){
        return a/b;
    }
    else return (int)(a/b)+1;
}

int main(void){

    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        if(n<=k){
            printf("%d\n",ceill(k,n));
        }
        else{
            if(n%k==0)printf("%d\n",1);
            else{
                printf("%d\n",2);
            }
        }
    }

    return 0;
}

$\mathbf{B.}\ \ \text{Inflation}$

Description

题目 Link

• 给 $n$ 个数 $p_1,p_2,\cdots,p_{n}$ 和一个数 $k$
• 你可以把任意的 $p_i$ 加上任意正整数 $x$
• 操作完之后必须满足 $\forall i=2,3,\cdots,n,$ 有 $\dfrac{p_i}{p_1+p_2+\cdots+p_{i-1}}\le\dfrac{k}{100}$
• 要求求出最小的给这些数加上的值。
• $2\le n\le 100,1\le k\le 100$
• $t$ 组数据，$1\le t\le 10^4$

Solution

珂以二分，也可以贪心qwq

这里讲一下贪心的做法w

首先很好想到的是维护一下前缀和 $S_i=\sum\limits_{j=1}^ip_i$，那么此时就是要求 $\dfrac{p_i}{S_{i-1}}\le\dfrac{k}{100}$。

（为了避免精度问题和一堆奇奇怪怪的问题，我们在这里把它化简成 $100p_i\le k\cdot S_{i-1}$。）

然后我们从前往后扫一遍整个序列 $p$，如果发现有不满足条件的，容易发现此时给第一个数加上尽可能大的值是一个很好的方案。

其实感性证明/理解一下就是：若 $\exists p_i,100p_i> k\cdot S_{i-1}$，那我们必须把 $S_{i-1}$ 变得更大一些，也就是把前 $i-1$ 个数增大。

然后如果增大的不是第一个的话，如果我们增大了 $p_a$，很有可能我们增大的那个 $p_a$ 又会太大以至于 $100p_a> k\cdot S_{a-1}$，不满足要求=_=

而综合来看，只有我们增大 $p_1$ 之后，才绝对不会产生任何负面影响qwq。

严格的证明根据这个思路基本也能证，这里就说一下思路吧w。

那所以我们每次发现一个不满足要求的 $p_i$，直接改第一个即可。

需要增加的值也不难算，就是 $\left\lceil\dfrac{100p_i}{k}\right\rceil-S_{i-1}$。

然后这里我还闲着没事维护了一个树状数组来单点修改查询前缀和，吃了点罚时（草云浅为啥这么菜脑子还这么抽啊）

Code：

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define int long long
#define MAXN 105

using namespace std;

int t;
int n,k;
int a[MAXN];
int s[MAXN];

bool cmp(int a,int b,int kqwq){
    return kqwq*a>=100*b;
}

struct BIT{

    int c[MAXN<<2];

    inline int lowbit(int x){
        return x&(-x);
    }

    inline void PreFix(){
        memset(c,0,sizeof(c));
    }

    inline void modify(int x,int k){
        for(int i=x;i<=n;i+=lowbit(i)){
            c[i]+=k;
        }
    }

    inline int query(int x){
        int ans=0;
        for(int i=x;i;i-=lowbit(i)){
            ans+=c[i];
        }
        return ans;
    }

};

BIT tree;

int ceill(int a,int b){
    if(a%b==0){
        return a/b;
    }
    else return (int)(a/b)+1;
}

signed main(void){

    scanf("%lld",&t);
    while(t--){
        tree.PreFix();
        int ansqwq=0;
        scanf("%lld%lld",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            tree.modify(i,a[i]);
        }
        for(int i=2;i<=n;i++){
            int sum=tree.query(i-1);
            if(!cmp(sum,a[i],k)){
                tree.modify(1,ceill(100*a[i],k)-sum);
                ansqwq+=ceill(100*a[i],k)-sum;
            }
        }
        printf("%lld\n",ansqwq);
    }

    return 0;
}

$\mathbf{D.}\ \ \text{Journey}$

啊啊啊好想鸽子啊咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕

简要提一下思路吧，明早下午起来再补完整题解qwq

首先有个结论：不难发现让 $\text{RLRLRLRLRL}\dots$ 这样交替出现下去是可以一直走下去并且完美返回的w

然后一旦断掉了，就比如 $\text{RLRLRLL}$，那么就必然不能再往后走了。

于是问题就变成了：对于每一个 $i$，求出 $\texttt{str[i]}$ 左边最长的、连续的、交替往复出现的 $\text{R}$ 和 $\text{L}$ 长度，右边同理。然后把左右长度加起来再加一（自己也算一个）即可。

暴力求解是 $O(n^2)$ 的。

然而 $n$ 总和为 $3e5$ ，被分成 $1e4$ 份的话每份应该挺小的，那平方一下也不会很大qwq

再加上 $2s$ 时限，而且这个算法实际效率应该比 $n^2$ 快很多，所以云浅当时其实想过直接暴力卡常艹过去（

不过后来在神仙劝阻/指导下还是搞了正解qwq

就是这个东西其实是可以预处理的qwq

以预处理左边为例：令 $\texttt{pre[i]}$ 为 $\texttt{str[i]}$ 左边最长的、连续的、交替往复出现的 $\text{R}$ 和 $\text{L}$ 的长度。

由于是向左，所以其实最后在 $\texttt{str[i]}$ 左边那个字符必须是 $\text{L}$，不然动不了=_=

然后搞一通：

int qwq=0;
for(int i=1;i<=n;i++){
    qwq+=(str[i]!=str[i-1]);
    if(str[i]==str[i-1])qwq=1;
    
    if(str[i]=='L')pre[i]=qwq;
    else pre[i]=0;
}

基本上就预处理完了。

右边的话其实差不多，只不过注意要把 $\texttt{suf[n]=0}$ 初始化带上，再注意亿点点细节即可。

啊睡大觉去了QAQ，去梦里和珂珂酱贴贴了qwq