ARC160
A
一眼没思路/kk
对于操作\((l1,r1)\),\((l2,r2)\)我们是可以直接比较两者之间的大小的
然后用\(nth\_element\)即可
好像有\(O(nlog(n))\)做法
就是考虑每个位置的答案是什么,如果确定了前\(i-1\)个是没变的时候取答案,第\(i\)位的答案要么是和后面的交换要么也是不变,这个大概二分一下就可以了
#include<bits/stdc++.h>
using namespace std;
const int MAXN=7005;
int n,k;
int A[MAXN];
struct Node{
int l,r;
bool operator<(const Node x)const{
if(l==x.l)
{
return A[r]<A[x.r];
}
else
{
if(((l<x.l)&&(l!=r))||(x.l==x.r))
{
return A[r]<A[l];
}
else
{
return A[x.r]>A[x.l];
}
}
}
}a[MAXN*MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
}
int Cnt=0;
for(int l=1;l<=n;l++)
{
for(int r=l;r<=n;r++)
{
a[++Cnt].l=l;
a[Cnt].r=r;
}
}
nth_element(a+1,a+k,a+1+Cnt);
for(int i=1;i<a[k].l;i++)
{
printf("%d ",A[i]);
}
for(int i=a[k].r;i>=a[k].l;i--)
{
printf("%d ",A[i]);
}
for(int i=a[k].r+1;i<=n;i++)
{
printf("%d ",A[i]);
}
}
B
首先肯定最多只有一个数\(>\sqrt n\)
然后钦定\(x\le y\le z\),枚举\(y\),则\(z\le\lfloor\dfrac{n}{y}\rfloor\)
注意相同即可
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int T;
int n;
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int Res=0;
for(int i=1;i*i<=n;i++)
{
int Lit=(n/i);
int Rp=((long long)(i-1)*(Lit-i))%MOD;
Rp=((long long)Rp*6)%MOD;
Res=((long long)Res+Rp)%MOD;
Rp=(Lit-i);
Rp=((long long)Rp*3)%MOD;
Res=((long long)Res+Rp)%MOD;
Rp=(i-1);
Rp=((long long)Rp*3)%MOD;
Res=((long long)Res+Rp)%MOD;
Rp=1;
Res=((long long)Res+Rp)%MOD;
}
printf("%d\n",Res);
}
}
C
简单\(dp\),注意到状态数不超过\(nlog(n)\)即可
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int MAXN=4e5+5;
int n;
int x;
int A[MAXN];
int dp[MAXN];
int Sum[MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
A[x]++;
}
dp[0]=1;
for(int i=2;i<=MAXN-5;i++)
{
int Mk=0;
for(int j=0;;j++)
{
if(!dp[j])
{
Mk=j-1;
break;
}
}
Sum[Mk+1]=0;
for(int j=Mk;j>=0;j--)
{
Sum[j]=((long long)Sum[j+1]+dp[j])%MOD;
dp[j]=0;
}
for(int j=0;j<=(A[i-1]+Mk)/2;j++)
{
dp[j]=Sum[max(0,2*j-A[i-1])];
}
}
printf("%d\n",dp[0]);
}
D
明显要倒着来
这里不好对\(A\)计数,考虑直接对操作序列计数,但可能会算重
实际上,直接限制每个区间加的次数\(<k\)即可
设\(f_i\)为\([1,i+k-1]\)加的次数,\(g_i\)为\(i\)加的次数
于是问题转换为满足\(\sum\limits_{i=1}^{n-k+1}f_i+\sum\limits_{i=1}^ng_i=\dfrac{m}{k},f_i<k\)的个数
然后这个经典容斥,钦定有\(i\)个数先取了\(k\)个即可
答案为\(\sum\limits_{i=0}^{n-k+1}(-1)^i\binom{n-k+1}{i}\binom{2n-k+\frac{m}{k}-ki}{2n-k}\)
// LUOGU_RID: 118704316
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int inv(int a,int p)
{
return Pow(a,p-2,p);
}
int n,k;
long long m;
int C(long long n,int m)
{
if(m<0||n<m)
{
return 0;
}
if((m==0)||(n==m))
{
return 1;
}
int res=1;
for(long long i=n-m+1;i<=n;i++)
{
res=((long long)res*((i%MOD)))%MOD;
}
int tes=1;
for(int i=1;i<=m;i++)
{
tes=((long long)tes*i)%MOD;
}
res=((long long)res*inv(tes,MOD))%MOD;
return res;
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
int Res=0;
scanf("%d %lld %d",&n,&m,&k);
if(m%k)
{
printf("0");
}
else
{
m/=k;
for(int i=0;i<=n-k+1;i++)
{
int Rp=C(n-k+1,i);
Rp=((long long)Rp*C(2*n-k+m-i*k,2*n-k))%MOD;
if(i&1)
{
Res=((long long)Res-Rp+MOD)%MOD;
}
else
{
Res=((long long)Res+Rp)%MOD;
}
}
printf("%d\n",Res);
}
}
E
每个叶子肯定要选
设叶子个数为\(k\)
对于一颗二叉树,一定能找出一个点满足删除这个点后每个子树内的叶子个数小于\(\dfrac{k}{2}\),证明大概类似于树的重心
我们设这个点为\(u\)
然后如果\(k\)为偶数,我们可以每次选不同子树的两个点来构造,使得其构成若干个环至少有两个交点,因此答案可以直接取到下界
如果\(k\)为奇数,实际上可以钦定一个点和其他点相连,而这个点连出来的边要和其他环有两个点相交,实际上这里就是要求这个点\(x\)不能和\(x\)到第一个三度点路径上的点相连,直接枚举\(x\)用\(set\)维护即可
// LUOGU_RID: 118785801
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int T;
int n;
int a[MAXN];
int x,y;
vector<int>g[MAXN];
int Siz[MAXN];
int Maxs[MAXN];
int Heart;
void dfs(int x,int f)
{
Siz[x]=(g[x].size()==1);
Maxs[x]=0;
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
dfs(v,x);
Maxs[x]=max(Maxs[x],Siz[v]);
Siz[x]+=Siz[v];
}
}
multiset<pair<int,int> >S;
int Res=0x3f3f3f3f;
int Fa[MAXN];
int Miu,Miv;
void find(int x,int f,int Last)
{
S.erase(S.find(make_pair(a[x],x)));
if(g[x].size()==1)
{
//printf("%d---\n",S.size());
int Tg=(*(S.begin())).second;
if(a[Tg]<Res)
{
Res=a[Tg];
Miu=x;
Miv=Tg;
}
}
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
Fa[v]=x;
if(g[v].size()==3)
{
int Now=x;
while(Now!=Fa[Last])
{
S.insert(make_pair(a[Now],Now));
Now=Fa[Now];
}
find(v,x,v);
Now=x;
while(Now!=Fa[Last])
{
S.erase(S.find(make_pair(a[Now],Now)));
Now=Fa[Now];
}
}
else
{
find(v,x,Last);
}
}
S.insert(make_pair(a[x],x));
}
vector<int>Leaf[MAXN];
int Ct=0;
void Get(int x,int f)
{
if(g[x].size()==1&&(x!=Miu))
{
Leaf[Ct].push_back(x);
}
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
Get(v,x);
}
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
g[i].clear();
}
S.clear();
Res=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
S.insert(make_pair(a[i],i));
}
for(int i=1;i<n;i++)
{
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,0);
for(int i=1;i<=n;i++)
{
Maxs[i]=max(Maxs[i],Siz[1]-Siz[i]);
if((g[i].size()>=2)&&(Maxs[i]<=(Siz[1]/2)))
{
Heart=i;
}
}
Miu=0;
//printf("%d??\n",Heart);
printf("%d\n",(Siz[1]+1)/2);
if(Siz[1]&1)
{
Fa[Heart]=0;
find(Heart,0,Heart);
printf("%d %d\n",Miu,Miv);
}
cerr<<Heart<<' '<<Siz[1]<<endl;
Ct=0;
priority_queue<pair<int,int> >q;
for(int i=0;i<g[Heart].size();i++)
{
int v=g[Heart][i];
++Ct;
Get(v,Heart);
if(Leaf[Ct].size())
{
q.push(make_pair(Leaf[Ct].size(),Ct));
}
}
while(q.size())
{
int tpx=q.top().second;
q.pop();
int tpy=q.top().second;
q.pop();
printf("%d %d\n",Leaf[tpx].back(),Leaf[tpy].back());
Leaf[tpx].pop_back();
Leaf[tpy].pop_back();
if(Leaf[tpx].size())
{
q.push(make_pair(Leaf[tpx].size(),tpx));
}
if(Leaf[tpy].size())
{
q.push(make_pair(Leaf[tpy].size(),tpy));
}
}
}
}