统计区间

题意：

给定一个字符串A求，有多少对整数(l,r)满足1<=l<=r<=N;并且Al~Ar=k;

思路:

正常思路使用三个for循环会超时，使用使用使用哈希表与区间和替换两个for循环。将时间复杂度降低至O（N）.在输入时求出区间和，在哈希表创建时需要用无序哈希表。 //无序哈希表数据定义：unordered_map<下标类型，数据类型> 表名

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6;
long long n,k,cnt,ans,sum;
long long a[N],s[N],p[N];
unordered_map <long long ,long long> mp;//定义哈希表
int main(){
	freopen("tjqj.in","r",stdin);
	freopen("tjqj.out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	for(int i=0;i<=n;i++){
		sum+=mp[s[i]-k];
		mp[s[i]]++;
	}
	cout<<sum;
	return 0;
}

旅行

题意：

沿着零条或多条道路行走，最终到达某个城市，问多少对城市可以作为小z旅行的起点和终点。

思路:

循环遍历所有的点作为起点，把能走到的点都标记，以i为起点进行路径标记。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> adj[2010];
bool vis[2010];
void dfs(int u){
	if(vis[u]) return;
	vis[u]=1;
	for (int i=0;i<adj[u].size();i++){
		dfs(adj[u][i]);//递归遍历
	}
}
int main(){
	int n,m,ans=0;
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		adj[a].push_back(b);//输入
	}
	for (int i=1;i<=n;i++){
		memset(vis,0,sizeof vis);//将vis赋值为0
    //（注意使用memset函数只能将数组赋值为0，1与极大值）
		dfs(i);
		for(int j=1;j<=n;j++){
			if(vis[j]) ans++;
		}
	}
	cout<<ans;
	return 0;
}