2021ICPC網路賽（第二場）

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;
}