2020牛客暑期多校第一场
MorphLing
7月 16, 2020
J.Easy_Integration
结论是(n!)^2 / (2n+1)!。听说是用Wallis积分算的，我还是找规律吧。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f,MOD=998244353;
int T,n,m;
int qpower(int x,int p)
{
int ret=1,base=x;
while(p)
{
if (p&1==1) ret=(1ll*ret*base)%MOD;
base=(1ll*base*base)%MOD;
p=p>>1;
}
return ret;
}
int ans[N];
int main()
{
ans[1]=6;
for (int i=2;i<=1000000;i++)
{
ans[i]=(1ll*ans[i-1]*2*(i*2+1))%MOD;
ans[i]=(1ll*ans[i]*qpower(i,MOD-2))%MOD;
}
int x;
while(scanf("%d",&x)!=-1) printf("%d\n",qpower(ans[x],MOD-2));
return 0;
}
I.1_or_2
把每个顶点拆成d[i]个点，每条边(u,v)拆成两个点把这两个点连边，并与对应的点连边，跑一次一般图最大匹配，判断是否存在完美匹配。
存在完美匹配时，某条边拆成的两个点要么互相匹配，要么各自与对应的顶点匹配，分别对应了用和不用这条边的两种情况。且每个顶点的度数都为d[i]。
一般图最大匹配用的是带花树的板子，存个档。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N=300+5;
int n,m;
int d[MAX_N];
int N;
bool Graph[MAX_N][MAX_N];
int Match[MAX_N];
bool InQueue[MAX_N],InPath[MAX_N],InBlossom[MAX_N];
int Head,Tail;
int Queue[MAX_N];
int Start,Finish;
int NewBase;
int Father[MAX_N],Base[MAX_N];
int Count;
void CreatGraph(){
int u,v;
vector<int>V[MAX_N];
memset(Graph,false,sizeof(Graph));
int tot=1;
for (int i=1;i<=n;i++)
{
scanf("%d",&d[i]);
for (int j=1;j<=d[i];j++) V[i].push_back(tot++);
}
for (int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
int x=tot++,y=tot++;
for (int j=0;j<d[u];j++) Graph[V[u][j]][x]=Graph[x][V[u][j]]=1;
for (int j=0;j<d[v];j++) Graph[V[v][j]][y]=Graph[y][V[v][j]]=1;
Graph[x][y]=Graph[y][x]=1;
}
N=tot-1;
}
void Push(int u){
Queue[Tail]=u;
Tail++;
InQueue[u]=true;
}
int Pop(){
int res=Queue[Head];
Head++;
return res;
}
int FindCommonAncestor(int u,int v){
memset(InPath,false,sizeof(InPath));
while(1){
u=Base[u];
InPath[u]=1;
if(u==Start)break;
u=Father[Match[u]];
}
while(1){
v=Base[v];
if(InPath[v])break;
v=Father[Match[v]];
}
return v;
}
void ResetTrace(int u){
int v;
while(Base[u]!=NewBase){
v=Match[u];
InBlossom[Base[u]]=InBlossom[Base[v]]=1;
u=Father[v];
if(Base[u]!=NewBase)Father[u]=v;
}
}
void BloosomContract(int u,int v){
NewBase=FindCommonAncestor(u,v);
memset(InBlossom,false,sizeof(InBlossom));
ResetTrace(u);
ResetTrace(v);
if(Base[u]!=NewBase)Father[u]=v;
if(Base[v]!=NewBase)Father[v]=u;
for(int tu=1;tu<=N;tu++){
if(InBlossom[Base[tu]]){
Base[tu]=NewBase;
if(!InQueue[tu])Push(tu);
}
}
}
void FindAugmentingPath(){
memset(InQueue,false,sizeof(InQueue));
memset(Father,0,sizeof(Father));
for(int i=1;i<=N;i++){
Base[i]=i;
}
Head=Tail=1;
Push(Start);
Finish=0;
while(Head<Tail){
int u=Pop();
for(int v=1;v<=N;v++){
if(Graph[u][v]&&(Base[u]!=Base[v])&&(Match[u]!=v)){
if((v==Start)||((Match[v]>0)&&Father[Match[v]]>0))BloosomContract(u,v);
else if(Father[v]==0){
Father[v]=u;
if(Match[v]>0)Push(Match[v]);
else{
Finish=v;
return;
}
}
}
}
}
}
void AugmentPath(){
int u,v,w;
u=Finish;
while(u>0){
v=Father[u];
w=Match[v];
Match[v]=u;
Match[u]=v;
u=w;
}
}
void Edmonds(){
memset(Match,0,sizeof(Match));
for(int u=1;u<=N;u++){
if(Match[u]==0){
Start=u;
FindAugmentingPath();
if(Finish>0)AugmentPath();
}
}
}
void PrintMatch(){
Count=0;
for(int u=1;u<=N;u++){
if(Match[u]>0)Count++;
}
if(Count==N)printf("Yes\n");
else printf("No\n");
}
int main(){
while(scanf("%d%d",&n,&m)==2){
CreatGraph();
Edmonds();
PrintMatch();
}
}
H.Minimum-cost_Flow
原题意是求总流量为1，每条边容量为$\frac{u}{v}$时的最小花费c。
将问题转化成总流量为$\frac{v}{u}$，每条边容量为1时的最小化花费c’。且有$c=c’*\frac{u}{v}$。
由于每条边容量相同且为1，可知每跑一次spfa之后如果找到一条增广路，则新增的流量一定为1，且整数之间的流量与花费的增长是线性的。因此先计算出流量为整数i时的花费cost[i]，然后将总流量$\frac{v}{u}$拆成整数部分和分数部分来计算。
通过增广路的个数算出最大流量，若最大流量小于总流量$\frac{v}{u}$则输出NaN。
#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" : "<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN=2e3+5;
int top,n,m,q,x,y,f;
ll u,v;
ll cost[MAXN];
bool vis[MAXN];
int s,t,dis[MAXN],pre[MAXN],last[MAXN],flow[MAXN],maxflow,mincost;
struct Edge{
int to,next,flow,dis;
}edge[MAXN];
int head[MAXN],num_edge;
queue <int> q_SPFA;
void add_edge(int from,int to,int flow,int dis)
{
edge[++num_edge].next=head[from];
edge[num_edge].to=to;
edge[num_edge].flow=flow;
edge[num_edge].dis=dis;
head[from]=num_edge;
}
bool spfa(int s,int t)
{
memset(dis,0x7f,sizeof(dis));
memset(flow,0x7f,sizeof(flow));
memset(vis,0,sizeof(vis));
q_SPFA.push(s); vis[s]=1; dis[s]=0; pre[t]=-1;
while (!q_SPFA.empty())
{
int now=q_SPFA.front();
q_SPFA.pop();
vis[now]=0;
for (int i=head[now]; i!=-1; i=edge[i].next)
{
if (edge[i].flow>0 && dis[edge[i].to]>dis[now]+edge[i].dis)
{
dis[edge[i].to]=dis[now]+edge[i].dis;
pre[edge[i].to]=now;
last[edge[i].to]=i;
flow[edge[i].to]=min(flow[now],edge[i].flow);
if (!vis[edge[i].to])
{
vis[edge[i].to]=1;
q_SPFA.push(edge[i].to);
}
}
}
}
return pre[t]!=-1;
}
void MCMF()
{
while (spfa(s,t))
{
int now=t;
maxflow+=flow[t];
mincost+=flow[t]*dis[t];
cost[++top]=mincost;
while (now!=s)
{
edge[last[now]].flow-=flow[t];
edge[last[now]^1].flow+=flow[t];
now=pre[now];
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=-1)
{
memset(head,-1,sizeof(head)); num_edge=-1;
s=1,t=n;
for (int i=1; i<=m; i++)
{
scanf("%d%d%d",&x,&y,&f);
add_edge(x,y,1,f); add_edge(y,x,0,-f);
}
memset(cost,0,sizeof(cost));
top=0;
mincost=0;
MCMF();
scanf("%d",&q);
for (int i=1;i<=q;i++)
{
scanf("%lld%lld",&u,&v);
if (u*top<v)
printf("NaN\n");
else
{
ll a=v/u;
ll b=v%u;
ll ans=cost[a]*u+(cost[a+1]-cost[a])*b;
ll k=__gcd(ans,v);
ans/=k,v/=k;
printf("%lld/%lld\n",ans,v);
}
}
}
return 0;
}
A.B-Suffix_Array
题解意思是根据s计算出一个数组C，满足 Ci=min{j>i && s[j]==s[i]}{j-i}，对于最后的a、b设为n，并在C数组最后加一个n+1，然后对C跑一下后缀数组，答案是按顺序输出sa[i]。
然而没看懂结论也不会后缀数组。贴代码存板子。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int n;
char S[MAXN];
int s[MAXN];
int last[2];
//char s[MAXN];
struct SA {
int sa[MAXN], ra[MAXN], height[MAXN];
int t1[MAXN], t2[MAXN], c[MAXN];
void build(int *str, int n, int m) {
str[n] = 0;
n++;
int i, j, p, *x = t1, *y = t2;
for (i = 0; i < m; i++) c[i] = 0;
for (i = 0; i < n; i++) c[x[i] = str[i]]++;
for (i = 1; i < m; i++) c[i] += c[i - 1];
for (i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
for (j = 1; j <= n; j <<= 1) {
p = 0;
for (i = n - j; i < n; i++) y[p++] = i;
for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = 0; i < m; i++) c[i] = 0;
for (i = 0; i < n; i++) c[x[y[i]]]++;
for (i = 1; i < m; i++) c[i] += c[i - 1];
for (i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1;
x[sa[0]] = 0;
for (i = 1; i < n; i++)
x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? p - 1 : p++;
if (p >= n) break;
m = p;
}
n--;
for (int i = 0; i <= n; i++) ra[sa[i]] = i;
for (int i = 0, j = 0, k = 0; i <= n; i++) {
if (k) k--;
j = sa[ra[i] - 1];
while (str[i + k] == str[j + k]) k++;
height[ra[i]] = k;
}
st_init(height, n);
}
int lg[MAXN], table[23][MAXN];
void st_init(int *arr, int n) {
if (!lg[0]) {
lg[0] = -1;
for (int i = 1; i < MAXN; i++)
lg[i] = lg[i / 2] + 1;
}
for (int i = 1; i <= n; ++i)
table[0][i] = arr[i];
for (int i = 1; i <= lg[n]; ++i)
for (int j = 1; j <= n; ++j)
if (j + (1 << i) - 1 <= n)
table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}
int lcp(int l, int r) {
l = ra[l], r = ra[r];
if (l > r) swap(l, r);
++l;
int t = lg[r - l + 1];
return min(table[t][l], table[t][r - (1 << t) + 1]);
}
} sa;
/*bool cmp(int i, int j) {
if (dis[i] != dis[j]) return dis[i] < dis[j];
if (i + dis[i] > n) return true;
if (j + dis[j] > n) return false;
int lcp = sa.lcp(i + dis[i], j + dis[j]);
return a[i + lcp + dis[i]] < a[j + lcp + dis[j]];
}*/
int main(){
while(scanf("%d",&n)!=-1)
{
scanf("%s",S);
last[0]=last[1]=0;
s[n]=n+1;
for (int i=n-1;i>=0;i--)
{
int now= S[i]=='a' ? 0 : 1;
if (last[now]==0) s[i]=n;
else s[i]=(last[now]-i);
last[now]=i;
}
n++;
sa.build(s,n,n+2);
for(int i = n-1;i >=1 ;i--)
printf("%d ",sa.sa[i]+1);
printf("\n");
}
return 0;
}