第一题

题意：给定n*m网络，定义两个棋子在同行同列则相互攻击，同时要求两个棋子的行和列不能一小一大，求满足条件的最大摆放的方案数。

题解：ans=C(max(n,m),min(n,m))，就是在max中取min个数字的组合，组合内排序构成一种方案。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long longusing namespace std;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}/*------------------------------------------------------------*/const int inf=0x3f3f3f3f,MOD=1000000007;void gcd(ll a,ll b,ll& d,ll& x,ll& y){    if(!b){d=a;x=1;y=0;}     else{gcd(b,a%b,d,y,x);y-=x*(a/b);}}ll inv(ll a,ll n){    ll d,x,y;    gcd(a,n,d,x,y);    return (x%n+n)%n;}ll n,fac[1010],fav[1010];int main(){    ll T,n,m;    scanf("%lld",&T);    fac[0]=1;fav[0]=1;    for(int i=1;i<=1001;i++)fac[i]=fac[i-1]*i%MOD;    for(int i=1;i<=1001;i++)fav[i]=inv(fac[i],MOD);    for(int i=1;i<=T;i++){        scanf("%lld%lld",&n,&m);        int mins=min(n,m);        int maxs=max(n,m);        printf("%lld\n",fac[maxs]*fav[mins]%MOD*fav[maxs-mins]%MOD);    }    return 0;}
          
         
        
       
      

 

第二题

 

第三题

 

第四题

 

第五题

最小费用流（不要求最大流），不用拆点，S向每个点连边生产，每个点向T连边销售，点与点之间连无向边运输。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long longusing namespace std;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}/*------------------------------------------------------------*/const int inf=0x3f3f3f3f,maxn=600;struct edge{
    int from,v,flow,cost;}e[500000];int n,m,first[maxn],d[maxn],cur[maxn],ans,S,T,tot=1,q[10010];bool vis[maxn];void insert(int u,int v,int flow,int cost){    tot++;e[tot].v=v;e[tot].flow=flow;e[tot].cost=cost;e[tot].from=first[u];first[u]=tot;    tot++;e[tot].v=u;e[tot].flow=0;e[tot].cost=-cost;e[tot].from=first[v];first[v]=tot;}bool spfa(){    memset(vis,0,sizeof(vis));    memset(d,0x3f,sizeof(d));    int head=0,tail=1;q[0]=T;vis[T]=1;d[T]=0;    while(head!=tail)     {         int x=q[head++];if(head>10000)head=0;         for(int i=first[x];i;i=e[i].from)          if(e[i^1].flow&&d[x]+e[i^1].cost
           
            10000)tail=0;} vis[y]=1; } } vis[x]=0; } return d[S]<0;}int dfs(int x,int a){ if(x==T||a==0)return a; vis[x]=1; int flow=0,f; for(int& i=cur[x];i;i=e[i].from) if(!vis[e[i].v]&&d[x]==e[i].cost+d[e[i].v]&&(f=dfs(e[i].v,min(a,e[i].flow)))>0) { e[i].flow-=f; e[i^1].flow+=f; ans+=e[i].cost*f; flow+=f; a-=f; if(a==0)break; } vis[x]=0; return flow;}int main(){ while(scanf("%d%d",&n,&m)==2){ S=0;T=n+1; int a1,b1,c1,d1,u1,v1,k1; tot=1; memset(first,0,sizeof(first)); for(int i=1;i<=n;i++){ a1=read();b1=read();c1=read();d1=read(); insert(S,i,b1,a1); insert(i,T,d1,-c1); } for(int i=1;i<=m;i++){ u1=read();v1=read();k1=read(); if(u1==v1)continue; insert(u1,v1,inf,k1); insert(v1,u1,inf,k1); } ans=0; memset(vis,0,sizeof(vis)); while(spfa()) { for(int i=S;i<=T;i++)cur[i]=first[i]; dfs(S,inf); } printf("%d\n",-ans); } return 0;}
           
          
         
        
       
      

 

第六题

题意：在无限的数轴上，给定n个区间，补充m个点使最长连续区间最长。n<=10^5。

题解：

区间左闭右开的好处：区间内距离和区间间距离直接计算，两区间左右端点重合就紧贴。

经典区间交问题：左闭右开，按左端点排序，分类讨论三种情况：

1.右端点<=R，包含。

2.右端点>R，左端点<=R，相交。

3.右端点>R，左端点>R，不相交。

（另一种思路，左+1右-1，排序后前缀和为0时加入一个区间。）

处理成若干个独立区间后，对于每个l计算出能延伸出最远的r，经典的双指针位移问题，多余的补充点直接加入答案。

双指针位移：for左端点，每次扩展右端点到极限。

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=200010;int n,m;struct cyc{
    int l,r;}a[maxn],b[maxn];bool cmp(cyc a,cyc b){
    return a.l
         
          R&&a[i].l<=R)R=a[i].r;            else{b[++tot]=(cyc){L,R};L=a[i].l;R=a[i].r;}        }        b[++tot]=(cyc){L,R};        n=tot;        int j=1,leave=m,ans=0;        for(int i=1;i<=n;i++){            while(j+1<=n&&leave-(b[j+1].l-b[j].r)>=0){                leave-=b[j+1].l-b[j].r;                j++;            }            ans=max(ans,b[j].r-b[i].l+leave);            leave+=b[i+1].l-b[i].r;            if(i==j){j=i+1;leave=m;}        }        printf("%d\n",ans);    }    return 0;}
         
        
       
      

 

PS：进复赛啦>w<！