Educational Codeforces Round 71 题解

题解 比赛-Codeforces
题目链接 编辑文章

这是赛后做的。珍爱生命,远离edu

A.There Are Two Types Of Burgers

题意

在你的餐厅里有两种汉堡:牛肉汉堡和鸡肉汉堡。每个牛肉汉堡需要 $2$ 片面包和 $1$ 片牛肉,一个鸡肉汉堡需要 $2$ 片面包和 $1$ 个鸡排。一个牛肉汉堡卖 $h$ 元,一个鸡肉汉堡卖 $c$ 元。你有 $b$ 片面包,$p$ 片牛肉和 $f$ 块鸡排。求最大收益。

所有数据 $\le 100$ 。

题解

水题,优先卖贵的,模拟即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int t,b,p,f,h,c;

signed main()
{
    t=read();
    while (t--)
    {
        b=read(); p=read(); f=read(); h=read(); c=read();
        if (h<c) swap(h,c),swap(p,f);
        b>>=1;
        if (b<=p) printf("%d\n",b*h);
        else if (b<=p+f) printf("%d\n",p*h+(b-p)*c);
        else printf("%d\n",p*h+f*c);
    }
    return 0;
}

B.Square Filling

题意

有一个 $N\times M$ 的全零矩阵,每次可以把 $2\times 2$ 的矩阵变成 $1$ 。要求变成目标矩阵,不要求最小化步骤,求操作序列。如果无解输出 $-1$ 。

$N,M\le 50$ 。

题解

枚举所有格点,如果目标矩阵中的小矩阵全为 $1$ 就把它染了。最后如果还有没染的就无解。

#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,m;
vector <pr> v;
bool s[55][55],t[55][55];

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) t[i][j]=read();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            bool flag=1;
            for (int k=i;k<=i+1;k++) for (int l=j;l<=j+1;l++) flag&=t[k][l]==1;
            if (!flag) continue;
            v.emplace_back(mp(i,j));
            for (int k=i;k<=i+1;k++) for (int l=j;l<=j+1;l++) s[k][l]=1;
        }
    }
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (s[i][j]!=t[i][j]) return 0&puts("-1");
    printf("%lu\n",v.size());
    for (auto i:v) printf("%d %d\n",i.first,i.second);
    return 0;
}

C.Gas Pipeline

题意

要修建一段天然气管道,高度至少为 $1$ ,如果遇到道路高度必须为 $2$ 。管道的价格为每单位 $a$ 元,柱子的价格为每单位 $b$ 元。求最小花费。

管道长度 $N\le 10^5$ ,多组数据,组数 $T\le 100$ 。

题解

用 $f[i][0/1]$ 表示当前要修第 $i$ 段管道,当前高度为 $1/2$ 时的最少花费。方程式看代码吧。

注意起点和终点的高度必须为 $1$ 。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

char s[200005];
ll t,n,a,b,f[200005][2];

signed main()
{
    t=read();
    while (t--)
    {
        n=read(); a=read(); b=read();
        scanf("%s",s+1);
        f[0][0]=b; f[0][1]=1e18;
        for (ll i=1;i<=n;i++)
        {
            if (s[i]=='1')
            {
                f[i][0]=1e18;
                f[i][1]=min(f[i-1][0]+((a+b)<<1)+b,f[i-1][1]+a+(b<<1));
            }
            else
            {
                f[i][0]=min(f[i-1][0]+a+b,f[i-1][1]+(a<<1)+b);
                f[i][1]=min(f[i-1][0]+((a+b)<<1),f[i-1][1]+a+(b<<1));
            }
        }
        printf("%lld\n",f[n][0]);
    }
    return 0;
}

D.Number Of Permutations

题意

有一个长度为 $N$ 的 pair 序列。如果 first 元素单调不降,或 second 元素单调不降,就称这个序列为坏序列,否则为好序列。求序列的所有排列中好序列的个数。

$N\le 3\times 10^5$ 。

题解

根据条件没法直接算出好序列,所以考虑容斥。设 $A$ 表示 first 单调不降的序列个数;$B$ 代表 second ,则

$$ans=N^2-A-B+(A \& B)$$

考虑算 $A$ ,显然相同的数可以交换位置,设数字 $i$ 的个数为 $cnt[i]$ ,则

$$A=\prod cnt[i]!$$

$B$ 同理。

然后算 $A\& B$ 。先考虑无解的情况,按 first 为第一关键字,second 为第二关键字从小到大排序,如果存在 $second[i]>second[i+1]$ 就无解。

否则至少有 $1$ 个解,用 map 统计相同 pair 的个数,然后按照上面的f方法计算即可。

#include<bits/stdc++.h>
#define ha 998244353
#define pr pair<int,int>
#define mp make_pair

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=300005;
pr s[N];
map <pr,int> m;
int n,cnt1[N],cnt2[N],fac[N];

signed main()
{
    n=read();
    int mx=0; fac[0]=1;
    for (int i=1;i<=n;i++)
    {
        s[i].first=read(); s[i].second=read();
        mx=max(mx,max(s[i].first,s[i].second));
        fac[i]=1ll*fac[i-1]*i%ha;
        cnt1[s[i].first]++;
        cnt2[s[i].second]++;
        m[s[i]]++;
    }
    int ans1=1,ans2=1,ans3=0;
    for (int i=1;i<=mx;i++)
    {
        if (cnt1[i]) ans1=1ll*ans1*fac[cnt1[i]]%ha;
        if (cnt2[i]) ans2=1ll*ans2*fac[cnt2[i]]%ha;
    }
    sort(s+1,s+n+1);
    for (int i=1;i<n;i++) if (s[i].second>s[i+1].second) goto output;
    ans3=1;
    for (auto i:m) ans3=1ll*ans3*fac[i.second]%ha;
    output:
    return !printf("%d",(((fac[n]-ans1+ha)%ha-ans2+ha)%ha+ans3)%ha);
}

E.XOR Guessing

题意

要求猜出一个 $[0,2^{14}-1]$ 的数 $x$,可以进行两次询问,格式为

$$? \ a_1,a_2,...,a_{100}$$

程序会从中选出任意一个数,并返回 $a_i \ \mathrm{xor} \ x$ 。最后要求输出 $x$ 。

题解

构造两组数,分别使得二进制前 $7$ 位为 $0$ 、后 $7$ 位为 $0$ ,然后对返回的两个数分别取前 $7$ 位和后 $7$ 位即为答案。

#include<bits/stdc++.h>

using namespace std;

int c,d;

signed main()
{
    cout<<"? ";
    for (int i=1;i<=100;i++) cout<<i<<" ";
    cout<<"\n";
    fflush(stdout);
    cin>>c;
    cout<<"? ";
    for (int i=1;i<=100;i++) cout<<(i<<7)<<" ";
    cout<<"\n";
    fflush(stdout);
    cin>>d;
    return !printf("! %d",(((c^d)>>7)<<7)^d);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空