Codeforces Round 912 (Div. 2)

什么位运算专场

A. Halloumi Boxes

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

int a[110];
int n,k;

void solve(){
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    if(k>1){
        cout<<"YES"<<endl;
        return;
    }
    for(int i=1;i<n;i++)
        if(a[i]<a[i-1]){
            cout<<"NO"<<endl;
            return;
        }
    cout<<"YES"<<endl;
}

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

B. StORage room

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

int board[1100][1100];
int a[1100];
int n;

void solve(){
    cin>>n;
    memset(a,0,sizeof a);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>board[i][j];
   map<int,int> path;
   for(int i=1;i<=n;i++){
        path.clear();
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            int x=board[i][j];
            for(int k=0;k<30;k++){
                if(x>>k & 1) path[1<<k]++;
            }
        }
        for(auto [x,y]:path)
            if(y==n-1) a[i]+=x;
   }

   for(int i=1;i<=n;i++)
   for(int j=1;j<=n;j++){
    if(i==j) continue;
    if((a[i]|a[j])!=board[i][j]){
        cout<<"NO"<<endl;
        return;
    }
   }

   cout<<"YES"<<endl;
   for(int i=1;i<=n;i++) cout<<a[i]<<" ";
   cout<<endl;
}

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

C. Theofanis' Nightmare

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

const int N = 1e5 + 10;
int pre[N];
int a[N];
int n;

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pre[i] = pre[i-1] + a[i];
    }

    deque<int> path;
    for(int i=1;i<=n;i++){
        if(pre[n]-pre[i-1]<0){
            if(path.size())path[path.size()-1]+=a[i];
            else path.push_back(a[i]);
        }else{
            path.push_back(a[i]);
        }
    }
    int sum=0;
    for(int i=0;i<path.size();i++) sum+=path[i]*(i+1);
    cout<<sum<<endl;
}

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

D1. Maximum And Queries (easy version)

昨天写的时候应该是爆int了，代码找不到了，也不想重新写了，偷个懒,看看别人的码吧，思路都一样。

#include <bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 1e5 + 5;

LL a[N], b[N], ans[105];
int n, q;

LL getCost(int x, LL k) {
    LL cost = 0;
    for (int j = 1; j <= n; j++) {
        if ((b[j] & (1ll << x)) == 0) {
            //使用位运算计算将b[j]的第x位二进制修改为1需要加上多少
            cost += (1ll << x) - ((1ll << (x + 1)) - 1ll & b[j]);
        }
        if (cost > k) return cost; //超过k就返回，避免数据溢出
    }
    return cost;
}


void solve(LL k) {
    memset(ans, 0, sizeof(ans));
    for (int i = 1; i <= n; i++) {
        b[i] = a[i];//复制一份数据
    }
    for (int i = 60; i >= 0; i--) {//检查第i位结果与运算的结果是否可能为1
        LL cost = getCost(i, k);
        if (cost <= k) {//花费在操作次数范围内
            ans[i] = 1;//与运算结果可以为1
            k -= cost;
            for (int j = 1; j <= n; j++) {
                if ((b[j] & (1ll << i)) == 0) {
                    //通过或运算将2^i位修改为1，再通过与运算将后面数字清0
                    b[j] = ((b[j] | (1ll << i)) & (1ll << i));
                }
            }
        }
    }
    LL  res = 0;
    for (int i = 0; i <= 60; i++) {
        res |= (ans[i] << i);//这里ans[i]如果不是long long类型也会发生溢出
    }
    cout << res << endl;
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    while (q--) {
        LL k;
        cin >> k;
        solve(k);
    }
    return 0;
}