链接：https://ac.nowcoder.com/acm/contest/4784#question
B 最小的n，是n！=p的倍数
从质因数的角度找，找到出现每个质因数的次数的最小的数再取max，假设质因数p出现了m次，p只会出现在p的倍数里面，p出现一次，p*2又出现一次，依次类推，特殊的n^2出现2次， n ^3出现3次…
1还需要特判
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5010;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tir(0);
int n,t;
int get(int x,int cnt)//找x出现cnt次的那个最小值
{
int i=x,res=0;
while(1)
{
int t=i;
while(t%x==0) t/=x,res++;
if(res>=cnt) return i;
i+=x;
}
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
if(n==1)
{
cout<<1<<endl;
continue;
}
int k=0,num[1000]={0};
map<int,int> mp;
for(int i=2;i<=n/i;i++)
{
if(n%i==0) num[k++]=i;
while(n%i==0)
{
mp[i]++;
n/=i;
}
}
if(n>1) num[k++]=n,mp[n]++;
int ans=0;
for(int i=0;i<k;i++)
ans=max(ans,get(num[i],mp[num[i]]));
cout<<ans<<endl;
}
return 0;
}
C 完全图每条边连n-1条边，wtm以为有n条，裂开。那么新出现一个连通块最少需要删n-1条边（将一个点完全割出来），两个就是n-1+n-2（割去一个点后，那个大的连通块剩n-1个点），m个就是
（n-1）+（n-2）+…+（n-m）=m+（n-1+n-m），找到这个规律后就可以二分了。数据范围1e18，会爆ll，可以用int128，也可以用python
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5010;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tir(0);
ll n,t,m;
void print(__int128 x)
{
if(!x)
{
puts("0");
return ;
}
string ret="";
while(x)
{
ret+=x%10+'0';
x/=10;
}
reverse(ret.begin(),ret.end());
cout<<ret<<endl;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
__int128 l=0,r=n;
while(l<r)//二分新增连通块的数量
{
__int128 mid = l+r >> 1;
if((mid*(2*n-mid-1)/2)>m) r=mid;
else l=mid+1;
}
print(r);//二分出不满足的最小值，答案就是l-1+1
}
return 0;
}
E 32为有符号整数的范围是（-2^31, 2 ^31-1）共有2 ^32个数，对于任意一个数a都存在一个数c-b在int范围内，因为会溢出，所以答案就是2 ^32
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010,inf=0x3f3f3f3f;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tir(0);
int n,a[N],l=-inf,r=inf;
int main()
{
cin>>n;
cout<<(1ll<<32);
return 0;
}
G 需要处理每一条边的贡献，然后按贡献从大到小赋值从小到大，每一条边的贡献是有多少路径（u，v）经过这条边，因为是一棵树，所以任意两点间路径唯一，那么贡献是多少呢，就是这条边两边的点数量的乘积，边两边任意两点一定会经过这条边，之前做过类似的可是给忘了…
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,h[N],e[N],ne[N],idx;
vector<long long> ve;
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int dfs(int u,int pre)
{
int cnt=0;
for(int i=h[u];i!=-1;i=ne[i])
{
int v=e[i];
if(v!=pre)
{
int res=dfs(v,u);//边(u,v)v那边点的数量
cnt+=res;
ve.push_back(1ll*res*(n-res));//n-res是u这边的数量，乘积就是边(u,v)的贡献
}
}
return cnt+1;//加上自身这个点
}
int main()
{
IOS
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs(1,-1);
sort(ve.begin(),ve.end());
long long ans=0;
for(int i=0;i<ve.size();i++)
ans+=1ll*ve[i]*(n-i-1);//按贡献一次递减赋值
cout<<ans;
return 0;
}
H 每个物品都是以2进制的形式给出的，如果n个物品的和大于等于2 ^30那么一定可以装满。
假设上面是对的，就会有三种情况，29的次数为0,1，2。如果有两个29，那么一定是可以的；如果只有一个29，那么剩余n-1个物品之和一定大于等于2^29,就和上面是类似的了；如果没有29，因为给出的都是二进制，所以可以把n个物品分为两部分，每部分的和都大于等于2 ^29，用这两部分取填满两个2 ^29的背包,又和上面类似了，这是看了题解后我的理解，貌似没问题吧
所以把大的填进去一定可以填满吧
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
typedef long long ll;
int t;
ll n,m,l,r,mid;
int a[N];
int main()
{
cin>>t;
while(t--)
{
cin>>n;
ll sum=0;
for(int i=0;i<n;i++) cin>>a[i],sum+=(1ll<<a[i]);
if(sum<(1ll<<30)) cout<<"impossible"<<endl;
else
{
bool st[N]={0};
pair<int,int> b[N];
for(int i=0;i<n;i++) b[i]={a[i],i};
sort(b,b+n);
sum=0;
for(int i=n-1;i>=0;i--)
{
sum+=(1ll<<b[i].first);
st[b[i].second]=1;
if(sum==(1ll<<30))
{
break;
}
}
for(int i=0;i<n;i++) cout<<st[i];
puts("");
}
} return 0;
}
I 可以找以最大的字符开头的后缀，比较一遍就可以了（数据范围小暴力找每一个子串也是可以的）
#include<iostream>
#include<string>
using namespace std;
string s;
char c=0;
int main()
{
cin>>s;
for(int i=0;i<s.size();i++)
c=max(c,s[i]);
string st;
for(int i=0;i<s.size();i++)
if(s[i]==c)
st=max(st,s.substr(i));
cout<<st;
}
J
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010,inf=0x3f3f3f3f;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tir(0);
int n,a[N],l=-inf,r=inf;
int main()
{
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
l=max(l,a[i]);
r=min(r,a[i]);
}
cout<<l-r;
return 0;
}