牛客小白月赛23

---

B-阶乘

题目描述

给定一个正整数 ${p}$。
求一个最小的正整数 ${n}$，使得 ${n!}$是${p}$的倍数。

输入描述

第一行输入一个正整数${T}$表示测试数据组数。
接下来${T}$行，每行一个正整数${p}$。

输出描述

输出${T}$行，对于每组测试数据输出满足条件的最小的${n}$。

示例1

输入

4
1
2
4
8
输出
1
2
4
4

备注

$T \leqslant 10^3, p \leqslant 10^9$

思路

如果对于任意$p$的质因子$i$，$i$的个数是$q$，总有，$x!$中有超过$q$个质因子$i$，那么$x!$就是$p$的倍数。
可以采用二分，每一次$\text{check}$枚举所有$p$的质因子，看此时的答案是否符合条件。计算质因子$i$的个数时，可以将$x!$看成$x$个数相乘，每隔$i^k$个数字一定会出现一个$i$的倍数，计算$\sum \limits_{k=1}^{\infty}\lfloor \frac{x}{i^k}\rfloor$即为$x!$所含质因子$i$的个数（当$\lfloor \frac{x}{i^k}\rfloor$就可以停止迭代）。

代码

#include<iostream>
#include<map>
#define ll long long
using namespace std;
ll n,p;
map<ll,ll>prime_factor;
//分解质因数
void divide()
{
	ll i;
	for(i=2;i*i<=p;i++)
	{
		while(p%i==0)
		{
			p/=i;
			//统计每个质因子的个数
			prime_factor[i]++;
		}
	} 
	if(p>1) prime_factor[p]++;
}
void init()
{
	map<ll,ll>e;
	swap(e,prime_factor);
}
bool check(ll x)
{
	ll cnt;
	auto it=prime_factor.begin();
	while(it!=prime_factor.end())
	{
		ll temp=x;
		//枚举所有质因子
		ll i=it->first;
		cnt=0;
		while(temp)
		{
			//统计x!中包含质因子i的个数  
			cnt+=temp/i;
			temp/=i;
		}
		//判断
		if(cnt<it->second) return false;
		it++;
	}
	return true;
}
void solve()
{
	init();
	cin>>p;
	ll l=1,r=p;
	divide();
	ll ans;
	//二分
	while(l<=r)
	{
		int mid=l+r>>1;
		if(check(mid))
		{
			//记录答案
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	cout<<ans<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

C-完全图

题目描述

在图论的数学领域，完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。
现在给定一个包含 ${n}$个顶点的完全图，你可以删掉图中的一些边，但是删掉的边不能超过 ${m}$ 条，请问删去边之后的图最多能有几个连通分量？

输入描述

第一行包含一个数字 ${T}$，表示测试数据组数。
接下来 ${T}$行，每行两个正整数${n}$,${m}$，中间用空格隔开。

输出描述

输出 ${T}$ 行，每行一个整数表示答案。

示例1

输入
2
5 1
5 5
复制
1
2
备注
$1\leqslant T\leqslant 10000 , 1 \leqslant n,m \leqslant 10^{18}$

思路

连通分量越多，需要删的边越多，这种单调的关系显然可以用二分解决。
找找规律，初始给一张$n$个节点的完全图，每个节点的度都为$n-1$，有$1$个连通分量；这时，选择一个节点与主图割裂，删掉与之相连的$n-1$条边后得到$2$个连通分量；接着又在大图中选择一个节点，删掉与之相连的$n-2$条边后得到$3$个连通分量……可得到规律，要获得$x$个连通分量，需要删除的边数为$(n-1)+(n-2)+\dots [n-(x-1)]=\sum\limits_{i=1}^{x-1}(n-i)=\frac{(2n-x)(x-1)}{2}$。
二分最多能够存在的连通分量$x$，计算需要删除的边数$\frac{(2n-x)(x-1)}{2}$，若需要删除的边数还小于等于$m$，则移动左指针；否则移动右指针。

代码

#include<iostream>
using namespace std;
long long n,m;
bool check(long long x)
{
	__int128 res;
	res=(n*2-(__int128)x)*((__int128)x-1)/2;
	if(res<=m) return true;
	else return false;
}
void solve()
{
	cin>>n>>m;
	long long l,r,ans;
	l=1;//最少有1个连通分量
	r=n;//最多存在n个连通分量
	while(l<=r)
	{
		long long mid=(l+r)/2;
		if(check(mid)) 
		{
			ans=mid;//记录答案
			l=mid+1;
		}
		else r=mid-1;
	}
	cout<<ans<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

后记

数据范围很大，用__int128。

E-A+B问题

题目描述

经典的A+B问题描述如下：
从标准输入流输入两个整数 $A$ 和 $B$，请你求出这两个数字的和。其中 $A$ 和 $B$ 都在$32$位有符号整数能存储的范围内。
下面是一份AC代码：

#include<iostream>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	cout<<a+b;
	return 0;
}

现在已知这个程序输出的结果是 $c$，请问有多少种可能的输入数据？

输入描述

一行，仅包含一个整数 $c$ ，这个整数的值在$32$位有符号整数的存储范围内。

输出描述

一个数，表示可能的输入数据的情况数。

示例1

输入
1
输出
4294967296
说明
以下输入数据都可以让该程序输出$1$
1 0
2 -1
-5 6
0 1
-2147483647 -2147483648
想要使上述程序输出$1$，总共有$4294967296$种可能的输入。

思路

有符号整数只是把最高位作为符号位而已，其真值仍然是一个在$\left[0,2^{32}\right)$的整数，也就是模$2^{32}$ 意义下的非负整数，即$(a\bmod 2^{32}+b\bmod 2^{32})\bmod 2^{32}=c$，所以无论$c$是多少，枚举$a \in \left[0,2^{32}\right)$，都能得到对应的$b$，所以答案总是$2^{32}$。

代码

#include<iostream>
using namespace std;
void solve()
{
	int c;
	cin>>c;
	cout<<(1LL<<32);
}
int main()
{
	solve();
	return 0;
}

H-奇怪的背包问题增加了

题目描述

有一个容量为$2^{30}$的背包，和$m$件物品，第$i$件物品的体积为$c_i$，你需要从中选出若干件，使得选出的物品的体积恰好等于背包容量。这些物品有一个奇怪的特性，那就是$c_i = 2^{k_i}$，其中$0 \leqslant k_i < 30$，即所有$c_i$都是$2$的$k_i$次幂。

输入描述

第一行，是一个正整数$T$$(1 \leqslant T \leqslant 100000)$，表示接下来要输入$T$组测试数据。
接下来有$T$测试数据的输入，对于每组测试数据，输入格式如下：
第一行，一个整数$m(1 \leqslant m \leqslant 100000, \sum m \leqslant 10^5)$。
第二行，用空格隔开的$m$个非负整数，第$i$个数字是$k_i$$ (0 \leqslant k_i < 30)$

输出描述

依次输出$T$行，按照输入数据的顺序依次给出每组测试数据的答案，对于一组测试数据：
如果存在一种符合条件的方案，则输出一个长度为$m$的$01$串，从前往后的第$i$位如果是$1$表示原序列中第$i$个物品被选中装进背包，为$0$则表示这个物品不被选中。
如果不存在符合条件的方案，请输出impossible。

示例1

输入
2
4
29 1 28 28
7
0 0 1 2 3 4 15
输出
1011
impossible

思路

结论:如果$\sum c_i \geqslant 2^{30}$，那肯定可以凑出$2^{30}$，我只需要把所有的数字从大到小排序，依次加入数字，肯定在某个时刻和就等于$2^{30}$。
证明：
如果有一个$2^{30}$，那肯定在第一步就找到方案了。如果没有$2^{30}$，那肯定最大的数字不大于$2^{29}$，假设一个一个加入，当前已经加入的数字的和是$S$，再加入一个数字$x$的时候，考虑$S$的二进制表示加上一个$2$的幂，可能会产生进位，这个进位有可能最终使$S$的位数增加$1$，或者也可能保持不变。如果这次进位使得最终$S$的位数增加$1$，那么这次进位肯定是类似这种情形$111000+1000$，也就是从$x$的$1$那一位往上的位，在$S$中是连续一段$1$，这样的加法肯定执行完之后产生的结果肯定是$2$的幂次，既然最终的和不小于$2^{30}$，那么在某一次进位的时候肯定产生了$2^{30}$这个数。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100004;
struct node
{
	int id;
	long long k;
}goods[N];
bool ans[N];
bool cmp(node a,node b)
{
	return a.k>b.k;
}
void solve()
{
	int m;
	cin>>m;
	int i;
	//初始化
	memset(ans,0,sizeof(ans));
	long long now=1LL<<30;
	for(i=1;i<=m;i++)
	{
		cin>>goods[i].k;
		goods[i].id=i;
	}
	//从大到小排序  
	sort(goods+1,goods+1+m,cmp);
	for(i=1;i<=m;i++)
	{
		if(now>=goods[i].k)
		{
			now=now-(1LL<<goods[i].k);
			ans[goods[i].id]=1;
			if(!now) //找到方案后直接return
			{
				for(i=1;i<=m;i++) cout<<ans[i];
				cout<<endl;
				return;
			}
		}
	}
	puts("impossible");
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

I-寻找子串

题目描述

字符串的子串是指字符串中连续的一段。
给定字符串$s$，请你找出字典序最大的子串。

输入描述

一行，包含一个字符串，字符串中只有小写英文字母，字符串的长度不超过$1000$。

输出描述

输出一个字符串，表示字符串$s$字典序最大的子串。

示例1

输入
ac
输出
c
说明
子串有三个,$\text{a}$,$\text{c}$,$\text{ac}$，字典序最大的是$\text{c}$。

思路

利用反证法，可以证明，字典序最大的子串显然是原字符串的一个后缀，所以只需要暴力枚举所有后缀，找到字典序最大的后缀即可。

代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
void solve()
{
	string s;
	string ans="";
	int i;
	cin>>s;
	//暴力枚举所有后缀  
	for(i=0;i<s.length();i++) ans=max(ans,s.substr(i,s.length()-i));
	cout<<ans;
}
int main()
{
	solve();
	return 0;
}

J-最大的差

题目描述

给定$n$个数字，请你从中选出两个数字，使得这两个数字的差尽量大，输出这个最大的差。

输入描述

第一行是一个正整数 $n(2 \leqslant n \leqslant 10^5)$。
第二行有$n$个空格隔开的整数，数字的绝对值不超过$10^5$。

输出描述

输出一个整数，表示最大的差值。

示例1

输入
3
1 2 1
输出
1

思路

排序，输出最大值和最小值的差。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100007;
int n,a[N];
void solve()
{
	cin>>n;
	int i;
	for(i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	cout<<a[n]-a[1];
}
int main()
{
	solve();
	return 0;
}