首页 > 其他分享 >「杂题乱刷」CF1759F

「杂题乱刷」CF1759F

时间:2024-05-23 15:20:21浏览次数:29  
标签:CF1759F ++ ll long lst mp 杂题 define

题目链接

CF1759F All Possible Digits(luogu)

CF1759F All Possible Digits(codeforces)

题意简述

有一个长度为 \(n\) 的 \(p\) 进制数,你需要求出至少通过几次操作才可以让 \(0 \sim p - 1\) 这 \(p\) 个数字都至少出现过一遍(包括中间过程)。

解题思路

我们很容易就能发现答案是具有单调性的,也就是说,如果操作 \(x\) 次是合法的,那么操作 \(x + 1\) 次也一定是合法的。

然后我们还可以发现一个性质,就是答案一定小于 \(p\),因为每一次操作都会使最后一位数字变化,所以操作 \(p - 1\) 次最后一位数字会变化 \(p\) 次,因此这个性质是正确的。

于是我们可以直接二分最少的操作次数即可,这里我选择使用分讨数字操作后是否进位的方式来进行二分。

参考代码

#include<bits/stdc++.h>
using namespace std
//#define map unordered_map
#define forl(i,a,b) for(register long long i=a;i<=b;i++)
#define forr(i,a,b) for(register long long i=a;i>=b;i--)
#define forll(i,a,b,c) for(register long long i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(register long long i=a;i>=b;i-=c)
#define lc(x) x<<1
#define rc(x) x<<1|1
//#define mid ((l+r)>>1)
#define cin(x) scanf("%lld",&x)
#define cout(x) printf("%lld",x)
#define lowbit(x) (x&-x)
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define ll long long
#define ull unsigned long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
ll t;
ll n,m;
ll a[110],b[110];
bool check(ll Mid)
{
	forl(i,0,n)
		a[i]=b[i];
	if(Mid+a[n]>=m)
	{
		map<ll,ll>mp;
		forl(i,1,n)
			mp[a[i]]++;
		ll pd=0;
		Mid-=m-a[n];
		ll lst=a[n]-1;
		a[n]=0,a[n-1]++;
		if(n-1==0)
			pd=1;
		forr(i,n-1,1)
		{
			if(a[i]==m)
			{
				a[i]=0,a[i-1]++;
				if(i==1)
					pd=1;
			}
		}
		if(pd)
			forl(i,0,n)
				mp[a[i]]++;
		else
			forl(i,1,n)
				mp[a[i]]++;
		while(mp[lst])
			lst--;
		return lst<=Mid;
	}
	else
	{
		map<ll,ll>mp;
		forl(i,1,n)
			mp[a[i]]++;
		ll lst=m-1;
		while(mp[lst])
			lst--;
		ll nxt=0;
		while(mp[nxt])
			nxt++;
//		cout<<Mid<<":"<<lst-a[n]<<endl;
		if(nxt<a[n])
			return 0;
		return max(0ll,lst-a[n])<=Mid;
	}
}
void solve()
{
	cin>>n>>m;
	forl(i,1,n)
		cin>>a[i],b[i]=a[i];
	ll L=0,R=m;
	while(L<R)
	{
		ll Mid=(L+R)/2;
		if(check(Mid))
			R=Mid;
		else
			L=Mid+1;
	}
	cout<<L<<endl;
}
int main()
{
	IOS;
	t=1;
	cin>>t;
	while(t--)
		solve();
	QwQ;
}

标签:CF1759F,++,ll,long,lst,mp,杂题,define
From: https://www.cnblogs.com/wangmarui/p/18208530

相关文章

  • 「杂题乱刷」CF1973D
    链接算简单题。你发现最大值肯定可以用\(n\)次查出来。然后可以证明\(ans\le\frac{n}{k}\)。总次数为\(n+\frac{n}{k}\timesk\le2n\)。代码:点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打c......
  • 「杂题乱刷」AT_abc354_f
    大家一起来做下这个典题。链接(at)链接(luogu)我们很容易可以想到处理前后缀的最长上升子序列的长度,然后容易\(O(n\log_2n)\)预处理。做完了。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要......
  • 「杂题乱刷」洛谷 P10467
    题目链接P10467[CCC2007]SnowflakeSnowSnowflakes解题思路字符串哈希板子题。思路就是我们给每个数列的所有排列都哈希一个值,然后判断是否有不同的数列的哈希值相同,如果有,就输出Twinsnowflakesfound.,否则就输出Notwosnowflakesarealike.。参考代码这里使用双哈......
  • 「杂题乱刷」AT_abc211_e
    题目链接[ABC211E]RedPolyomino(luogu)[ABC211E]RedPolyomino(at)解题思路从第三个样例可以看出总的方案数一定很少,因此我们可以直接确定第一个被染色的格子后直接向外爆搜,搜到最后可以使用哈希判重,但光凭这样的话\(2\)秒钟肯定跑不过去,因此我们可以在搜索的过程中使用......
  • 「杂题乱刷」洛谷 P10468 兔子与兔子
    题目链接P10468兔子与兔子解题思路字符串哈希板子题。思路就是我们给字符串的每一个前缀和后缀都用一种特定的方式使其变为一个值,比如取一个乘数和模数,可以证明这样出错的概率极低。参考代码这里使用自然溢出三哈希。#include<bits/stdc++.h>usingnamespacestd;#defin......
  • 最优化杂题乱讲
    你校的最优化杂题乱讲。保证难度随机排序,使用mt19937生成题目序列。最优化问题往往使用贪心,dp,二分,最短路解决。其中贪心往往可以通过感性理解,凭借人类本能想到贪心方式,继而写出正解,但有些比较厉害的题目却需要进行严谨的证明,而且可能会推出与感性结论相差很大的结论。dp则......
  • 杂题选讲II
    CliqueConnectAT_abc352_e朴素的想法是按题意暴力建边跑最小生成树,发现一个联通块内的很多边是冗余的,可以相邻两点建边跑最小生成树即可。//author:yhy#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;usingPii=pair<LL,LL>;constLLkMaxN......
  • 杂题选讲I
    MUHandCubeWallsCF471D由于序列同时加\(x\),该序列的差分数组不变,所以求出\(a,b\)的差分数组跑kmp或哈希。书柜题目描述:有\(A,B\)两种书排成的序列,序列长度为\(n\),两种书高度分别为\(h_A,h_B\),\(q\)次询问每次给定一段区间,你需要移除一些书使得剩下的书严格递增......
  • 5月杂题
    1.CF1805F2SurvivaloftheWeakest(hardversion)先对\(a\)排序。先想想F1,可以发现难点在于值域很大,但你发现我们可以把所有数减掉\(a_1\),如果还剩\(x\)个操作就把答案加上\(a_12^x\)即可。每次一操作完就减,这样你可以发现序列中的最大值不会增大,这就做完了。考虑F......
  • 「杂题乱刷」AT_abc096_d
    对下脑电波。题目链接(luogu)题目链接(at)发现我们可以找出所有\(x\)当且仅当\(x\)为质数且\(x\bmod5=3\),这样任意五个数加起来就必定为合数了。代码:点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题......