Contestant. Rank 761. Rating +41.
A. Rigged!
题意
给定 \(n\) 个人的臂力 \(s_i\) 和耐力 \(e_i\)。若比赛的杠铃重量为 \(w\)，那么所有满足 \(s_i \geq w\) 的人都可以举起杠铃，且可以举起 \(e_i\) 次。
输出最小的 \(w\)，使第一个玩家能举起的次数严格最多。
思路
显然，我们要做的就是，让耐力大于等于第一个玩家的人都举不起杠铃。
那么，我们统计耐力大于等于第一个玩家的所有玩家的力量最大值，然后判断最大值是否小于第一个玩家的力量即可。
如果满足，那么 \(w = s_1\)，否则无解。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<pii> a(n + 1);
for(int i=1;i<=n;i++){
cin >> a[i].fs >> a[i].sc;
}
int mx = 0;
for(int i=2;i<=n;i++){
if(a[i].sc >= a[1].sc){
mx = max(mx, a[i].fs);
}
}
if(mx >= a[1].fs) {
cout << -1 << '\n';
return;
}
cout << a[1].fs << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}有点抽象的题面（
B. Chips on the Board
题意
给定一个 \(n \times n\) 的方阵，以及两个长为 \(n\) 的序列 \(a, b\)。
现在，需要在方阵中标记若干点，使对于方阵的任意一个点 \((i, j)\)，它的同一行或同一列至少有一个点被标记。
若标记点 \((i, j)\) 的代价为 \(a_i + b_j\)，输出满足条件的最小代价和。
思路
考虑下面的问题：
选定若干行和若干列进行涂色，使最后整个方阵都涂上色的最小代价和。
那么显然，要么我们把行全都填满，要么我们把列全都填满。
在本题也是一样的，只是我们全都填满行后，还得考虑列的选择；对列也是一样的。
但是，因为我们可以任意选，从而我们一定会选最小的。
那么，最后问题的答案就是 \(\min(n \cdot a_{\min} + \sum b_i,~n \cdot b_{\min} + \sum a_i)\)。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n);
int sum1 = 0, sum2 = 0;
for(int i=0;i<n;i++) {
cin >> a[i];
sum1 += a[i];
}
for(int i=0;i<n;i++) {
cin >> b[i];
sum2 += b[i];
}
sum1 += *min_element(all(b)) * n, sum2 += *min_element(all(a)) * n;
cout << min(sum1, sum2) << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}有意思的思维，但题面还是有点（
C. Make it Alternating
题意
给定一个二进制字符串，定义一次操作为选定一个位置，并将其删除。
输出使字符串变为 \(0, 1\) 交替需要的最小操作数，以及对应的方案数。
思路
首先，前者很好算，我们只需进行 "去重" 即可：\(00110001 \rightarrow 0101\)。
至于后者，我们先一块一块进行考虑。对于每一块，若长度为 \(cnt\)，那么我们就需要在 \(cnt\) 中选 \(cnt - 1\) 个数进行删除，也就是 \(C_{cnt}^{cnt - 1} = C_{cnt}^1 = cnt\) 种组合方式。
其次，我们得到了方案的所有组合方式，但方案的执行是有先后顺序的，从而我们还得乘上一个全排列。
后者可以通过预处理阶乘实现。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
int fact[N];
void init(){
fact[0] = fact[1] = 1;
for(int i=2;i<=2e5;i++) fact[i] = fact[i - 1] * i % mod;
}
void solve() {
string s;
cin >> s;
s = s + " ";
int ans = 0, cnt = 1;
int tmp = 1;
for(int i=1;i<s.size();i++){
if(s[i] == s[i - 1]){
tmp ++;
}else{
ans = (ans + tmp - 1) % mod;
cnt = cnt * tmp % mod;
tmp = 1;
}
}
cnt = cnt * fact[ans] % mod;
cout << ans << ' ' << cnt << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
init();
int t = 1;
cin >> t;
while (t--) solve();
}注意，不是对每一块求全排列然后乘起来
D. Sum of XOR Functions
题意
给定一个长为 \(n\) 的数组 \(a\)，输出 \(\sum_{l=1}^{n} \sum _ {r=l}^{n} f(l, r) \cdot (r - l + 1)\)，其中 \(f(l, r) = a_l \oplus a_{l+1} \oplus \ldots \oplus a_{r-1} \oplus a_r\)。
思路
我们可以一位一位考虑本题，这样对异或具有交换律。
那么，问题就转化为了：给定一个二进制序列，输出所有 连续子序列的异或和与序列长度的乘积 的总和。
这是一个比较经典的问题，我们直接暴力枚举右端点，然后在枚举的过程中记录左端点的个数，满足最后整个序列的异或和为 \(1\)，从而将区间的和变为每个点的值之和。
异或和的值取决于区间中 \(1\) 个数的奇偶性，那么我们不妨记录前 \(i\) 个数中 \(0\) 的个数，以及 \(1\) 的个数，然后在出现 \(1\) 的时候，交换 \(0, 1\) 的个数即可（可以理解为进行了一次翻转，原来不合法的变为了合法）。
最后，我们累加每一位的结果即可。
时间复杂度：\(O(64n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
int ans = 0;
for(int i=60;i>=0;i--){
int cnt0 = 0, cnt1 = 0;
int pre0 = 0, pre1 = 0;
for(int j=1;j<=n;j++){
pre0 = (pre0 + cnt0) % mod, pre1 = (pre1 + cnt1) % mod;
if(a[j] & (1ll << i)){
ans = (ans + (pre0 + 1) * (1ll << i) % mod) % mod;
swap(pre0, pre1), swap(cnt0, cnt1);
cnt1 ++, pre1 ++;
}else{
ans = (ans + pre1 * (1ll << i) % mod) % mod;
cnt0 ++, pre0 ++;
}
}
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}有意思的数学题（