2020牛客暑期多校训练营（第一场）AFIHJ

总结：
这次比赛题面很难理解，还是英语太菜，先开的I，但是因为题意表述不清，然后题意讨论了好久，然后发现F有人过了，就去写F，结果F题意理解错了导致WA了两发，及时发现改正，然后开的J，手推了一会儿，然后交给lyx去写，因为取模的问题WA了一发，然后又回来看I题，决定试一试题意，结果到最后题意理解还是错的。

A

题意

给定一个字符串，根据题目要求将每个后缀的b函数进行排序，从小到大输出对应后缀的起始位置。

思路

对B序列建后缀数组。定义c[i]=j-i，j为索引i后面最近的索引使得s[i]==s[j]，即c[i]的值是i后面离“i指针”对应的字母最近的与s[i]同字符的距离。c数组后缀排序就是实际字符串b函数从大到小的排序。由此用后缀数组对c数组求sa数组即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false),cin.tie(0);
#define ll long long
#define inf 0x3f3f3f3f
const int N=1e5+5;
//set<string>b;
//set<string>::iterator it;
int n,m,sa[N],x[N],y[N],p[N];
char s[N];
void quicksort()
{
	int i;
	for(i=0;i<m;i++)
	{
		p[i]=0;
	}
	for(i=0;i<n;i++)
	{
		p[x[i]]++;
	}
	for(i=1;i<m;i++)
	{
		p[i]+=p[i-1];
	}
	for(i=n-1;i>=0;i--)
	{
		sa[--p[x[y[i]]]]=y[i];
	}
}
void get_sa()
{
	quicksort();
	int i,j,t;
	for(j=1,t=1;t<n;j<<=1,m=t)
	{
		t=0;
		for(i=n-j;i<n;i++)
		{
			y[t++]=i;
		}
		for(i=0;i<n;i++)
		{
			if(sa[i]>=j) y[t++]=sa[i]-j;
		}
		quicksort();
		for(i=0;i<n;i++)
		{
			y[i]=x[i];
		}
		x[sa[0]]=0,t=1;
		for(i=1;i<n;i++)
		{
			if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])
				x[sa[i]]=t-1;
			else
				x[sa[i]]=t++;
		}
	}
}
int main()
{
    IO;
    int a,b,i,j;
    while(cin>>n)
    {
    	cin>>s;
		a=n;b=n;
    	for(i=n-1;i>=0;i--)
    	{
    		y[i]=i;
    		if(s[i]=='a')
    		{
    			if(a==n) x[i]=1;
    			else x[i]=n-a+i+1;
    			a=i;
			}
			else
			{
				if(b==n) x[i]=1;
				else x[i]=n-b+i+1;
				b=i;
			}
		}
		x[n]=0;y[n]=n;
		n++;
		m=n+1;
		get_sa();
		for(i=1;i<n-1;i++)
		{
			cout<<sa[i]+1<<" ";
		}
		cout<<sa[n-1]+1<<endl;
	} 
    return 0; 
}

F

题意

给你两个字符串，比较这两个字符串各自重复无限次以后的字典序。

思路

将两个字符串重复到这两个字符串长度中较大的那个的两倍的长度，就可以比较了。在重复过程中若字符不相等可直接比较出答案。

代码

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int inf = ~0u >> 1;
typedef pair<int,int> P;
#define REP(i, a, n) for (int i = a; i < (n); ++i)
#define PER(i, a, n) for (int i = (n) - 1; i >= a; --i)
int main() {
    IO;
    string a, b;
    while (cin >> a >> b) {
        if (a == b) {
            cout << "=" << endl;
        }
        else {
            string aa, bb;
            int la = a.length(), lb = b.length();
            int cnt = max(la,lb)*2;
            bool flag=true;
            REP(i, 0, cnt) {
                if(a[i % la]>b[i % lb]) {
                    cout << ">" << endl;
                    flag=false;
                    break;
                }
                else if(a[i % la]<b[i % lb]) {
                    cout << "<" << endl;
                    flag=false;
                    break;
                }
            }
            if (flag==true)
            {
                cout << "=" << endl;
            }
             
        }
    }
     
    return 0;
}

I

题意

给你一个n个点m条边的无向图，通过删除一些边使每个点的度数满足di，若存在则输出Yes，否则输出No。

思路

通过拆点来跑一般图的最大匹配，将度数为2的点进行拆点，拆完的点连向对应的x，y点。如果达到完美匹配，这条边的另一头必定匹配着另一个点的一个度，表示拆点原点相连，这样一条边的匹配是合乎要求的。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
deque<int>q;
bool G[N][N],g[N][N],inque[N],inblossom[N],vis[N];
int match[N],pre[N],base[N];
int n,m,t,u,v,d,id;
vector<int>V[N];
struct node{
    int u,v;
}E[N];
int Find(int u,int v){
    bool inpath[N]={false};
    while(1){
        u=base[u];
        inpath[u]=true;
        if(match[u]==-1)break;
        u=pre[match[u]];
    }
    while(1){
        v=base[v];
        if(inpath[v])return v;
        v=pre[match[v]];
    }
}

void reset(int u,int anc){
    while(u!=anc){
        int v=match[u];
        inblossom[base[u]]=1;
        inblossom[base[v]]=1;
        v=pre[v];
        if(base[v]!=anc)pre[v]=match[u];
        u=v;
    }
}

void contract(int u,int v,int n){
    int anc=Find(u,v);
    memset(inblossom,0,sizeof(inblossom));
    reset(u,anc);reset(v,anc);
    if(base[u]!=anc)pre[u]=v;
    if(base[v]!=anc)pre[v]=u;
    for(int i=1;i<=n;i++)
        if(inblossom[base[i]]){
            base[i]=anc;
            if(!inque[i]){
                q.push_back(i);
                inque[i]=1;
            }
        }
}

bool dfs(int s,int n){
    for(int i=0;i<=n;i++)pre[i]=-1,inque[i]=0,base[i]=i;
    q.clear();q.push_back(s);inque[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop_front();
        for(int v=1;v<=n;v++){
            if(g[u][v]&&base[v]!=base[u]&&match[u]!=v){
                if(v==s||(match[v]!=-1&&pre[match[v]]!=-1))contract(u,v,n);
                else if(pre[v]==-1){
                    pre[v]=u;
                    if(match[v]!=-1)q.push_back(match[v]),inque[match[v]]=1;
                    else{
                        u=v;
                        while(u!=-1){
                            v=pre[u];
                            int w=match[v];
                            match[u]=v;
                            match[v]=u;
                            u=w;
                        }
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

void calculate()
{
    int ans=0;
    memset(match,-1,sizeof(match));
    for(int i=1;i<=id-1;i++)
        if(match[i]==-1&&dfs(i,id-1)) ans++;
    if(ans*2==id-1) printf("Yesn");
    else printf("Non");
}

void init(){
    id=1;
    memset(G,0,sizeof(G));
    memset(g,0,sizeof(g));
    for(int i=1;i<=n;i++) V[i].clear();
}

void build(){
    for(int i=1;i<=m;i++){
        for(auto k:V[E[i].u]) g[k][id]=g[id][k]=1;
        id++;
        for(auto k:V[E[i].v]) g[k][id]=g[id][k]=1;
        g[id][id-1]=g[id-1][id]=1;
        id++;
    }
}

int main(){
    while(~ scanf("%d%d",&n,&m)){
        init();
        for(int i=1;i<=n;i++){
            scanf("%d",&d);
            while(d--) V[i].push_back(id++);
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            G[u][v]=G[v][u]=1;
            E[i].u=u,E[i].v=v;
        }
        build();
        calculate();
    }
}

H

题意

给你一个n个点，m条边的有向图，并给出每条边的费用。然后进行q次询问，每次询问给出每条边的容量u/v，并且所有边的容量相等。 对于每次询问，你需要输出总流量为1时，从点1到点n的最小费用（分数表示）。

思路

比赛时候看了这个题，题意没看很懂，感觉是网络流的东西，但是如果每次询问都跑一遍显然是会T掉的，赛后看了别人的思路，发现是最小费用最大流的题，还需要预处理。
对于每次询问，总流量为1，每条边容量为u/v。考虑缩放，同时乘以v，则总流量为v，每条边容量为u，这时算出来的总费用除以v即为答案。 我们可以在询问之前，预处理得到所有增广路的费用，每次进行一次SPFA算法后，就能得到一条增广路的费用，将其记录于path数组中（按增广顺序能保证每条增广路费用是升序的），并求其前缀和，方便后续询问的处理。
查询之前，先预处理得到：
（1）path[a]，下标从0开始，表示单位容量(流量跑满，流量=容量)时第a+1条增广路费用。
（2）sum[a]，下标从1开始，表示单位容量(流量跑满，流量=容量)时前a条增广路总费用。
接下来处理每次询问。
假设v=a*u+b(b<u)，即前a条增广路流量都为u，第a+1条增广路流量达不到u，流量为b。
由于sum和path是之前预处理得到的单位容量情况下的费用，所以sum[a]要乘以u得到流量为u时前a条增广路总费用，path[a]要乘以b得到流量为b时第a+1条增广路费用，则ans=(sum[a]*u+path[a]*b)/v。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1010,M=1010,inf=(1ll<<63)-1;
ll n,m,s,t,cnt,mincost,head[N],dis[N],vis[N],cur[N],sum[M];
vector<ll>path;
struct edge
{
    ll to,next,cap,cost;//cap是容量，cost是单位流量的花费
}e[M<<1];
void add(ll x,ll y,ll z,ll c)
{
    e[cnt].to=y;
    e[cnt].cap=z;
    e[cnt].cost=c;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void add_edge(ll x,ll y,ll z,ll c)
{
    add(x,y,z,c);
    add(y,x,0,-c);//反向边容量为0，单位流量的花费为-c
}
bool spfa()
{
    queue<int>q;
    for(ll i=1;i<=n;i++)
        dis[i]=inf;
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    vis[s]=1;//入队标记
    q.push(s);
    while(!q.empty())
    {
        ll u=q.front();q.pop();
        vis[u]=0;//出队标记
        for(ll i=head[u];i!=-1;i=e[i].next)
        {
            ll v=e[i].to;
            if(e[i].cap>0&&dis[u]+e[i].cost<dis[v])
            {
                dis[v]=dis[u]+e[i].cost;
                if(!vis[v])
                {
                    vis[v]=1;//入队标记
                    q.push(v);
                }
            }
        }
    }//队列为空时 vis也全部被置为0
    if(dis[t]!=inf)return 1;
    return 0;
}
ll dfs(ll u,ll flow)
{
    vis[u]=1;//注意用vis标记走过的点，防止死循环
    if(u==t)return flow;//到达汇点，返回这条增广路上的最小流量
    for(ll& i=cur[u];i!=-1;i=e[i].next)
    {
        ll v=e[i].to;
        if(e[i].cap>0&&dis[v]==dis[u]+e[i].cost&&!vis[v])
        {
            ll di=dfs(v,min(flow,e[i].cap));//min(flow,e[i].w)表示起点到v的最小流量
            if(di>0)//防止dfs结果return 0的情况，如果di=0会死循环
            {
                e[i].cap-=di;
                e[i^1].cap+=di;//反向边加上di
                mincost+=di*e[i].cost;
                return di;//di表示整条增广路上的最小流量，回溯的时候一直向上返回，返回的di是不变的
            }
        }
    }
    vis[u]=0;//还原标记的点
    return 0;//找不到增广路，到不了汇点
}
ll dinic()
{
    ll maxflow=0;
    path.clear();
    while(spfa())//先spfa进行"探路"并分层，分层后进行多次dfs
    {
        path.push_back(dis[t]); // 每次spfa后得到一条增广路的费用
        memcpy(cur,head,sizeof(head));
        while(ll d=dfs(s,inf))//while循环的意义：只要dfs不为0，就一直dfs，直到找不到增广路
            maxflow+=d;
    }
    return maxflow;
}
// 以上都是dinic算法的模板，只是增加了path数组，用来在每次spfa后记录dis[t]。

int main()
{
    ios::sync_with_stdio(false);
    ll x,y,c,q,u,v;
    while(cin>>n>>m)
    {
        s=1,t=n;
        memset(head,-1,sizeof(head));
        cnt=0;
        mincost=0;
        for(ll i=1;i<=m;i++)
        {
            cin>>x>>y>>c;  // 点、边、费用
            add_edge(x,y,1,c); // 将每条边容量置为1
        }
        dinic(); // 跑费用流，得到path数组记录在单位容量的情况下，每条增广路上的费用(从小到大)
        ll pnum=path.size(); // 增广路个数
        for(ll i=0;i<pnum;i++)
            sum[i+1]=sum[i]+path[i]; // path[i]是第i+1条增广路费用
        // 查询之前，先预处理得到：
        // sum[a]，表示单位容量(流量跑满，流量=容量)时前a条增广路总费用
        // path[a]，表示单位容量(流量跑满，流量=容量)时第a+1条增广路费用
        cin>>q;
        while(q--)
        {
            cin>>u>>v;
            // 每条增广路容量由u/v扩成u，总流量由1扩成v，最后费用除以v即可
            if(u*pnum<v)printf("NaNn"); // 容量<总流量
            else
            {
                // 假设：v=a*u+b(b<u)，即前a条增广路流量都为u，第a+1条增广路流量达不到u，流量为b
                ll a=v/u;
                ll b=v%u;
                // 由于sum和path是之前预处理得到的单位容量情况下的费用
                // 所以sum[a]要乘以u得到流量为u时前a条增广路总费用，
                // path[a]要乘以b得到流量为b时第a+1条增广路费用
                ll ans=sum[a]*u+path[a]*b;
                ll k=__gcd(ans,v);
                ans/=k;
                v/=k;
                printf("%lld/%lldn",ans,v);
            }
        }
    }
    return 0;
}

J

题意

题目很简洁明了，求一个定积分结果要以p*q^-1的形式（mod998244353）

思路

看到题目第一反应求逆元，然后就是求解定积分了。数学基础不牢我们手算了n=1,2,3,4,5,6,7的结果，然后找出a[i]=a[i-1]2i/(4*(2*i+1))的规律，最后用费马小定理求逆元并记得用ll存数即可。

代码

#include<iostream>
#include<cmath>
#include<stack>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <complex>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
typedef long long ll;
const ll inf =1e17;
#define scn(a) scanf("%d",&a)
#define scd(a) scanf("%lf",&a)
#define scl(a) scanf("%lld",&a)
#define ptf(a) printf("%dn",a)
#define mes(a,b) memset(a,b,sizeof(a))
#define fon(s,n) for(int i=s;i<=n;i++)
#define range(i,a,b) for(int i=a;i<=b;++i)
#define rerange(i,a,b) for(int i=a;i>=b;--i)
//#define N 100010
const ll p =998244353;
const int S=20;
ll gcd(ll a,ll b) { return b>0 ? gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll q_pow(ll a,ll b,ll mod)
{
ll ans=1,res=a;
while(b){
if(b&1) ans=ans*res%mod;
res=res*res%mod;
b>>=1;
}
return ans%mod;
}
ll a[1000005];

void init(){
for(ll i=2;i<=1000000;i++){
a[i]=((a[i-1]%p)*(4*(2*i+1)%p))%p;
a[i]*=q_pow(2*i,p-2,p);
a[i]%=p;
}
}
int main()  
{  
a[1]=6;init();
ll n;
while(~scl(n)){
ll ans=q_pow(a[n],p-2,p);
cout<<ans<<endl;
}
    return 0;  
}

最后

以上就是殷勤河马为你收集整理的2020牛客暑期多校训练营（第一场）AFIHJ的全部内容，希望文章能够帮你解决2020牛客暑期多校训练营（第一场）AFIHJ所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。