F
签到题。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=2e5+7;
string s1,s2;
int main(){
while(cin>>s1>>s2){
if(s1+s2==s2+s1) printf("=
");
if(s1+s2<s2+s1) printf("<
");
if(s1+s2>s2+s1) printf(">
");
}
}
J
数学推导题。
[int_{0}^{1}x^n(1-x)^n = frac{1}{n+1}(1-x)^ndx^n+1 \
= frac{1}{n+1}(x^{n+1}(1-x)^n)igg|^{1}_{0}+nint_0^1x^{n+1}(1-x)^{n-1}dx\
=frac{n}{n+1}int_0^1x^{n+1}(1-x)^{n-1}dx \
int_0^1x^{n+1}(1-x)^{n-1}dx=frac{1}{n+2}(1-x)^{n-1}igg|_0^1+(n+1)int_0^1x^{n+2}(1-x)^{n-2}dx\
int_0^1x^n(1-x)^{n-1}dx=frac{n}{n+1}int_0^1x^{n+1}(1-x)^{n-1}dx \
int_0^1x^{n+1}(1+x)^{n-1}dx=frac{n-1}{n+2}int_0^1x^{n+2}(1-x)^{n-2}dx\
vdots\
int ^1_0x^{n+1}(1-x)^{n-1}dx=frac{1}{2n}int_0^1 x^{n+2}(1-x)^{n-2}dx\
int_0^1x^{2n}dx=frac{1}{2n+1}\
int^1_0x^n(1-x)^ndx=frac{n}{n+1} imesfrac{n-1}{n+2} imesfrac{n-2}{n+3}cdotsfrac{1}{2n} imesfrac{1}{2n+1}
]
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const ll mod=998244353;
const int N=2e6+7;
ll powmod(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll dp[N];
int main(){
dp[0]=dp[1]=1;
for(int i=2;i<N;i++) dp[i]=dp[i-1]*i%mod;
int n;
while(~scanf("%d",&n)){
ll tmp=dp[2*n+1]*powmod(dp[n],mod-2)%mod;
ll Ans=dp[n]*powmod(tmp,mod-2)%mod;
printf("%lld
",Ans);
}
}
H
最小费用最大流。本题的关键在于如何分配分数流量使得能让1流量的流流到汇点。首先我们发现图中每一条边的最大流量是相等的，所以每条边能贡献的流量相同，那么问题可以转换为选取最小的若干的增广路，使得最大流量为1的情况下，费用最小。我们可以默认每条边的流量为1，然后跑MCMF算法，存下每一条增广路的花费，按照增广路的花费从小到大排序，每次询问从小到达取增广路，直到流量为1，答案也可以一并算出来。如果取完所有的增广路，流量还未为1，则输出"NaN"。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=5007;
const ll INF=0x3f3f3f3f3f3f3f;
#define PII pair <ll,ll>
#define fr first
#define sc second
#define mp make_pair
struct MinCostFlow{
vector<PII> ld;
struct edge{
ll v,f,c,r;
edge(ll _v, ll _f, ll _c, ll _r) :v(_v), f(_f), c(_c), r(_r) {}
};
ll V=0,h[N],dis[N],pv[N],pe[N];
vector <edge> G[N];
inline void init(ll n){
for(ll i=0;i<=V;i++) G[i].clear();
V=n;
ld.clear();
}
inline void Ins(ll u,ll v,ll f,ll c){
G[u].push_back(edge(v,f,c,G[v].size() ));
G[v].push_back(edge(u,0,-c,G[u].size()-1 ));
}
PII MCMF(ll s,ll t,ll Flow){
ll cost=0,flow=0,newflow;fill(h,h+1+V,0);
while(Flow){
priority_queue <PII,vector<PII>,greater<PII> > Q;
fill(dis,dis+V+1,INF);
dis[s]=0,Q.push(mp(0,s));
while(!Q.empty()){
PII now=Q.top();Q.pop();
ll u=now.sc;
if(dis[u]<now.fr) continue;
for(ll i=0;i<G[u].size();i++){
edge &e=G[u][i];
if(e.f>0&&dis[e.v]>dis[u]+e.c+h[u]-h[e.v]){
dis[e.v]=dis[u]+e.c+h[u]-h[e.v];
pv[e.v]=u,pe[e.v]=i;
Q.push(PII(dis[e.v],e.v));
}
}
}
if(dis[t]==INF) break;
for(ll i=0;i<=V;i++) h[i]+=dis[i];
newflow=Flow;
for(ll x=t;x!=s;x=pv[x]) newflow=min(newflow,G[pv[x]][pe[x]].f);
Flow-=newflow,flow+=newflow,cost+=newflow*h[t];
ld.push_back(mp(newflow*h[t],newflow));
for(ll x=t;x!=s;x=pv[x]){
edge &e=G[pv[x]][pe[x]];
e.f-=newflow;
G[x][e.r].f+=newflow;
}
}
return mp(flow,cost);
}
}A;
int main(){
ll n,m;
while(~scanf("%lld%lld",&n,&m)){
ll s=1,t=n;
A.init(n);
for(ll i=1;i<=m;i++){
ll u=input(),v=input(),c=input();
A.Ins(u,v,1,c);
}
PII Ans=A.MCMF(s,t,INF);
sort(A.ld.begin(),A.ld.end());
ll q=input();
while(q--){
ll u=input(),v=input();
ll fm=0,fz=v,ct=0;
for(auto t:A.ld){
if(ct+u<=v){
fm+=t.fr*u;
ct+=u;
}else if(ct<v){
fm+=(v-ct)*t.fr;
ct+=(v-ct);
}else break;
}
if(ct==v){
ll gd=__gcd(fm,fz);
printf("%lld/%lld
",fm/gd,fz/gd);
}else printf("NaN
");
}
}
}
I
带花树开花算法。
最大流错误做法
被我用最大流水过去了。最大流在判奇环时会出现错误。
测试数据：
3 3
1 1 1
1 2
2 3
3 1
No
最大流建模就是每一个点拆成出点和入点，入点于源点相连，流量为该点的(d[i])值,出点于汇点相连，流量为该点的(d[i])值，对于一个入点与一个出点之间有一条流量为1的边的条件是在图上与之相连的。对于这个网络跑最大流，如果最大流等于(d[])数组之和，则是"Yes"，否则为"No"。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=200;
const int M=4007;
const int INF=0x3f3f3f3f;
#define clr(a,b) memset(a,b,sizeof(a))
int n,m,s,t;
int cnt=0;
int head[N];
int dis[N],q[N];
int d[N];
vector <int> G[N];
struct edge{
int v,w,next;
}e[M];
void Ins(int u,int v,int w){
e[cnt]=(edge){v,w,head[u]};head[u]=cnt++;
e[cnt]=(edge){u,0,head[v]};head[v]=cnt++;
}
int MkLevel(){
int x,l=0,r=0;
clr(dis,0);
dis[s]=1,q[r++]=s;
while(l<r){
x=q[l++];
for(int i=head[x];i!=-1;i=e[i].next){
if(e[i].w&&!dis[e[i].v]){
dis[e[i].v]=dis[x]+1;
if(e[i].v==t) return 1;
q[r++]=e[i].v;
}
}
}
return 0;
}
int extend(int s,int Lim){
if(s==t) return Lim;
int tmp,cost=0;
for(int i=head[s];i!=-1;i=e[i].next){
if(e[i].w&&dis[s]==dis[e[i].v]-1){
tmp=extend(e[i].v,min(Lim-cost,e[i].w));
if(tmp>0){
e[i].w-=tmp,e[i^1].w+=tmp,cost+=tmp;
if(Lim==cost) break;
}else dis[e[i].v]=-1;
}
}
return cost;
}
int Dinic(){
int ans=0;
while(MkLevel()) ans+=extend(s,INF);
return ans;
}
int main(){
while(~scanf("%d%d",&n,&m)){
cnt=0;
clr(head,-1);
int sum=0;
for(int i=1;i<=n;i++) d[i]=input(),G[i].clear(),sum+=d[i];
for(int i=1;i<=m;i++){
int u=input(),v=input();
G[u].push_back(v);
G[v].push_back(u);
}
s=0,t=2*n+1;
// cout<<s<<" "<<t<<endl;
for(int i=1;i<=n;i++){
Ins(s,i,d[i]);
// cout<<s<<" "<<i<<" "<<d[i]<<endl;
Ins(n+i,t,d[i]);
// cout<<n+i<<" "<<t<<" "<<d[i]<<endl;
for(auto v:G[i]){
Ins(i,n+v,1);
// cout<<i<<" "<<n+v<<" "<<1<<endl;
}
}
printf("%s
",Dinic()==sum?"Yes":"No");
}
}
开花树正确做法
待补
A
待补