前言 & 吐槽
非常好比赛，爱来自百度。
先是服务器崩溃导致延期到 16:00 - 19:00。
然后赛时客户端也一直卡，给题目描述翻个页都要卡几秒。
基本是跟榜做的，除了 T8 来不及看之外都看了，但怎么全是一眼题。
此外还有一些槽点。比赛体验总体来说不算很好。
希望百度之星明年还是回去用 bestcoder 吧，这个 matiji 真受不住了。
反正能进决赛了，就不打 R2 R3 了。
T5
签到题。
单组询问复杂度 \(O(1)\)。
#include <bits/stdc++.h>
typedef unsigned uint;
typedef long long llt;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _min(T&a,T b){return b<a?(a=b,true):false;}
template<typename T>bol _max(T&a,T b){return a<b?(a=b,true):false;}
// And in that light, I find deliverance.
voi solve()
{
uint p,k;scanf("%u%u",&p,&k);
if(k<p)printf("%u\n",k);
else if(p==1)puts("1");
else printf("%u\n",k-k/p+!(k%p));
}
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
freopen("QAQ.out","w",stdout);
#endif
uint t;scanf("%u",&t);
while(t--)solve();
return 0;
}
T1
枚举一下相遇点，跑 bfs 即可。
总复杂度 \(O(n)\)。
#include <bits/stdc++.h>
typedef unsigned uint;
typedef long long llt;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _min(T&a,T b){return b<a?(a=b,true):false;}
template<typename T>bol _max(T&a,T b){return a<b?(a=b,true):false;}
// And in that light, I find deliverance.
ullt a,b,c;
uint n,m,u,v;
std::vector<uint>Way[100005];
uint Dist[3][100005];
voi bfs(uint p,uint*D)
{
for(uint i=0;i<n;i++)D[i]=-1;
std::queue<uint>Q;D[p]=0,Q.push(p);
while(Q.size())
{
p=Q.front(),Q.pop();
for(auto s:Way[p])if(_min(D[s],D[p]+1))
Q.push(s);
}
}
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
freopen("QAQ.out","w",stdout);
#endif
scanf("%llu%llu%llu%u%u%u%u",&a,&b,&c,&u,&v,&n,&m),c=a+b-c,u--,v--;
while(m--){uint u,v;scanf("%u%u",&u,&v),Way[--u].push_back(--v),Way[v].push_back(u);}
bfs(u,Dist[0]),bfs(v,Dist[1]),bfs(n-1,Dist[2]);
ullt ans=-1llu;
for(uint i=0;i<n;i++)if(~Dist[0][i]&&~Dist[1][i]&&~Dist[2][i])_min(ans,Dist[0][i]*a+Dist[1][i]*b+Dist[2][i]*c);
if(~ans)printf("%llu\n",ans);else puts("-1");
return 0;
}
T2
暴力枚举行的切割方案，对列的方案 dp 即可。
复杂度 \(O(n^32^n)\)。
#include <bits/stdc++.h>
typedef unsigned uint;
typedef long long llt;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _min(T&a,T b){return b<a?(a=b,true):false;}
template<typename T>bol _max(T&a,T b){return a<b?(a=b,true):false;}
// And in that light, I find deliverance.
uint S[16][16];
uint Dp[16][16];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
freopen("QAQ.out","w",stdout);
#endif
uint n,k,ans=-1;scanf("%u%u",&n,&k);
for(uint i=1;i<=n;i++)
{
for(uint j=1;j<=n;j++)scanf("%u",S[i]+j),S[i][j]+=S[i][j-1];
for(uint j=1;j<=n;j++)S[i][j]+=S[i-1][j];
}
for(uint i=0;i<(1u<<(n-1));i++)
{
std::vector<uint>V;for(uint j=0;j<n-1;j++)if(i>>j&1)V.push_back(j+1);
if(V.size()>k)continue;
V.insert(V.begin(),0),V.insert(V.end(),n);
for(uint i=1;i<=n;i++)
{
for(uint j=0;j<=i;j++)Dp[i][j]=-1;
for(uint j=0;j<i;j++)
{
uint s=0;
for(uint k=1;k<V.size();k++)_max(s,S[i][V[k]]-S[i][V[k-1]]-S[j][V[k]]+S[j][V[k-1]]);
for(uint k=0;k<=j;k++)_min(Dp[i][k+1],std::max(Dp[j][k],s));
}
}
for(uint i=1;i<=n&&i+V.size()<=k+3;i++)_min(ans,Dp[n][i]);
}
printf("%u\n",ans);
return 0;
}
T3
枚举一下删谁，二分一下答案位置就好了。
预处理一些信息可以做到 \(O(n\log n)\)。
不知道是题目假了还是数据假了，应为只要 \(\ge m\) 即视为结束。
结果罚了两发，还因此在这题花了好久时间。/fn
#include <bits/stdc++.h>
typedef unsigned uint;
typedef long long llt;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _min(T&a,T b){return b<a?(a=b,true):false;}
template<typename T>bol _max(T&a,T b){return a<b?(a=b,true):false;}
// And in that light, I find deliverance.
uint T[100005],V[100005];ullt SumM[100005],Sum[100005];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
freopen("QAQ.out","w",stdout);
#endif
uint n,m;scanf("%u%u",&n,&m);if(!m)return puts("0"),0;
std::vector<std::pair<uint,uint> >P;
while(n--){uint a,b;scanf("%u%u",&a,&b);if(b)P.push_back({a,b});}
if(P.size()<=1)return puts("-1"),0;
std::sort(P.begin(),P.end()),n=P.size();
for(uint i=0;i<n;i++)T[i]=P[i].first,V[i]=P[i].second,Sum[i+1]=Sum[i]+V[i];
for(uint i=1;i<n;i++)SumM[i]=SumM[i-1]+Sum[i]*(T[i]-T[i-1]);
ullt ans=0;
for(uint i=0;i<n;i++)if(SumM[i]<m)
{
uint l=i,r=n-1;
while(l<r){uint mid=(l+r+1)>>1;if(SumM[mid]-V[i]*(T[mid]-T[i])<m)l=mid;else r=mid-1;}
_max(ans,T[l]+(m+V[i]*(T[l]-T[i])-SumM[l]+Sum[l+1]-V[i]-1)/(Sum[l+1]-V[i]));
}
if(!ans)exit(233);
printf("%llu\n",ans);
return 0;
}
T6
\(a\) 在 \(b\) 前的概率为 \(a/(a+b)\)，分治 FFT 统计一下贡献即可。
复杂度 \(O(n+v\log^2v)\)。
#include <bits/stdc++.h>
typedef unsigned uint;
typedef long long llt;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _min(T&a,T b){return b<a?(a=b,true):false;}
template<typename T>bol _max(T&a,T b){return a<b?(a=b,true):false;}
// And in that light, I find deliverance.
const ullt Mod=998244353,g=3;
struct modint
{
ullt v;
modint():v(0){}
modint(ullt v):v(v%Mod){}
ullt&operator()(){return v;}
friend modint operator+(modint a,modint b){return a()+b();}
friend modint operator-(modint a,modint b){return a()+Mod-b();}
friend modint operator*(modint a,modint b){return a()*b();}
friend modint operator/(modint a,modint b){return a*b.inv();}
friend modint operator^(modint a,ullt b)
{
modint ans(1);
while(b)
{
if(b&1)ans*=a;
a*=a,b>>=1;
}
return ans;
}
modint inv(){return(*this)^(Mod-2);}
modint&operator+=(modint b){return*this=*this+b;}
modint&operator-=(modint b){return*this=*this-b;}
modint&operator*=(modint b){return*this=*this*b;}
modint&operator/=(modint b){return*this=*this/b;}
modint&operator^=(ullt b){return*this=*this^b;}
voi read(){scanf("%llu",&v),v%=Mod;}
voi print(){printf("%llu",v);}
voi println(){print(),putchar('\n');}
};
typedef std::vector<modint>modvec;
struct NTT
{
uint n;std::vector<uint>Rev;modvec G;
voi bzr(uint len)
{
n=1;while(n<len)n<<=1;
Rev.resize(n),G.resize(n);
modint w=modint(g)^((Mod-1)/n);
for(uint i=1;i<n;i++)Rev[i]=(Rev[i>>1]|(i&1?n:0))>>1;
G[0]=1;for(uint i=1;i<n;i++)G[i]=G[i-1]*w;
}
voi ntt(modvec&x,bol op)
{
if(x.size()<n)x.resize(n);
for(uint i=1;i<n;i++)if(i<Rev[i])std::swap(x[i],x[Rev[i]]);
for(uint i=1;i<n;i<<=1)for(uint j=0;j<n;j+=i<<1)for(uint k=0;k<i;k++)
{
modint u=x[j|k],v=x[i|j|k]*G[n/i/2*k];
x[j|k]=u+v,x[i|j|k]=u-v;
}
if(op)
{
std::reverse(x.begin()+1,x.begin()+n);
modint v=modint(n).inv();
for(uint i=0;i<n;i++)x[i]*=v;
}
}
};
uint Cnt[100005];
modint S[200005];
voi dfs(uint l,uint r)
{
if(l==r)return;
uint mid=(l+r)>>1;
dfs(l,mid),dfs(mid+1,r);
modvec A,B;
for(uint i=l;i<=mid;i++)A.push_back(Cnt[i]);
for(uint i=mid+1;i<=r;i++)B.push_back(modint(i)*Cnt[i]);
NTT s;s.bzr(r-l);
s.ntt(A,0),s.ntt(B,0);
for(uint i=0;i<A.size();i++)A[i]*=B[i];
s.ntt(A,1);
for(uint i=0;i<r-l;i++)S[l+mid+1+i]+=A[i];
}
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
freopen("QAQ.out","w",stdout);
#endif
uint n;scanf("%u",&n);
for(uint i=0,v;i<n;i++)scanf("%u",&v),Cnt[v]++;
dfs(1,100000);
modint ans;
for(uint i=1;i<200000;i++)
ans+=S[i]/i;
ans.println();
return 0;
}
T7
首先肯定是 \(k\) 个一位数加一个 \(n-k\) 位数。
对于 \(n-k\) 很小的情况，可以直接暴力解决。
否则，由于没有 \(0\)，那个 \(n-k\) 位数即为高 \(n-k-8\) 位最大的数，使用哈希或者 SA 求出所有合法位置枚举一下即可。
总复杂度 \(O(n\log n)\)。SA 写挂了好几次。/fn
#include <bits/stdc++.h>
typedef unsigned uint;
typedef long long llt;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _min(T&a,T b){return b<a?(a=b,true):false;}
template<typename T>bol _max(T&a,T b){return a<b?(a=b,true):false;}
// And in that light, I find deliverance.
chr C[1000005];uint Rank[1000005],SA[1000005],H[1000005],n;
voi build()
{
for(uint i=0;i<n;i++)SA[i]=i;
std::sort(SA,SA+n,[&](uint a,uint b){return C[a]<C[b];});
for(uint i=n-1;~i;i--)Rank[SA[i]]=i!=n-1&&C[SA[i]]==C[SA[i+1]]?Rank[SA[i+1]]:i;
for(uint h=1;h<n;h<<=1)
{
static uint Cnt[1000005];
for(uint i=0;i<h;i++)H[i]=n-h+i;
for(uint i=0,j=h;i<n;i++)if(SA[i]>=h)H[j++]=SA[i]-h;
for(uint i=0;i<n;i++)Cnt[i]=i;
for(uint i=n-1;~i;i--)SA[Cnt[Rank[H[i]]]--]=H[i];
bol ok=true;
for(uint i=n-1;~i;i--)H[SA[i]]=i!=n-1&&Rank[SA[i]]==Rank[SA[i+1]]
&&(SA[i]+h<n?Rank[SA[i]+h]:-1u)==(SA[i+1]+h<n?Rank[SA[i+1]+h]:-1u)?(ok=false,H[SA[i+1]]):i;
for(uint i=0;i<n;i++)Rank[i]=H[i];
if(ok)break;
}
for(uint i=0,j=0;i<n;i++)
{
if(j)j--;
if(Rank[i])while(i+j<n&&SA[Rank[i]-1]+j<n&&C[i+j]==C[SA[Rank[i]-1]+j])j++;
H[Rank[i]]=j;
}
// for(uint i=0;i<n;i++)puts(C+SA[i]);
}
uint W[1000005];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
freopen("QAQ.out","w",stdout);
#endif
uint k;scanf("%u%u%s",&n,&k,C);
if(!k)return puts(C),0;
if(n-k<=8)
{
uint ans=0,s=0;for(uint i=0;i<n;i++)s+=C[i]-'0';
for(uint l=0;l<=k;l++)
{
uint t=0,q=0;for(uint j=0;j<n-k;j++)t=t*10+(C[l+j]-'0'),q+=C[l+j]-'0';
_max(ans,t+s-q);
}
printf("%u\n",ans);
return 0;
}
static uint S[1000005];
for(uint i=0;i<n;i++)S[i+1]=S[i]+(C[i]-'0');
build();
uint r=n-1;while(SA[r]>k)r--;
for(uint i=0;i<n-k;i++)W[i]=C[SA[r]+n-k-i-1]-'0';
uint w=S[SA[r]+n-k]-S[SA[r]];
while(H[r]>=n-k-8)if(SA[--r]<=k)_min(w,S[SA[r]+n-k]-S[SA[r]]);
W[0]+=S[n]-w;
uint t=0;
while(W[t])W[t+1]+=W[t]/10,W[t]%=10,t++;
while(t--)putchar(W[t]+'0');
putchar('\n');
return 0;
}
T4
随便拿个平衡树维护一下就好了。复杂度 \(O(n\log n)\)。
比赛最后半小时时开这题，写完刚好结束了，所以不知道代码有没有写挂。/fn
#include <bits/stdc++.h>
typedef unsigned uint;
typedef long long llt;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _min(T&a,T b){return b<a?(a=b,true):false;}
template<typename T>bol _max(T&a,T b){return a<b?(a=b,true):false;}
// And in that light, I find deliverance.
namespace Splay
{
struct node
{
node*son[2],*fath;uint siz,maxv;std::vector<uint>v;
node(uint v):son({NULL,NULL}),fath(NULL),siz(1),maxv(v),v({v}){}
bol howson(){return this==fath->son[1];}
voi pushup()
{
maxv=v.back(),siz=1;
if(son[0])_max(maxv,son[0]->maxv),siz+=son[0]->siz;
if(son[1])_max(maxv,son[1]->maxv),siz+=son[1]->siz;
}
voi rotate()
{
if(!fath)return;
node*f=fath,*ff=fath->fath;bol sk=howson();
if((fath=ff))ff->son[f->howson()]=this;
if((f->son[sk]=son[!sk]))son[!sk]->fath=f;
(son[!sk]=f)->fath=this,f->pushup(),pushup();
}
voi println()
{
printf("%u",(uint)v.size());
for(auto s:v)printf(" %u",s);
puts("");
}
}*rot;
voi splay(node*p)
{
while(p->fath)
{
if(p->fath->fath)(p->fath->howson()==p->howson()?p->fath:p)->rotate();
p->rotate();
}
(rot=p)->pushup();
}
voi kth(uint k)
{
node*p=rot;
while(true)
{
if(p->son[0])
{
if(k<p->son[0]->siz){p=p->son[0];continue;}
k-=p->son[0]->siz;
}
if(!k)return splay(p);
k--,p=p->son[1];
}
}
voi insert(uint k,uint v)
{
if(!rot){rot=new node(v);return;}
if(k<rot->siz)kth(k);
if(!k)return(rot->son[0]=new node(v))->fath=rot,splay(rot->son[0]);
node*p=k==rot->siz?rot:rot->son[0];
while(p->son[1])p=p->son[1];
(p->son[1]=new node(v))->fath=p,splay(p);
}
typedef std::pair<uint,uint>RET;
RET doit(uint k,uint v)
{
if(!rot)return insert(k,v),RET{0,1};
kth(k);
if(rot->maxv<=v)return insert(k,v),RET{k+1,rot->siz};
if(rot->v.back()>v)return rot->v.push_back(v),rot->pushup(),RET{(k+1)%rot->siz,1};
node*p=rot->son[rot->son[1]&&rot->son[1]->maxv>v];
while(true)
{
if(p->son[0]&&p->son[0]->maxv>v){p=p->son[0];continue;}
if(p->v.back()>v)break;
p=p->son[1];
}
p->v.push_back(v),splay(p);
uint r=rot->son[0]?rot->son[0]->siz:0;
return{(r+1)%rot->siz,r+rot->siz*(r<k)+1-k};
}
voi dfs(node*p)
{
if(!p)return;
dfs(p->son[0]);
p->println();
dfs(p->son[1]);
}
voi print(uint k)
{
printf("%u\n",rot->siz);
kth(k);
rot->println();
dfs(rot->son[1]);
dfs(rot->son[0]);
}
}
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
freopen("QAQ.out","w",stdout);
#endif
uint n,k=0;ullt s=0;
scanf("%u",&n);
if(!n)return puts("0 0");
while(n--)
{
uint v;scanf("%u",&v);
auto t=Splay::doit(k,v);
k=t.first,s+=t.second;
}
printf("%llu ",s);
Splay::print(k);
return 0;
}