A

模拟

注意是出来自己之外有80%

int a[N];
void solve() {
	int n;
	cin >> n;
	rep(i, 1, n) {
		cin >> a[i];
	}

	int ans = 0;
	rep(i, 1, n) {
		int cnt = 0;
		rep(j, 1, n) {
			if (a[j] <= a[i]) {
				cnt++;
			}
		}
		if (cnt * 10 >= 8 * n) {
			ans += a[i];
		}
	}
	cout << ans << '\n';
}

B

前缀和

前缀和维护每个人开始的第一年

int t[N], a[N];
void solve() {
	int n, q, s;
	cin >> n >> q >> s;

	rep(i, 1, n) {
		cin >> t[i];
	}
	a[1] = s;
	rep(i, 2, n) {
		a[i] = a[i - 1] + t[i - 1];
	}

	rep(i, 1, q) {
		int x, y;
		cin >> x >> y;

		cout << a[x] + y - 1 << '\n';
	}
}

C

构造 位运算 格雷码/打表

打表可以发现，的情况是这样，观察可以发现的部分，似乎是把前面的反转，然后都加4实现的。这个模式有一定得道理，在每个长度内部，只有两种异或，长度了不得不出现更大的异或时，仍然保证只有一个，剩下的异或还是都是

按这个方案暴力构造，每轮都把所有元素反转，接到后面，加上，复杂度也只有

void solve() {
	int n;
	cin >> n;
	vi ans = {0, 1};
	vi t;
	t.reserve(1 << n);
	ans.reserve(1 << n);

	rep(i, 1, n - 1) {
		int cur = 1 << i;

		for (int i = ans.size() - 1; i >= 0; i--) {
			t.push_back(ans[i] + cur);
		}
		for (int x : t) {
			ans.push_back(x);
		}
		t.clear();
	}
	for (int x : ans) {
		cout << x << ' ';
	}
}

如果学过数电的格雷码，会发现这就是格雷码的构造方式，格雷码的优化目标是最小化

和本题有点区别，但格雷码保证相邻两个元素只有一个二进制位不同，并且尽可能让不同的二进制位是低位，实际上使得它在本题的优化目标下仍然是对的。

D

exgcd变形

一个长度n的线段，两个人分别从两端开始走，每秒可以走或停，一个人必须走a，另一个人必须走b。问是否存在某一秒结束后，两个人在同一位置，如果存在，最小化这个时间。

完全可以抽象成，求

看出来这个问题是exgcd还不行，需要了解一下exgcd的本质。这个不定方程对应平面上一条直线，是只看第一象限的部分，我们想要的整数解，试着条线段上的一些整点。exgcd能解出一个特解，就是找到一个整点，并且得到，利用特解和g，能表示出通解的形式

这是一个类似参数方程的东西，我们把看成参数，就是在这个线段上的整点间移动，我们要求，那么也有一个取值范围。

接下来来看我们的优化目标，注意到随着变化一个变大一个变小，那么是一个下凹函数，如果极值点在的取值范围内，答案就是极值点附近的整点，极值点不是整点的话，就是最近的两个整点。如果极值点不在的取值范围内，那么此时就是单增或单减，答案就是取值的两个端点之一。

到这一步就可以二分/三分了，或者，由于这个表达式比较好分析，也可以直接解方程得到极值点，方程就是，解出的答案分别上下取整，就是极值点附近的两个整点。

把极值点附近的整点，还有取值范围的两个端点分别计算，取最小，就是答案，这样可以省去分类讨论

可能爆，复杂度并不高，可以考虑python

import sys


def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y


def solve():
    line = sys.stdin.readline()
    t = int(line.strip())

    results = []
    for _ in range(t):
        line = sys.stdin.readline()
        n, a, b = map(int, line.split())

        g, x, y = exgcd(a, b)

        if n % g != 0:
            results.append("No")
            continue

        x0 = x * (n // g)
        y0 = y * (n // g)
        dx = b // g
        dy = a // g

        l = -x0 // dx
        if x0 + l * dx < 0:
            l += 1

        r = y0 // dy
        if y0 - r * dy < 0:
            r -= 1

        if l > r:
            results.append("No")
            continue

        kk = (y0 - x0) // (dx + dy)

        mn = -1
        resx, resy = -1, -1

        for k in (l, r, kk, kk + 1):
            if l <= k <= r:
                curx = x0 + k * dx
                cury = y0 - k * dy
                mx = max(curx, cury)
                if mn == -1 or mx < mn:
                    mn = mx
                    resx, resy = curx, cury

        results.append("Yes")
        results.append(f"{resx} {resy}")

    sys.stdout.write("\n".join(results) + "\n")

solve()

F

构造 打表

用个，个组成的序列，使得所有子数组的之和最大。构造先打表，这个问题打表很好做，爆搜即可。

观察在的答案可以发现，就是用出现次数较少的元素，把另一种元素尽可能均分，实现也很简单

定性分析的话，假设出现较少的是0，那么如果把0聚在一起放，会出现一段很长的连续1，这个区间内所有子数组都是，这是不优的，而用把尽可能均分的话，每一个段的长度都不会太长，产生的子数组个数也不会太多，所有跨过边界的，含的区间，都是2，这样我们使得的子数组个数最大化，0的子数组个数最小化。

如果出现较少的是1，那么类似地，如果我们把1堆一起，会出现很长的连续0段，都是1，而如果用1均匀隔开0，我们可以让为2的子数组个数最大化，1的子数组个数最小化。

void solve() {
    int a,b;
    cin>>a>>b;
    string s;
    if(a>b){
        swap(a,b);
        int x=b/(a+1);
        int y=b%(a+1);
        rep(i,1,a+1){
            rep(j,1,x){
                s+='0';
            }
            if(i<=y){
                s+='0';
            }
            if(i!=a+1){
                s+='1';
            }
        }
    }
    else{
        int x=b/(a+1);
        int y=b%(a+1);
        rep(i,1,a+1){
            rep(j,1,x){
                s+='1';
            }
            if(i<=y){
                s+='1';
            }
            if(i!=a+1){
                s+='0';
            }
        }
    }
    cout<<s<<'\n';
}

G

数学 搜索 剪枝

把一个数变成他的数位乘积，表示一个数能执行的次数，称之为韧性。问在范围内找两个数的韧性和最大，并且不相等。

这个函数实际上之和一个数的数位组成的多重集有关，数位的排列无影响，再加上包含这两个数位，，太小了不可能是答案，所以如果暴力，只需枚举大小为，只包含的多重集个数，这方案数并不多，可以直接枚举。

具体复杂度估计，可以考虑这样的多重集个数，用隔板法来思考就是,18个球用8个隔板隔开，。

每次枚举出来一个多重集合，计算，由于只有量级，这是可以接受的。

接下来就是找是否存在一个，内有两个不同。可以发现内就有很多个不同的，而内最大的，从里取两个即可。并且由于这题只要求提交答案，不用在线跑这个搜索，我们完全可以本地跑搜索，慢一点也无所谓了。

实际上，还有剪枝，注意到如果一个多重集同时包含，乘起来最低位一定是0，也就是，做一轮就没了，肯定不是最优答案，所以的枚举是互斥的。并且合数的乘积可能可以用质数表示，可以先不枚举合数，所以我们需要枚举的就只有这两组，实际上这两组就能跑出来最优答案

H

堆/线段树

每次攻击会消灭一个点附近曼哈顿距离不超过2的所有点上的人，每次修改一个点的人数，问此时攻击哪个点能消灭的人数最多？

网格,询问，考虑每一行维护一个可以单点修，查最值得数据结构，可以是堆或者线段树，维护如果攻击，能消灭的人数，然后查询时枚举行，考虑每一行的最值。更新时，由于每次攻击只能覆盖到曼哈顿距离不超2的点，所以这次更新能影响答案的位置也只有附近曼哈顿距离不超过2的点。这只更新个点，没有必要线段树，直接堆就可以。

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
 
    vector<set<pii>>s(n + 1);
    vvi a(n + 1, vi(m + 1));
    vvi b(n + 1, vi(m + 1));
    rep(i, 1, n) {
        rep(j, 1, m) {
            cin >> a[i][j];
        }
    }
 
    rep(i, 1, n) {
        rep(j, 1, m) {
            rep(x, -2, 2) {
                int t = 2 - abs(x);
                rep(y, -t, t) {
                    int X = x + i;
                    int Y = y + j;
                    if (X < 1 || X > n || Y < 1 || Y > m)continue;
                    b[i][j] += a[X][Y];
                }
            }
//          cout<<b[i][j]<<' ';
            s[i].insert({b[i][j], j});
        }
//      cout<<'\n';
    }
 
    while (q--) {
        int x, y, z;
        cin >> x >> y >> z;
 
        rep(i, -2, 2) {
            int t = 2 - abs(i);
            rep(j, -t, t) {
                int X = x + i;
                int Y = y + j;
                if (X < 1 || X > n || Y < 1 || Y > m)continue;
                s[X].erase({b[X][Y], Y});
                b[X][Y] += z;
                s[X].insert({b[X][Y], Y});
            }
        }
 
        pii pos;
        int mx = 0;
        rep(i, 1, n) {
            auto it = *s[i].rbegin();
            if (it.fi > mx) {
                mx = it.fi;
                pos = {i, it.se};
            }
//          cout << i << ' ' << it.se << ' ' << it.fi << '\n';
        }
        cout << pos.fi << ' ' << pos.se << '\n';
    }
}

I

数学 搜索

扭蛋机有6种颜色，独立的抽三次，开始有6块钱，每一块都可以押一个颜色，最后某个颜色如果压中了，有一个筹码，倍率2，两个倍率3，三个倍率10，也可以留着钱不压。

问最后剩下的最大钱数（赚的钱+不压的钱）

状态空间并不大，直接爆搜。发现就是一块都不压是最优得，也就是这个游戏的期望收益是负的。这个也是很多游戏的经典诈骗结论，可以考虑这个结论

void solve() {
    cout<<"######";
}