在zxyer学长的威逼利诱之下，我写起了题目。这是一套难度中等的几乎没有细节的题目。

 

　　第一题 定点爆破 题目大意：有n个点和t的时间限制。对于m个区间，每个区间都有左端，右端和去掉这个区间的花费，还可以消耗1的时间不消耗费用去掉单个点，求清空所有点的最小花费。

　　题解：也不难，看上去就像是dp，我们以右端点拉个链，直接跑01背包就好了，区间最小值这边用的倍增，可以用线段树处理，然后我专门卡了内存，要用滚动数组存。

　　代码如下：

#include
     
      #include
      
       #include
       
        using namespace std;const int inf=2147483647;int n,m,t,f[2][5001][15],h[5001];struct bom{
   int l,c,nxt;}b[1001];void add(int l,int r,int c){b[m+1]={l,c,h[r]};h[r]=m+1;}int mi(int x,int y){
   return x
       
      
     

 

 　　第二题 后宫着♂火 题目大意：对于n个点，选这些点要花费点权，这些点有2种关系，每种关系有ki个：

　　　　　　1.x和y同时选减少wj的花费

　　　　　　2.x和y一个选一个不选增加vj的花费

　　　　求选点方案中最小的花费（一般是负的）

　　题解：这是一道网络流的题目。我们建n个点从源点连ai的边到i表示如果选这个点要ai的花费，再建k1个点先把结果加上wj然后从x，y到它连INF边，再从他到汇点连wj的边，如果xy有一个不选那它一定要选。然后对x和y之间建双向边，花费为vj，然后跑最小割，割边就是选取的。

代码如下：

#include
     
      #include
      
       using namespace std;const int inf=2147483647;int n,m1,m2,tot=1,h[6010],ans,d[6010],q[6010],iter[6010],t;int mn(int x,int y){
   return x
       
        0)        {            int v=e[i].to;            if(!d[v])d[v]=d[x]+1,q[++r]=v;        }    }}int dfs(int x,int fl){    int ans=0;    if(x==t)return fl;    for(int &i=iter[x];i;i=e[i].nxt)if(e[i].cap&&d[e[i].to]==d[x]+1)    {        int v=e[i].to;        int f=dfs(v,mn(fl-ans,e[i].cap));        e[i].cap-=f;e[i^1].cap+=f;ans+=f;    }    return ans;}int flow(){    int ans=0;    while(1)    {        memset(d,0,sizeof(d));        bfs();        if(!d[t])return ans;        for(int i=0;i<=t;i++)iter[i]=h[i];        ans+=dfs(0,inf);    }}int main(){
        init();    printf("%d",flow()-ans);    return 0;}void init(){    scanf("%d%d%d",&n,&m1,&m2);    t=n+m1+m2*2+1;    for(int i=1;i<=n;i++)    {        int x;        scanf("%d",&x);        if(x>=0)add(0,i,x);        else add(i,t,-x),ans-=x;    }    for(int i=1;i<=m1;i++)    {        int a,b,c;        scanf("%d%d%d",&a,&b,&c);        add(n+i,t,c);add(a,n+i,inf);add(b,n+i,inf);        ans+=c;    }    for(int i=1;i<=m2;i++)    {        int a,b,c;        scanf("%d%d%d",&a,&b,&c);        int p1=n+m1+i,p2=n+m1+m2+i;        add(0,p1,c);add(p1,a,inf);add(p1,b,inf);        add(p2,t,c);add(a,p2,inf);add(b,p2,inf);        ans+=c;    }}
       
      
     

第三题 签到题

给定n和k求一个和式%100000007的值，这个和式为。

题解:其实这么多都是骗人的，就是递推出每一项%100000007,我们发现该数为质数，所以使用exgcd递推和，乘法递推直接计算就好了。

我的做法把它化简成然后减短代码。

#include
     
      using namespace std;int clz=100000007;long long ans,n,x,cnt=1,now=1,p,q;int div(int x,int y){
   int xx=x/y;if(xx*y>x)xx--;return xx;}void exgcd(int a,int b,int c){    if(b==0){p=c/a;q=0;return;}    exgcd(b,a-div(a,b)*b,c);    long long k=q%clz;    q=p-k*div(a,b);    p=k;}int main(){    scanf("%lld%lld",&n,&x);    for(int i=1;i<=n;i++)cnt=cnt*i%clz;    for(int i=1;i<=n;i++)    {        exgcd(i,-clz,cnt);        p=p<0?p+clz:p;        ans=(ans+p*(now=x*now%clz))%clz;    }    printf("%d",ans);    return 0;}
     

P.S.辛辛苦苦写的题目居然几乎没人做！！！！！！！！！