首页 > 其他分享 >【题解】AT agc057A Antichain of Integer Strings

【题解】AT agc057A Antichain of Integer Strings

时间:2025-01-04 11:22:30浏览次数:6  
标签:mathbb ch fu 题解 mid agc057A Antichain define

记 \(f(x)\) 为最小的大于 \(x\) 的 \(y\),使得 \(x\) 是 \(y\) 的子串。易得:

\[f(x)=\min(10x,x+10^{|x|}) \]

其中 \(|x|\) 表示 \(x\) 的位数。

可以发现,\(f(x)\) 为一个严格单调递增的函数。

考虑贪心策略,显然选小的数不如选大的数优,因为小的数更有可能成为别的数的子串。于是,我们要求的其实就是这样一个集合 \(\mathbb{A}\),满足:

\[\mathbb{A}=\{x\in[l,r]\mid f(x)>r\} \]

因为 \(f(x)\) 是严格单增的,因此二分即可。

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
	char ch;\
	int fu=1;\
	while(!isdigit(ch=getchar()))\
		fu-=(ch=='-')<<1;\
	x=ch&15;\
	while(isdigit(ch=getchar()))\
		x=(x<<1)+(x<<3)+(ch&15);\
	x*=fu;\
}
#define int ll
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int pw10[]={
1,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000,
10000000000,
100000000000};
il int len(int x){
	int res=0;
	do{
		res++,x/=10;
	}while(x);
	return res;
}
il int f(int x){
	return min(x*10,x+pw10[len(x)]);
}
namespace cplx{
	bool end;
	il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
//	for(int i=1;i<=33;i++){
//		cout<<i<<" "<<f(i)<<"\n";
//	}
	int T;
	read(T);
	while(T--){
		int l,r,L,R;
		read(l)read(r);
		L=l,R=r;
		while(l<r){
			int mid=(l+r)>>1;
			if(f(mid)>R){
				r=mid;
			}
			else{
				l=mid+1;
			}
		}
		printf("%d\n",R-l+1);
	}
	return 0;
}
}
signed main(){return asbt::main();}

标签:mathbb,ch,fu,题解,mid,agc057A,Antichain,define
From: https://www.cnblogs.com/zhangxyhp/p/18651688

相关文章

  • 网卡丢包问题解决
    1、查看局域网内是否有MAC冲突;2、UDP丢包可以先增大协议栈缓存空间:接收端:echo2129999999>/proc/sys/net/core/rmem_maxecho2129999999>/proc/sys/net/core/rmem_default发送端:echo2129999999>/proc/sys/net/core/wmem_defaultecho2129999999>/proc/sys......
  • Luogu P4287 SHOI2011 双倍回文 题解 [ 紫 ] [ manacher ]
    双倍回文:回文子串结论的经典应用。结论先放本题最关键的结论:一个字符串本质不同的回文子串最多只有\(n\)个。考虑如何证明:假设我们一个一个地在当前字符串(黑色部分)的结尾加入字符(红色部分),那么会出现如下情况:显然,加入红色字符后,字符串中最多只可能新出现一个本质不同的回文......
  • P1309 [NOIP2011 普及组] 瑞士轮 题解
    P1309[NOIP2011普及组]瑞士轮题目大意:for(i<=r)让这2n个选手的成绩降序排序,第1-第2打,第3-第4打,......,第2n-1和第2n打i--i+1打,谁能打赢?谁的实力大谁就打赢了排序最快是2nlogn,所以上述暴力过程,时间复杂度是:R(2nlog2n+2n)=2e8超时了解释:为什么是......
  • 题解:AtCoder [ARC176D] Swap Permutation
    题意原题链接给定一个长度为\(n\)的排列\(p\),并执行以下操作\(m\)次:选择\(1\leqi<j\leqn\),交换\(p_i\)和\(p_j\)。定义一个序列\(p\)的权值为\(\sum_{i=1}^{n-1}|p_i-p_{i-1}|\)。求在\(\binom{n}{2}^m\)种可能的操作后,\(p\)的价值之和。答案对\(998244353\)......
  • 题解:CF1830A Copil Copac Draws Trees
    首先这道题肯定不能暴力枚举,我们要思考其他算法。我们可以给每一条边编一个号。然后从根开始遍历这棵树,当一条边的编号比他祖先到他祖先的祖先的那条边的编号还要小时,就说明顺序错了,要再等一轮。这个就简单了,直接dfs就行,注意答案要加\(1\)。#include<bits/stdc++.h>using......
  • 深入理解 Java Set 集合:原理、应用与高频面试题解析
    深入理解JavaSet集合:原理、应用与高频面试题解析在Java中,Set是一种重要的集合接口,用于存储不重复的元素。无论是在实际开发中,还是在面试场景中,Set都是一个高频的知识点。本篇文章将详细介绍JavaSet集合的基础知识、常见实现类、应用场景以及面试常考题,最后通过总结帮助......
  • 题解:CF2044D Harder Problem
    CF2044DHarderProblem思路构造一个\(1\simn\)都出现了一次的数列(这样每个数都是众数了),然后只要保证在数组\(a\)里面出现了的数在最前面就好了。AC代码#include<bits/stdc++.h>usingnamespacestd;#defineN200005longlongt,vis[N],cnt,n,a[N];intmain(){ cin......
  • 题解 - 出栈序列(2022.10上海月赛丙组T5)
    题目描述给定一个长度为几的、仅由小写字母组成的字符串,将其按序依次放入栈中。请问在所有可能的出栈序列中,字典序最小的出栈序列是多少?输入格式输入第一行,一个正整数几输入第二行,一个长度为几的字符串输出格式输出所有出栈序列中,字典序最小的出栈序列数据范围对......
  • 题解 - 机会成本(2022.9上海月赛丙组T2)
    题目描述明天有门考试,今晚只能复习一门课,请计算应该复习哪一门课,才能让所有考试的分数总和达到最大,如果选择复习第之门课,则这门课的考试分数为a;,若放弃复习第之门课,则这门考试的分数为6;。输入格式第一行:单个整数表示n第二行到第n+1行:每行两个整数表示a;......
  • 【题解】Luogu P7171 [COCI2020-2021#3] Selotejp
    注:题解中\(\operatorname{lsh}\),\(\operatorname{rsh}\),\(\operatorname{or}\)分别表示按位左移、按位右移、按位或,即c++语言中的<<,>>,|。我也是打上轮廓线DP了。设\(f_{x,y,S}\)表示当前在\((x,y)\)格子,前\(m\)个格子的状态为\(S\)时的最小花费。这里的状态是指......