D

没啥好说的，考虑加法取模的性质

from math import gcd
a = input()
b = int(input())
r = 0
for i in a:
    r = r * 10 + int(i)
    r %= b
print(gcd(r , b))

E

跑dijkstra

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 505;
int n;
int mp[N][N], dis[N][N];
bool vis[N][N];

struct node {
    int x, y, st;
    bool operator < (const node& b)const {
        return st > b.st;
    }
};
priority_queue<node>q;
int step[4][2] = { 1,0,-1,0,0,1,0,-1 };

void dij() {
    q.push({ 1,1,mp[1][1] });
    memset(dis,0x3f,sizeof dis);
    dis[1][1] = mp[1][1];
    while (!q.empty()) {
        auto now = q.top();
        q.pop();
        if (vis[now.x][now.y])continue;
        vis[now.x][now.y] = true;

        for (int i = 0; i < 4; i++) {
            int dx = now.x + step[i][0];
            int dy = now.y + step[i][1];

            if (dx > 0 && dx <= n && dy > 0 && dy <= n && !vis[dx][dy]) {
                
                dis[dx][dy] = max(mp[dx][dy], dis[now.x][now.y]);
                q.push({ dx,dy,dis[dx][dy] });
            }
        }
    }
}


int main(void)
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> mp[i][j];
    dij();
    cout << dis[n][n];
    return 0;
}

F

区间和最值线段树 上模版

#include<bits/stdc++.h>
#define lt i<<1
#define rt i<<1|1
#define int long long
using namespace std;
const int N = 5e5 + 5;
int n, w[N], q;
struct segment_tree {
	int l, r, sum;
	int lx, rx, sx;
	int ln, rn, sn;
}tr[N * 4];

void pushup(int i)
{
	tr[i].sum = tr[lt].sum + tr[rt].sum;
	tr[i].lx = max(tr[lt].lx, tr[lt].sum + tr[rt].lx);
	tr[i].rx = max(tr[rt].rx, tr[rt].sum + tr[lt].rx);
	tr[i].sx = max(max(tr[lt].sx, tr[rt].sx), tr[rt].lx + tr[lt].rx);

	tr[i].ln = min(tr[lt].ln, tr[lt].sum + tr[rt].ln);
	tr[i].rn = min(tr[rt].rn, tr[rt].sum + tr[lt].rn);
	tr[i].sn = min(min(tr[lt].sn, tr[rt].sn), tr[rt].ln + tr[lt].rn);
}

void build(int i, int l, int r)
{
	tr[i] = { l,r,w[l],w[l],w[l],w[l],w[l],w[l],w[l]};
	if (l == r)return;

	int m = l + r >> 1;

	build(lt, l, m);
	build(rt, m + 1, r);
	pushup(i);
}

segment_tree query(int i, int l, int r)
{
	if (l <= tr[i].l && tr[i].r <= r)
		return tr[i];

	int mid = tr[i].l + tr[i].r >> 1;
	if (l > mid)return query(rt, l, r);
	else if (r <= mid)return query(lt, l, r);
	else {
		segment_tree ltr = query(lt, l, r),rtr=query(rt,l,r),ans;
		ans.sum = ltr.sum + rtr.sum;
		ans.lx = max(ltr.lx, ltr.sum + rtr.lx);
		ans.rx = max(rtr.rx, rtr.sum + ltr.rx);
		ans.sx = max(max(ltr.sx, rtr.sx), rtr.lx + ltr.rx);

		ans.ln = min(ltr.ln, ltr.sum + rtr.ln);
		ans.rn = min(rtr.rn, rtr.sum + ltr.rn);
		ans.sn = min(min(ltr.sn, rtr.sn), rtr.ln + ltr.rn);
		return ans;
	}
}

signed main(void)
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int l, r;
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> w[i];
	build(1, 1, n);
	cin >> q;
	while (q--) {
		cin >> l >> r;
		segment_tree res = query(1, l, r);
		cout << max(abs(res.sx), abs(res.sn))<<'\n';
	}
	return 0;
}