2026 海亮夏令营题单与知识点总结

	for(int i = 1;i <= k;i++){
		int x, y;cin >> x >> y;
		b[x][y] = -1;
		d[x + 1][y]++;
		d[x][y + 1]++;
		d[x - 1][y]++;
		d[x][y - 1]++;
		d[x + 1][y + 1]++;
		d[x - 1][y + 1]++;
		d[x + 1][y - 1]++;
		d[x - 1][y - 1]++;
	}

void bfs(int sx, int sy, int sz, int cnt) {
	queue<node> q;
    q.push({sx, sy, sz, cnt});
    v[sx][sy][sz] = 1;
    while (q.size()) {
        node u = q.front();
        q.pop();
        int x = u.x, y = u.y, z = u.z, cnt = u.cnt;
        v[x][y][z] = 0;
        if (x > n or y > n or z > n or x < 1 or y < 1 or z < 1)
            continue;
        if (u.cnt > ds[x][y][z])
            continue;
        ds[x][y][z] = u.cnt;
        if (!d[x + 1][y][z] and !v[x + 1][y][z]) {
            q.push({ x + 1, y, z, cnt + 1 });
            v[x + 1][y][z] = 1;
        }
        if (!d[x][y + 1][z] and !v[x][y + 1][z]) {
            q.push({ x, y + 1, z, cnt + 1 });
            v[x][y + 1][z] = 1;
        }
        if (!d[x - 1][y][z] and !v[x - 1][y][z]) {
            q.push({ x - 1, y, z, cnt + 1 });
            v[x - 1][y][z] = 1;
        }
        if (!d[x][y - 1][z] and !v[x][y - 1][z]) {
            q.push({ x, y - 1, z, cnt + 1 });
            v[x][y - 1][z] = 1;
        }
        if (!d[x][y][z + 1] and !v[x][y][z + 1]) {
            q.push({ x, y, z + 1, cnt + 1 });
            v[x][y][z + 1] = 1;
        }
        if (!d[x][y][z - 1] and !v[x][y][z - 1]) {
            q.push({ x, y, z - 1, cnt + 1 });
            v[x][y][z - 1] = 1;
        }
    }

void solve(string ss){
	stack<int> s;int cnt = 0;
	for(int i = 0;i < ss.size();i++){
		if(ss[i] == '('){
			cnt++;
		}
		if(ss[i] == ')'){
			cnt--;
			if(ss[i - 1] == '('){
				B[cnt]++;
			}
		}
	}int x = 0;
	for(int i = 0;i <= 5000000;i++){
		B[i] += x;
		x = B[i] / 2;
		B[i] %= 2;
//		cout << B[i];
	}
//	cout << endl;
}

	while(T--){
		scanf("%lld%lld", &n, &m);
		int x = 1.5 + sqrt(2.25 - 2 * (n - m));
//		printf("%lld\n", x);
		int ans = (((x*x)+5)*x/6 + (n-x-1)*(2*m-n+x+2)/2)%MOD;
		printf("%lld\n", ans);
	}

void dfs(int u, int root, bool flag) {
    dfn[u] = 1;
    dp[u][0] = 0;
    int mi = INT_MAX;
    for (auto v : adj[u]) {
        if (v == root)
            continue;
        dfs(v, root, flag);
        dp[u][0] += max(dp[v][1], dp[v][0]);
        mi = min(mi, max(dp[v][0], dp[v][1]) - dp[v][0]);
    }
	dp[u][1] = 1 + dp[u][0] - mi;
	if (flag && u == a[root]){
		dp[u][1] += mi;
	}
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        adj[a[i]].push_back(i);
    }
    int sum = 0;
    for (int x = 1; x <= n; x++) {
        if (!dfn[x]) {
            while (!vis[x]) {   //环 
                vis[x] = 1;
                x = a[x];
            }
            dfs(x, x, 0);      
//			cout << x; 
            int ans = max(dp[x][0], dp[x][1]);
            dfs(x, x, 1);
            sum += max(dp[x][0], ans);
        }
    }
    cout << sum;

	for(int i = 1;i <= n * 2;i++){
		int x, y;cin >> x >> y;
		ans += max(x, y);sum[i] = x + y;
	}
	sort(sum + 1, sum + 1 + n * 2);
	for(int i = 1;i <= n;i++){
		ans -= sum[i]; 
	} 
	cout << ans;

	for(int ii = 1;ii <= tot;ii++){
		bool i = ii % 2;
		for(int j = 0;j <= m;j++){
			dp[i][j][0] = dp[i][j][1] = 0;
		}
		for(int j = 0;j <= m;j++){
			ans[i][j][0] = ans[i][j][1] = zero;
			if(j >= c[num[ii]]){
				if(num[ii] != num[ii - 1]){
					int kk = dp[!i][j - c[num[ii]]][0] < dp[!i][j - c[num[ii]]][1] ? 1 : 0;
					dp[i][j][1] = dp[!i][j - c[num[ii]]][kk] + w[ii];
					ans[i][j][1] = ans[!i][j - c[num[ii]]][kk];
					add(i, j, 1, ii);
				}else{
					dp[i][j][1] = dp[!i][j - c[num[ii]]][1] + w[ii];
					ans[i][j][1] = ans[!i][j - c[num[ii]]][1];
					add(i, j, 1, ii);
				}
			}
			int kk = dp[!i][j][0] < dp[!i][j][1] ? 1 : 0;
			dp[i][j][0] = dp[!i][j][kk];
			ans[i][j][0] = ans[!i][j][kk];

	for(int j = 1;j <= k;j++){
		for(int i = 2;i <= n;i++){
			while(l <= r and dp[q[j - 1][r]][j - 1] <= dp[i - 1][j - 1]){
				r--;
			}q[j - 1][++r] = i - 1;
			while(l <= r and abs(d[i] - d[q[j - 1][l]]) > m){
				l++;
			}
			
//			cout << q[j-1][l] << ' ';
			dp[i][j] = max(dp[q[j - 1][l]][j - 1] + a[i], dp[i][j]);
//			cout << i << ' ' << j << ' ' << dp[i][j] << endl;
			ans = max(ans, dp[i][j]);
		}
	}

void mdy(int &p, int l, int r, int d) {
	t[++id] = t[p]; p = id;
	t[p].d++;
//	pushup(pp);
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    if (d <= mid)
        mdy(t[p].l, l, mid, d);
    else
        mdy(t[p].r, mid + 1, r, d);
}
int qry(int p, int q, int l, int r, int k) {
    if (l == r)
        return l;
    int mid = (l + r) >> 1;
    int lcnt = t[t[p].l].d - t[t[q].l].d;
    if (k <= lcnt)
        return qry(t[p].l, t[q].l, l, mid, k);
    else
        return qry(t[p].r, t[q].r, mid + 1, r, k - lcnt);
}

void mdy(int &p, int l, int r, int d, int v) {
	if (!p) p = ++id;
    if (l == r) {
        t[p].d += v;
        return;
    }
    int mid = (l + r) >> 1;
    if (d <= mid)
        mdy(t[p].l, l, mid, d, v);
    else
        mdy(t[p].r, mid + 1, r, d, v);
    pushup(p);
}
int tk(int p, int l,int r,int v){
	if(l == r) return l;
	int mid = (l + r) >> 1;
	if(v <= t[t[p].l].d) return tk(t[p].l, l, mid, v);
	else return tk(t[p].r, mid + 1, r, v - t[t[p].l].d);
}

	int cnt = 1, j = n;
	for(int i = j - 1;i >= 1;i--){
		while(b[i] > b[j]) i--;
		if(b[i] <= b[j] and i > 0){
			cnt++;j = i;
//			cout << i << endl;
		} 
	}

    for (int i = 1; i <= n; i++) { cin >> a[i]; tot += a[i]; }
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = tot; j >= a[i]; j--) 
            dp[j] |= dp[j - a[i]];
    for (int i = tot / 2; i >= 0; i--)
        if (dp[i]) { cout << tot - 2 * i << '\n'; return 0; }

		int o = 0, e = 0, cnt = 0;
		for(int i = 1;i <= n;i++){
			cin >> a[i];
			if(a[i] % 2 == 0) e += a[i];
			else{
				cnt++;
				o += a[i] - 1;
			}
		}
		if(cnt == 0) cout << e <<'\n';
		else cout << (int)((o + e) / cnt / 2) * 2 + 1 << '\n';
	}

	for(int i = n;i >= 1;i--){
		st[i] = tot;tot *= s[i];
	}
	for(int i = 0;i < tot;i++) cin >> b[i];
	for(int d = 1;d <= n;d++){
		for(int i = tot - 1;i >= 0;i--){
			if(i / st[d] % s[d]) b[i] -= b[i - st[d]];
		}
	}

	while(T--){
		int n, s, t;
		cin >> n >> s >> t;
		if(s == t) cout << 0 << '\n';
		else if((s | t) == (1 << n) - 1) cout << (s ^ t) << '\n';
		else cout << (s ^ ((1 << n) - 1)) + (t ^ ((1 << n) - 1)) << '\n';
	}

	for(int k = 1;k <= n + m - 2;k++){
		char mn = 'z' + 1;
		

		for(auto x : q){
			int i = x.fi, j = x.se;
			if(i < n) mn = min(mn, a[i + 1][j]);
			if(j < m) mn = min(mn, a[i][j + 1]);
		}
		
		nq.clear();
		
		for(auto x : q){
			int i = x.fi, j = x.se;
			
			if(i < n and a[i + 1][j] == mn and !vis[i + 1][j]){
				vis[i + 1][j] = 1;
				nq.push_back({i + 1, j});
			}
			
			if(j < m and a[i][j + 1] == mn and !vis[i][j + 1]){
				vis[i][j + 1] = 1;
				nq.push_back({i, j + 1});
			}
		}
		
		cout << mn;
		q = nq;
	}

void dfs(int u, int fa,int k){
	if(adj[u].size() == 0){
		dp[u] = k + 1;
		return ;
	}
	for(int v : adj[u]){
		if(v == fa) continue;
		dfs(v, u, k);
		dp[u] = max(dp[u], dp[v] - 1);
		if(dp[v] < 2) flag = 0;
	}
//	cout << u << ' ' << dp[u]<<'\n';
}
bool check(int k){
	flag = 1;
	memset(dp, 0, sizeof dp);
	dfs(1, 0, k);
	if(dp[1] > 0 and flag) return 1;
	else return 0;
}

	int ans = 0;

	for(int i = 0;i <= c;i++){
		int tmp = C(c, i) * fac[k - i] % MOD;

		if(i & 1){
			ans = (ans - tmp + MOD) % MOD;
		}else{
			ans = (ans + tmp) % MOD;
		}
	}

void exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

signed main() {
    int a, b, x, y;
    cin >> a >> b;
    exgcd(a, b, x, y);
    x = (x % b + b) % b;
    cout << x << endl;

bool check(int k){
	int tot = 0;
	for(int i = 1;i <= n;i++){
		if(a[i] - k >= 0) tot += a[i] - k;
		if(tot >= m) return 1;
	}
	return 0;
}

		int k = (yy - y) * (xx - x);
		
		f = min(f, w - f);
		
		int b = 0;
		if(x < f){
			b = (min(xx, f) - x) * (yy - y);
		}
		
		k += b;
		
		cout << w * h - k * (c + 1) << '\n';
	}

	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=-1;
	
	for(int i=0;i<len;i++){
		for(int j=0;j<=n;j++){
			for(int v=1;v<=i+1;v++){
				int l=i-v+1;
				if(sum[l][i]>j) continue;
				if(dp[l][j-sum[l][i]]>1000) continue;
				
				dp[i+1][j]=min(dp[i+1][j],
					dp[l][j-sum[l][i]]+1);
			}
		}
	}

void dfs(int id,long long sum[]){
	if(find_ans==1) return;
	if(id==1){
		bool flag=1;
		for(int i=1;i<=n;i++){
			if(sum[i]!=score[i]){
				flag=0;
				break;
			}
		}
		if(flag==1){
			find_ans=1;
		}
		return;
	}
	//branch 1
	for(int i=1;i<=n;i++){
//		if(i>1&&sum[i]==sum[i-1]) continue;
		long long nxt_sum=sum[i]*id;
		if(nxt_sum>score[i]) continue;
		if(score[i]%nxt_sum!=0) continue;
		sum[i]=nxt_sum;
		dfs(id-1,sum);
		sum[i]/=id;
		if(find_ans==1) return;
	}
	//branch 2
	dfs(id-1,sum);
}

		for(int j = 1;j <= m;j++){
			int st = max(2ll, (l + prime[j] - 1) / prime[j]);

			for(int i = st;i <= r / prime[j];i++){
				p[prime[j] * i - l] = 1;
			}
		}

		int cnt = 0;
		for(int i = l;i <= r;i++){
			if(!p[i - l]){
				a[++cnt] = i;
			}
		}

	for(int i = 1;i <= m;i++){
		cin >> a >> b;
		cnt += a / n;
		a %= n;
		if((a + x >= y and y > x) or ((a + x) % n >= y and (a + x) % n < x)) cnt++;
		x += a;x %= n;
		cnt += b / n;
		b %= n;
		if((b + y >= x and x > y) or ((b + y) % n >= x and (b + y) % n < y)) cnt++;
		y += b;y %= n;
	}

    int n, m;
    cin >> n >> m;
    
    int g = __gcd(n, m);
    int ans = (n + m) / g - 2;
    
    cout << ans;

void dfs2(int u, int fa){
	int m1 = 0, m2 = 0, v1 = 0;
	for(int v : adj[u]){
		if(v == fa) continue;
		int k = md[v] + 1;
		if(k > m1){
			m2 = m1;
			m1 = k;
			v1 = v;
		}else if(k > m2){
			m2 = k;
		}
	}

	for(int v : adj[u]){
		if(v == fa) continue;
		int k = (v == v1 ? m2 : m1);
		father[v] = max(father[u], k) + 1;
		dfs2(v, u);
	}
}

bool check(int x){
    for(int i = (int)node.size() - 1;i >= 0;i--){
        int u = node[i];
        int sum = 0, best = INF;

        for(auto [v, w] : g[u]){
            sum += cnt[v];
            sum = min(sum, m + 1);

            if(len[v] + w <= x){
                best = min(best, len[v] + w);
            }
        }

        if(g[u].empty()){
           
            cnt[u] = 1;
            len[u] = 0;
        }else if(best != INF){
          
            cnt[u] = sum;
            len[u] = best;
        }else{
   
            cnt[u] = min(m + 1, sum + 1);
            len[u] = 0;
        }
    }

    int sum = 0;

    for(int u : root){
        sum += cnt[u];
        if(sum > m) return 0;
    }

    return 1;
}

	int n, m;cin >> n >> m;
	if(m < 2) cout << 1;
	else cout << 0;
	for(int i = 2;i <= n;i++){
		if(i > m) cout << 0;
		else cout << 1;
	}

	for(int i = 1;i <= n;i++){
		int t = 1111111, j = i, tot = 7, cnt = 0;
		while(t){
			while(t * m <= j){
				j -= t * m;
				cnt += tot;
			}
			t /= 10;tot--;
		}
		if(j > 0) cout << -1 << ' ';
		else cout << cnt << ' ';
	}

    for(int i = 1;i <= m;i++){
        int x, y, z;
        cin >> x >> y >> z;
        a[x] += z;
        a[y] -= z;
    }

    int ans = 0;
    for(int i = 1;i <= n;i++){
        if(a[i] > 0) ans += a[i];
    }

    cout << ans / 10 << '.' << ans % 10;

void dfs(int u, int fa){
	for(int j = 0;j <= lmt;j++){
		dp[u][j] = dp[fa][j];
		if(j - w[u] >= 0){
			dp[u][j] = max(dp[u][j], dp[fa][j - w[u]] + v[u]);
		}
	}
	for(int j = 1;j <= lmt;j++){
		dp[u][j] = max(dp[u][j], dp[u][j - 1]);
	}
	if(u * 2 <= n && u * 2 <= 127) dfs(u * 2, u);
	if(u * 2 + 1 <= n && u * 2 + 1 <= 127) dfs(u * 2 + 1, u);
}

void solve(int now, int sumw, int sumv){
	if(now == cnt + 1){
		maxx = max(maxx, sumv + dp[ed][x - sumw]);
		return;
	}
	if(sumw + w[a[now]] <= x){
		solve(now + 1, sumw + w[a[now]], sumv + v[a[now]]);
	}
	solve(now + 1, sumw, sumv);
}