Loading...  div4真的太爽辣！ # A. Division? 考察if语句的使用，略。 # B. Triple 给一个数列，问有没有数字出现三次以上。拿map暴力计数就可以了。 # C. Odd/Even Increments 给一个数列，每次可以把所有奇数位+1或者所有偶数位+1，问能否将所有数字的奇偶性变为一样。 显然分奇偶位置存储然后分别判断奇偶性是否相同即可。 # D. Colorful Stamp 一维数组，每个位置有B、R、W三种颜色，初始全是W，每次你可以将相邻两个刷成BR或者RB（覆盖、不能越界），问能否得到目标序列。 ## 做法 我也不知道为什么是对的但是……显然是把W当做分隔符然后把数组分段，每一段只要不是由单一颜色构成就行。 赛后想了一下其实也容易证明： 首先分段这件事不用多说。那么对于每一段，假设左边是B，那么我们就用BR一路刷到右边，然后再用RB从最右边一路刷到最左边的R处，然后再用RB从这个地方往右刷所有的R就行了。反之同理。 # E. 2-Letter Strings 给定多个长度为2的字符串，问有多少组**不完全相同**的字符串？ ## 做法 遍历一下，分别计数并更新“front为某个字符的有多少”，“back为某个字符的有多少”，“某个字符串有多少”，然后容斥一下就行了。 ## 代码 ```cpp cin>>n; vector<string> ar; map<string, ll> m; map<char, ll> l, r; ll ans = 0; m.clear(), l.clear(), r.clear(); FOR(i,1,n) { string str; cin>>str; ar.push_back(str); } for (auto v : ar) { ans += l[v.front()] + r[v.back()] - 2*m[v]; l[v.front()]++; r[v.back()]++; m[v]++; } cout<<ans<<endl; ``` # F. Eating Candies 一维上顺序排列着若干堆糖果，每堆有其数量，A和B分别从左边和右边开吃，要求他俩吃的总数量相同，问最多一共吃多少堆糖果？ ## 做法 从左往右求前缀和通知记录每个前缀和存在的位置，然后从右往左求后缀和看前缀和有没有对应的数字，然后位置是否不相交，如果可以就更新答案即可。 ## 代码 ```cpp int t, n; #define N 200005 ll a[N]; map<ll, int> pre; int main() { cin >> t; while (t--) { cin >> n; ll s = 0; pre.clear(); FOR(i, 1, n) { cin >> a[i]; s += a[i]; if (pre.find(s) != pre.end()) umin(pre[s], i); else pre[s] = i; } ll ans = 0; s = 0; for (int i = n; i >= 1; i--) { s += a[i]; if (pre.find(s) != pre.end() && pre[s] < i) ans = max(ans, (ll)pre[s] + n - i + 1); } cout << ans << endl; } return 0; } ``` # G. Fall Down 二维平面上有一些石头和平台，均占一格，石头会下落但不能穿过平台，问最终形态是什么样。 ## 做法 暴力模拟即可。 ```cpp int t, n, m; #define N 55 char a[N][N]; bool ok(int x, int y) { int pos = 0; FOR(i, x, n) { if (a[i][y] == 'o') break; if (a[i][y] == '.') pos = i; } if (pos == 0) return false; a[pos][y] = '*'; return true; } int main() { cin >> t; while (t--) { cin >> n >> m; FOR(i, 1, n) FOR(j, 1, m) scanf(" %c", &a[i][j]); FOR(i, 1, n) FOR(j, 1, m) if (a[i][j] == '*') { if (ok(i,j)) a[i][j] = '.'; } FOR(i, 1, n) { FOR(j, 1, m) cout << a[i][j]; cout << endl; } } return 0; } ``` # H. Maximal AND ## 题意 给定一个数列$A$和操作次数$k$，每次操作可以令任意数字$a_i=a_i\vee(1<<j)$，其中$j\in[0,30]$，求 $$ \max\bigwedge_{a_{i} \in A} a_{i} $$ 其中$\wedge$和$\vee$表示分别表示按位与和按位或。 ## 分析 计数所有数字在每一位上$1$的个数，然后从高位往低位贪心即可。 ## 代码 ```cpp int t, n, k; #define N 200005 int a[N]; int cnt[50]; int main() { cin >> t; while (t--) { cin >> n >> k; memset(cnt, 0, sizeof cnt); FOR(i, 1, n) { cin >> a[i]; FOR(j, 0, 30) { if (a[i] & (1 << j)) cnt[j]++; } } int ans = 0; for (int i = 30; i >= 0; i--) if (cnt[i] == n) ans |= 1 << i; else if (k >= n - cnt[i]) { k -= n - cnt[i]; ans |= 1 << i; } cout << ans << endl; } return 0; } ``` © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏