第一次体会到了(skipped)的快感(逃
mm我再也不直接蒯别人code了qwq
A
题意
一个长度为(n)的数组,可以给里面的任意单个元素加1(m)次,问最后 数组最大值 的最小值和最大值
题解
普及T1难度
最大的最大值就是最大值+m
最小的最大值是尽量先把所有数加成当前最大值,然后平摊,答案为(max(lceil frac{sum a_i+m}{n} ceil,max a_i))
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define inf 999999999
using namespace std;
using namespace std;
const LL mod=1;
il LL rd()
{
re LL x=0,w=1;re char ch;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,m,k,a[110];
int main()
{
///////qwqwqwqwq
n=rd(),m=rd();
for(int i=1;i<=n;i++) a[i]=rd();
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) k+=a[n]-a[i];
printf("%d %d
",a[n]+max((m-k+n-1)/n,0),a[n]+m); //和题解有出入(逃
return 0;
}
B
题意
数据有(n)组数,每组数有一个价值(c_i)和一个字符串(S),字符串(S)中包含3个字母(A,B,C)，问集齐(ABC)三个字母的最小价值（一个字母可以有多个）
题解
提高T1难度
把ABC状压成([000]-[111]),然后选三个状态能按位(or)成([111])加起来取(min)
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define inf 999999999
using namespace std;
const LL mod=1;
il LL rd()
{
re LL x=0,w=1;re char ch;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int a[10],n,ans=23333333;
int main()
{
n=rd();
for(int j=1;j<=7;j++) a[j]=23333333;
for(int i=1;i<=n;i++)
{
int nn=0,x=rd();
char cc[5];
scanf("%s",cc);
int l=strlen(cc);
for(int j=0;j<l;j++) nn|=1<<(cc[j]-65);
a[nn]=min(a[nn],x);
}
for(int i=0;i<=7;i++)
for(int j=i;j<=7;j++)
for(int k=j+1;k<=7;k++)
if((i|j|k)==7) ans=min(ans,a[i]+a[j]+a[k]);
printf("%d
",ans<=300000?ans:-1);
return 0;
}
C
题意
一个长度为(n)的数组,有两种操作
(1,l,r quad) 把(a[r]=a[r]*a[l]),同时删去(a[l]) (合并)
(2,l quad) 删去(a[l]) (只能用一次)
给出方案,使得操作(n-1)次后最后剩下的数最大
题解
分类讨论即可
-
如果全是0,或者一个负数和0,全部合并
-
剩下情况,把所有0合并,如果负数个数为奇数,就把绝对值最小的负数合并到0上去,然后把0删了,合并剩下的
注意细节
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define inf 999999999
using namespace std;
const LL mod=1;
il LL rd()
{
re LL x=0,w=1;re char ch;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int a[200010],n,b[200010],m,c,d,e;
bool v[200010];
int main()
{
n=rd();
a[0]=-1111111111;
for(int i=1;i<=n;i++) a[i]=rd();
for(int i=1;i<=n;i++)
{
c+=(a[i]==0),d+=(a[i]<0);
if(a[i]<0&&a[i]>a[e]) e=i;
if(a[i]==0) v[i]=true,b[++m]=i;
}
if(d<=1&&c+d==n)
{
for(int i=2;i<=n;i++) printf("1 %d %d
",i-1,i);
}
else
{
if(d&1) v[e]=true,b[++m]=e;
sort(b+1,b+m+1);
for(int i=2;i<=m;i++) printf("1 %d %d
",b[i-1],b[i]);
if(m) printf("2 %d
",b[m]);
int la=1,now;
while(la<=n&&v[la]) ++la;
now=la;
while(now<=n)
{
++now;
while(now<=n&&v[now]) ++now;
if(now>n) break;
printf("1 %d %d
",la,now),la=now;
}
}
////////qwq wqwqwqwqwqwqwq
return 0;
}
D
题意
给一个长度为(n)的数组,问有多少个区间的(a_i)之和小于(t)
题解
n方做法是先预处理前缀和,然后枚举左右端点,判断区间和是否小于(t),统计答案
但是可以枚举右端点,把前面前缀和用什么数据结构维护一下,例如(Treap/Splay/set)什么的,然后把大于(pre_r-t)的前缀个数加进答案
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define inf 999999999
using namespace std;
const LL mod=1;
il LL rd()
{
re LL x=0,w=1;re char ch;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
struct spl
{
int ch[2],sz,fa,cs;LL x;
spl(){x=cs=sz=fa=ch[0]=ch[1]=0;}
void init(){x=cs=fa=ch[0]=ch[1]=0;}
}tr[200010];
int rt,tot;
void pushup(int x){tr[x].sz=tr[tr[x].ch[0]].sz+tr[tr[x].ch[1]].sz+tr[x].cs;}
void rot(int x)
{
int y=tr[x].fa;int z=tr[y].fa;
int yy=(tr[y].ch[1]==x),zz=(tr[z].ch[1]==y);
tr[z].ch[zz]=x;tr[x].fa=z;
tr[y].ch[yy]=tr[x].ch[yy^1];tr[tr[x].ch[yy^1]].fa=y;
tr[x].ch[yy^1]=y;tr[y].fa=x;
pushup(y),pushup(x);
}
void Spl(int x,int en)
{
while(tr[x].fa!=en)
{
int y=tr[x].fa;int z=tr[y].fa;
if(z!=en) ((tr[z].ch[0]==y)^(tr[y].ch[0]==x))?rot(x):rot(y);
rot(x);
}
if(!en) rt=x;
}
void inst(LL x)
{
int now=rt;
while(tr[now].x!=x&&tr[now].ch[x>tr[now].x])
now=tr[now].ch[x>tr[now].x];
if(tr[now].x==x)
++tr[now].cs;
else
{
++tot,tr[tot].ch[0]=tr[tot].ch[1]=0,tr[tot].sz=tr[tot].cs=1,tr[tot].fa=now,tr[tot].x=x;
if(now) tr[now].ch[x>tr[now].x]=tot;
now=tot;
}
Spl(now,0);
}
void find(LL x)
{
int now=rt;
while(tr[now].ch[x>tr[now].x]&&tr[now].x!=x)
now=tr[now].ch[x>tr[now].x];
if(now) Spl(now,0);
}
int ftnt(LL x,int ffa)
{
find(x);
int now=tr[rt].ch[ffa];
if((tr[rt].x>x&&ffa)||(tr[rt].x<x&&!ffa)) return rt;
while(tr[now].ch[ffa^1]) now=tr[now].ch[ffa^1];
return now;
}
void del(LL x)
{
int ft=ftnt(x,0),nt=ftnt(x,1);
Spl(ft,0);Spl(nt,ft);
if(tr[tr[tr[rt].ch[1]].ch[0]].cs>1)
{
--tr[tr[tr[rt].ch[1]].ch[0]].cs;
Spl(tr[tr[rt].ch[1]].ch[0],0);
}
else
tr[tr[rt].ch[1]].ch[0]=0;
}
LL kth(int k)
{
int now=rt;
while(1)
{
if(k<=tr[tr[now].ch[0]].sz) now=tr[now].ch[0];
else if(k>tr[tr[now].ch[0]].sz+tr[now].cs) k-=tr[tr[now].ch[0]].sz+tr[now].cs,now=tr[now].ch[1];
else return tr[now].x;
}
}
int n;
LL a[200010],t,ans;
int main()
{
////////平衡树板子题qwq
n=rd();t=rd();
inst(-(1ll<<58)),inst(1ll<<58),inst(0);
for(int i=1;i<=n;i++)
{
a[i]=a[i-1]+rd();
Spl(ftnt(a[i]-t,1),0);
ans+=i-(tr[tr[rt].ch[0]].sz-1);
inst(a[i]);
}
cout<<ans;
return 0;
}
E
题意
一个(n)行(m)列的矩阵,每个位置有权值(a_{i,j})
给定一个出发点,每次可以等概率的移动到一个权值小于当前点权值的点,同时得分加上两个点之间欧几里得距离的平方(欧几里得距离:(sqrt{(x_1-x_2)^2+(y_1-y_2)^2})),问得分的期望
题解
显然设(f_{i,j})为到达((i,j))的答案,转移就是从这个格子转移到权值更小的地方,记为比某个格子((i,j))权值更小的格子数为(b_{i,j}),即$$f_{i,j}=sum_{k=1}{n}sum_{l=1}{m}[a_{i,j}<a_{k,l}]*frac{f_{k,l}+(i-k)2+(j-l)2}{b_{k,l}}$$
对所有格子排个序后转移,复杂度为(O((mn)^2))级别的
这里其实可以倒着推,也就是(f_{i,j})为起点在((i,j))的答案,式子可以写成这样$$f_{i,j}=frac{sum_{k=1}{n}sum_{l=1}{m}[a_{i,j}>a_{k,l}]*(f_{k,l}+(i-k)2+(j-l)2)}{b_{i,j}}$$
看着好像没能优化多少,但是如果把式子中的两个平方拆开,即$$f_{i,j}=frac{sum_{k=1}{n}sum_{l=1}{m}[a_{i,j}>a_{k,l}]*(f_{k,l}+i2+j2+k2+l2-2ik-2jl)}{b_{i,j}}$$
(下式中的(sum_{k=1}^{n}sum_{l=1}^{m})和([a_{i,j}>a_{k,l}])都省略或简写)
[f_{i,j}=frac{b_{i,j}(i^2+j^2)+sum f_{k,l}+sum k^2+sum l^2+isum(-2k)+jsum(-2l)}{b_{i,j}}
]
所以维护好前缀的(sum f_{k,l} sum k^2 sum l^2 sum(-2k) sum(-2l))救星了
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define inf 999999999
using namespace std;
const int N=1000+10,mod=998244353;
il LL rd()
{
re LL x=0,w=1;re char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,m,nm;
struct nnn
{
LL a,x,y;
bool operator < (const nnn &b)const {return a<b.a;}
}a[N*N];
LL ans[N][N],inv[N*N],sum,sx,sy,ssx,ssy;
int main()
{
n=rd(),m=rd();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[++nm]=(nnn){rd(),i,j};
sort(a+1,a+nm+1);
inv[0]=inv[1]=1;
for(int i=2;i<=nm;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
for(int l=1,r=1,su=0;l<=nm;++r,l=r)
{
while(r<nm&&a[l].a==a[r+1].a) ++r;
for(int i=l;i<=r;i++)
ans[a[i].x][a[i].y]=((a[i].x*a[i].x%mod+a[i].y*a[i].y%mod)%mod*su%mod+ssx*a[i].x%mod+ssy*a[i].y%mod+(sx+sy+sum)%mod)%mod*inv[su]%mod;
for(int i=l;i<=r;i++)
{
sx=(sx+a[i].x*a[i].x%mod)%mod,
ssx=(ssx-2*a[i].x%mod+mod)%mod,
sy=(sy+a[i].y*a[i].y%mod)%mod,
ssy=(ssy-2*a[i].y%mod+mod)%mod,
sum=(sum+ans[a[i].x][a[i].y])%mod;
}
su=r;
}
int r=rd(),c=rd();
cout<<ans[r][c]<<endl;
return 0;
}
F
题意
给定一棵(n)个点的树,将叶子节点分为数个集合使单个集合里两点之间最长距离不超过(k),求最少集合数
题解
orz 秒切此题的gzy
参考消防局的设立/将军令
把所有叶子节点按照深度从大到小排序,从前往后考虑一个叶子,如果叶子没被覆盖,把距离在(k)以内的所有叶子给覆盖掉,同时(++ans)
至于为什么,我怕讲不清所以不讲了,反正就是类似的贪心思路,把能覆盖的都覆盖
#include<bits/stdc++.h>
#define il inline
#define re register
#define LL long long
#define db double
using namespace std;
const int N=1000000+10;
il LL rd()
{
LL x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[N<<1],nt[N<<1],hd[N],d[N],tot=1;
il void add(int x,int y)
{
++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot,++d[x];
++tot,to[tot]=x,nt[tot]=hd[y],hd[y]=tot,++d[y];
}
int n,k,f[N],fa[N],v[N],ans,h,tl,sta;
struct nn{int x,y;}qq[N];
bool nl[N];
int main() //此代码为bfs版本
{
n=rd(),k=rd();
for(int i=1;i<n;i++) add(rd(),rd());
int q[N];h=1,tl=0;
sta=1;
while(sta<=n&&d[sta]==1) ++sta;
q[++tl]=sta;
while(h<=tl)
{
int x=q[h++];
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==fa[x]) continue;
fa[y]=x,q[++tl]=y,nl[x]=true;
}
}
/* for(int i=n;i>=1;i--)
{
int x=q[i],ma=-n,mi=n;
for(int j=hd[x];j;j=nt[j])
{
int y=to[j];
if(y==fa[x]) continue;
ma=max(ma,f[y]),mi=min(mi,f[y]);
}
if(ma==-n&&mi==n) {f[x]=1;continue;}
if(mi+ma+1<=0) f[x]=mi+1;
else f[x]=ma+1;
if(f[x]>k) ++ans,f[x]=-k;
}
ans+=(f[sta]>0);*/ //这段注释掉的代码和上面那个bfs合起来是类似于dp的消防局的设立/将军令的做法
for(int i=n;i>=1;i--)
{
if(!v[q[i]]&&!nl[q[i]])
{
++ans;
int now=q[i];
h=1,tl=0;
qq[++tl]=(nn){now,k},v[now]=i;
while(h<=tl)
{
int x=qq[h].x,z=qq[h].y;++h;
if(z==0) continue;
for(re int j=hd[x];j;j=nt[j])
{
int y=to[j];
if(v[y]==i) continue;
v[y]=i;
qq[++tl]=(nn){y,z-1};
}
}
}
}
printf("%d
",ans);
///qwq?qwqwqwqwqwqwq! qwq??
return 0;
}