#include <iostream>
#include <unordered_set>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
/* result.append(n-1, '9');*/
/* */
const double PI = 3.14159265358979323846;
//vector<pair<double, double>> points;
vector<vector<int>> adj; // 邻接表表示树
vector<int> redCount; // 存储每个节点的子树中红色节点的数量
void dfs(int node, int parent, const string &colors) {
redCount[node] = (colors[node - 1] == 'R' ? 1 : 0); // 如果当前节点是红色，计数为1
for (int child : adj[node]) {
if (child != parent) {
dfs(child, node, colors);
redCount[node] += redCount[child]; // 累加子树中的红色节点数量
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
adj.resize(n + 1);
redCount.resize(n + 1, 0);
// 构建树的邻接表
for (int i = 2; i <= n; i++) {
int parent;
cin >> parent;
adj[parent].push_back(i);
adj[i].push_back(parent);
}
string colors;
cin >> colors;
dfs(1, -1, colors); // 从根节点开始DFS
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int x;
cin >> x;
cout << redCount[x] << endl; // 直接输出预处理得到的结果
}
return 0;
}
// /* i/f(i)*/
long long computeSum(long long n) {
long long sum = 0;
for (long long k = 0; (1LL << k) <= n; ++k) {
long long power = 1LL << k;
long long next_power = 1LL << (k + 1);
long long count = (n / power) - (n / next_power);
// 组内奇数的和为 count^2
sum += count * count;
}
return sum;
}
int main() {
int t;
cin >> t;
while (t--) {
long long n;
cin >> n;
cout << computeSum(n) << '\n';
}
return 0;
}
//字符串解密
string decryptCipher(const string& cipher) {
unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
string plaintext;
// 预计算每个辅音字母的最近元音和下一个辅音
vector<char> nearestVowel(26);
vector<char> nextConsonant(26);
// 初始化最近元音
char prevVowel = 'a';
for (char c = 'a'; c <= 'z'; ++c) {
if (vowels.count(c)) {
prevVowel = c;
} else {
// 找到最近的元音
char nextVowel = 'u';
for (char v : {'a','e','i','o','u'}) {
if (v >= c) {
nextVowel = v;
break;
}
}
nearestVowel[c-'a'] = (abs(c - prevVowel) <= abs(c - nextVowel)) ? prevVowel : nextVowel;
}
}
// 初始化下一个辅音
for (char c = 'a'; c <= 'z'; ++c) {
if (vowels.count(c)) continue;
char next = c + 1;
while (next <= 'z' && vowels.count(next)) {
next++;
}
nextConsonant[c-'a'] = (next > 'z') ? 'z' : next;
}
// 解密过程
for (char c : cipher) {
if (vowels.count(c)) {
plaintext += c;
} else {
plaintext += c;
plaintext += nearestVowel[c-'a'];
plaintext += nextConsonant[c-'a'];
}
}
return plaintext;
}
/* 分享日常*/
int main() {
int n, T, H;
cin >> n >> T >> H;
vector<vector<int>> events(n, vector<int>(3));
for (int i = 0; i < n; ++i) {
cin >> events[i][0] >> events[i][1] >> events[i][2];
}
// DP表：dp[i][j][k]表示前i个事件，时间j，精力k时的最大快乐值
vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(T + 1, vector<long long>(H + 1, 0)));
for (int i = 1; i <= n; ++i) {
int t = events[i - 1][0], h = events[i - 1][1], a = events[i - 1][2];
for (int j = 0; j <= T; ++j) {
for (int k = 0; k <= H; ++k) {
dp[i][j][k] = dp[i - 1][j][k]; // 不选当前事件
if (j >= t && k >= h) {
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - t][k - h] + a); // 选当前事件
}
}
}
}
long long ans = 0;
for (int j = 0; j <= T; ++j)
{
for (int k = 0; k <= H; ++k)
{
ans = max(ans, dp[n][j][k]);
}
}
cout << ans << endl;
return 0;
}
// f(i)的和
long long calculateSum(long long n) {
long long sum = 0;
for (int k = 1; (1LL << k) - 1 <= n; ++k)
{
long long m = (1LL << k) - 1; // (1LL << k) == 2ᵏ
long long count = ((n - m) / (1LL << (k + 1))) + 1;
sum += m * count;
}
return sum;
}
// 统计二进制中1的个数是否为偶数
bool isGoodNumber(int num) {
int count = 0;
while (num) {
count += num & 1;
num >>= 1;
}
return count % 2 == 0;
}
////// 牛牛最近学了二叉树AVL
struct NodeInfo {
bool isBalanced;
int depth;
};
unordered_map<int, NodeInfo> memo;
NodeInfo checkAVL(int node, const vector<pair<int, int>>& tree) {
if (node == 0) return {true, 0};
if (memo.count(node)) return memo[node];
auto left = checkAVL(tree[node].first, tree);
auto right = checkAVL(tree[node].second, tree);
bool balanced = left.isBalanced && right.isBalanced &&
abs(left.depth - right.depth) <= 1;
int depth = max(left.depth, right.depth) + 1;
return memo[node] = {balanced, depth};
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<int, int>> tree(n+1);
for (int i = 1; i <= n; ++i) {
cin >> tree[i].first >> tree[i].second;
}
vector<int> levels(n+1, 0);
// BFS计算层次
vector<int> q = {1};
levels[1] = 1;
while (!q.empty()) {
int u = q.back(); q.pop_back();
if (tree[u].first) {
levels[tree[u].first] = levels[u] + 1;
q.push_back(tree[u].first);
}
if (tree[u].second) {
levels[tree[u].second] = levels[u] + 1;
q.push_back(tree[u].second);
}
}
int minLevel = INT_MAX;
int result = -1;
for (int i = 1; i <= n; ++i) {
auto info = checkAVL(i, tree);
if (info.isBalanced) {
if (levels[i] < minLevel ||
(levels[i] == minLevel && i < result)) {
minLevel = levels[i];
result = i;
}
}
}
cout << result << endl;
return 0;
}
//小红的有根数路径选择
int MIN_max = INT_MAX;
int m,n;
vector<int>arr;
vector<vector<int>> children;
void dfs(int node ,int cursum,int sun_max)
{
cursum += arr[node];
sun_max = max(sun_max,arr[node]);
if(cursum >= m)
{
if(sun_max<MIN_max) // 在满足路径节点权之和的条件下 使最大和最小 //
{
MIN_max =sun_max;
}
return;
}
for(int ch:children[node])
{
dfs(ch,cursum,sun_max);
}
}
int main()
{
cin>>n>>m;
arr.reserve(n+1);
children.reserve(n+1);
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}
for(int i=1;i<=n;i++)
{
int c;
cin>>c;
children[i].resize(c);
for(int j=0;j<c;j++)
{
cin>>children[i][j];
}
}
dfs(1,0,0);
if(MIN_max!=INT_MAX)
{
cout<<MIN_max<<endl;
}
else {
cout<<-1<<endl;
}
}
//矩阵判断
bool isSubmatrix(const vector<string>& large, const vector<string>& small, int m, int n) {
for (int i = 0; i <= m - n; ++i) {
for (int j = 0; j <= m - n; ++j) {
bool match = true;
for (int x = 0; x < n && match; ++x) {
for (int y = 0; y < n && match; ++y) {
if (large[i + x][j + y] != small[x][y]) {
match = false;
}
}
}
if (match) return true;
}
}
return false;
}
//最大可能
long long maxOperations(const string &a) {
long long cnt1 = 0; //遇到过的1的计数值
long long res = 0; //当前遍历的计数值
long long cnt_right_string = 0;//右端移位的最大值
long long cnt_left_string = 0;//左端移位的最大值
for (char c : a) {
res++;
if (c == '1') {
cnt1++;
cnt_right_string = cnt_right_string+a.length()-cnt1-res+1;
cnt_left_string = cnt_left_string+res-cnt1 ;
}
}
return max(cnt_right_string,cnt_left_string);
}
//vector<string>grid(n);
bool isValid(const vector<string>& grid, int n, int m) {
vector<vector<bool>> isBlock(n, vector<bool>(m, false));
// Step 1: Identify all 2x2 blocks
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < m - 1; ++j) {
if (grid[i][j] == '*' && grid[i][j+1] == '*' &&
grid[i+1][j] == '*' && grid[i+1][j+1] == '*') {
isBlock[i][j] = true;
isBlock[i][j+1] = true;
isBlock[i+1][j] = true;
isBlock[i+1][j+1] = true;
}
}
}
// Step 2: Check all '*' are part of some 2x2 block
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == '*' && !isBlock[i][j]) {
return false;
}
}
}
// Step 3: Check no two blocks are adjacent
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < m - 1; ++j) {
if (isBlock[i][j] && isBlock[i][j+1] &&
isBlock[i+1][j] && isBlock[i+1][j+1]) {
// Check 8 adjacent positions
for (int di = -1; di <= 2; ++di) {
for (int dj = -1; dj <= 2; ++dj) {
if (di >= 0 && di <= 1 && dj >= 0 && dj <= 1) continue;
int ni = i + di;
int nj = j + dj;
if (ni >= 0 && ni < n && nj >= 0 && nj < m)
{
if (grid[ni][nj] == '*' && !(ni >= i && ni <= i+1 && nj >= j && nj <= j+1)) {
// return false;
}
}
}
}
}
}
}
//检查任何两个2×2块是否不相邻。对于每个2×2块，检查其周围8个相邻格子是否存在其他不属于当前块的'*'，如果存在则返回false。
return true;
}
//字符串的XOR
int main() {
string T;
cin >> T;
// 确定密钥（只需第一个字符即可，题目保证唯一性）
int key = T[0] ^ 'C';
// 验证前8个字符是否符合（题目说保证唯一，可省略）
bool valid = true;
const string header = "CHICKENS";
for (int i = 0; i < 8 && i < T.size(); ++i) {
if ((T[i] ^ key) != header[i]) {
valid = false;
break;
}
}
if (!valid) {
return 1;
}
// 解密整个字符串
string S;
for (char c : T) {
S += char(c ^ key);
}
cout << S << endl;
return 0;
}
// 小y 爱数学
const int MAX_N = 2e5 + 5;
vector<int> min_prime(MAX_N, 0);
void sieve() {
for (int i = 2; i < MAX_N; ++i) {
if (min_prime[i] == 0) {
min_prime[i] = i;
for (int j = i + i; j < MAX_N; j += i) {
if (min_prime[j] == 0) {
min_prime[j] = i;
}
}
}
}
}
bool is_valid(int num) {
if (num < 8) return false; // 最小为2 * 2 * 2=8
vector<pair<int, int>> factors;
// 质因数分解
while (num > 1) {
int p = min_prime[num];
int cnt = 0;
while (num % p == 0) {
num /= p;
cnt++;
}
factors.emplace_back(p, cnt);
}
// 判断条件
if (factors.size() >= 3) return true; // 情况1
if (factors.size() == 2) {
if (factors[0].second >= 2 || factors[1].second >= 2) return true; // 情况2
}
if (factors.size() == 1 && factors[0].second >= 3) return true; // 情况3
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
sieve(); // 预处理筛法
int n;
cin >> n;
int count = 0;
for (int i = 0; i < n; ++i) {
int num;
cin >> num;
if (is_valid(num)) {
count++;
}
}
cout << count << "\n";
return 0;
}
//方卡 要么红要么绿
int main() {
int N, M;
cin >> N >> M;
vector<int> costs;
for (int i = 0; i < M; ++i) {
int A, B;
cin >> A >> B;
if (A >= N) {
costs.push_back(0);
} else {
int diff = B - A;
int cost = (diff + 1) / 2; // 等价于ceil(diff / 2)
costs.push_back(cost);
}
}
sort(costs.begin(), costs.end());
long long total_cost = 0;
for (int i = 0; i < M - 1; ++i) {
total_cost += costs[i];
}
cout << total_cost << endl;
return 0;
}
// 等式的可能
bool isPrime(int num) {
if (num < 2) return false;
if (num == 2) return true;
if (num % 2 == 0) return false;
for (int i = 3; i * i <= num; i += 2) {
if (num % i == 0) return false;
}
return true;
}
void dfs(const string& s, int pos, int current_num, int current_sum, int& count) {
if (pos == s.length()) {
int total = current_sum + current_num;
if (isPrime(total)) {
count++;
}
return;
}
// 不插入加号，继续累积数字
dfs(s, pos + 1, current_num * 10 + (s[pos] - '0'), current_sum, count);
// 插入加号，将当前数字加入总和，开始新的数字
dfs(s, pos + 1, s[pos] - '0', current_sum + current_num, count);
}
int countPrimeExpressions(const string& s) {
int count = 0;
dfs(s, 1, s[0] - '0', 0, count);
return count;
}
int main() {
string s;
cin >> s;
cout << countPrimeExpressions(s) << endl;
return 0;
}
//小红的数分解 有理数
pair<int, int> maxProduct(int x) {
if (x == 1) return {1, 1};
if (x == 2) return {2, 1};
if (x == 3) return {3, 1};
if (x == 4) return {4, 1};
int product = 1;
while (x > 4) {
product *= 3;
x -= 3;
}
product *= x;
return {product, 1};
}
int main() {
int x;
cin >> x;
auto res = maxProduct(x);
cout << res.first << " " << res.second << endl;
return 0;
}
// 预定义11x11的"里"字模板（根据示例1修正）
vector<string> li_template = {
"...........",
"..*******..",
"..*..*..*..",
"..*******..",
"..*..*..*..",
"..*******..",
".....*.....",
"..*******..",
".....*.....",
".*********.",
"..........."
};
int main() {
int n;
cin >> n;
for (int i = 0; i < 11; ++i) {
for (int r = 0; r < n; ++r) { // 每行重复n次
for (int j = 0; j < 11; ++j) {
for (int c = 0; c < n; ++c) { // 每个字符重复n次
cout << li_template[i][j];
}
}
cout << endl;
}
}
return 0;
}
//字符串旋转
bool canTransform(const string& S, const string& T) {
if (S.length() != T.length()) return false;
string temp = S + S;
return temp.find(T) != string::npos;
}
int main() {
int testCases;
cin >> testCases;
while (testCases--) {
string S, T;
cin >> S >> T;
// 检查字符组成是否相同
string sortedS = S; string sortedT = T;
sort(sortedS.begin(), sortedS.end()); sort(sortedT.begin(), sortedT.end());
if (sortedS != sortedT) {
cout << "No" << endl;
continue;
}
// 检查循环移位
if (canTransform(S, T)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
//与或和
int countPairs(int A, int B)
{
if (A > B) return 0; // 如果 A > B，则不可能有这样的整数对
int count = 0;
// 遍历所有可能的 X
for (int X = A; X <= B; ++X) {
int Y = A | (B & ~X); // 根据 X 计算 Y
if (X <= Y && (X & Y) == A && (X | Y) == B) {
count++;
}
}
return count;
}
// xiaohongchuan
int maxRedString(const string& s) {
vector<int> prev(26, 0);
vector<int> curr(26, 0);
for (char c : s) {
int max_len = 0;
// 检查相邻字母
if (c > 'a') max_len = max(max_len, prev[c - 'a' - 1]);
if (c < 'z') max_len = max(max_len, prev[c - 'a' + 1]);
curr[c - 'a'] = max_len + 1;
// 复制其他字母的状态
for (int i = 0; i < 26; ++i) {
if (i != c - 'a') {
curr[i] = prev[i];
}
}
swap(prev, curr);
}
return *max_element(prev.begin(), prev.end());
}
//胜者为王
double calculateProbability(const vector<int>& a, const vector<int>& selected) {
double prob = 1.0;
for (int s : selected) {
for (int i = 0; i < a.size(); ++i) {
if (i != s) {
prob *= (double)a[s] / (a[s] + a[i]);
}
}
}
return prob;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<bool> mask(n, false);
fill(mask.begin(), mask.begin() + k, true);
double total_prob = 0.0;
do {
vector<int> selected;
for (int i = 0; i < n; ++i) {
if (mask[i]) {
selected.push_back(i);
}
}
double prob = calculateProbability(a, selected);
// 计算其他选手不全胜的概率
for (int i = 0; i < n; ++i) {
if (!mask[i]) {
double not_perfect = 1.0;
for (int j = 0; j < n; ++j) {
if (j != i) {
not_perfect *= (double)a[i] / (a[i] + a[j]);
}
}
prob *= (1.0 - not_perfect);
}
}
total_prob += prob;
} while (prev_permutation(mask.begin(), mask.end()));
cout << fixed << setprecision(10) << total_prob << endl;
return 0;
}
// 计算三元数的个数
int countTriples(int n, int m) {
int count = 0;
for (int z = 0; z <= n; ++z) {
int k = m - z;
if (k < 0 || k > 2 * n) continue;
int lower = max(0, k - n);
int upper = min(k, n);
if (lower > upper) continue;
count += upper - lower + 1;
}
return count;
}
// youyou 的字母串
int main() {
string str;
cin>>str;
vector<int> count(26,0);
for(char c:str)
{
count[c - 'a']++;
}
int min_count = max_num;
for (int target = 0 ; target<26; target++)
{
int cur_count = 0 ;
for (int ch = 0; ch <26; ch++ )
{
if (count[ch]>0)
{
int cur_shunshizhen = (target - ch +26)%26;
int cur_nishizhen = (ch -target + 26)%26;
int cur_min = min(cur_shunshizhen,cur_nishizhen);
cur_count += cur_min * count[ch];
}
}
min_count=min(min_count,cur_count);
}
cout<<min_count<<endl;
}
}
//平滑序列
long long pinghuavalu(const vector<long long>&nums)
{
long long pinhuazhi = 0;
long long n = nums.size();
for(int i=1;i<n;i++)
{
pinhuazhi = max(pinhuazhi,nums[i]-nums[i-1]) ;
}
return pinhuazhi;
}
long long min_pinghuavalue( vector<long long>&nums)
{
vector<int> pinhuazhiidx;
long long pinghua_ =0,min_pinghua=0;
int n = nums.size();
if(n<=2)
{
return 0;
}
pinghua_ = pinghuavalu(nums);
for(int i=1;i<n;i++)
{
if(abs(nums[i]-nums[i-1])==pinghua_)
{
pinhuazhiidx.push_back(i);
}
}
min_pinghua = pinghua_;
for(int i:pinhuazhiidx)
{
if(i>0)
{
int temp_ai = nums[i];
if(i+1<n)
{
nums[i] = (nums[i+1]+nums[i-1])/2;
}
else {
nums[i] = ( nums[i-1]) ;
}
min_pinghua = min(min_pinghua,pinghuavalu(nums));
nums[i] = temp_ai;
}
if(i-1 >=0)
{
int temp_ai = nums[i-1];
if(i-2>=0)
{
nums[i-1] = (nums[i-2]+nums[i])/2;
}
else {
nums[i-1] = ( nums[i]) ;
}
min_pinghua = min(min_pinghua,pinghuavalu(nums));
nums[i-1] = temp_ai;
}
}
return min_pinghua;
}
// 前K小区间
typedef pair<long long, pair<int, int>> P; // {abs_sum, {start, end}}
string getKey(int start, int end) {
return to_string(start) + "," + to_string(end);
}
int main() {
int n, k;
cin >> n >> k;
vector<long long> nums(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> nums[i];
nums[i] += nums[i - 1]; // 计算前缀和
}
priority_queue<P, vector<P>, greater<P>> pq; // 小根堆
unordered_set<string> visited;
// 初始化：所有长度为1的区间
for (int i = 1; i <= n; ++i) {
long long sum = nums[i] - nums[i - 1];
pq.push({abs(sum), {i, i}});
visited.insert(getKey(i, i));
}
vector<long long> result;
while (!pq.empty() && result.size() < k) {
auto [abs_sum, range] = pq.top();
pq.pop();
result.push_back(abs_sum);
// 尝试扩展右边界
if (range.second + 1 <= n) {
int new_start = range.first;
int new_end = range.second + 1;
string key = getKey(new_start, new_end);
if (visited.find(key) == visited.end()) {
long long new_sum = nums[new_end] - nums[new_start - 1];
pq.push({abs(new_sum), {new_start, new_end}});
visited.insert(key);
}
}
}
// 输出结果
for (int i = 0; i < k; ++i) {
cout << result[i] << " ";
}
cout << endl;
return 0;
}
// 游游的水果大礼包
int main() {
long long n, m, a, b;
cin >> n >> m >> a >> b;
long long max_val = 0; // a*x + b *y
long long max_x = min(n / 2, m); // x的最大可能值
long long max_y = min(n, m / 2); // y的最大可能值
// 只需要检查x的边界附近和y的边界附近
for (long long x = max(0LL, max_x); x <= max_x; ++x)
{
long long y = min((n - 2 * x), (m - x) / 2);
y = max(y, 0LL);
max_val = max(max_val, a * x + b * y);
}
for (long long y = max(0LL, max_y); y <= max_y; ++y)
{
long long x = min((n - y) / 2, (m - 2 * y));
x = max(x, 0LL);
max_val = max(max_val, a * x + b * y);
}
cout << max_val << endl;
return 0;
}
// 树上交换节点
int main() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
// 树的边信息（虽然不影响环分解，但题目要求输入）
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
}
vector<bool> visited(n + 1, false);
int cycles = 0;
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
int current = i;
while (!visited[current]) {
visited[current] = true;
current = a[current];
}
cycles++;
}
}
cout << n - cycles << endl;
return 0;
}
//正整数x 在0-y之间最大异或值
int findMaxY(int x, int k) {
int y = 0;
for (int i = 30; i >= 0; --i) { // 处理30位（10^9最多30位）
int mask = 1 << i;// 如果x的当前位是0，y的当前位是1（如果不超过k）
if (!(x & mask)) {
if ((y | mask) <= k) {
y |= mask;
}
}// 如果x的当前位是1，y的当前位是0（默认）
}
return y;
}
//赛程安排
vector<pair<int, int>> generateSchedule(int n) {
vector<pair<int, int>> matches;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
matches.emplace_back(i, j);
}
}// 按字典序排序（已满足，因为i<j）
return matches;
}
//
int solve() {
int n;
cin >> n;
vector<int> x(n+1);
for (int i = 1; i <= n; ++i) {
cin >> x[i];
}
vector<vector<int>> dp(n+1, vector<int>(2));
dp[1][0] = x[1]; // 第一只必须打
dp[1][1] = -INF; // 第一只不能跳过
for (int i = 2; i <= n; ++i) {
// 打当前怪物
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + x[i];
// 跳过当前怪物（前一只必须打）
dp[i][1] = dp[i-1][0];
}
return max(dp[n][0], dp[n][1]);
}
//1-A 回家
int minSteps(int a, int b) {
int total = abs(a) + abs(b);
return total - 1; // 适用于a和b同号且绝对值相等的情况
}
int main() {
int a, b;
cin >> a >> b;
// 特殊情况处理：当a和b同号且绝对值相等时
if (abs(a) == abs(b)) {
cout << abs(a) << endl; // 全用对角线移动
}
// 特殊情况处理：当a或b为0时
else if (a == 0 || b == 0) {
cout << max(abs(a), abs(b)) << endl;
}
// 一般情况：a和b不同号且绝对值不等
else {
cout << minSteps(a, b) << endl;
}
return 0;
}
//与和或
int countPairs(int A, int B)
{
if (A > B) return 0; // 如果 A > B，则不可能有这样的整数对
int count = 0;
// 遍历所有可能的 X
for (int X = A; X <= B; ++X) {
int Y = A | (B & ~X); // 根据 X 计算 Y
if (X <= Y && (X & Y) == A && (X | Y) == B) {
count++;
}
}
return count;
}
//字符串解密-01串解10进制
int binaryToDecimal(const string& s, int start, int len) {
int num = 0;
for (int i = 0; i < len; ++i) {
num = (num << 1) | (s[start + i] - '0');
}
return num;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
vector<int> result;
int pos = 0;
int len = 1;
while (pos + len <= s.size()) {
int num = binaryToDecimal(s, pos, len);
result.push_back(num);
pos += len;
len = len % 10 + 1;
}
cout << result.size() << endl;
for (int i = 0; i < result.size(); ++i) {
if (i > 0) cout << " ";
cout << result[i];
}
cout << endl;
return 0;
}
//牛牛的果园
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> trees(n + 1, vector<int>(101, 0)); // trees[pos][h]
for (int i = 0; i < m; ++i) {
int pos, h;
cin >> pos >> h;
trees[pos][h]++;
}
int total = 0;
for (int pos = 1; pos <= n; ++pos) {
vector<int>& counts = trees[pos];
int max_apples = 0;
// 计算滑动窗口和
int window_sum = 0;
for (int h = 1; h <= k; ++h) {
window_sum += counts[h];
}
max_apples = window_sum;
for (int h = k + 1; h <= 100; ++h) {
window_sum += counts[h] - counts[h - k];
max_apples = max(max_apples, window_sum);
}
total += max_apples;
}
cout << total << endl;
return 0;
}
//六边形战士
const double PI = 3.14159265358979323846;
double calculateArea(int l, const vector<int>& x) {
vector<pair<double, double>> points;
for (int i = 0; i < 6; ++i) {
double theta = i * PI / 3;
double r = (x[i] / 100.0) * l;
points.emplace_back(r * cos(theta), r * sin(theta));
}
double area = 0;
for (int i = 0; i < 6; ++i) {
int j = (i + 1) % 6;
area += points[i].first * points[j].second - points[j].first * points[i].second;
} // Area = 1/2 * |Σ(xᵢ*yᵢ₊₁ - xᵢ₊₁*yᵢ)|
return abs(area) / 2;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int l;
cin >> l;
vector<int> x(6);
for (int i = 0; i < 6; ++i) {
cin >> x[i];
}
cout << fixed << setprecision(6) << calculateArea(l, x) << endl;
return 0;
}
//找K
bool isValid(long long K, long long N) {
return (K * K * K + 3 * K * K + 2 * K) <= 6 * N;
}
long long findMaxK(long long N) {
long long left = 1, right = 1e5, ans = 0;
while (left <= right) {
long long mid = (left + right) / 2;
if (isValid(mid, N)) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
//小写转大写
string processString(const string& s) {
string result = s;
for (int p = 1; p <= s.size(); ++p) {
if (__builtin_popcount(p) % 2 == 1) {
result[p-1] = toupper(result[p-1]);
}
}
return result;
}
//交错值的最大值
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
// 计算原始交错和
long long sum = 0;
for (int i = 0; i < n; ++i) {
sum += (i % 2 == 0 ? a[i] : -a[i]);
}
// 找出奇数位最小值和偶数位最大值
int min_odd = INT_MAX, max_even = INT_MIN;
for (int i = 0; i < n; ++i) {
if (i % 2 == 0) { // 奇数位（因为从0开始）
if (a[i] < min_odd) min_odd = a[i];
} else { // 偶数位
if (a[i] > max_even) max_even = a[i];
}
}
long long case1 = sum + 2 * (max_even - min_odd);
// 找出奇数位最大值和偶数位最小值
int max_odd = INT_MAX, min_even = INT_MIN;
for (int i = 0; i < n; ++i) {
if (i % 2 == 0) { // 奇数位
if (a[i] > max_odd) max_odd = a[i];
} else { // 偶数位
if (a[i] < min_even) min_even = a[i];
}
}
long long case2 = sum + 2 * (max_odd - min_even);
// 取三种情况的最大值
long long max_sum = max(sum, max(case1, case2));
cout << max_sum << endl;
return 0;
}
//小红的乘法操作
int minOperations(int x, int y, int a, int b) {
if (a == b) return 0;
if (b % a != 0) return -1;
queue<pair<long long, int>> q;
unordered_map<long long, bool> visited;
q.push({a, 0});
visited[a] = true;
while (!q.empty()) {
auto [current, steps] = q.front();
q.pop();
if (current == b) return steps;
long long next1 = current * x;
if (next1 <= b && !visited[next1]) {
visited[next1] = true;
q.push({next1, steps + 1});
}
long long next2 = current * y;
if (next2 <= b && !visited[next2]) {
visited[next2] = true;
q.push({next2, steps + 1});
}
}
return -1;
}
//分配苹果
long long calculateSum(long long x, long long cnt) {
if (x >= cnt) {
return (x + x - cnt + 1) * cnt / 2;
}
return (x + 1) * x / 2 + (cnt - x);
}
bool check(long long n, long long m, long long k, long long x) {
long long left = calculateSum(x, k);
long long right = calculateSum(x, n - k + 1);
return (left + right - x) <= m;
}
long long maxApples(long long n, long long m, long long k) {
long long left = 1, right = m, ans = 1;
while (left <= right) {
long long mid = (left + right) / 2;
if (check(n, m, k, mid)) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
//生化危机
const int N = 110;
int grid[N][N];
bool visited[N][N];
int n, m;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int dfs(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y] || grid[x][y] == 0) {
return 0;
}
visited[x][y] = true;
int sum = grid[x][y];
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
sum += dfs(nx, ny);
}
return sum;
}
void solve() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
visited[i][j] = false;
}
}
int missileCount = 0;
int maxZombies = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] > 0 && !visited[i][j]) {
++missileCount;
int current = dfs(i, j);
maxZombies = max(maxZombies, current);
}
}
}
cout << missileCount << " " << maxZombies << endl;
}
//数字变换
int maxOperations(int a, int b) {
if (b % a != 0) return -1; // 无法通过乘法得到b
int d = b / a;
if (d == 1) return 0; // 无需操作
if (d < 1) return -1; // 不可能
// 质因数分解
int count = 0;
for (int p = 2; p * p <= d; p++)
{
while (d % p == 0)
{
count++;
d /= p;
}
}
if (d > 1)
count++; // 剩余的大于1的质因数
return count;
}
//小牛的魔法
int main() {
int a, b;
cin >> a >> b;
string s = to_string(a);
// 降序排序数字
sort(s.begin(), s.end(), greater<char>());
// 处理分段
vector<string> parts;
for (int i = 0; i < b - 1; ++i) {
parts.push_back(string(1, s[i])); // 单独成段
}
parts.push_back(s.substr(b - 1)); // 剩余数字组成最后一段
// 计算和
int sum = 0;
for (const string& part : parts) {
sum += stoi(part);
}
cout << sum << endl;
return 0;
}
//序列 abcdf
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string T;
cin >> T;
// 状态：a, ac, ace, b, bd, bdf
int a = 0, ac = 0, ace = 0;
int b = 0, bd = 0, bdf = 0;
for (char ch : T) {
if (ch == 'a') {
a++;
ace = max(ace, ac); // a不能出现在c/e后
}
else if (ch == 'c')
{
if (a > 0)
ac = max(ac + 1, a + 1);
ace = max(ace, ac);
}
else if (ch == 'e')
{
if (ac > 0)
ace = max(ace + 1, ac + 1);
}
if (ch == 'b') {
b++;
bdf = max(bdf, bd);
} else if (ch == 'd') {
if (b > 0) bd = max(bd + 1, b + 1);
bdf = max(bdf, bd);
} else if (ch == 'f') {
if (bd > 0) bdf = max(bdf + 1, bd + 1);
}
}
cout << ace + bdf << endl;
return 0;
}
//敏感字词串
struct TrieNode {
unordered_map<char, TrieNode*> children;
TrieNode* fail;
vector<int> output;
};
class ACAutomaton {
private:
TrieNode* root;
unordered_map<string, int> wordCount;
vector<string> words;
public:
ACAutomaton() : root(new TrieNode()) {}
void insert(const string& word, int index) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->output.push_back(index);
}
void buildFailureLinks() {
queue<TrieNode*> q;
root->fail = root;
for (auto& pair : root->children) {
pair.second->fail = root;
q.push(pair.second);
}
while (!q.empty()) {
TrieNode* curr = q.front();
q.pop();
for (auto& pair : curr->children) {
char c = pair.first;
TrieNode* child = pair.second;
TrieNode* fail = curr->fail;
while (fail != root && fail->children.find(c) == fail->children.end()) {
fail = fail->fail;
}
if (fail->children.find(c) != fail->children.end()) {
child->fail = fail->children[c];
} else {
child->fail = root;
}
child->output.insert(child->output.end(), child->fail->output.begin(), child->fail->output.end());
q.push(child);
}
}
}
void search(const string& text) {
TrieNode* curr = root;
for (int i = 0; i < text.size(); ++i) {
char c = text[i];
while (curr != root && curr->children.find(c) == curr->children.end()) {
curr = curr->fail;
}
if (curr->children.find(c) != curr->children.end()) {
curr = curr->children[c];
}
for (int idx : curr->output) {
wordCount[words[idx]]++;
}
}
}
void addWord(const string& word) {
words.push_back(word);
}
int getTotalCount() {
int total = 0;
for (auto& pair : wordCount) {
total += pair.second;
}
return total;
}
void build() {
for (int i = 0; i < words.size(); ++i) {
insert(words[i], i);
}
buildFailureLinks();
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
string text;
cin >> text;
ACAutomaton ac;
for (int i = 0; i < m; ++i) {
string word;
cin >> word;
ac.addWord(word);
}
ac.build();
ac.search(text);
cout << ac.getTotalCount() << endl;
return 0;
}
//
int main() {
int n, k;
cin >> n >> k;
string str;
cin>>str;
string temp = str.substr(0,k-1);
for(int i =0;i<=n-k;i++)
{
str[i]=str[i+k-1];
}
if((n-k+1)%2==1)
{
reverse(temp.begin(),temp.end());
str = str.substr(0,n-k+1)+temp;
}
else
{
str = str.substr(0,n-k+1)+temp;
}
cout << str << endl;
}
//双陆棋
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> pos(n + 1); // 棋子编号1~n
unordered_set<int> occupied;
for (int i = 1; i <= n; ++i) {
cin >> pos[i];
occupied.insert(pos[i]);
}
int m;
cin >> m;
while (m--) {
int a;
cin >> a;
int target = pos[a] + 1;
if (occupied.find(target) == occupied.end()) {
occupied.erase(pos[a]);
pos[a] = target;
occupied.insert(target);
}
}
for (int i = 1; i <= n; ++i) {
cout << pos[i] << "\n";
}
return 0;
}
//牛牛的礼物
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
long long total = 0;
long long min_odd = 10001 ; // 初始化为最大值
long long min_od = 10001 ; // 初始化为最大值
for (int i = 0; i < n; ++i) {
cin >> a[i];
if (a[i] % 2 == 1)
{
total += a[i]; // 奇数和
if (a[i] < min_odd) {
min_odd = a[i];
}
}
else
{
if (a[i] < min_od) {
min_od = a[i];
}
total += a[i] - 1; // 取偶数的 最大奇数
}
}
if (total % 2 == 0)
{
if (min_odd != 10001 )
{
total -= min_od-1;
} else
{
total += min_od-1; // 没有奇数朵花可选
}
}
cout << total << endl;
return 0;
}
，哈哈哈哈哈
影石Insta360公司福利 444人发布