codeforces.com/contest/1649--补题

codeforces.com/contest/1649–补题

C. Weird Sum

题意：给定一个矩阵，矩阵每个点都有一个颜色，求每两个相同颜色的点之间的曼哈顿举例，曼哈顿距离=|x1-x2|+|y1-y2|

样例：

//input
2 3
1 2 3
3 2 1
1
2
3
4

//output
7
1
2

算法1：暴力 时间复杂度O($n^2$) – TLE

算法2：思维 O($2n$)

​ 所有对的曼哈顿距离，肯定是横坐标的曼哈顿距离+纵坐标的曼哈顿距离，所以我们可以分开来看，可以先看横坐标x，可以计算出当前点的当前点前面有j个点，所以当前点和他们的横坐标的曼哈顿距离就为 $j\ast x_i-(x_0+x_1+...+x_{j-1})$，这样只需要两次循环即可，时间复杂度由$n^2$降到2n

#include 
#include 
#include 
using namespace std;
typedef long long ll;
vector<pair<int,int>>ve[100005];//按颜色存储点，将矩阵上的点存到对应颜色的容器中
bool cmp1(pair<int,int>a1,pair<int,int>a2){//按照横坐标从小到大排序
	return a1.first<a2.first;
}
bool cmp2(pair<int,int>a1,pair<int,int>a2){//按照纵坐标从小到大排序
	return a1.second<a2.second;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	int r=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			int a;
			scanf("%d",&a);
			if(a>r)r=a;//存储总共有多少个颜色
			ve[a].push_back(make_pair(i,j));
		}
	}
	ll sum=0;
	for(int i=1;i<=r;i++){
		sort(ve[i].begin(),ve[i].end(),cmp1);//按横坐标排序
		ll s=0;
		for(int j=0;j<ve[i].size();j++){
			sum=sum+1ll*j*ve[i][j].first-s;//求横坐标的曼哈顿距离
			s=s+ve[i][j].first;
		}
		s=0;
		sort(ve[i].begin(),ve[i].end(),cmp2);//按纵坐标排序
		for(int j=0;j<ve[i].size();j++){
			sum=sum+1ll*j*ve[i][j].second-s;//求纵坐标的曼哈顿距离
			s=s+ve[i][j].second; 
		}
	}
	cout<<sum;//输出结果
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

D. Integral Array

题意：给定一个序列，求 序列中任何两个数，这两个数不一定非得是两个数，大数/小数（下取整）的结果一定要在序列中，问是否成立

样例：

//input
4
3 5
1 2 5
4 10
1 3 3 7
1 2
2
1 1
1
1
2
3
4
5
6
7
8
9
10

//output
Yes
No
No
Yes
1
2
3
4
5

题解：思维

​ 不能通过暴力，去找是否不成立，可以假设 存在一个不在序列中的数 t，使得$[t\ast a_i,t\ast (a_i+1)-1]\notin a$，则不成立，否则 成立，可通过前缀和 快速查询 区间内是否存在数字可快速求解。

#include 
using namespace std;
const int maxn=1e6+10;
int st[2*maxn];
int s[2*maxn];
int main(){
	int t;
	scanf("%d",&t);
	int n,c=0;
	while(t--){
		for(int i=0;i<=2*c;i++){
			st[i]=s[i]=0;
		}
		scanf("%d%d",&n,&c);
		for(int i=0;i<n;i++){
			int tmp;
			scanf("%d",&tmp);
			st[tmp]++;
		}
		bool flag=true;
		for(int i=1;i<=2*c;i++){
			s[i]=s[i-1]+st[i];//通过前缀和 快速判断 区间内 是否有 数字存在 
		}
		for(int i=1;i<=c;i++){//通过序列中的数 * 序列外的数 看结果是否依然在序列中 
			if(!st[i])continue;
			for(int j=1;i*j<=c;j++){//注意范围 
				if(st[j])continue;
				if(s[i*j-1]!=s[i*(j+1)-1])flag=false;//数组下标为 表达式的 注意表达式范围 否则 runtime error 
			}
		}
		if(flag)printf("Yes\n");
		else printf("No\n");
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34