T3集会

题目描述:

有N个人住在一条数轴上.第i个人住在坐标Xi处.你需要举办一个所有N个人都必须参加的集会.集会可以在任意整数坐标处举行.如果你选择在坐标P处举行集会，第i个人将花(Xi−P)^2点体力来参加集会.求出N个人必须花费的最小总体力点数.

解决方案:

对于每个可能的P值，计算所有人到P点的距离的平方，然后将这些平方值相加，得到该P值下的总体力花费。‌比较所有P值下的总体力花费，找到其中的最小值。

正确代码:

#include<bits/stdc++.h>
using namespace std;
int a[111];
int main(){
	//freopen("jihui.in","r",stdin);
	//freopen("jihui.out","w",stdout);
	int n,ans=100000000,x=0,y=111;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		x=max(x,a[i]);
		y=min(y,a[i]);
	}
	for(int i=y;i<=x;i++){
		int s=0;
		for(int j=0;j<n;j++) s+=pow(a[j]-i,2);
		ans=min(s,ans);
	}
	cout<<ans;
	return 0;
}

错误原因:

算法不对，我原来算P用的是把所有项加起来x2.

T4统计区间

题目描述：

给定一个长度为N的序列A=(A1,A2,…,AN)和一个整数K。 问A中有多少个连续子序列的和等于K？换句话说，有多少对整数(l,r)满足以下所有条件？1≤l≤r≤N左边公示表示求Al∼Ar的和=K

约束条件

• $1≤N≤2×10^5$
• $∣Ai∣≤10^9$
• $∣K∣≤10^9×10^6$
• 输入中的所有值都是整数。

主要使用思想：

1.前缀和 2.桶

解决方案:

枚举区间右端点，求有几个左端点满足$Sr−Sl−1=k$

正确代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+10;
ll a[N],b[N],n,k;
int main(){
	freopen("tjqj.in","r",stdin);
	freopen("tjqj.out","w",stdout);
	cin>>n>>k;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		b[i]=b[i-1]+a[i];
	}
	unordered_map<ll,ll> m;
	ll s=0;
	for(ll i=0;i<=n;i++){
		s+=m[b[i]-k];
		m[b[i]]++;
	}
	cout<<s<<endl;
	return 0;
}

T5旅行

问题描述

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

约束条件

• $2≤N≤2000$
• $0≤M≤min(2000,N(N−1))$
• $1≤Ai,Bi≤N$
• $Ai≠Bi$
• $(Ai,Bi)$各不相同。
• 输入中的所有值均为整数。

主要使用思想：

1.深度优先搜索 2.图论 3.标记

正确代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
vector<int> adj[2010];
bool vis[2010];
void dfs(int u) // u即表示当前节点
{
	if (vis[u]) return; // 当前节点已经走过
	vis[u] = 1; // 之前没走过，现在走了，标记一下
	for (int i = 0; i < adj[u].size(); i++)
	{
      int j = adj[u][i];
  		dfs(j);
	}
}
int main()
{
	int n, m, ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;  // a --> b
		adj[a].push_back(b);
	}
	// 循环遍历所有的点作为起点，把能走到的点都标记
	for (int i = 1; i <= n; i++)
	{
		memset(vis, 0, sizeof vis);
		dfs(i);  // 以i为起点进行路径标记
		for (int j = 1; j <= n; j++)
			if (vis[j]) ans++;
	}
	cout << ans;
	return 0;
}

注：所有freopen已注释