hdu多校第十场题解(=100人)_综合

时间不多了，然而hdu的多校还没开始补。。博主打算先解决掉>=100人的题，其他的题等以后再补吧。
Problem E. TeaTree
第一次见线段树合并的题，没想到线段树还能这么用。真好玩。。
这题没什么逻辑问题，std也写的很好。这里就不多说了。

#include<bits/stdc++.h>
using namespace std;
const int maxv=1e5+5;
const int maxn=1e5+5;
const int maxnd=8.1e7+10;
vector<int>V[maxv];
void init()
{for(int i=1;i<maxv;i++)for(int j=1;j*i<maxv;j++)V[j*i].push_back(i);
}
int root[maxn];
int tot;
int ch[maxnd][2];
int newnode()
{tot++;ch[tot][0]=ch[tot][1]=0;return tot;
}void build(int l,int r,int v,int &rt)
{if(rt==0)rt=newnode();if(l==r)return;int m=l+r>>1;if(v<=m)build(l,m,v,ch[rt][0]);else build(m+1,r,v,ch[rt][1]);
}
int f;
int ans[maxn];
int fa[maxn];
int merge(int root1,int root2,int l,int r)
{if(root1==0||root2==0){return root1^root2;}if(l==r){ans[f]=max(ans[f],l);return root1;}int m=l+r>>1;ch[root1][0]=merge(ch[root1][0],ch[root2][0],l,m);ch[root1][1]=merge(ch[root1][1],ch[root2][1],m+1,r);return root1;
}int main()
{init();memset(ans,-1,sizeof(ans));int n;scanf("%d",&n);for(int i=2;i<=n;i++)scanf("%d",&fa[i]);int x;for(int i=1;i<=n;i++){scanf("%d",&x);root[i]=newnode();for(int j=0;j<V[x].size();j++)build(1,maxv,V[x][j],root[i]);}for(int i=n;i>=1;i--){f=fa[i];root[f]=merge(root[f],root[i],1,maxv);}for(int i=1;i<=n;i++)printf("%d\n",ans[i]);return 0;
}

Problem G. Cyclic
比赛的时候oeis过的，我觉得这样不行。。
看了题解才觉得自己推公式才最爽。题解也写的很详细了。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int maxn=1e5+5;
//***************************************************
//返回d=gcd(a,b)；和对应于等式ax+by=d中的x，y
long long extgcd(long long a,long long b,long long &x,long long &y)
{if(a==0&&b==0)return -1;//无最大公约数if(b==0){x=1;y=0;return a;}long long d=extgcd(b,a%b,y,x);y-=a/b*x;return d;//返回gcd(a,b)
}
//****************求逆元******************************
//ax=1(mod n)
long long mod_reverse(long long a,long long n)
{long long x,y;long long d=extgcd(a,n,x,y);if(d==1)return (x%n+n)%n;return -1;
}
long long tab1[maxn],tab2[maxn];
void init()
{tab1[0]=1;for(int i=1;i<=100000;i++)tab1[i]=tab1[i-1]*i%mod;tab2[100000]=mod_reverse(tab1[100000],mod);for(int i=99999;i>=0;i--)tab2[i]=tab2[i+1]*(i+1)%mod;
}
long long C(int a,int b)
{return tab1[a]*tab2[b]%mod*tab2[a-b]%mod;
}
int main()
{init();int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);long long ans=0;for(int i=0;i<n;i++){int flag=(i%2?-1:1);ans=(ans+1LL*flag*C(n,i)*tab1[n-1-i]%mod)%mod;}if(n%2)ans--;else ans++;printf("%lld\n",(ans%mod+mod)%mod);}}

Problem I. Count
这个题也是oeis过的呜呜呜。。
题解已经将式子化成这样
$\sum_{i=1}^n\sum_{a=1}^{i-1}[gcd(2i-a,a)=1]$
为什么会往下面化呢，这里说明两点内容。
1，x如果与n互质->n-x与n互质
2，n是奇数->与n互质的奇数占一半

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e7+5;int phi[maxn];
void phi_table(int n)
{for(int i=2;i<=n;i++)phi[i]=0;phi[1]=1;for(int i=2;i<=n;i++)if(!phi[i])for(int j=i;j<=n;j+=i){if(!phi[j])phi[j]=j;phi[j]=phi[j]/i*(i-1);}
}
long long sum[maxn];
void init()
{phi_table(maxn-5);for(int i=2;i<=maxn-5;i++){sum[i]=sum[i-1];if(i%2)sum[i]+=phi[i]/2;else sum[i]+=phi[i];}
}int main()
{init();int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);printf("%lld\n",sum[n]);}return 0;}

Problem J. CSGO
这题好巧妙啊。。
由于k不大，后面的累加实际上可以用(1<

#include<bits/stdc++.h>
using namespace std;long long S[1<<5],B[1<<5];
const long long inf=0x3f3f3f3f3f;
int x[6];
int main()
{int T;scanf("%d",&T);while(T--){memset(S,-inf,sizeof(S));memset(B,-inf,sizeof(B));int n,m,K;scanf("%d %d %d",&n,&m,&K);for(int i=1;i<=n;i++){int val;scanf("%d",&val);for(int j=0;j<K;j++)scanf("%d",&x[j]);for(int j=0;j<(1<<K);j++){long long res=0;for(int k=0;k<K;k++)res+=((((j>>k)&1)<<1)-1)*x[k];res+=val;S[j]=max(S[j],res);}}for(int i=1;i<=m;i++){int val;scanf("%d",&val);for(int j=0;j<K;j++)scanf("%d",&x[j]);for(int j=0;j<(1<<K);j++){long long res=0;for(int k=0;k<K;k++)res+=((((j>>k)&1)<<1)-1)*x[k];res+=val;B[j]=max(B[j],res);}}long long ans=-inf;for(int i=0;i<(1<<K);i++)ans=max(ans,S[i]+B[(1<<K)-1-i]);printf("%lld\n",ans);}return 0;}

Problem L.Videos
这个费用流建图方式也好棒啊。。
题解讲的很详细了。

#include<bits/stdc++.h>
using namespace std;
const int maxn1=205;
//下标从0到N-1
//最小费用最大流，求最大费用只需取相反数，结果取相反数即可。
const int maxn=800;
const int maxm=maxn*maxn;
const int inf=0x3f3f3f3f;
struct Edge
{int to,next,cap,flow,cost;Edge(int _t,int _n,int _c,int _f,int _cost):to(_t),next(_n),cap(_c),flow(_f),cost(_cost){}Edge(){}
}edges[maxm];
int head[maxn],tot;
int pre[maxn],dis[maxn];
bool vis[maxn];
int N;
void init(int n)
{N=n;tot=0;memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost)
{edges[tot]=Edge(v,head[u],cap,0,cost);head[u]=tot++;edges[tot]=Edge(u,head[v],0,0,-cost);head[v]=tot++;
}
bool spfa(int s,int t)
{queue<int>q;for(int i=0;i<N;i++){dis[i]=inf;vis[i]=false;pre[i]=-1;}dis[s]=0;vis[s]=true;q.push(s);while(!q.empty()){int u=q.front();q.pop();vis[u]=false;for(int i=head[u];~i;i=edges[i].next){int v=edges[i].to;if(edges[i].cap>edges[i].flow&&dis[v]>dis[u]+edges[i].cost){dis[v]=dis[u]+edges[i].cost;pre[v]=i;if(!vis[v]){vis[v]=true;q.push(v);}}}}if(pre[t]==-1)return 0;return 1;
}
int minCostMaxflow(int s,int t,int &cost)
{int flow=0;cost=0;while(spfa(s,t)){int Min=inf;for(int i=pre[t];~i;i=pre[edges[i^1].to]){if(Min>edges[i].cap-edges[i].flow)Min=edges[i].cap-edges[i].flow;}for(int i=pre[t];~i;i=pre[edges[i^1].to]){edges[i].flow+=Min;edges[i^1].flow-=Min;cost+=edges[i].cost*Min;}flow+=Min;}return flow;
}int id[maxn1][2];
int main()
{int T;scanf("%d",&T);while(T--){int n,m,k,W;scanf("%d %d %d %d",&n,&m,&k,&W);int tot1=0;int S=++tot1,T=++tot1;id[0][0]=id[0][1]=++tot1;for(int i=1;i<=n;i++){id[i][0]=++tot1;id[i][1]=++tot1;}init(maxn);addedge(S,id[0][0],k,0);id[n+1][0]=id[n+1][1]=T;for(int i=0;i<=n;i++){addedge(id[i][0],id[i+1][0],inf,0);addedge(id[i][1],id[i+1][1],inf,0);}int st,ed,w,op;for(int i=1;i<=m;i++){scanf("%d %d %d %d",&st,&ed,&w,&op);++tot1;addedge(id[st][op],tot1,1,0);addedge(tot1,id[ed][!op],1,-w);addedge(tot1,id[ed][op],1,W-w);}int ct;minCostMaxflow(S,T,ct);printf("%d\n",-ct);}return 0;
}