2026年编程兔冬令营集训第二场作业

1、前缀和 2、最短路径

1、一维前缀和定义b[i]=sum(a[1]~a[i])，则有sum(a[l]~a[r]) = b[r]-b[l-1]
#include<bits/stdc++.h>
using namespace std;
long long a[100005], sum[100005];
int main(){
	int n,q,l,r;
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		sum[i]= sum[i-1]+a[i];//求前缀和
	}
	cin>>q;
	while(q-->0){
		cin>>l>>r;
		cout<<sum[r]-sum[l-1]<<endl;//快速求区间和
	}
	return 0;
}

2、二维前缀和定义：构建前缀和数组：对于二维矩阵a，定义前缀和数组sum[i][j]表示从矩阵左上角(1,1)到位置(i,j)的矩形区域内所有元素的和，其递推公式为：
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j]

查询子矩阵和：若要查询以(x1,y1)为左上角、(x2,y2)为右下角的子矩阵的元素和，公式为：
sum(x2,y2,x1,y1) = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]


#include<bits/stdc++.h>
using namespace std;
long long a[1005][1005], sum[1005][1005];
int main(){
	int n,m,q,x1,y1,x2,y2;
	scanf("%d%d%d",&n,&m,&q); //输入较多，使用scanf 
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%lld",&a[i][j]);
			sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];
		}
	}

	while(q-->0){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		long long s =sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
		printf("%lld\n",s);//输出较多，使用printf 
	}
	return 0;
}

3、异或性质 a^a =0,a^a^b=b,异或前缀和定sum[i]=a[1]…^…a[i])，则有xor(a[l]~a[r]) =sum[r]^sum[l-1] 
#include<bits/stdc++.h>
using namespace std;
long long a[5005];
int main(){
	long long i,j,n,ans=0;
	cin>>n;
	for(i=1;i<=n;++i) {
		cin>>a[i];
		a[i] = a[i]^a[i-1];//异或前缀和
	}
	for(i=1;i<=n;++i)
		for(j=i;j<=n;++j){
			ans=max(ans, a[j]^a[i-1]);//枚举i~j,快速求区间异或和
		}
	cout<<ans<<endl;
	return 0;
}
4、异或性质 a^a =0,a^a^b=b;a^b=c相当于a=c^b异或前缀和定sum[i]=a[1]…^…a[i])，则有xor(a[l]~a[r]) =sum[r]^sum[l-1]，要使得xor(a[l]~a[r]) =sum[r]^sum[l-1]=k，则需要sum[l-1]^k=sum[r]，也就是sum[l-1]=sum[r]^k，对于每一个r只需要找到最靠近的l就可。
同时应用到动态规划，假设dp[i]表示从第一个数到第i个数可以划分的区间数量的最大值。则有dp[r] = max(dp[r-1],dp[l-1]+1)。
#include<bits/stdc++.h>
using namespace std;
long long a[500005];
long long dp[500005];
map<long long,long long> mp;//记录sum[i]与i的映射关系
int main(){
	long long i,j,n,k,t,ans=0;
	cin>>n>>k;
	dp[0] = 0;
	mp[0] = 0;
	for(i=1;i<=n;++i) {
		cin>>a[i];
		a[i] = a[i]^a[i-1];//前缀异或和
		t= a[i]^k;//t=sum[l-1]=sum[r]^k
		dp[i] = dp[i-1];
		if (mp.find(t)!=mp.end()){//找到最靠近的j就可
			j=mp[t];
			dp[i] = max(dp[i], dp[j]+1); 
		}
		mp[a[i]] = i;//更新前缀和映射
		ans = max(ans, dp[i]);
	}
	
	cout<<ans<<endl;
	return 0;
}

5、单点到多点的最短距离，dijkstra 算法处理带非负权图，使用优先队列处理priority_queue，贪心思想每次扩展总距离最短的点。
#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<long long, long long>> pq;//从大到小排序，可以取负数(从小到大)
vector<pair<long long, long long>> vc[100005];//边权图
pair<long long, long long>  p;
long long dis[100005];//出发点到每个点的最短距离
int main(){
	long long i,j,n,m,s,k,t,ans=0,vi,ui,wi;
	//cin>>n>>m>>s;
	scanf("%lld%lld%lld",&n,&m,&s);
	memset(dis,-1,sizeof(dis));
	dis[s] =0;
	//建立边的关系,注意是有向边 
	for(i=0;i<m;++i){
		//cin>>vi>>ui>>wi;
		scanf("%lld%lld%lld",&vi,&ui,&wi);
		vc[vi].push_back(make_pair(ui,wi));
		//vc[ui].push_back(make_pair(vi,wi));
	}
	pq.push(make_pair(0,s));
	while(pq.size()>0){//dijkstra 算法模板
		p = pq.top(); wi=-p.first;vi=p.second;
		pq.pop();
		//选出当前剩余中距离最短的点来进行扩展 
		if (wi==dis[vi]){
			for(i=0;i<vc[vi].size();++i){
				p = vc[vi][i]; ui=p.first; wi = p.second;
				if (dis[ui] == -1 || dis[ui]> dis[vi]+wi){
					dis[ui] = dis[vi]+wi;
					pq.push(make_pair(-dis[ui],ui));
				}
			}
		}
	}
	for(i=1;i<=n;++i) printf("%lld ",dis[i]); 
	printf("\n");
	return 0;
}


6、不论经过多少轮交换，交换的总价是Va-Vb+交换次数(思考一下为什么？）。所以交换次数越少越好，这时候可以使用队列queue来替换优先队列处理priority_queue（思考一下为什么？）。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n,m,s,t,v[N];
vector<int> e[N];
queue<pair<int,int> > q;//交换次数，每次权值都为1
bool vis[N];
int main() {
	cin >> n >> m >> s >> t;
	for(int i = 0;i<n;i++) cin >> v[i];
	for(int i = 0;i<m;i++) {
		int u,v;
		cin >> u >> v;
		e[u].push_back(v);
	}
	q.push({s,0});
	while(!q.empty()) {
		int u = q.front().first;
		int st = q.front().second;
		q.pop();
		if(u == t) {
			cout << st + v[t] - v[s];
			return 0;
		}
		for(auto v : e[u]) {
			if(!vis[v]) {
				vis[v] = true;
				q.push({v,st+1});
			}
		}
	}
	cout << "No solution";
	return 0;
}
7、由于离开时间必须是 k 的整数倍，可以将时间对 k 取模，将问题转化为 分层图最短路径问题。定义状态 (r, u)，表示在模 k 余数为 r 的时刻到达节点 u 的最早时间。
对于每条边 (u, v, a)，假设当前在 u 的时刻为 T（模 k 余数为 cur），需要等待到不小于 a 且模 k 余数为 (cur+1) mod k 的时刻才能通过这条边。到达 v 的时刻为 T + 1 + 等待时间。

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

// 定义节点结构体，用于优先队列
struct Node {
    int v;    // 节点编号
    int w;    // 到达该节点的实际时间
    int k;    // 时间模 k 的余数
    // 重载 < 运算符，用于优先队列（小顶堆）
    bool operator <(const Node &b) const {
        return w > b.w; // 注意：这里反向定义，使得实际时间小的优先级高
    } 
};

const int N = 1e4 + 5;     // 最大节点数
const int INF = 0x3f3f3f3f; // 无穷大
const int K = 110;         // k 的最大值（100+10）
vector<Node> g[N];         // 邻接表存图，每个元素是 {v, a_i}（这里用Node但只用了v和w，注意w是开放时间）
int dis[K][N];             // dis[i][j]：在模k余i的时刻到达节点j的最早时间
bool vis[K][N];            // 标记数组，记录状态是否已访问

void Dijkstra(int k) {
    priority_queue<Node> pq; // 优先队列（小顶堆）
    pq.push({1, 0, 0});      // 初始状态：在余数0时刻到达节点1，实际时间为0
    memset(dis, 0x3f, sizeof(dis)); // 初始化距离为无穷大
    dis[0][1] = 0;                 // 初始状态距离为0

    while (!pq.empty()) {
        int cur = pq.top().k;      // 当前状态的余数
        int u = pq.top().v;        // 当前节点
        pq.pop();
        if (vis[cur][u]) continue; // 如果已访问，跳过
        vis[cur][u] = true;        // 标记为已访问

        // 遍历从u出发的所有边
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].v;     // 邻居节点
            int a = g[u][i].w;     // 该边的开放时间
            int next = (cur + 1) % k; // 下一步的余数（因为通过边需要1单位时间）

            int t = dis[cur][u];   // 当前实际时间
            // 如果当前时间t小于开放时间a，需要等待
            if (t < a) {
                // 计算需要等待的k的倍数：ceil((a - t) / k)
                int wait = (a - t + k - 1) / k * k;
                t += wait;
            }
            // 通过边后，到达v的时间为 t+1
            if (dis[next][v] > t + 1) {
                dis[next][v] = t + 1;
                pq.push({v, t+1, next});
            }
        }
    }
}

int main() {
	freopen("bus.in","r",stdin);
	freopen("bus.out", "w",stdout);
    int n, m, k;
    cin >> n >> m >> k;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        // 将边加入邻接表：从u到v，开放时间为w
        g[u].push_back({v, w}); // 这里Node结构体的k字段未使用（默认为0）
    }
    Dijkstra(k);
    // 输出答案：在余数0时刻到达n的最早时间
    if (dis[0][n] == INF) cout << -1;
    else cout << dis[0][n];
    return 0;
}