A

统计原数组中的奇数个数 $k$，则偶数个数为 $n-k$。只要 $a_1$ 为奇数，那么将所有的偶数都跟在后面就能保证接下来的前缀和都是奇数，接下来安排剩下的 $k-1$ 个奇数，每 $2,4,6...$ 个都能贡献一个，总数为 $$1+n-k+\lfloor \frac{k-1}2\rfloor$$

特殊的，当 $k=0$，结果也为 $0$

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n; cin >> n;
    int k = 0;
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;
        k += x % 2;
    }
    if(k == 0) {
        cout << 0;
        return 0;
    }
    cout << 1 + n - k + (k - 1) / 2;
    return 0;
}

B

没有任何回文子串，相当于没有任何长度为 $2$ 或 $3$ 的子串，因为更长长度的回文子串一定包含 $2$ 或 $3$ 的回文子串(最中心)。

从前到后模拟修改即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
string s;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>s;
	for(int i=0;i<n;i++)
	{
		bool f=0;
		while(s[i]==s[i-2]||s[i]==s[i-1]) //构成回文子串时修改它 
		{
			s[i]=s[i]+1;
			if(s[i]=='z'+1) s[i]='a';
			while(s[i]==s[i+1]||s[i]==s[i+2]) //防止与后面的字符形成新的回文子串  
			{
				s[i]=s[i]+1;
				if(s[i]=='z'+1) s[i]='a';
			}
			f=1;
		}
		ans+=f;
	}
	cout<<ans<<"\n"<<s<<"\n";
	return 0;
}

C

将猫猫按照由大到小排序，优先放置面积更大的（方便快速结束搜索）。按顺序枚举每一只猫猫，从地图左上到右下找寻第一个能放置当前猫猫的空白部分，做好标记，继续搜索并回溯。

判断空白部分能否放置当前猫猫、已放置的部分做标记等操作可使用位运算简化加速。并进行相应的剪枝操作。

#include<bits/stdc++.h>
using namespace std;
int k,n,m,ans,rem; // rem剩余位置
struct Point {
    int x,y;
};
struct C {
    int h,w,s;
    bool friend operator < (C l,C r) {
        return l.s>r.s; // 按照面积大小排序
    }
};
C cats[21];
int used[21],rows[21],fmask; // 位运算 fmask 最低 m 位都是 1
//  黑科技，直接卡搜索时间避免超时
clock_t start_time;
bool TLE() {
    return double(clock() - start_time) / CLOCKS_PER_SEC > 1.8;
}
Point find_first() {
    for(int i=0; i<n; ++i) {
        if(rows[i] != fmask) {
            int mask = (~rows[i]) & fmask; // row[i] 取反 和 fmask 与运算
            int col = __builtin_ctz(mask);
            return {i,col};
        }
    }
    return {-1,-1};
}
// 检测能否在(x,y)放h×w的矩形
bool judge_place(int x,int y,int h,int w) {
    if(x+h>n || y+w>m) return 0;
    int mask = ((1<<w)-1)<<y; // 构造掩码
    for(int i=x; i<x+h; ++i) {
        if(rows[i] & mask) return 0; // 不为零表示重叠处有1
    }
    return 1;
}
// 放矩形（猫）
void place_cat(int x,int y,int h,int w) {
    int mask = ((1<<w)-1)<<y;
    for(int i=x; i<x+h; ++i) {
        rows[i] |= mask;
    }
    rem -= h*w;
}
// 移除
void remove_cat(int x,int y,int h,int w) {
    int mask = ((1<<w)-1)<<y;
    for(int i=x; i<x+h; ++i) {
        rows[i] &= ~mask;
    }
    rem += h*w;
}
// 计算剩余最小面积
int min_rema() {
    int ret = n*m + 1;
    for(int i=0; i<k; ++i) {
        if(!used[i])
            ret = min(ret, cats[i].s);
    }
    return ret;
}
// 估价函数：最多能放多少个
int cal(int placed) {
    int rema = rem;
    int min_rem = min_rema();
    if(min_rem > n*m) return placed;
    return placed + rema / min_rem;
}
void dfs(int placed) {
    // 超时检查
    if(TLE()) return;  
    if(placed > ans) ans = placed;  
    // 剪枝：乐观估计 <= 当前最优解
    if(cal(placed) <= ans) return;
    // 剪枝：剩余面积 < 最小猫猫面积
    if(rem < min_rema()) return;
    // 找到第一个空位
    Point p = find_first();
    if(p.x == -1) {
        ans = max(ans, placed);
        return;
    }
    int x = p.x, y = p.y;
    // 尝试放置每个未使用的猫猫
    for(int i=0; i<k; ++i) {
        if(used[i]) continue;
        // 猫猫旋转
        for(int j=0; j<2; ++j) {
            int h = j?cats[i].w:cats[i].h;
            int w = j?cats[i].h:cats[i].w;          
            if(judge_place(x,y,h,w)) {
                place_cat(x,y,h,w);
                used[i] = 1;
                dfs(placed + 1);
                used[i] = 0;
                remove_cat(x,y,h,w);
            }
            if(cats[i].h == cats[i].w) break;
        }
    }
    // 跳过当前空位（标记为障碍）
    int mask = 1 << y;
    rows[x] |= mask;
    rem--;
    dfs(placed);
    rows[x] &= ~mask;
    rem++;
}
int main() {
    start_time = clock();
    cin >> k >> n >> m;
    int valid_count = 0;
    for(int i=0; i<k; ++i) {
        int h, w;
        cin >> h >> w;
        // 检查猫猫是否能放下（两种方向）
        bool can_fit = (h <= n && w <= m) || (w <= n && h <= m);
        if(can_fit) {
            cats[valid_count].h = h;
            cats[valid_count].w = w;
            cats[valid_count].s = h * w;
            valid_count++;
        }
    }
    // 更新k为实际能放下的猫猫数量
    k = valid_count;
    if(k == 0) {
        cout << 0 << endl;
        return 0;
    }
    sort(cats, cats + k);
    fmask = (1 << m) - 1;
    rem = n * m;
    dfs(0);
    cout << ans << endl;
    return 0;
}

D

刨除起点到达的第 $1$ 个被搬起的矿区，其他的被搬起的矿区都是从 $0$ 或 $n+1$ 而来，所以每个矿区的搬起代价是 $C_i=min(i,n+1-i)+c_i$，并且是独立的。

枚举第一个去搬起的矿区 $i$，接下来去的矿区一定是 $C_i$ 的一段前缀。采用前缀和+二分，直接判定当前枚举情况下，还能继续去搬几个矿区。

#include <iostream>
#include <algorithm>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
using lint = long long;
const int N = 2e5 + 10;

struct Data
{
    int a, t, st;
    // t：从任意两边出发的花费
    // st：从 0 出发的花费
} arr[N];

lint s[N]; // 花费的前缀和
int T, ans, n, c;

bool check(int k, int i, int lim)
{
    // 还要传送 k 次，第一次传送是在 i，剩余的钱数为 lim
    return (i > k ? s[k] : s[k + 1] - arr[i].t) <= lim;
}

void binary_search(int i)
{
    int l = -1, r = n;
    // 最少可以传送 0 次，最多还可以传送 n-1 次，故将 l,r 向外移动一个
    while (l + 1 != r)
    {
        int mid = l + r >> 1;
        if (check(mid, i, c - arr[i].st))
            l = mid; // 总花费减去 0->i 的花费
        else
            r = mid;
    }
    ans = max(ans, l + 1); // l 是还可以的，初始还从 i 传送了，故 +1
}

int main()
{
    std::cin.tie(0)->sync_with_stdio(0);
    std::cin >> n >> c, ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> arr[i].a;
        arr[i].st = i + arr[i].a;
        arr[i].t = min(i, n + 1 - i) + arr[i].a;
    }
    std::sort(arr + 1, arr + n + 1, [](const Data &p, const Data &q)
                { return p.t < q.t; });
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + arr[i].t;
    for (int i = 1; i <= n; ++i)
    { // 枚举第一个前往的位置
        if (arr[i].st <= c)
            binary_search(i); // 二分还可以传送的次数
    }
    std::cout << ans << '\n';
    return 0;
}