差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest1 [2020/05/13 17:36]
jxm2001
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest1 [2021/07/11 10:01] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:contest1被移动至2020-2021:teams:legal_string:组队训练比赛记录:contest1
@@ 行 1: / 行 1: @@
+[[https://codeforces.com/gym/102569|比赛链接]]
 ====== 题解 ======
@@ 行 5: / 行 7: @@
 === 题意 ===
-这么定义一个数组的哈希值：每次从数组开头取出两个数，将后一个数减去前一个数得到的数值放入数组开头，如此重复，直到数组中只剩下一个数，最后这个数便为数组的哈希值。现在每次操作把一个区间的数加上一个值，要求输出每次操作后数组的哈希值。
+给定一个长度为$n$的数组，这么定义该数组的哈希值：每次从数组开头取出两个数，将后一个数减去前一个数得到的数值放入数组开头，如此重复，直到数组中只剩下一个数，最后这个数便为数组的哈希值。现在有$m$次操作，每次操作把一段区间的数加上$v$，要求输出每次操作后数组的哈希值
-显然数组的哈希值为/sum{/lef(-1/rig)^n}
+===题解===
+显然数组的哈希值为$\sum_{i=1}^n{\left(-1\right)^\left(n-i\right)\times a_i}$
+因此当区间左右端点奇偶性相同时对哈希值无贡献，奇偶性不同时如果区间左端点与$n$奇偶性相同则哈希值加$v$，否则减$v$
+时间复杂度$O\left(n+m\right)$
 ===== B. Bonuses on a Line =====
+=== 题意 ===
+数轴上有 $n$ 份奖金，每份奖金的坐标为 $x_i$ ，总共有 $t$ 秒的时间，每秒可走 $1$ 的距离。初始在原点 $0$ 位置，问最多能获得多少份奖金？
+=== 题解 ===
+先向某一方向跑，然后再折返跑向另一方向。例如先向负方向跑，在每份奖金处，利用二分查找，找到能够折返跑到正方向的奖金的最大份数即可。
+时间复杂度 $O\left(n\log n\right)$
+=== 代码 ===
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=200005;
+typedef long long ll;
+vector<ll>neg;
+vector<ll>pos;
+int main(){
+	ll n,t;
+	scanf("%lld %lld",&n,&t);
+	for(ll i=1;i<=n;i++){
+		ll x;
+		scanf("%lld",&x);
+		if(x<0) neg.push_back(-x);
+		else pos.push_back(x);
+	}
+	reverse(neg.begin(),neg.end());
+	neg.push_back(1e15);pos.push_back(1e15);
+	ll maxx=0;
+	for(ll i=0;i<neg.size()-1;i++){
+		if(t>=neg[i]) maxx=max(maxx,i+1);
+		ll left=t-2*neg[i];
+		ll p=upper_bound(pos.begin(),pos.end(),left)-pos.begin()-1;
+		if(p>=0) maxx=max(maxx,i+1+p+1);
+	}
+	for(ll i=0;i<pos.size()-1;i++){
+		if(t>=pos[i]) maxx=max(maxx,i+1);
+		ll left=t-2*pos[i];
+		ll p=upper_bound(neg.begin(),neg.end(),left)-neg.begin()-1;
+		if(p>=0) maxx=max(maxx,i+1+p+1);
+	}
+	printf("%lld",maxx);
+	return 0;
+}
+</code>
 ===== C. Manhattan Distance =====
+===题意===
+在直角坐标系中给定$n$整点$\left(-10^8\le x_i,y_i\le 10^8\right)$，可以得到$\frac{n\times \left(n-1\right)}{2}$个点对，将所有点对的哈密顿距离排序，要求输出第k大的哈密顿距离$\left(2\le n\le 100000,1\le k\le \frac{n\times \left(n-1\right)}{2}\right)$
+===题解===
+大概思路为二分答案$d$，统计哈密顿距离$\le d$的点对个数
+首先，将坐标系顺时针旋转$45$度，放大$\sqrt{2}$倍，所以所有点坐标变为$\left(x-y,x+y\right)$，与某个点哈密顿距离$\le d$转化为在以该点为中心的边长为$2d$的网格正方形中
+考虑用滑动窗口+树状树组统计答案，具体过程见代码
+时间复杂度$O\left(\log\left(4\times 10^8\right)  n\log n\right)$
+===代码===
+<code cpp>
+#include <iostream>
+#include <cstdio>
+#include <cstdlib>
+#include <algorithm>
+#include <cstring>
+#include <cctype>
+#define _for(i,a,b) for(int i=(a);i<(b);++i)
+#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
+#define mem(a,b) memset(a,b,sizeof(a))
+using namespace std;
+typedef long long LL;
+inline int read_int(){
+	int t=0;bool sign=false;char c=getchar();
+	while(!isdigit(c)){sign|=c=='-';c=getchar();}
+	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
+	return sign?-t:t;
+}
+inline LL read_LL(){
+	LL t=0;bool sign=false;char c=getchar();
+	while(!isdigit(c)){sign|=c=='-';c=getchar();}
+	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
+	return sign?-t:t;
+}
+#define lowbit(x) (x)&(-x)
+const int MAXN=1e5+5;
+struct Node{
+	int x,y;
+	bool operator < (const Node &b)const{
+		return x<b.x||(x==b.x&&y<b.y);
+	}
+}node[MAXN];
+int n,m,c[MAXN],Y[MAXN];
+LL k;
+void add(int pos,int v){
+	while(pos<=n){
+		c[pos]+=v;
+		pos+=lowbit(pos);
+	}
+}
+int query(int pos){
+	int ans=0;
+	while(pos){
+		ans+=c[pos];
+		pos-=lowbit(pos);
+	}
+	return ans;
+}
+LL Count(int d){
+	mem(c,0);
+	LL ans=0;
+	for(int i=1,j=1;i<=n;i++){
+		while(j<i&&node[i].x-node[j].x>d){
+			int pos=lower_bound(Y+1,Y+m,node[j].y)-Y;
+			add(pos,-1);
+			j++;
+		}
+		int pos1=upper_bound(Y+1,Y+m,node[i].y+d)-Y-1;
+		int pos2=lower_bound(Y+1,Y+m,node[i].y-d)-Y-1;
+		int pos3=lower_bound(Y+1,Y+m,node[i].y)-Y;
+		ans+=query(pos1)-query(pos2);
+		add(pos3,1);
+	}
+	return ans;
+}
+int main()
+{
+	n=read_int(),k=read_LL();
+	int x,y;
+	_rep(i,1,n){
+		x=read_int(),y=read_int();
+		node[i].x=x-y,node[i].y=x+y;
+		Y[i]=x+y;
+	}
+	sort(node+1,node+n+1);
+	sort(Y+1,Y+n+1);
+	m=unique(Y+1,Y+n+1)-Y;
+	int lef=1,rig=4e8,mid,ans=-1;
+	while(lef<=rig){
+		mid=lef+rig>>1;
+		if(Count(mid)<k)
+		lef=mid+1;
+		else{
+			ans=mid;
+			rig=mid-1;
+		}
+	}
+	cout<<ans;
+	return 0;
+}
+</code>
 ===== D. Lexicographically Minimal Shortest Path =====
@@ 行 17: / 行 183: @@
 ===== E. Fluctuations of Mana =====
+签到题
 ===== F. Moving Target =====
@@ 行 32: / 行 199: @@
 ===== M. Notifications =====
+签到题
 ====== 总结 ======

CVBB ACM Team

用户工具

站点工具

差别

页面工具