Educational Codeforces Round 71 (Rated for Div. 2) Solution

题意：

给一些面包，鸡肉，牛肉，你可以做成鸡肉汉堡或者牛肉汉堡并卖掉

一个鸡肉汉堡需要两个面包和一个鸡肉，牛肉汉堡需要两个面包和一个牛肉

求能得到的最多的钱

直接贪心，哪个比较贵就选哪个做，剩下的材料再做另一个

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e5+;

int T,n,a,b,va,vb;

int main()

{

    T=read();

    while(T--)

    {

        n=read(),a=read(),b=read();

        va=read(),vb=read();

        if(va>vb) { int t=min(a,n/); printf("%d\n",va*t+vb*min(b,(n-t*)/)); }

        else { int t=min(b,n/); printf("%d\n",vb*t+va*min(a,(n-t*)/)); }

    }

    return ;

}

B. Square Filling

题意：

给一个矩阵，求把一个空矩阵进行一些操作后能否得到给定矩阵

操作为选择一个 $2*2$ 的子矩阵并把里面的数全部变成 $1$，不要求最少次数，如果能则输出具体操作

显然枚举所有左上角看看能不能操作，能的话就尽量操作

最后判断一下是否得到给定矩阵就行了

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=;

int n,m,a[N][N],b[N][N];

vector <int> X,Y;

int main()

{

    n=read(),m=read();

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++) a[i][j]=read();

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

        {

            if(a[i][j]&&a[i+][j]&&a[i][j+]&&a[i+][j+])

            {

                X.push_back(i); Y.push_back(j);

                b[i][j]=b[i+][j]=b[i][j+]=b[i+][j+]=;

            }

        }

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++) if(a[i][j]&&!b[i][j]) { printf("-1\n"); return ; }

    int ans=X.size(); printf("%d\n",ans);

    for(int i=;i<ans;i++) printf("%d %d\n",X[i],Y[i]);

    return ;

}

C. Gas Pipeline

题意：

铺水管，需要支柱和管道，各有价格，从 $0$ 铺到 $n$ 求最小花费

管道高度可以为 $1$ 或 $2$，高度为 $1$ 时只要一个支柱，为 $2$ 时要两个，管道高度变化的时候要格外一个管道

某些位置强制管道高度为 $2$

显然考虑 $dp$，设 $f[i][0/1]$ 当前铺到位置 $i$ ，高度为 $1,2$ 时的最小花费，转移显然，具体看代码，注意$long\ long$

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e5+;

const ll INF=1e18;

int T,n,va,vb;

char s[N];

ll f[N][];

int main()

{

    T=read();

    while(T--)

    {

        n=read(),va=read(),vb=read();

        scanf("%s",s+);

        f[][]=vb; f[][]=INF;//初始高度必须为1

        for(int i=;i<=n;i++)

        {

            f[i][]=min(f[i-][]+va+vb,f[i-][]+va*+vb);

            f[i][]=min(f[i-][]+va*+vb*,f[i-][]+va+vb*);

            if(s[i]==''||s[i+]=='') f[i][]=INF;

        }

        printf("%lld\n",f[n][]);

    }

    return ;

}

D. Number Of Permutations

题意：

给一个数列 $a$ ，求合法排列方案数，不合法指 $a$ 的某一排列中某一维单调不减

见计数想容斥

先考虑一个很 $naive$ 的东西，给一个数列求单调不减的排列数，值同样的数也看成不同的

显然每个值互相之间不能交换，只能同一个值之间乱换，同一个值的贡献就是这个值的所有数全排列，整个数列的答案就是每个值贡献乘法原理乘起来

回到原问题，数列变成两维了，感觉合法不好求，考虑求出不合法的方案

显然答案就是：全排列方案数减强制一个不合法方案数加两个都不合法方案数，然后就变成求单调不减的排列数了

两个都不合法的方案数也很好求，具体看代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=6e5+,mo=;

int n;

ll fac[N],ans;

struct dat{

    int a,b;

}d[N];

inline bool cmp1(const dat &A,const dat &B) { return A.a!=B.a ? A.a<B.a : A.b<B.b; }

inline bool cmp2(const dat &A,const dat &B) { return A.b!=B.b ? A.b<B.b : A.a<B.a; }

int main()

{

    n=read();

    fac[]=; for(int i=;i<=n;i++) d[i].a=read(),d[i].b=read(),fac[i]=fac[i-]*i%mo;

    ans=fac[n];//全排列

    sort(d+,d+n+,cmp1); ll t=; int cnt=;

    for(int i=;i<=n;i++)

    {

        if(i==||d[i].a==d[i-].a) cnt++;

        else t=t*fac[cnt]%mo,cnt=;

    }

    t=t*fac[cnt]%mo;

    ans-=t;//第一维不合法

    sort(d+,d+n+,cmp2); t=; cnt=;

    for(int i=;i<=n;i++)

    {

        if(i==||d[i].b==d[i-].b) cnt++;

        else t=t*fac[cnt]%mo,cnt=;

    }

    t=t*fac[cnt]%mo;

    ans-=t;/*第二维不合法*/ t=; cnt=;

    for(int i=;i<=n;i++)

    {

        if(i==||(d[i].a==d[i-].a&&d[i].b==d[i-].b)) cnt++;

        else t=t*fac[cnt]%mo,cnt=;

        if(i!=&&d[i].a<d[i-].a) t=;//注意可能不存在两维同时不减的情况

    }

    t=t*fac[cnt]%mo;

    ans+=t;//两维都不合法

    printf("%lld\n",(ans%mo+mo)%mo);

    return ;

}

E. XOR Guessing

人生第一道交互题 $2333$

让你猜一个 $[0,2^{14}-1]$ 的数，你只能询问两次，每次你给出 $100$ 个数，系统会在你给的 $100$ 个数里面随便找一个值 $v$ 并返回答案与 $v$ 的异或值

要如何通过两次询问确定这个答案，询问时你给出的所有数必须互不相同

考虑一下如果能全给出 $0$ ，那么答案很显然，这样问一次就够了

考虑先确定答案二进制下的前半段，那么我们只要给出 $100$ 个二进制下高的 $7$ 位全为 $0$ 的数，不论系统返回什么值，高位的 $7$ 位就一定能确定

然后我们再问低位的 $7$ 位，同样给出 $100$ 个二进制下低的 $7$ 位全为 $0$ 的数即可

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

int ans;

int main()

{

    cout<<"? ";

    for(int i=;i<=;i++)cout<<i<<" "; cout<<<<endl;

    int t; cin>>t;

    ans=t>>;

    cout<<"? ";

    for(int i=;i<=;i++) cout<<(i<<)<<" "; cout<<(<<)<<endl;

    int res; cin>>res;

    ans=(ans<<)|(res ^ ((res>>)<<) );

    cout<<"! "<<ans<<endl;

    return ;

}

F. Remainder Problem

题意：

给一个长度为 $5*10^5$ 的数列，初始全为 $0$，进行不超过 $5*10^5$ 次询问

把某个位置值加上一个数，或者询问所有位置模 $x$ 意义下等于 $y$ 的位置的数值之和

发现如果 $x$ 一直很大，那么我们直接暴力枚举即可，如果 $x$ 一直很小，我们只要随便开个二维数组维护一下就行

考虑分类讨论一下，把询问分成大的和小的，大的就暴力枚举，小的就从二维数组里面查询

分界点取 $\sqrt {n}$ 或者某个差不多的数即可，复杂度 $O(n \sqrt {n})$

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=5e5,M=;

int n;

ll A[N+],sum[M+][M+];

int main()

{

    n=read(); int opt,a,b;

    for(int i=;i<=n;i++)

    {

        opt=read(),a=read(),b=read();

        if(opt==)

        {

            A[a]+=b;

            for(int i=;i<=M;i++) sum[i][a%i]+=b;

        }

        if(opt==)

        {

            if(a>M)

            {

                ll ans=;

                for(int i=b;i<=N;i+=a) ans+=A[i];

                printf("%lld\n",ans);

            }

            else printf("%lld\n",sum[a][b]);

        }

    }

    return ;

}

G. Indie Album

比赛的时候竟然没看出来 $woc$，[NOI2011]阿狸的打字机了解一下，差不多的做法

佛了

巴特西

Educational Codeforces Round 71 (Rated for Div. 2) Solution

最新文章

热门文章