D. 统计区间

题意：

给定一个长度为N的序列A和一个整数K。问A中有多少个连续子序列的和等于K

思路：

求pre[i]-pre[j]=k的方案数转换成pre[i]-k=pre[j]的方案数，统计pre[j]的数量

题解：

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

const int N=2e5+5;
long long n,k,a[N],pre[N],ans;

int main(){
	freopen("tjqj.in","r",stdin);
	freopen("tjqj.out","w",
stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pre[i]=pre[i-1]+a[i];
	}

	unordered_map<long
 long,long long> mp; 
	for(int i=0;i<=n;i++){
		ans+=mp[pre[i]-k];
		mp[pre[i]]++;
	}
	cout<<
ans;
	return 0;
}

E. 旅行

题意：

Z国有N个城市，编号为1到N，以及M条道路，编号为1到M。道路i从城市Ai通向城市Bi，但不能从城市Bi反向到达城市Ai。小Z计划进行一次旅行，她可以从某个城市出发，沿着零条或多条道路行走，最终到达某个城市。 有多少对城市可以作为小z旅行的起点和终点？我们区分顺序不同的城市对（即(a,b)和(b,a)视为不同）。

思路：

循环遍历所有的点作为起点，把能走到的点都标记，以i为起点进行路径标记，遍历当前点u能够到达的所有节点j，并以j为新的起点继续出发，输出

题解

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

const int N=2005; 
int n,m,a,b,ans,v[N];
vector<int> adj[N];

void dfs(int l){
	if (v[l]) return;
	v[l]=1;
	for (int i=0;i<adj[l].size();i++){
        int j=adj[l][i];
		dfs(j);
	}
}

int main(){
	freopen("lx.in","r",stdin);
	freopen("lx.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		adj[a].push_back(b);
	}
	for(int i=1;i<=n;i++){
		memset(v, 0, sizeof v);
		dfs(i);
		for (int j=1;j<=n;j++) if(v[j]) ans++;
	}
	cout<<ans;
	return 0;
}

F. 我讨厌非整数

题意：

给定一个长度为N的正整数序列A。共有(2^N - 1)种方式选择A中的一个或多个元素。其中有多少种选择的平均值是整数？请将答案对998244353取模后输出。