乐趣区

关于acm:XCPC真题1Bits-Reverse-Empty-Squares-Wall-Painting

jiezi

🎈 作者：Eriktse
🎈 简介：19 岁，211 计算机在读，现役 ACM 银牌选手🏆力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换 C ++/Python 算法。（优质好文继续更新中……）🚀
🎈 浏览原文取得更好浏览体验：https://www.eriktse.com/algorithm/1147.html

A. Bits Reverse

题目链接：https://codeforces.com/gym/102823/problem/D

题意

给定两个数字 x 和y，当初有一种操作：将 y 的二进制数的间断三位进行翻转。问起码操作多少次能够使得 x = y，或输入-1 示意无奈使得x = y。

剖析

因为每次固定选间断三位进行翻转，咱们能够想一下间断三位翻转的一些性质。

首先两头这个数字必定是不变的，而后两边的数字 swap 一下。

也就是每次会抉择间隔为 2 的两个数字进行一次替换，那么如果某个 1 在奇数位上，替换后仍然在奇数位上，如果在偶数位上，替换后仍然在偶数位上。

如下图，红色区域的二进制数和蓝色区域的二进制数是互相独立的。

所以咱们能够进行奇偶分类的探讨，求出在奇数位上所需的操作次数，而后再求在偶数位上所需的操作次数即可。

咱们能够发现，如果要使得操作后 x = y，那么对于奇数位（即上图中的蓝色区域），y 最高位的 1 肯定对应 x 最高位的 1，以此类推。而在奇数位上挪动一格须要的操作次数是1 次。

具体看下图的对应关系：

代码

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

const int N = 105;

int a[N], b[N], pa, pb;
int kase;

int getabs(int x){return x < 0 ? -x : x;}

void solve()
{
    cout << "Case" << ++ kase << ":";
    int x, y;cin >> x >> y;
    pa = pb = 0;
    int ans = 0;
    for(int i = 0;i < 64; i += 2)
    {if(x >> i & 1)a[++ pa] = i;
        if(y >> i & 1)b[++ pb] = i;
    }
    if(pa != pb)
    {
        cout << -1 << '\n';
        return;
    }
    
    for(int i = 1;i <= pa; ++ i)ans += getabs(a[i] - b[i]) / 2;
    pa = pb = 0;
    for(int i = 1;i < 64; i += 2)
    {if(x >> i & 1)a[++ pa] = i;
        if(y >> i & 1)b[++ pb] = i;
    }
    
    if(pa != pb)
    {
        cout << -1 << '\n';
        return;
    }
    
    for(int i = 1;i <= pa; ++ i)ans += getabs(a[i] - b[i]) / 2;
    cout << ans << '\n';
}


signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _;cin >> _;
    while(_ --)solve();
    return 0;    
}

B. Empty Squares

题目链接：https://codeforces.com/gym/104252/problem/E

题意

给定一个长度为 n，高度为1 的矩形，当初你手上有高度均为 1，长度别离为1, 2, 3, ..., n 的共 n 个矩形，但你一开始曾经放了一个长度为 k 的矩形到两头，并使得右边空了 e 个格子。

问接下来你该怎么 不重叠 地搁置矩形，能够使得残余的空格起码，输入起码空格个数。

剖析

看一眼数据范畴，发现 n 只有1000，咱们不放枚举最终矩形的状态（即右边有 i 个格子，两头 k 个格子，左边 e 个格子），而后判断一下这种状况能不能填满。

当初问题就变为了写一个函数 f(l,k,r) 求这种状态的矩形是否可能被恰好不留空位地结构进去。

进行一个简略的分类探讨（无妨设 l <= r）：

限度条件 状况
l != r != k 肯定能够，就是用长度别离为 l,r,k 的矩形填充即可。
l = r = k 当 k >= 5 时肯定能够结构进去（1+4+5+2+3），其余状况能够简略手算一下发现肯定不行。
r=k 两个较大的相等，咱们必须将 r 拆开，然而 r 可能拆出 l，咱们只须要枚举1 + (r - 1) 和2 + (r - 2)两种状况即可，l 至少等于这四个数字当中的一个，所以两种状况必然有一种成立（留神保障i != r - i，拆出来的两个数字也不能相等）。
l= k 或 l =r 相似的拆开 l 即可。

ok 了。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 9;

bool f(int l, int k, int r)
{if(l != r && l != k && r != k)return true;
    if(l > r)swap(l, r);
    //l <= r
    if(l == k && k == r)
    {return l > 4;}else if(l == r || l == k)
    {for(int i = 1;i <= 2 && i < l - i; ++ i)
        {if(i != k && l - i != k)return true;
        }
    }else if(k == r)
    {for(int i = 1;i <= 2 && i < r - i; ++ i)
        {if(i != l && r - i != l)return true;
        }
    }
    return false;
}


signed main()
{
    int n, k, e;cin >> n >> k >> e;
    int ans = n - k;
    for(int i = 0;i <= e; ++ i)
    {for(int j = 0;j <= n - k - e; ++ j)
        {if(f(i, k, j))
            {
                //cout << "l, k, r =" << i << '' <<    k <<' '<< j <<'\n';
                ans = min(ans, n - i - j - k);
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

C. Wall Painting

题意

给定 n 个数字（题目如同没说分明，应该是 1e9 以内的非负整数），求其中选出 i 个数字的所有组合的异或和之和。

剖析

拆位，假如以后思考的是第 w 位，那么咱们只须要枚举出 w 位的所有组合状况并求和即可，不同位之互不影响（因为咱们只须要所有的组合异或和 之和）。

最外层枚举从 n 个数字中选出的数字的个数，即 i，而后对于第 w 位，失去这一位上的cnt0 和cnt1别离示意二进制位上的 0/1 的个数（能够预处理进去）。

而后开始枚举选 j 个1，天然就选 i-j 个0，且这种状况的奉献为：

$$C_{cnt1}^{j} \times C_{cnt0}^{i-j} \times 2^w \times [j \% 2 = 1]$$

还有一种 dp 的写法，我本人写的时候是用 dp 的，比拟 sb，这就不写了。

代码

//C - Wall Painting
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1009, p = 1e6 + 3;
int C[N][N];
void init(int n)
{for(int i = 0;i <= n; ++ i)C[i][0] = 1;
    for(int i = 1;i <= n; ++ i)
        for(int j = 1;j <= n; ++ j)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % p;
}

int n;
int a[N], c[50][2];


void solve()
{for(int i = 1;i <= n; ++ i)cin >> a[i];
    memset(c, 0, sizeof c);
    for(int i = 1;i <= n; ++ i)
        for(int j = 0;j <= 40; ++ j)
            c[j][a[i] >> j & 1] ++;
    
    
    // 枚举抉择的数字的个数 i
    for(int i = 1;i <= n; ++ i)
    {
        int ans = 0;
        // 枚举位数
        for(int w = 0;w <= 40; ++ w)
        {// 在这一位上抉择 j 个 1 和 (i - j) 个 0
            for(int j = 1;j <= i && j <= c[w][1]; j += 2)
            {ans = (ans + (1ll << w) * C[1]][j] % p * C[0]][i - j] % p) % p;
            }
        }
        cout << ans << "\n"[i == n];
    }
        
}

signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init(1002);
    while(cin >> n)solve();
        
    return 0;
}
退出移动版