A. 终结者

贪心DP

using namespace std;
int n, a[205], b[205], ans;
int solve(int x, int y) {
    int res = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] <= a[x] && b[i] >= a[x] || a[i] <= a[y] && b[i] >= a[y])
            res++;
    return res;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i], b[i] += a[i];
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++) ans = max(ans, solve(i, j));
    cout << ans;
    return 0;
}

# B. 田忌赛马

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

int n;
int a[100005], b[100005];

int calc(int *a, int *b) {
    int ans = 0;
    int la = 0, ra = n - 1, lb = 0, rb = n - 1;
    for (int i = 0; i < n; i++) {
        if (a[la] > b[lb]) {
            ans += 2;
            la++, lb++;
        } else if (a[ra] > b[rb]) {
            ans += 2;
            ra--, rb--;
        } else {
            ans += (a[la] == b[rb]);
            la++, rb--;
        }
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }
    sort(a, a + n);
    sort(b, b + n);
    printf("%d %d", calc(a, b), 2 * n - calc(b, a));
}

# C. 棋盘覆盖
- 很经典的问题，其实就是通过递归把大问题小化

#include<bits/stdc++.h>
#define M 305
using namespace std;
int mark[M][M]={0};
int id=0;
struct node{
	int x1,y1,x2,y2,x,y;
};
bool checkIn(node A,int x,int y){
	return (x>=A.x1&&x<=A.x2&&y>=A.y1&&y<=A.y2);
}
void dfs(int x1,int y1,int x2,int y2,int x,int y){
	if(x1==x2)return;
	node tmp[4];
	int ny=y1+(y2-y1+1)/2;
	int nx=x1+(x2-x1+1)/2;
	tmp[0]=(node){x1,y1,nx-1,ny-1,nx-1,ny-1};
	tmp[1]=(node){x1,ny,nx-1,y2,nx-1,ny};
	tmp[2]=(node){nx,y1,x2,ny-1,nx,ny-1};
	tmp[3]=(node){nx,ny,x2,y2,nx,ny};
	id++;
	for(int i=0;i<4;i++){
		if(checkIn(tmp[i],x,y)){
			for(int j=0;j<4;j++){
				if(j==i)continue;
				mark[tmp[j].x][tmp[j].y]=id;
			}
			tmp[i].x=x,tmp[i].y=y;
			break;
		}
	}
	for(int i=0;i<4;i++)
		dfs(tmp[i].x1,tmp[i].y1,tmp[i].x2,tmp[i].y2,tmp[i].x,tmp[i].y);
}
int main(){
	int K,x,y;
	scanf("%d %d %d",&K,&x,&y);
	dfs(1,1,1<<K,1<<K,x,y);
	for(int i=1;i<=(1<<K);i++,puts(""))
		for(int j=1;j<=(1<<K);j++)printf("%d ",mark[i][j]);
	puts("");
	return 0;
}

# D. 排座位(2)

#include <bits/stdc++.h>
#define int long long
#define N 3005
using namespace std;
const int mod = 1e9 + 7;
int n, fac[N], ans = 1;
string s[N];
void solve(int l, int r, int pos) {
    if (l == r)
        return;
    int cnt = 1, ll = l;
    for (int i = l; i <= r; i++) {
        if (s[i][pos] != s[ll][pos]) {
            solve(ll, i - 1, pos + 1);
            cnt++, ll = i;
        }
    }
    solve(ll, r, pos + 1);
    ans = ans * fac[cnt] % mod;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // cerr<<(&ed-&st)/1024.0/1024<<"\n";
    cin >> n;
    fac[0] = 1;
    for (int i = 1; i <= 27; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    for (int i = 1; i <= n; i++) cin >> s[i];
    sort(s + 1, s + n + 1), solve(1, n, 0);
    cout << ans;
    return 0;
}

E. 竞选班长

枚举 + 贪心

#include <bits/stdc++.h>
using namespace std;
int n, a[2005], b[2005], Min = 1e9;
vector<int> t[2005];
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 2; i <= n; i++) scanf("%d", &b[i]), t[a[i]].push_back(b[i]);
    for (int i = 2; i <= n; i++) sort(t[i].begin(), t[i].end());
    for (int i = t[1].size(); i <= n; i++) {
        int res = 0, cnt = t[1].size();
        priority_queue<int, vector<int>, greater<int> > c;
        for (int j = 2; j <= n; j++)
            if (t[j].size() >= i)
                for (int k = 0; k < t[j].size(); k++)
                    if (k <= t[j].size() - i)
                        res += t[j][k], cnt++;
                    else
                        c.push(t[j][k]);
            else
                for (int k = 0; k < t[j].size(); k++) c.push(t[j][k]);
        for (int j = 1; j <= i - cnt; j++) res += c.top(), c.pop();
        Min = min(Min, res);
    }
    printf("%d", Min);
    return 0;
}