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

「杂题乱刷2」CF1301C

时间:2024-09-06 18:25:24浏览次数:14  
标签:数字 ll re 杂题 sum CF1301C define

怎么没有二分的题解啊,写一篇。

题目链接

CF1301C Ayoub's function

解题思路

发现我们可以将问题转化成将 \(n - m\) 个 \(1\) 分成 \(m\) 份,设第 \(i\) 份的数字之和为 \(sum_i\),则这样的分配方案的贡献为 \(\frac{n \times (n+1)}{2} - \sum_{i=1}^{n} sum_i^2\)。

容易发现要使得这样的贡献最小,你选择的不同的每份数字和的个数一定不超过 \(2\)。

因此你可以通过简单的数学来计算出这两种数字的取值,至于两种数字的数量可以直接二分。

单组测试时间复杂度 \(O(\log m)\)。

参考代码

#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll i=a;i<=b;i++)
#define forr(i,a,b) for(re ll i=a;i>=b;i--)
#define forll(i,a,b,c) for(re ll i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(re ll i=a;i>=b;i-=c)
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
ll _t_;
void _clear(){}
ll n,m;
ll ans;
void solve()
{
	ans=0;
	_clear();
	cin>>n>>m;
	if(m==0)
	{
		cout<<0<<endl;
		return ;
	}
	if(n==m)
	{
		cout<<(n+1)*n/2<<endl;
		return ;
	}
	ll last=n-m;
	ll num=last/(m+1);
//	cout<<"number:"<<num<<endl;
	ll L=0,R=m+1;
	while(L<R)
	{
		ll Mid=(L+R+1)/2;
		if(Mid*num<=last)
			L=Mid;
		else
			R=Mid-1;
	}
	ll _0=L,_1=last-L*num;
	_0-=_1;
//	cout<<L<<":"<<_0<<' '<<_1<<endl;
	cout<<(n+1)*n/2 - (_0*(num+1)*num/2 + _1*(num+2)*(num+1)/2)<<endl;
}
int main()
{
	IOS;
	_t_=1;
 	cin>>_t_;
	while(_t_--)
		solve();
	QwQ;
}

标签:数字,ll,re,杂题,sum,CF1301C,define
From: https://www.cnblogs.com/wangmarui/p/18400804

相关文章

  • 杂题总结
    杂题总结记号约定不难注意意味着我在初见的时候想到了难以注意意味着我没有注意到P8421[THUPC2022决赛]rsraogpsP8421[THUPC2022决赛]rsraogps-洛谷|计算机科学教育新生态(luogu.com.cn)首先套路性扫描线,然后这个问题就变成增量构造。不难注意不知怎么......
  • 「杂题乱刷2」CF862D
    简单题。题目链接CF862DMahmoudandEhabandthebinarystring解题思路首先我们可以发现,字符串的第一个字母不是\(1\)就是\(0\),因此我们可以容易花费\(2\)次询问来找到数字\(0\)或数字\(1\)所在的一个位置。然后,显然的,我们以先找到的数字为\(0\)为例,那么我们就......
  • 「杂题乱刷2」CF862C
    怎么题解区里都没有随机化的题解啊/jy。于是就有了这篇题解。题目链接CF862CMahmoudandEhabandthexor解题思路思路非常简单。首先容易发现在\(n=1\)时,直接构造一个\(x\)这个数即可。其次我们考虑\(n=2\)的情况,由于异或的基本性质,我们可以得出当\(x=0\)......
  • 「杂题乱刷2」CF1493C
    题目链接K-beautifulStringsCF1493C解题思路首先,如果原字符串是合法的直接输出原字符串即可。然后我们考虑一个最简单的暴力,你枚举第一个你构造的字符串比原串大的字符的位置,再枚举这个字符,然后后面的肯定是从后往前贪心放即可,在此不再赘述。这样的复杂度是\(O(|S|^2\tim......
  • 「杂题乱刷2」CF1567D
    duel到的。题目链接CF1567D解题思路发现在越高的数位上,你获取的利益就会越大。因此你肯定是每次将尽可能多的数分到最高的数位上是最优的。但是你会发现,有可能你这样分数位后后面的数就分不到权值了,你只需要保证去掉当前分掉的权值之后,剩下可以分的权值不小于还剩下没分到......
  • 8 月杂题记
    AT_joisc2017_c题目描述:过于复杂,略。答案明显具有单调性。考虑二分答案。有一个很自然的想法,没点燃的要向正在燃的靠近,且一定以最大速度走\(T\)秒。对于一个区间\([L,R]\),满足让它能用一个点燃的互相点燃。有一个条件为\(X_r-X_l\le2\times(r-l)\timesv\time......
  • 「杂题乱刷2」CF1183E & CF1183H
    vp到的。题目链接CF1183ESubsequences(eazyversion)CF1183HSubsequences(hardversion)解题思路考虑动态规划。设\(dp_{i,j}\)表示考虑到字符串前\(i\)个字符中选取的字符长度为\(j\)的不同的子序列数量。于是我们就有以下转移:\(dp_{i,j}=dp_{i-1,j}+dp_{......
  • 2024年8月杂题
    P3226[HNOI2012]集合选数很巧妙,原问题不好做,转化成矩阵上选择不相邻数字的方案,变成了我们熟悉的问题。[ARC068F]Solitaire难。题目的条件告诉我们最后队列里呈现“V”字形。如何计算删数的方案??找到合法方案的约束条件,用DP去计数,构造过程,都很难。[ARC068E]SnukeLine胡......
  • 杂题 Solution 速通 #1
    [ICPC2021NanjingR]AncientMagicCircleinTeyvat设\(f_x\)表示钦定至少有\(x\)条边的四元子图个数,由容斥我们有一条边都没有的子图个数是\(f_0-f_1+f_2-f_3+f_4-f_5+f_6\),而所有边都有的个数就是\(f_6\)。作差之后只需要求\(f_0,f_1,f_2,f_3,f_4,f_5\)。子图计数只......
  • 网络流部分题目及杂题选做
    网络流网络流初探A.【例题1】求最大流P3376模板。B.卖猪问题SP4063&&P4638Solution[trick]:网络流有时间顺序要求的考虑分层图,优化建图的思路很妙。D.危桥通行P3163Solution正常按照题意建边,危桥建边权为\(1\)的双向边,普通的桥建边权为\(inf\)的双向边,源点向......