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

思路： 求S[i]-S[j]=k的方案数转换成S[i]-k=S[j]的方案数，统计S[j]的数量

题解：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long n,m,k;
long long a[200005],s[200005];
int main(){ 
	//freopen("tjqj.in","r",stdin);
	//freopen("tjqj.out","w",stdout);
	cin>>n>>k;
	s[0]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];//前缀和
	}
	unordered_map<ll , ll > mp;//定义
	ll ans=0;
	for(int i=0;i<=n;i++){
		ll x=s[i]-k;
		ans+=mp[x];
		mp[s[i]]++;
	}
	cout<<ans;
	
	
	return 0;
}

T4

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

思路 递归遍历全部城。 满足条件则计数 题解

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>c[2010];
bool v[2010];
void x(int u){// u：当前节点
	if(v[u])return;// 判断节点已经走过
	v[u]=1;//没走，标记一下
	for(int i=0;i<c[u].size();i++){// 遍历当前点u
		int j=c[u][i];
		x(j);
	}
};
int main(){
	freopen("lx.in","r",stdin);
	freopen("lx.out","w",stdout);
	int n,m,s=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		c[a].push_back(b);
	}
  // 循环遍历所有的点，能走到的点标记
	for(int i=1;i<=n;i++){
		memset(v,0,sizeof v);
		x(i);
		for(int j=1;j<=n;j++)if(v[j])s++;
	}// 以i为起点标记
	cout<<s;
	return 0;
}