情况

时间：2024年7月11日8:20

题解

A

题意

最初，塔没有任何立方体。在一次移动中，Nikita要么将 1 立方体准确地放在塔顶，要么将 1 立方体从塔顶移走。有没有可能在 n 移动后，生成的塔正好有 m 立方体？

思路

n<m不可能
n>=m，(n-m)%2==0，则可以，否则不行

代码

void solve()
{
    int a, b;
    cin >> a >> b;
    if(a<b){cout << "No\n";
        return;}

    else if((a-b)%2==0){cout << "Yes\n";
        return;}
    else{cout << "No\n";
        return;
}}

B

题意

要求你给一个数组表示一个数字X。
$x=∑_{i=0}^{n-1}a_i \cdot 2^i$
要求数组只有-1，0，1。数组不能连续两个不为0。

思路

把x取二进制每一位，维护一个最高位数。
从最小位开始往后遍历：
如果上一位和这一位都不为0，改为上一位为-1，这一位为0，下一位加1
如果这一位=2，进位，下一位+1，这一位为0

代码

void solve()
{
    int wei[33] = {0};
    LL n;
    cin >> n;
    LL temp = n;
    for (int i = 0; temp > 0; i++)
    {
        int h = (n >> i) & 1;
        wei[i + 1] = h; // cout << h << ' ';
        temp = n >> i;
    }
    int flag = 0;
    for (int i = 1; i < 33; i++)
    {
        if (wei[i - 1] != 0 && wei[i] != 0)
        {
            wei[i - 1] = -1;
            wei[i] = 0;
            wei[i + 1] += 1;
        }
        if (wei[i] == 2)
        {
            wei[i] = 0;
            wei[i + 1] += 1;
            flag = i+1;
        }else if(wei[i]==1){
            flag = i;
        }
    }
    cout << flag << endl;
    for (int i = 1; i <=flag; i++)
    {
        
        cout << wei[i] << ' ';
    }

    cout << endl;
}

问题

取位操作还得熟记：(n >> i) & 1

C

题意

假设Nikita有一个整数数组 a，长度为 n 。如果数组的子序列的最小公倍数（LCM）不包含在 a 中，他将称该子序列为特殊的。空子序列的LCM等于 0 。
Nikita想知道： a 的最长特殊子序列的长度是多少？帮他回答这个问题！

思路

首先排个序。
最大的数，他如果不是其他所有数的最小公倍数，那么证明选所有的数为子序列，其最小公倍数也都不在这个数组中（大于最大值）
之后先计算出最大值这个数的所有因子，放进set中。
遍历每个因子。如果这个数组的元素有这个因子，就放进子序列中。
这个子序列的最小公倍数，也必须保证不能在这个数组中，才能使用这个子序列。用一个map来维护这个数组，找有没有子序列的最小公倍数。

代码

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

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100000;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int lcm(LL a, int b)
{
    return a * b / gcd(a, b);
}

void solve()
{
    int n;
    cin >> n;
    int a[N];

    map<int, int> mp;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        mp[a[i]]++;
    }
    sort(a, a + n);
    bool best = false;
    for (int i = 0; i < n; i++)
    {
        if (a[n - 1] % a[i] != 0)
        {
            cout << n << endl;
            return;
        }
    }
    set<int> posans;
    for (int i = 1; i <= sqrt(a[n - 1]); i++)
    { // 因子
        if (a[n - 1] % i == 0)
        {
            posans.insert(i);
            posans.insert(a[n - 1] / i);
        }
    }
    int ans = 0;

    for (auto whats : posans)
    {
        LL lcmn = 1;
        int howmany = 0;
        for (int j = 0; j < n; j++)
        {
            if (whats % a[j] == 0)
            {
                howmany++;
                lcmn = lcm(lcmn, a[j]);
            }
        }
        if (lcmn != 1 && mp[lcmn] == 0)
        {
            ans = max(ans, howmany);
        }
    }
    cout << ans << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

问题

问题就是，不敢写。

D

7月11日，心累啊···,三个小时，照着写，都不懂

题意

你会得到一个二进制（仅由0和1组成） n×m𝑛×𝑚 矩阵。您还可以获得一个XORificator，使用它可以反转所选行中的所有值（即用1替换0，用0替换1）。
如果矩阵中的一列恰好包含一个1，则该列被认为是特殊的。您的任务是找到可以同时特殊化的最大列数，以及应该在其上使用XORificator的行集。

思路

//两个质数
    /*如果想将一列变成特殊列，对于每一行，有变或不变。
    对于每一列，它的特殊列有n种情况。
    对于每一种情况，需要一个方案，这个方案包含了对于n行的操作，所以这个方案有n的长度。
    n*n*m的复杂度。
    对于每一种方案，可以得到的复杂列有一个个数，找出个数最大的那一种方案。
    但是，对于一种方案来源，这种方案和得到全是0的方案，只差了一个数。因此n行的长度，被抵消了，不需要了。
    */

代码

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

#define endl ‘\n’
#define ll long long
#define int long long

const int mod=1e9+7;

signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t–){
int n,m;
cin>>n>>m;
vectorarr(n);
for(int i=0;i<=n-1;i++){
cin>>arr[i];
}
int u=127,v=131;//首先你使用双hash别被卡，
int dp1[n+1],dp2[n+1];//然后预处理u和v的n次方
dp1[0]=1;
dp2[0]=1;
for(int i=1;i<=n;i++){
dp1[i]=dp1[i-1]u%mod;
dp2[i]=dp2[i-1]v%mod;
}
map<pair<int,int>,int>da;//一个map用于记录这个操作出现了几次
map<pair<int,int>,pair<int,int>>ca;//再来一个map记录这个操作是在哪一列和那一个行
for(int i=0;i<=m-1;i++){
int ans1=0,ans2=0;//开始hash
for(int j=0;j<=n-1;j++){
if(arr[j][i]==’1’){
ans1=(ans1u+1)%mod;
ans2=(ans2v+1)%mod;
}
else {
ans1=(ans1u)%mod;
ans2=(ans2v)%mod;
}
}
for(int j=0;j<=n-1;j++){//这个位置变成1
int z1=ans1,z2=ans2;
if(arr[j][i]==’1’){//如果他是1
z1=((z1-dp1[n-j-1])%mod+mod)%mod;//我们需要消除这个位置的影响
z2=((z2-dp2[n-j-1])%mod+mod)%mod;
}
else {
z1=(z1+dp1[n-j-1])%mod;//反之加上
z2=(z2+dp2[n-j-1])%mod;
}
da[{z1,z2}]++;//加上这个操作出现的次数
if(da[{z1,z2}]==1){//记录第一次出现这个hash的时候，答案是什么样子的
ca[{z1,z2}]={i,j};
}
}
}
int ans=0;//答案是多少
pair<int,int>wei={0,0};//还原，找出那一列，哪一行
for(auto &[x,y]:da){
ans=max(ans,y);
if(ans==y){
wei=ca[x];
}
}
cout<<ans<<endl;//输出
for(int i=0;i<=n-1;i++){
if(i==wei.second){//按照之前的操作再走一遍
if(arr[i][wei.first]==’1’){
cout<<0;
}
else {
cout<<1;
}
continue;
}
if(arr[i][wei.first]==’1’){
cout<<1;
}
else {
cout<<0;
}
}
cout<<endl;
}
return 0;
}