首先由于作者水平有限，可能只有部分的题解，且有些做法不一定标准，但是均可过题，大家见谅...
A: B-Suffix Array
这是一道结论题：首先题目是要求求一个B数组，但是这个B数组的求***有一定的问题，也就是整个字符串的B数组的一个后缀，但是它不一定满足是这个后缀的B数组，感觉可能有点绕...
然后B数组是求的和这个数最接近的pre，那么我们可以同理搞一个C数组，然后求一个与这个数最接近的suf，然后根据这个C数组做一下后缀排序，然后逆序的就是这个ans数组！
上面没有证明，这个证明可以感性理解下，感觉有一篇博客写的比较好，大概是你考虑比较Cx比Cy大，和Cx比Cy小的2种情况，然后分别发现与之对应的Bx和By的情况恰好相反，可以多举几个例子就可以发现。
同理这样的思路类似的字符串题也可以转化一下！
然后就是如果没有suf的情况，我们就设它为n，然后最后要在末尾加一个很大的数，这样保证答案的正确性...（这是一个易错点）
（另：这种做法叉姐说当且仅当字符集是2才满足条件，大家谨慎使用）
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=100005;
int n,buc[N],c[N],sa[N],rnk[N],fir[N],sec[N];char str[N];
void print(){
for(int i=1;i<=n;i++)printf("%d%c",sa[i]," \n"[i==n]);
for(int i=1;i<=n;i++)printf("%d%c",rnk[i]," \n"[i==n]);
}
void suffixsort(){
for(int i=1;i<=n;i++)buc[i]=0;
for(int i=1;i<=n;i++)buc[c[i]]++;
for(int i=1;i<=n;i++)buc[i]+=buc[i-1];
for(int i=n;i>=1;i--)sa[buc[c[i]]--]=i;
rnk[sa[1]]=1;for(int i=2;i<=n;i++)rnk[sa[i]]=rnk[sa[i-1]]+(c[sa[i]]!=c[sa[i-1]]);
//print();
for(int k=1;k<=n;k<<=1){
for(int i=1;i<=n;i++)fir[i]=rnk[i],sec[i]=(i+k<=n?rnk[i+k]:0);
for(int i=1;i<=n;i++)buc[i]=0;
for(int i=1;i<=n;i++)buc[sec[i]]++;
for(int i=1;i<=n;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)rnk[buc[sec[i]]--]=i;
for(int i=1;i<=n;i++)buc[i]=0;
for(int i=1;i<=n;i++)buc[fir[i]]++;
for(int i=1;i<=n;i++)buc[i]+=buc[i-1];
for(int i=n;i>=1;i--)sa[buc[fir[rnk[i]]]--]=rnk[i];
rnk[sa[1]]=1;for(int i=2;i<=n;i++)rnk[sa[i]]=rnk[sa[i-1]]+(fir[sa[i]]!=fir[sa[i-1]]||sec[sa[i]]!=sec[sa[i-1]]);
//printf("k:%d\n",k);print();
}
}
int main(){
while(scanf("%d",&n)!=EOF){
scanf("%s",str+1);
for(int i=1;i<=n;i++){
c[i]=0;
for(int j=i+1;j<=n;j++)if(str[j]==str[i]){c[i]=j-i;break;}
if(!c[i])c[i]=n;
}
n++;c[n]=n;suffixsort();
for(int i=n-1;i>=1;i--)printf("%d%c",sa[i]," \n"[i==1]);
}
return 0;
}F:Infinite String Comparision
这场的签到题，感觉没有什么好说的吧，就是大概我们长度为x和y，比较到x+y就可以了，其实是x+y-gcd(x,y)但是我也不是很会证明，考试的时候可以举一个100000和99999的极限例子就可以发现这个规律
作者在比赛的时候为了保险比到了3*max(x,y)，这也是一种不错的考场做法...
代码这里可以有很多写法，实现起来很简单，就不给了/xk
H：Minimum-cost Flow
这题考察了一些有关于网络流的流量一些变形和转化
首先是我们可以发现这里的流量和费油可以同时乘上一个常数c，然后最后计算的时候我们只需要把它再除回来就可以了！
然后我们可以搞一个1作为稳定的流量，针对不同的流量我们只需要除一个常数1/c即可！
注意，这个ans函数在坐标系里是凸函数，因此我们增广的时候用一个vector<int>span，记录一下增广的过程的费用，然后我们只需要在询问的时候遍历这个vector然后卡到最优即可，由于图的大小较小，所以这个vector的大小不会很大，我们就O(size)完成了一次查询！
注意一种NaN的情况，就是无论如何都增广不到指定ans的一种可能，要特判一下！
代码：</int>
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=105,M=205,Inf=2e9;
int n,m,q,fst[N],tote,s,t,dis[N],mn[N],pre[N],from[N];bool inq[N];LL flow,cost;
struct Edge{int to,f,w,nxt;}e[M];
vector<LL>span;
inline void adde(int u,int v,int f,int w){
e[++tote]=(Edge){v,f,w,fst[u]};fst[u]=tote;
e[++tote]=(Edge){u,0,-w,fst[v]};fst[v]=tote;
}
inline bool EK(){
queue<int>que;while(!que.empty())que.pop();
for(int i=1;i<=n;i++)dis[i]=Inf,inq[i]=false;
que.push(s),inq[s]=true,dis[s]=0,mn[s]=Inf;
while(!que.empty()){
int u=que.front();que.pop();inq[u]=false;
for(int i=fst[u];i!=-1;i=e[i].nxt){
int v=e[i].to,f=e[i].f,w=e[i].w;
if(f>0&&dis[v]>dis[u]+w){
dis[v]=dis[u]+w;mn[v]=min(mn[u],f);pre[v]=i;from[v]=u;
if(!inq[v])inq[v]=true,que.push(v);
}
}
}
return dis[t]<Inf;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++)fst[i]=-1;tote=1;
s=1;t=n;flow=cost=0;span.clear();
for(int i=1,u,v,w;i<=m;i++)scanf("%d%d%d",&u,&v,&w),adde(u,v,1,w);
while(EK()){
for(int i=t;i!=s;i=from[i])e[pre[i]].f-=mn[t],e[pre[i]^1].f+=mn[t];
flow+=(LL)mn[t];cost+=(LL)dis[t]*mn[t];span.pb(dis[t]);
}
scanf("%d",&q);
while(q--){
LL u,v;scanf("%lld%lld",&u,&v);//u/v*v/u
if(flow*u<v)puts("NaN");
else{
LL ff=v,cc=u,ans=0;
for(auto x:span)if(ff>=u)ff-=u,ans+=u*x;else{ans+=ff*x;break;}
LL g=__gcd(ans,v);printf("%lld/%lld\n",ans/g,v/g);
}
}
}
return 0;
}I：1 or 2
这题的正解好像是什么带花树，很神仙，作者不会
于是这里有两种优秀的做法，时间在目前配置的较水的数据比标算快
1 随机化，也就是叉姐说的概率算法，可以每次考虑还不满足条件的情况，然后用一个vector记录一个点的边的编号和另外一个点，然后我们把不满足条件的一一调整，这里可能是一种比较奇怪的随机化，类似于相对于一个模板我们不断类似于退火的思想慢慢靠近，然后最后判断是否满足条件，中间到底是先调整哪边我们要用随机的思想，这样可以较好的利用最优性的概率，然后达到算法的稳定性！
2 dfs爆搜，这个算法需要改变一下搜索的方式，然后我们加一些剪枝就可以通过，比较玄学！可以见代码：
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=105;
int n,m,d[N],id[N];bool usd[N];vector<pii>e[N];
bool dfs(int dep){
if(dep>n)return true;
int u=id[dep];
if(!d[u])return dfs(dep+1);
for(auto edg:e[u]){
int v=edg.first,num=edg.second;
if(!d[v]||usd[num])continue;
d[u]--,d[v]--,usd[num]=true;
if(dfs(dep))return true;
d[u]++,d[v]++,usd[num]=false;
}
return false;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++)scanf("%d",&d[i]),id[i]=i,e[i].clear();
for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),e[u].pb(pii(v,i)),e[v].pb(pii(u,i)),usd[i]=false;
sort(id+1,id+n+1,[&](int u,int v){return e[u].size()<e[v].size();});
puts(dfs(1)?"Yes":"No");
}
return 0;
}J：Easy Integration
积分题，作者不太会证明，考试的时候降智了，没写出来...
后来可以通过分子和分母找规律，可以得到结论：
(n!)^2/(2n+1)！
这里有一个好办法，就是通过模数和分数给出在模数下取模的形式，即ans，得到分子和分母（dreamoon神仙以前出的一道题）
给出这个找分子和分母的程序（网上的代码，不是作者写的，这里借鉴一下）
找分数的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
void f(ll a, ll b, ll c, ll d, ll& x, ll& y){
ll q = a / b + 1;
if (q <= c / d){
x = q;
y = 1;
return;
}
q--;
a -= q * b; c -= q * d;
f(d, c, b, a, y, x);
x += q * y;
return;
}
int main(){
int t;
scanf("%d", &t);
while (t--){
ll b, y, a, p, x;
scanf("%lld%lld", &p, &x);
f(p, x, p, x - 1, b, y);
a = b * x - y * p;
printf("%lld/%lld\n", a, b);
}
return 0;
}作者本题的代码就不给了，很好实现一个快速幂和逆元就可以完事了...见谅
京公网安备 11010502036488号