列表

详情

NC20306. [SCOI2015]小凸解密码

描述

小凸得到了一个密码盘，密码盘被等分成N个扇形，每个扇形上有一个数字(0～9)，和一个符号（“+”或"*")密码盘解密的方法如下：
首先，选择一个位置开始，顺时针地将数字和符号分别记在数组A和数组C
解密的方法如下
B0=A0
当x>0时：
若Cx为“+”，Bx=(Ax+Ax-1)%10，注意：x-1是下标值
若Cx为“*”，Bx= (Ax×Ax-1)%10,注意：x-1是下标值
操作完成后，可以得到一个长度为n的数组B，然后以B0为起点将B数组顺时针写成一个环，解密就完成了，称得到的环为答案环。
现在小凸得到了一份指令表，指令表上有2种操作。
一种指令是修改操作，即改变原来密码盘上一个位置的数字和符号。
另一种指令是询问操作，具体如下：
首先从指令给出的位置开始完成解密，得到答案环。
答案环上会有一些0连在一起，将这些连在一起的0称为零区间，找出其中距离B0最远的那个零区间，输出这个距离。
零区问和B0的距离定义为：零区问内所有0到B0距离中的最小值。

输入描述

第1行包含2个整数n,m，代表密码盘大小和指令个数
接下来n行，每行包含1个整数和1个字符，按顺时针顺序给出了密码盘上的数组和符号
接下来m行，依次给出指令
每行第1个整数代表指令类型
若第1个墼数为1，代表本行对应指令为修改操作，之后依次有2个整数pos，num和1个字符opt，分别代表修改的位置，以及修改后该位置的数字和字符
若第1个整数为2，代表本行对应指令位询问操作，之后有1个整数pos，代表本次操作中解密的开始位置
密码盘上的位置标号为0到n-l
数据保证合法，即数据中0≤pos<N，0≤num≤9，opt为“+”或“*”

输出描述

对于每个询问操作1行，输出答案，若答案环上没有0，输出-1

示例1

输入: 

5 8
0 *
0 *
0 *
0 *
0 *
2 0
1 0 1 +
1 2 1 +
2 3
1 1 1 +
1 3 1 +
1 4 1 +
2 4

输出: 

0
2
-1

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 182ms, 内存消耗: 15544K, 提交时间: 2022-05-22 16:05:13 

#include<algorithm>
#include<cstdio>
#define I (J+1)
#define J (i+j>>1)
#define P (k<<1)
#define S (P^1)
using namespace std;
const int N=1e5+5;
int n,m,s,t,a[N];
char c[N];
struct node{
	int x,y,z,s1,s2,t1,t2;
	void pre(int i){
		x=y=i,z=1,s1=t1=i?-1:0,s2=t2=-1;
	}
}f[N*8];
node operator+(node a,node b){
	node c={a.x,b.y,a.z+b.z};
	int j=a.y||b.x?-1:0;
	if(b.s1==j)c.s1=a.s1,c.s2=a.s2;
	else
		c.s1=b.s1+a.z,c.s2=b.s2!=j?b.s2+a.z:a.s1;
	if(a.t1==j)c.t1=b.t1,c.t2=b.t2;
	else
		c.t1=a.t1+b.z,c.t2=a.t2!=j?a.t2+b.z:b.t1;
	return c;
}
int cal(int i){
	int s=i%n,t=(s+n-1)%n;
	if(c[s]=='+')
		return(a[s]+a[t])%10;
	return(a[s]*a[t])%10;
}
void pre(int i,int j,int k){
	if(i==j)f[k].pre(cal(i));
	else
		pre(i,J,P),pre(I,j,S),f[k]=f[P]+f[S];
}
void vary(int s,int t,int i,int j,int k){
	if(i==j)f[k].pre(t);
	else{
		if(s<I)vary(s,t,i,J,P);
		if(s>J)vary(s,t,I,j,S);
		f[k]=f[P]+f[S];
	}
}
node ask(int s,int t,int i,int j,int k){
	if(s==i&&j==t)return f[k];
	if(t<I)return ask(s,t,i,J,P);
	if(s>J)return ask(s,t,I,j,S);
	return ask(s,J,i,J,P)+ask(I,t,I,j,S);
}
void vary(int s,int t){vary(s,t,0,n*2-1,1);}
node ask(int s,int t){return ask(s,t,0,n*2-1,1);}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;++i)
		scanf("%d %c",a+i,c+i);
	pre(0,n*2-1,1);
	while(m--){
		scanf("%d%d",&s,&t);
		if(s==1){
			scanf("%d %c",a+t,c+t);
			vary(t,cal(t));
			vary(t+n,cal(t));
			vary(t+1,cal(t+1));
			if(t!=n-1)
				vary(t+n+1,cal(t+1));
		}else{
			vary(t,a[t]);
			node a=ask(t,t+(n-1)/2),b=ask(t+(n+1)/2,t+n-1);
			if(~b.t1&&(a.x||b.t1))++b.t1;
			if(~b.t2&&(a.x||b.t2))++b.t2;
			printf("%d\n",a.y||b.x?max(a.s1,b.t1):max(max(a.s2,b.t2),min(a.s1,b.t1)));
			vary(t,cal(t));
		}
	}
}

上一题

© 2025 nowcoder.com