Codeforces Round #574 (Div. 2) A~E Solution

ゞ浴缸里的玫瑰 2021-10-14 16:51 256阅读 0赞

[A. Drinks Choosing][]

有 $n$ 个人，每个人各有一种最喜欢的饮料，但是买饮料的时候只能同一种的两个两个买(两个一对)

学校只打算卖 $\\left \\lceil \\frac\{n\}\{2\} \\right \\rceil$ 对

这意味着有些学生喝不到最喜欢的饮料，求最多有多少学生能喝的最喜欢的饮料

人数和饮料种数均小于等于 $1000$

直接贪心，对于喜欢同一种饮料的学生中，如果人数为奇数，要么单独买一对，然后把另一个给不喜欢这种饮料的人

要么喝自己不喜欢的饮料，设喜欢某种饮料的学生人数为奇数的饮料种数为 $x$，那么显然答案就是 $\\left \\lfloor \\frac\{x\}\{2\} \\right \\rfloor$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<map>
    using namespace std;
    typedef long long ll;
    typedef long double ldb;
    inline int read()
    {
        int x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
        return x*f;
    }
    const int N=1e5+7;
    int n,k,a[N],cnt[N],ans;
    int main()
    {
        n=read(),k=read();
        for(int i=1;i<=n;i++) a[i]=read(),cnt[a[i]]++;
        for(int i=1;i<=k;i++)
            if(cnt[i]&1) ans++;
        printf("%d\n",n-ans/2);
    }

A. Drinks Choosing

[B. Sport Mafia][]

有个人，进行了 $n$ 此操作，每次操作分为两种，放一些糖到盒子里，并且放的数量比上一次多 $1$，或者如果盒子有糖也可以选择从盒子里拿一个糖吃掉

第一次操作固定是往盒子里放一个糖，已知操作次数 $n$ 和最后剩下的糖的数量 $k$

求 $ta$ 吃的糖数量，保证有解

直接设进行了 $x$ 次 $1$ 操作，那么剩下的操作都是吃糖，所以可以列出方程

$x(x+1)/2=k+(n-x)$

解一下方程答案的公式就出来了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<map>
    using namespace std;
    typedef long long ll;
    typedef long double ldb;
    inline int read()
    {
        int x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
        return x*f;
    }
    ll n,k;
    int main()
    {
        n=read(),k=read();
        // p*(p+1)/2=k+n-p
        // p^2+p=2k+2n-2p
        // p^2+3p-(2k+2n)=0
        // 9+8(n+k)
        // (-3+sqrt(8(n+k)+9))/2
        ll p=(sqrt((n+k)*8+9)-3)/2;
        printf("%lld\n",p*(p+1)/2-k);
        return 0;
    }

B. Sport Mafia

[ ][Link 1]

[C. Basketball Exercise][Link 1]

两排长度为 $n$ 的数 $A,B$，从左到右每次可以选择 $A,B$ 中的一个或者不选，对于同一排不能选择相邻的数，求能得到的最大值

显然设 $F\[i\]\[0/1\]$ 表示从左到右选到第 $i$ 个位置，当前位置选择的数是 $A/B$，转移显然，具体看代码

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<map>
    using namespace std;
    typedef long long ll;
    typedef long double ldb;
    inline int read()
    {
        int x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
        return x*f;
    }
    const int N=1e6+7;
    int n,a[N][2];
    ll f[N][2];
    int main()
    {
        n=read();
        for(int i=1;i<=n;i++) a[i][0]=read();
        for(int i=1;i<=n;i++) a[i][1]=read();
        f[1][0]=a[1][0]; f[1][1]=a[1][1];
        for(int i=2;i<=n;i++)
        {
            f[i][0]=max(f[i-1][1]+a[i][0],f[i-1][0]);
            f[i][1]=max(f[i-1][0]+a[i][1],f[i-1][1]);
        }
        printf("%lld\n",max(f[n][0],f[n][1]));
        return 0;
    }

C. Basketball Exercise

[D1. Submarine in the Rybinsk Sea (easy edition)][D1. Submarine in the Rybinsk Sea _easy edition]

对于两个数 $A,B$，它们从左到右每一位分别是 $A\[1\]A\[2\]...A\[m\],B\[1\]B\[2\]B\[m\]$

定义函数 $F(A,B)$ 表示把两个数错位插在一起的结果，即 $A\[1\]B\[1\]...A\[m-1\]B\[m-1\]A\[m\]B\[m\]$

（具体例子看原题面）

给定数列 $a\[\]$，求 $\\sum\_i\\sum\_jF(a\[i\],a\[j\])$，保证数列中每个数的长度相等

考虑每一个数对答案的贡献，发现当它(设为 $C$)被 $i$ 枚举到时的贡献总是 $C\[1\]0C\[2\]0C\[3\]0...C\[m\]0$，被 $j$ 枚举到时的贡献总是 $C\[1\]0C\[2\]...0C\[m\]$

显然被 $i,j$ 枚举到的次数都为 $n$，所以贡献可以一起算

具体操作起来写个函数把数转化一下就行了，我的写法要注意 $unsigned\\ long\\ long$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

D1. Submarine in the Rybinsk Sea (easy edition)

[D2. Submarine in the Rybinsk Sea (hard edition)][D2. Submarine in the Rybinsk Sea _hard edition]

题目同上，唯一的区别就是数列 $a\[\]$ 中每个数的长度不一定相等

同样考虑每个数的贡献，发现一个数 $C$ 被 $i$ 枚举到时的贡献只和此时被 $j$ 枚举到的数的长度有关，被 $j$ 枚举到时的贡献也同理

所以记录一下长度为 $k$ 的数有多少个，把相同的贡献一起计算就好了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<map>
    using namespace std;
    typedef unsigned long long ll;
    typedef long double ldb;
    inline int read()
    {
        int x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
        return x*f;
    }
    const int N=1e6+7,mo=998244353;
    ll n,a[N],f[27],ans;
    int p[27],cnt[27];
    int Len(ll x) { int res=0; while(x) res++,x/=10; return res; }
    ll F(ll x,int type,int num)
    {
        int len=0; for(ll t=x;t;t/=10) p[++len]=t%10;
        ll res=0;
        for(int i=1;i<=min(len,num);i++) res+=p[i]*f[i*2+type];
        for(int i=num+1;i<=len;i++) res+=p[i]*f[num+i];
    //    cout<<x<<" "<<num<<" "<<res<<endl;
        return res%mo;
    }
    int main()
    {
        n=read();
        for(int i=1;i<=n;i++) a[i]=read();
        f[1]=1; for(int i=2;i<=20;i++) f[i]=f[i-1]*10;
        for(int i=1;i<=n;i++) cnt[Len(a[i])]++;
        for(int i=1;i<=n;i++)
        {
    //        cout<<a[i]<<endl;
    //        for(int j=1;j<=10;j++) F(a[i],0,j);
    //        for(int j=1;j<=10;j++) F(a[i],-1,j);
            for(int j=1;j<=10;j++) ans=(ans+F(a[i],0,j)*cnt[j]%mo)%mo;
            for(int j=1;j<=10;j++) ans=(ans+F(a[i],-1,j)*cnt[j]%mo)%mo;
        }
        printf("%lld\n",ans);
        return 0;
    }

D2. Submarine in the Rybinsk Sea (hard edition)

[E. OpenStreetMap][]

给一个 $n\*m$ 的矩阵，求其中所有 $a\*b$ 的子矩阵的元素最小值之和

$n,m<=1000$

和这一题同样的思路：[\[HAOI2007\]理想的正方形][HAOI2007]

直接单调队列横着竖着扫一遍就好了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<map>
    using namespace std;
    typedef unsigned long long ll;
    typedef long double ldb;
    inline int read()
    {
        int x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
        return x*f;
    }
    const int N=3007;
    int n,m,a,b,h[N][N];
    int F[N][N],G[N][N],Q[N];
    ll g[N*N],x,y,z,ans;
    int main()
    {
        n=read(),m=read(),a=read(),b=read();
        int tot=0;
        g[0]=read(),x=read(),y=read(),z=read();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                h[i][j]=g[tot];
                tot++; g[tot]=(g[tot-1]*x+y)%z;
            }
        for(int i=1;i<=n;i++)
        {
            int L=1,R=0;
            for(int j=1;j<=m;j++)
            {
                while(L<=R&&Q[L]<=j-b ) L++;
                while(L<=R&&h[i][j]<=h[i][Q[R]]) R--;
                Q[++R]=j; F[i][j]=h[i][Q[L]];
    //            cout<<F[i][j]<<" ";
            }
        }
        for(int j=1;j<=m;j++)
        {
            int L=1,R=0;
            for(int i=1;i<=n;i++)
            {
                while(L<=R&&Q[L]<=i-a) L++;
                while(L<=R&&F[i][j]<=F[Q[R]][j]) R--;
                Q[++R]=i; G[i][j]=F[Q[L]][j];
    //            cout<<G[i][j]<<" ";
                if(i>=a&&j>=b) ans+=G[i][j];
            }
        }
        printf("%lld\n",ans);
        return 0;
    }

E - OpenStreetMap

转载于:https://www.cnblogs.com/LLTYYC/p/11285801.html

[A. Drinks Choosing]: http://codeforces.com/contest/1195/problem/A
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211015/8c348d88bf44443e8dea4b62bb112a47.png
[B. Sport Mafia]: http://codeforces.com/contest/1195/problem/B
[Link 1]: http://codeforces.com/contest/1195/problem/C
[D1. Submarine in the Rybinsk Sea _easy edition]: http://codeforces.com/contest/1195/problem/D1
[D2. Submarine in the Rybinsk Sea _hard edition]: http://codeforces.com/contest/1195/problem/D2
[E. OpenStreetMap]: http://codeforces.com/contest/1195/problem/E
[HAOI2007]: https://www.luogu.org/problem/P2216