\(\color{white}{\mathbb{名之以：海棠}}\)

考场 \(t1\) 看见题意非常简单，觉得可能是个简单题

暴力算出几个小样例右端点右移的时候左端点都是单调右移的，以为具有单调性，于是想了一系列维护单调性的方法，然而拍大样例的时候挂的很惨（又一次前一个半小时啥也没干）

看 \(t2\)，时间不够了写了个 \(floyd\) 直接跳

\(t3\) 发现部分分很多，认真思考两个特殊点，一个小时找到了能得 \(50\) 分的做法

最后 \(t1\) 又加了个退火，在暴力能跑出来的范围内正确性还可以

出分发现 \(t1\) 捆绑测试所以 \(1\) 分也没骗到，\(t3\) 没考虑到逆序对可能很多没模爆了 \(long\) \(long\)，又惨挂 \(35\)

这次难度分析再次出现重大失误，事实证明 \(t2\) 是最可做的

以后应该增加开题前思考分析时间，并且部分分也应进行对拍

A. 送花

首先当右端点右移时最优坐决策点不是单调的，因为加入一个数后可能使一个之前位置的贡献变小，那么原来依赖其贡献的最优区间可能左端点左移更优

线段树维护区间的贡献

对于右端点右移一位的时候，将这个值上上一个位置到上一个位置的值加当前贡献，上一个位置到这个位置的值减当前贡献，然后线段树维护区间最大值即可

B. 星空

首先是距离的转化，先把坐标系旋转45度

类似于曼哈顿转切比雪夫距离，这道题的距离是 \(min(|x_1-x_2|,|y_1-y_2|)\)

先处理出距离为零的，用并查集合并在一起，然后按 \(x\) 和 \(y\) 分别排序后找最近点对即可

对于方案数相当于距离和答案相等的边两端点并查集里 \(size\) 值的乘积

代码实现 
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=1e5+5;

int n,xx,yy,fa[maxn],siz[maxn],ans=0x3f3f3f3f,ans1=0,cnt,tot;

pair<int,int>edge[maxn];

int read(){

	int x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(isdigit(ch)){

		x=x*10+ch-48;

		ch=getchar();

	}

	return x*f;

}

struct Node{

	int x,y,id;

}p[maxn];

bool cmpx(Node a,Node b){

	return a.x!=b.x?a.x<b.x:a.y<b.y;

}

bool cmpy(Node a,Node b){

	return a.y!=b.y?a.y<b.y:a.x<b.x;

}

int find(int x){

	return fa[x]==x?x:fa[x]=find(fa[x]);

}

void merge(int x,int y){

	x=find(x);

	y=find(y);

	if(x==y)return;

	fa[x]=y;

	siz[y]+=siz[x];

	return ;

}

void add(int x,int y){

	if(x>y)swap(x,y);

//	cout<<x<<" "<<y<<endl;

	edge[++cnt]=make_pair(x,y);

	return ;

}

signed main(){

	n=read();

	for(int i=1;i<=n;i++){

		xx=read();

		yy=read();

		p[i].x=xx+yy;

		p[i].y=xx-yy;

		fa[i]=i;

		siz[i]=1;

		p[i].id=i;

	}

//	for(int i=1;i<=n;i++){

//		cout<<"ppp "<<p[i].x<<" "<<p[i].y<<endl;

//	}

	sort(p+1,p+n+1,cmpx);

	for(int i=1;i<=n;i++){

		int j=i+1;

		while((p[j].x==p[i].x||p[j].y==p[i].y)&&j<=n){

			merge(p[i].id,p[j].id);

			j++;

		}

		if(j<=n)ans=min(ans,p[j].x-p[i].x);

	}

//	cout<<"hhh"<<endl;

	sort(p+1,p+n+1,cmpy);

	for(int i=1;i<=n;i++){

		int j=i+1;

		while((p[j].y==p[i].y||p[j].x==p[i].x)&&j<=n){

			merge(p[i].id,p[j].id);

			j++;

		}

		if(j<=n)ans=min(ans,p[j].y-p[i].y);

	}

	for(int i=1;i<=n;i++){

		int j=i+1;

		while((p[j].y==p[i].y||p[j].x==p[i].x)&&j<=n){

			j++;

		}

		if(j<=n&&p[j].y-p[i].y==ans)add(find(p[i].id),find(p[j].id));//cout<<"hhh "<<i<<" "<<j<<endl,

	}

	sort(p+1,p+n+1,cmpx);

	for(int i=1;i<=n;i++){

		int j=i+1;

		while((p[j].x==p[i].x||p[j].y==p[i].y)&&j<=n){

			j++;

		}

		if(j<=n&&p[j].x-p[i].x==ans)add(find(p[i].id),find(p[j].id));//cout<<"hhh "<<i<<" "<<j<<endl,

	}

//	for(int i=1;i<=n;i++){

//		if(fa[i]==i)cout<<"hhh "<<i<<" "<<siz[i]<<endl;

//	}

	sort(edge+1,edge+cnt+1);

	tot=unique(edge+1,edge+cnt+1)-edge-1;

	for(int i=1;i<=tot;i++){

		int x=edge[i].first;

		int y=edge[i].second;

//		cout<<"kkk "<<x<<" "<<y<<endl;

		ans1+=siz[x]*siz[y];

	}

	cout<<ans<<endl<<ans1;

	return 0;

}

C. 零一串

对于每个是 \(1\) 的位置处理一个长度为 \(T\) 的零一串，每一个是一的位置表示这一时刻这个 \(1\) 能不能左移，那么最终结果很容易能处理出来

考虑怎样从上一个位置转移过来：

对于第 \(i\) 个 \(1\) 如果可以在 \(j\) 的时刻左移，如果 \(i+1\) 个位置是紧邻的，那么它只能在 \(j+1\) 时刻左移，表达在 \(01\) 串上是右移一位

如果不紧邻，那么有几个 \(0\) 后面的可以移几次，相当于把 \(0!\) 串的前面几个 \(0\) 变成 \(1\)

发现只有首尾进行操作，用队列维护即可

对于第二问的答案，是在求每个 \(01\) 串第 \(i\) 的和

如果把矩阵拍在序列上，一定对应一段连续区间，用差分维护即可

代码实现 
#include<bits/stdc++.h>

using namespace std;

#define int long long

deque<int>q;

const int maxn=1e7+5;

const int mod=998244353;

char c[maxn];

int t,n,pos[maxn],cnt,all,dis[maxn],cf[maxn],sum[maxn],ans,num,ori;

bool ans1[maxn];

int po(int a,int b){

	int ans=1;

	while(b){

		if(b&1)ans=1ll*ans*a%mod;

		a=1ll*a*a%mod;

		b>>=1;

	}

	return ans;

}

signed main(){

//	freopen("shuju.in","r",stdin);

//	freopen("my.out","w",stdout);

	cin>>t;

	scanf("%s",c+1);

	n=strlen(c+1);

	for(int i=1;i<=n;i++){

		if(c[i]=='1')num++;

		else ori+=num;

	}

	ori%=mod;

	for(int i=1;i<=n;i++){

		if(c[i]=='1')pos[++cnt]=i;

	}

	for(int i=1;i<=t;i++){

		q.push_back(i);

	}

	for(int k=1;k<=cnt;k++){

		all++;

		if(q.back()+all>t&&q.size())q.pop_back();

		q.push_front(1-all);

		for(int j=1;j<=pos[k]-pos[k-1]-1&&q.size();j++){

			cf[q.front()+all]++;

			cf[min(cnt-k+q.front()+all+1,t+1)]--;

			q.pop_front();

		}

		dis[k]=t-q.size();

		ans1[pos[k]-dis[k]]=1;

	}

	for(int i=0;i<=t;i++){

		if(i)sum[i]=(sum[i-1]+cf[i])%mod;

		ori+=sum[i];

		ori%=mod;

		ans^=(po(233,i)*ori%mod);

	}

	for(int i=1;i<=n;i++)cout<<ans1[i];

	cout<<endl<<ans;

	return 0;

}

\(\color{white}{\mathbb{知否，知否，应是绿肥红瘦。}}\)

最新文章

  1. 使用的 SQL Server 版本不支持数据类型“datetime2”.
  2. HDU 2717 Catch That Cow （bfs）
  3. 慕课网-安卓工程师初养成-3-2 Java中的算术运算符
  4. objective-c 中的关联介绍
  5. 匹配“is outside location”
  6. JavaScript当中的eval函数
  7. Nodejs的运行原理-libuv篇
  8. 认识 WebService
  9. Kibana-4.6.6 marvel插件license过期重新注册
  10. 枚举类 enum，结构体类 struct
  11. 猪年设计素材：一波免费猪猪icon已为你备好
  12. sql join 语句的小总结
  13. xdg-open命令智能打开各种格式的文件
  14. java通过poi编写excel文件
  15. 《deep sort》复现过程
  16. 白话 Ruby 与 DSL 以及在 iOS 开发中的运用
  17. web前端切图处理
  18. 马婕 2014年MBA，mpacc备考 报刊宣读1 中国的电子商务（转）
  19. Gradle入门（6）：创建Web应用项目
  20. Input Size VS Time Complexity

热门文章

  1. PHP：字符串转数组，数组转字符串；字符串截取、替换、查找
  2. 论文笔记：（CVPR2019）Relation-Shape Convolutional Neural Network for Point Cloud Analysis
  3. 小技巧 | Get 到一个 Web 自动化方案，绝了！
  4. CF877B Nikita and string TJ
  5. Java方法02——定义与调用
  6. Java基础——变量与常量及命名规范
  7. 跟Waf斗智斗勇的一天
  8. 得到、微信、美团、爱奇艺APP组件化架构实践
  9. 为什么npm install 经常失败
  10. GitHub自动化部署(CD) asp.net core 5.0 项目(免费空间)