C. 翻转
首先如果第一个和最后一个棋子颜色不一样，那么是没办法用规则进行翻转的，输出 -1 。
如果第一个和最后一个颜色相同，则遍历该串，若当前遍历的棋子颜色不一样，则看两边棋子颜色是否与当前棋子不同，若不同则可以改变颜色，若有一个相同则不能改变颜色，输出 -1 。
#include <bits/stdc++.h>
int main() {
int T;
std::cin >> T;
while (T -- ) {
std::string s, p;
std::cin >> s >> p;
int result = 0;
for (int i = 0 ; i < s.size() ; i ++ ) {
if (s[i] != p[i]) {
if (i == 0 || i == s.size() - 1) {
result = -1;
break;
} else {
if (p[i - 1] != p[i] && p[i + 1] != p[i]) {
result ++ ;
p[i] = (p[i] == '0' ? '1' : '0');
} else {
result = -1;
break;
}
}
}
}
std::cout << result << "\n";
}
return 0;
}
D. 阶乘的和
将 \(A_i\) 从小到大进行排序，若 \(A_1\) 的数量为 \(A_2\) 的倍数，则可以将 \(A_1\) 转化为 \(A_2\)。
举例：
若有 3 3 3 3 4
则结果为 3! + 3! + 3! + 3! + 4! = 2 * 4!
按照该办法从小到大枚举，直到\(A_i\) 的数量不能刚好是 \(A_{i+1}\) 的倍数，或者 \(A_i\) 是最后一个元素，此时的 m 为\(A_i\)。
#include <bits/stdc++.h>
int main() {
int n;
std::cin >> n;
std::map<int,int> mp;
int Min = 2e9;
for (int i = 0 ; i < n ; i ++ ) {
int x;
std::cin >> x;
mp[x] ++ ;
Min = std::min(Min,x);
}
while(mp[Min]) {
if(mp[Min] % (Min + 1) == 0) {
mp[Min + 1] += mp[Min] / (Min + 1);
Min ++ ;
} else break;
}
std::cout << Min << "\n";
return 0;
}
E. 公因数匹配
首先用线性筛法将素数预处理出来，由于 \(A_i\) 的数据范围最大为 \(10^6\)，则可以预处理出来在 \(10^6\) 以内的合数的所有质因子。
之后遍历该数列，用 pos 数组记录因子最先出现的位置，将相同因子的头两次出现位置保存起来，按照规则排序之后输出第一个数据。
#include <bits/stdc++.h>
const int N = 1000100;
int n;
int a[N];
bool st[N];
int pos[N];
int primes[N], cnt;
std::vector<int> v[N];
void get_primes(int n) {
for (int i = 2 ; i <= n ; i ++ ) {
if(!st[i]) primes[cnt ++ ] = i;
for (int j = 0 ; primes[j] <= n / i ; j ++ ) {
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
return ;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
get_primes(N);
for (int i = 0 ; i < cnt ; i ++ ) {
for (int j = 1 ; j * primes[i] < N ; j ++ ) {
v[j * primes[i]].push_back(primes[i]);
}
}
std::cin >> n;
for (int i = 0 ; i < n ; i ++ ) {
std::cin >> a[i];
}
std::vector<std::pair<int,int>> res;
for (int i = 0 ; i < n ; i ++ ) {
int last = n + 1;
for (auto & t : v[a[i]]) {
if(!pos[t]) {
pos[t] = i + 1;
} else {
last = std::min(last,pos[t]);
}
}
res.push_back({last,i + 1});
}
sort(res.begin(),res.end(),[](const std::pair<int,int> &a,const std::pair<int,int> &b){
return a.first == b.first ? a.second < b.second : a.first < b.first ;
});
std::cout << res[0].first << " " << res[0].second << "\n";
return 0;
}
G. 太阳
将每个线段投影到 x 轴上，由于投射到 x 轴上可能数据范围过大，这里要用离散化进行处理。
按照 y 值的大小顺序进行遍历，如果该线段有未被前面的线段遮挡的部分，则能被太阳照亮。
这里用bool数组存当前线段之前的线段有没有遮挡该区域。
觉得应该会超时，但是数据点全过了，应该是没有极限的数据？
#include <bits/stdc++.h>
#define N 100100
int n,X,Y;
struct Seg {
int x,y,l;
}seg[N];
bool st[N * 3];
double sg[N][2];
double Numb[N * 3];
double Compute(double x, double y) {
double result = (y / (y - Y)) * (X - x) + x;
return result;
}
bool Compare(Seg &a, Seg &b) {
return a.y > b.y;
}
int main() {
std::cin >> n >> X >> Y;
for (int i = 1 ; i <= n ; i ++ ) {
int x,y,l;
std::cin >> x >> y >> l;
seg[i] = {x,y,l};
}
std::sort(seg+1,seg+1+n,Compare);
int idx = 0;
for (int i = 1 ; i <= n ; i ++ ) {
int x = seg[i].x, y = seg[i].y, l = seg[i].l;
sg[i][0] = Compute(x,y), sg[i][1] = Compute(x + l,y);
Numb[++ idx] = Compute(x,y), Numb[++ idx] = Compute(x + l, y);
}
std::sort(Numb + 1, Numb + 1 + idx);
int result = 0;
for (int i = 1 ; i <= n ; i ++ ) {
int l = std::lower_bound(Numb + 1, Numb + 1 + idx, sg[i][0]) - Numb + 1;
int r = std::lower_bound(Numb + 1, Numb + 1 + idx, sg[i][1]) - Numb + 1;
int flag = 0;
for (int k = l ; k < r ; k ++ ) {
if(!st[k]) {
flag = 1;
st[k] = true;
}
}
if(flag) result ++ ;
}
std::cout << result << "\n";
return 0;
}