Reincarnation

正因为梦易碎，才格外美好。

ZROI - 2023noip十连测附加赛3

发表于 分类于 ，
本文字数： 8.2k 阅读时长 ≈ 7 分钟

再见了，所有的正如 。

邓老师邓明扬出的题。

题面

对第三题题意的补充

任意时刻指的是：每一次标记了 后对所有的 都要进行判断，而判断里面的计算只考虑已经被标记的位置。

题解

代码

A. 小好吃说鬼话

titie:AC Code
 
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
// ----- Eternally question-----
// Problem: A. [2020提高组十连测day4]小好吃说鬼话
// Contest: ZROI - 23 noip附加赛 day3
// URL: http://zhengruioi.com/contest/1504/problem/1564
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-11-16 08:26:30
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=t?-1:1;
}
template<class T,class ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void write(bool x){ putchar(x?'1':'0'); }
inline void write(char c){ putchar(c); }
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10,MAXC=27;
const int Inf=0x3f3f3f3f;
char S[MAXN],T[MAXN];
int Lens,Lent;
int Dp[2][MAXN];
struct Segment_tree
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	struct Segment
	{ int l,r,val,cov; }Tr[MAXN<<2];
	inline void pushUp(int p){ Tr[p].val=std::min(Tr[ls].val,Tr[rs].val); }
	inline void upDate(int p,int c){ Tr[p].val=Tr[p].cov=c; }
	inline void pushDown(int p)
	{
		if(Tr[p].cov==-Inf) return ;
		upDate(ls,Tr[p].cov),upDate(rs,Tr[p].cov);
		Tr[p].cov=-Inf;
	}
	void build(int p,int l,int r)
	{
		Tr[p].l=l,Tr[p].r=r,Tr[p].cov=-Inf;
		if(l==r) return ;
		int mid=(Tr[p].l+Tr[p].r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		pushUp(p);
	}
	void modifyCov(int p,int l,int r,int c)
	{
		if(l<=Tr[p].l&&Tr[p].r<=r) return upDate(p,c);
		pushDown(p);
		int mid=(Tr[p].l+Tr[p].r)>>1;
		if(l<=mid) modifyCov(ls,l,r,c);
		if(mid<r) modifyCov(rs,l,r,c);
		pushUp(p);
	}
	int queryMin(int p,int l,int r)
	{
		if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
		pushDown(p);
		int mid=(Tr[p].l+Tr[p].r)>>1,res=Inf;
		if(l<=mid) checkMin(res,queryMin(ls,l,r));
		if(mid<r) checkMin(res,queryMin(rs,l,r));
		return res;
	}
	void modify(int l,int r,int c){ if(l<=r) modifyCov(1,l,r,c); }
	int query(int l,int r){ return l>r?Inf:queryMin(1,l,r); }
}Tr;
int premin[MAXN];
int main()
{
	scanf("%s%s",S+1,T+1);
	Lens=std::strlen(S+1),Lent=std::strlen(T+1);
	if(Lens<Lent)
	{
		std::swap(Lens,Lent);
		char tmp[MAXN];
		std::memcpy(tmp,S,sizeof(S));
		std::memcpy(S,T,sizeof(T));
		std::memcpy(T,tmp,sizeof(tmp));
	}
	if(Lens-Lent>50) return puts("-1"),0;
	std::memset(Dp,0x3f,sizeof(Dp));
	for(int i=1;i<=Lens;++i) Dp[1][i]=i-1+(S[i]!=T[1]);
	for(int j=2;j<=Lent;++j)
	{
		int op=j&1;
		premin[std::max(1,j-50)-1]=Inf;
		for(int i=std::max(1,j-50);i<=j+50&&i<=Lens;++i)
		{
			Dp[op][i]=Dp[op^1][i]+1,premin[i]=Dp[op^1][i]-i;
			if(i!=std::max(1,j-50)) checkMin(premin[i],premin[i-1]);
		}
		for(int i=std::max(1,j-50);i<=j+50&&i<=Lens;++i) checkMin(Dp[op][i],premin[i-1]+i-1+(S[i]!=T[j]));
	}
	int ans=Inf;
	for(int i=Lent;i<=Lens;++i) checkMin(ans,Dp[Lent&1][i]+(Lens-i));
	write(ans>50?-1:ans,'\n');
	return 0;
}
/*

*/

B. 小好吃很呆滞

AC Code
 
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int B=1e9;
int n,pw[12]={1,10,100,1000,10000,100000,1000000,10000000,100000000};
bool flg;
//考虑计算对数
//Q=(Z-z)/(Z+z)
//ln Z-ln z=ln(Z/z)=ln(1+Q)-ln(1-Q)=F(Q)=2[Q+{1/3}Q^3+{1/5}Q^5...}
//Z=2,z=1 -> ln2=F(1/3)
//Z=1024,z=1000 -> 10ln2-3ln10=F(3/253)
struct bnum{//900位有效数字 
	ll a[102];
	ll& operator [](int x){
		return a[x];
	}
	friend bnum operator +(bnum a,bnum b){
		bnum c;
		for(int i=0;i<100;i++) c[i]=a[i]+b[i];
		for(int i=0;i<100;i++) if(c[i]>B) c[i+1]++,c[i]-=B;
		return c;
	}
	friend bool operator <(bnum a,bnum b){
		for(int i=99;~i;i--) if(a[i]^b[i]) return a[i]<b[i];
		return 0;
	}
	friend bnum operator *(bnum a,bnum b){
		bnum c;memset(c.a,0,sizeof(c.a));
		for(int i=0;i<100;i++)
		for(int j=100-i;j<100;j++){
			c[j+i-100]+=a[i]*b[j];
			if(c[j+i-100]>=B) c[j+i-99]+=c[j+i-100]/B,c[j+i-100]%=B; 
		}
		for(int i=0;i<100;i++) if(c[i]>=B) c[i+1]+=c[i]/B,c[i]%=B;
		if(c[99]*10<B){
			for(int i=99;i;i--) c[i]=(c[i]*10+c[i-1]/(B/10))%B;
			c[0]=c[0]*10%B;
		}
		return c;
	}
}u,v,w,k1,k2,k3,ans,x,l,r;
int main()
{
	scanf("%d",&n);
	k1[0]=1,k2[0]=3;
	u[99]=2e8,v[99]=8e8,x[99]=1e8;
	for(int i=0;i<n;i++) l[99-i/9]=r[99-i/9]=r[99-i/9]+pw[8-i%9];
	r[99-(n-1)/9]+=pw[8-(n-1)%9];
	while(x<l){
		w=u*v,k3=k1+k2;
		if(w<u){
			u=w,k1=k3;
			while(x*u<r){
				x=x*u,ans=ans+k1;
				if(l<x) break;
			}
		}
		else v=w,k2=k3;
	}
	for(int i=99;~i;i--){
		if(flg)
		for(int j=8;j;j--) if(ans[i]<pw[j]) putchar('0');
		if(ans[i]) flg=1;
		if(flg) printf("%lld",ans[i]);
	}
	/*if(n==2) printf("50");
	if(n==3) printf("143");
	if(n==5) printf("10627");
	if(n==8) printf("31379594");
	if(n==13) printf("2277292670320");*/
	return 0;
}

C. 小好吃在摸鱼

AC Code
 
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// ----- Eternally question-----
// Problem: C. [2020提高组十连测day4]小好吃在摸鱼
// Contest: ZROI - 23 noip附加赛 day3
// URL: http://zhengruioi.com/contest/1504/problem/1566
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-11-15 14:42:50
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e4+10;
int N,K,p[MAXN],ans[MAXN];
int Id[MAXN],Tot,pre[MAXN],nxt[MAXN];
bool Vis[MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,K);
	for(int i=1;i<=N;++i) read(p[i]),Id[++Tot]=i;
	for(int k=1;Tot;++k)
	{
		std::memset(Vis,0,sizeof(Vis)),
		std::memset(nxt,0,sizeof(nxt));
		int cnt=0;Id[Tot+1]=N;
		for(int i=1;i<=Tot;++i) nxt[Id[i]]=Id[i+1],pre[Id[i]]=Id[i-1];
		for(int i=N;i;--i)
			if(nxt[p[i]])
			{
				if(!Vis[p[i]]) ans[p[i]]=k,Vis[pre[p[i]]]=Vis[nxt[p[i]]]=1;
				pre[nxt[p[i]]]=pre[p[i]],nxt[pre[p[i]]]=nxt[p[i]];
			}
		for(int i=1;i<=Tot;++i) if(!ans[Id[i]]) Id[++cnt]=Id[i];
		Tot=cnt;
	}
	for(int i=1;i<=N;++i) write(ans[i],' ');
	return 0;
}
/*

*/
相关文章