#include "bits/stdc++.h"
using namespace std;
#define all(v) (v).begin(), (v).end()
#define io ios::sync_with_stdio(0)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define rson rt << 1 | 1, mid + 1, r
#define lson rt << 1, l, mid
#define lll __int128
#define lowbit(i) ((-i) & (i))
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
template<class T>void read(T &x)
{
x=0;
int f=0;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘)
{
f|=(ch==‘-‘);
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘)
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x=f?-x:x;
return;
}
#define ull unsigned long long
#define eps 1e-12
#define sc(x) scanf("%lld", &(x))
#define mem(a,b) memset(a,b,sizeof(a))
#define endl "\n"
#define inf 0x3f3f3f3f
#define ll long long
const int mod = 1e9+7;
const int maxn=5e5+10;
int a[maxn];
void work()
{
mem(a,0);
int n;
cin>>n;
rep(i,1,n)
{
int now;
cin>>now;
a[now]++;
}
int ans=0;
rep(i,0,100)
{
if(a[i]==0)
{
ans+=i;
break;
}
a[i]--;
}
rep(i,0,100)
{
if(a[i]==0) {ans+=i;break;}
}
cout<<ans<<endl;
}
signed main()
{
int t;
cin>>t;
while(t--)
work();
}
当ans为正数时,正数取前5大,负数取前5小,枚举取答案
负数时, 负数取前五大,取答案
有0时ans最小为0
#include "bits/stdc++.h"
using namespace std;
#define all(v) (v).begin(), (v).end()
#define io ios::sync_with_stdio(0)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define rson rt << 1 | 1, mid + 1, r
#define lson rt << 1, l, mid
#define lll __int128
#define lowbit(i) ((-i) & (i))
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
template<class T>void read(T &x)
{
x=0;
int f=0;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘)
{
f|=(ch==‘-‘);
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘)
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x=f?-x:x;
return;
}
#define ull unsigned long long
#define eps 1e-12
#define sc(x) scanf("%lld", &(x))
#define mem(a,b) memset(a,b,sizeof(a))
#define endl "\n"
#define inf 0x3f3f3f3f
#define ll long long
#define int long long
const int mod = 1e9+7;
const int maxn=5e5+10;
int a[maxn];
int b[maxn];
int c[maxn];
int ans;
void dfs(int dep,int st,int ed,int now)
{
// cout<<st<<" "<<ed<<endl;
if(dep==5)
{
ans=max(ans,now);
return ;
}
rep(i,st,ed)
{
dfs(dep+1,i+1,ed,now*c[i]);
dfs(dep,i+1,ed,now);
}
return ;
}
int cmp(int a,int b)
{
return a>b;
}
void work()
{
int la=0,lb=0,n;
ans=-1e18;
cin>>n;
rep(i,1,n)
{
int now;
cin>>now;
if(now>0) a[++la]=now;
else if(now<0) b[++lb]=now;
else if(now==0) ans=0;
}
sort(a+1,a+1+la,cmp);
sort(b+1,b+1+lb);
int e1=min(la,1ll*5);
int e2=min(lb,1ll*5);
int l=0;
// rep(i,1,e2) cout<<b[i]<<endl;
rep(i,1,e1) c[++l]=a[i];
rep(i,1,e2)
{
c[++l]=b[i];
// cout<<b[i]<<" "<<c[l]<<endl;
}
// rep(i,1,l) cout<<c[i]<<endl;
if(l>=5)
dfs(0,1,l,1);
sort(a+1,a+1+la,cmp);
sort(b+1,b+1+lb,cmp);
e1=min(la,1ll*5);
e2=min(lb,1ll*5);
l=0;
// rep(i,1,e2) cout<<b[i]<<endl;
rep(i,1,e1) c[++l]=a[i];
rep(i,1,e2)
{
c[++l]=b[i];
// cout<<b[i]<<" "<<c[l]<<endl;
}
// rep(i,1,l) cout<<c[i]<<endl;
if(l>=5)
dfs(0,1,l,1);
cout<<ans<<endl;
}
signed main()
{
int t;
cin>>t;
while(t--)
work();
}
树的重心最多有 2 个且相邻
取一个重心上不是另一个重心相连的子树, 破坏掉连到另一个重心上即可
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
//?óê÷μ???D?
const int maxn=5e5+5;
struct node
{
int to,nex;
} tr[maxn*4];
int n,ans;
int max_part[maxn];
int sizx[maxn],cnt;
int head[maxn];
int f[maxn];
void add(int u,int v)
{
tr[cnt].to=v;
tr[cnt].nex=head[u];
head[u]=cnt++;
}
void dfs(int u,int fa)
{
f[u]=fa;
sizx[u]=1;
max_part[u]=0;
for(int i=head[u]; ~i; i=tr[i].nex)
{
int v=tr[i].to;
if(v==fa)
{
continue;
}
dfs(v,u);
sizx[u]+=sizx[v];
max_part[u]=max(max_part[u],sizx[v]);
}
max_part[u]=max(max_part[u],n-sizx[u]);
ans=min(max_part[u],ans);
}
int kk=0,ansv=0;
void dfs1(int u,int fa)
{
if(kk) return ;
for(int i=head[u]; ~i; i=tr[i].nex)
{
int v=tr[i].to;
if(v==fa) continue;
if(sizx[v]==1)
{
ansv=v;
kk=1;
return ;
}
dfs1(v,u);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
for(int i=1;i<=cnt;i++)
{
head[i]=-1;
tr[i].nex=0,tr[i].to=0;
}
cnt=0;
ans=0x3f3f3f3f3f;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
f[i]=0;
max_part[i]=0;
head[i]=-1;
sizx[i]=0;
}
for(int i=1; i<n; i++)
{
int u,v;
scanf("%d %d",&u,&v);
add(u,v);
add(v,u);
}
dfs(1,0);
int root,minx=0x3f3f3f3f;
int num=0;
for(int i=1;i<=n;i++)
{
if(max_part[i]==ans)
{
root=i;
break;
}
}
int root2;
for(int i=1;i<=n;i++)
{
if(max_part[i]==ans)
root2=i;
}
int mx=0,pos;
for(int i=head[root];~i;i=tr[i].nex)
{
int v=tr[i].to;
// cout<<v<<endl;
if(v!=root2)
{
pos=v;
break;
}
}
cout<<pos<<" "<<root<<"\n";
cout<<pos<<" "<<root2<<"\n";
}
}
维护差分
应为 b 是非递减, c 是非递增
所以答案应该在 bn 和 c1 中取得
把正差分加到 b 上, 负差分加到 c 上为最优
记正差分的和为sum, b1 为 x, c1 为 y
所以 x+y=a1 bn=x+sum
所以 ans=max( x+sum, a1-x )
且当x+sum=a1-x时取得最小值
#include "bits/stdc++.h"
using namespace std;
#define all(v) (v).begin(), (v).end()
#define io ios::sync_with_stdio(0)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define rson rt << 1 | 1, mid + 1, r
#define lson rt << 1, l, mid
#define lll __int128
#define lowbit(i) ((-i) & (i))
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define int long long
template<class T>void read(T &x)
{
x=0;
int f=0;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘)
{
f|=(ch==‘-‘);
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘)
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x=f?-x:x;
return;
}
#define ull unsigned long long
#define eps 1e-12
#define sc(x) scanf("%lld", &(x))
#define mem(a,b) memset(a,b,sizeof(a))
#define endl "\n"
#define inf 0x3f3f3f3f
#define ll long long
#define dbug cout<<"here\n";
const int mod = 1e9+7;
const int maxn=5e5+10;
int a[maxn];
int b[maxn];
void work()
{
int n,q;
read(n);
rep(i,1,n) read(a[i]);
int sum=0;
rep(i,1,n) b[i]=a[i]-a[i-1];
rep(i,1,n) if(b[i]>0&&i!=1) sum+=b[i];
int x;
x=(b[1]-sum)/2;
int ans=max(x+sum,b[1]-x);
printf("%lld\n",ans);
read(q);
while(q--)
{
int l,r,d;
read(l),read(r),read(d);
if(l==1) b[1]+=d;
else
{
if(b[l]>0&&b[l]+d<=0)
{
sum-=b[l];
b[l]+=d;
}
else
{
if(b[l]>0)
{
b[l]+=d;
sum+=d;
}
else
{
b[l]+=d;
if(b[l]>0) sum+=b[l];
}
}
}
if(r!=n)
{
r++;
d=-d;
if(b[r]>0&&b[r]+d<=0)
{
sum-=b[r];
b[r]+=d;
}
else
{
if(b[r]>0)
{
b[r]+=d;
sum+=d;
}
else
{
b[r]+=d;
if(b[r]>0) sum+=b[r];
}
}
}
x=(b[1]-sum)/2;
ans=max(x+sum,b[1]-x);
printf("%lld\n",ans);
}
}
signed main()
{
work();
}
简单的想法就是枚举质数, 然后判断这个质数是否为x的质因子以及系数, 但是1E5内的质数接近1E4, 查询次数不允许.
所以对质数进行分块, 设m为质数的个数,每次删掉 sqrt(m) 的质数,同时维护一下应该剩余数的个数res, 每次删完 sqrt(m) 之后查询 1, 看和res是否相同, 确定最小的质因数, 之后同上枚举后面的每个质数
Codeforces Round #670 (Div. 2)
原文：https://www.cnblogs.com/minun/p/13681920.html