A.惊鸿

链接：https://ac.nowcoder.com/acm/contest/51208/A

来源：牛客网

题目描述

云浅有四个正整数 a1,a2,a3,a4a_1,a_2,a_3,a_4a1,a2,a3,a4。

她可以进行任意次操作，每次操作中，她可以选出某两个 ai,aja_i,a_jai,aj，然后将 aia_iai 变为 ai or aja_i\text{ or }a_jai or aj。其中 or\text{or}or 是位或运算。

她想要最大化 a1+a2+a3+a4a_1+a_2+a_3+a_4a1+a2+a3+a4 的值。你需要帮她求出这个最大值。

输入描述:

本题有多组数据。第一行一个正整数 TTT 表示数据组数。

每组数据会输入四个非负整数 a1,a2,a3,a4a_1,a_2,a_3,a_4a1​,a2​,a3​,a4​，并换行。

对于 100%100\%100% 的数据，1≤T≤104,0≤a1,a2,a3,a4<2291\le T\le 10^4,0\le a_1,a_2,a_3,a_4<2^{29}1≤T≤104,0≤a1​,a2​,a3​,a4​<229。

输出描述:

对于每组数据，输出一行一个非负整数表示 a1+a2+a3+a4a_1+a_2+a_3+a_4a1​+a2​+a3​+a4​ 的最大值。

示例1

输入

复制

2

1 1 4 5

1 2 3 4

输出

复制

20

28

#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 4;int T;
int a[N], w[N];int main()
{scanf ("%d", &T);while (T -- ){memset(w, 0, sizeof w);LL res = 0;for (int i = 0; i < 4; i ++ ) scanf ("%d", &a[i]);for (int i = 0; i < 4; i ++ ){for (int j = 0; j < 4; j ++ )a[i] = max(a[i], a[i] | a[j]);}for (int i = 0; i < 4; i ++ ) res += a[i];printf ("%lld\n", res);}return 0;
}

B.风间

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010;typedef long long LL;int n;
int a[N], b[N];int main()
{int T;scanf ("%d", &T);while (T -- ){LL ra = 0, rb = 0;bool flag = true;scanf ("%d", &n);for (int i = 1; i <= n; i ++ ) scanf ("%d", &a[i]);for (int i = 1; i <= n; i ++ ) scanf ("%d", &b[i]);LL cnt = 0;for (int i = 1; i <= n; i ++ ){if (a[i] % 2 != b[i] % 2){flag = false;break;}else cnt += (abs(a[i] - b[i]) / 2);}if (!flag) puts("-1");else printf ("%lld\n", cnt);}return 0;
}

C.梦迹

示例1

输入

复制

4 3 6

1 0 4 6

2 2

4 4

1 2

输出

复制

5

7

7

树状数组：

代码：

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int N = 300010;int n, q, w;
LL tr[N], a[N];
LL ans;int lowbit(int x)
{return x & (-x);
}void add(int x, int c)
{for (int i = x + 1; i < N; i += lowbit(i)) tr[i] += c;
}LL query(int x)
{LL res = 0;for (int i = x + 1; i; i -= lowbit(i)) res += tr[i];return res;
}int main()
{scanf ("%d%d%d", &n, &q, &w);for (int i = 1; i <= n; i++){scanf ("%lld", &a[i]);add(a[i], 1);ans += query(w - a[i]);}while (q--){int p, x; cin >> p >> x;ans -= query(w - a[p]);add(a[p], -1);a[p] = x;add(a[p], 1);ans += query(w - a[p]);printf ("%lld\n", ans);}return 0;
}

D.Small Cloud Sugar Candy

示例1

输入

复制

2

5 4

1 1 4

5 1 4

2 3 3

3 4 1

4 4

1 2 3

2 4 1

1 3 2

3 4 1

输出

复制

2 2 1 0 2

-1

代码：

#include <bits/stdc++.h>using namespace std;#define x first
#define y second
typedef pair<int, long long> PII;
typedef long long LL;
const int N = 200010, mod = 998244353;
const long long INF = 1e18;int a[N], r[N];
LL c[N], ans[N], q[N << 4];
vector<PII> V[N];
bool flag;void bfs(int S)
{int hh = 0, tt = 0;q[tt ++ ] = S;LL val = INF;c[S] = 0, a[S] = 1;while(hh < tt){int x = q[hh ++ ];r[x] = 1;if(ans[x] != INF){LL temp = (ans[x] - c[x]) / a[x];if(val == INF)val = temp;else if(val != temp)flag = false;}if(!flag) return;for(auto it : V[x]){int y = it.x;LL z  = it.y;LL c1 = z - c[x];int b1 = -a[x];if(r[y] == 0){q[tt ++ ] = y;c[y] = c1;a[y] = b1;}else{LL c2 = c[y];int b2 = a[y];if(b1 == b2){if(c1 != c2)flag = false;}else if(abs(c2 - c1) & 1){flag = false;}else{LL temp = (c2 - c1) / (b1 - b2);if(val == INF)val = temp;else if(val != temp)flag = false;}}}}if(!flag)return;if(val == INF)val = 0;hh = 0, tt = 0;q[tt ++ ] = S;r[S] = 2;while(hh < tt){int x = q[hh ++ ];ans[x] = c[x] + a[x] * val;for(auto it : V[x]){int y = it.first;if(r[y] == 1){q[tt ++ ] = y;r[y] = 2;}}}
}int main()
{int T;scanf ("%d", &T);while (T -- ){flag = true;int n, m;scanf ("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ){V[i].clear();ans[i] = INF;a[i] = r[i] = c[i] = 0;}for (int i = 1; i <= m; i ++ ){int x, y, z;scanf ("%d%d%d", &x, &y, &z);if (x == y){if (z % 2) flag = false;else{if (ans[x] == INF) ans[x] = z / 2;else if (ans[x] != z / 2) flag = false;}}else{V[x].push_back({y, z});V[y].push_back({x, z});}}for (int i = 1; i <= n; i ++ )if (ans[i] == INF) bfs(i);if (!flag) puts("-1");else{for (int i = 1; i <= n; i ++ ) printf ("%lld ", ans[i]);puts("");}}return 0;
}