2021ICPC网络赛（第二场）_yezzz的博客

2021ICPC网络赛（第二场）

H.

分析：

• 两个条件:

  • 任意 r r r 个的并集 > = 128 >=128 >=128
  • 每一个构造的集合长度 < = ∣ 512 r ∣ <=|\frac{512}{r}| <=∣r512​∣（向上取整）

• 构造方法：将 256 256 256 拆分成 k k k 段， d = 256 / k d=256/k d=256/k

  每 d d d 段长度设置起点 s t st st ，在接下来的长度 l e n len len 用 1 1 1 去覆盖

• 大坑点： 256 % k 256\%k 256%k 的多余的部分不能全部留给最后一段，要均分（每段最多分到 1 1 1 ），所以 s t st st 和 l e n len len 都还要判断一下

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

using namespace std;

signed main()
{
    int k,r;
    cin>>k>>r;
    int len=ceil(512/r), d=256/k;
    if(2*(r-1)*k+4*r<k*r)
    {
        cout<<"-1"<<endl; return 0;
    }
    int st=0, yu=256%k;
    for(int i=1;i<=k;i++)
    {
        int t=len;
        if(yu) t++;
        for(int j=1;j<=256;j++)
        {
            if((j>st || 256-st+j<=t) && t)
            {
                cout<<"1"; t--;
            }
            else cout<<"0";
        }
        cout<<endl;
        st+=d;
        if(yu) { st++; yu--; }
    }
    return 0;
}

M.

分析：

• 从最低位到高位，依次相加减，分类讨论进位的多种情况

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
int p[N], a[N], b[N], c[N];
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    int fp=0; // 表示进位
    for(int i=1;i<=n;i++)
    {
        fp*=p[i]; // 进位加到当前位，同号相加，不变，异号相减
        int t=a[i]+b[i]+fp;
        if(t==0 || t==1) { c[i]=t; fp=0; }
        else if(t==-1) { c[i]=1; fp=-1; }
        else if(t==2) { c[i]=0; fp=1; }
        else if(t==3) { c[i]=1; fp=1; }
        fp*=p[i]; // 当前位进到下一位，若当前的 sgn 是 -1 那进到下一位还要取反
    }
    for(int i=1;i<n;i++) cout<<c[i]<<' ';
    cout<<c[n]<<endl;
    return 0;
}