A题和B题是一如既往的签到题。

C题是一道拓扑序dp题，题意是给定一个DAG，问你从1号点走到n号点，在长度不超过T的情况下，要求经过的点数最多，换个思维，设dp[i][j]表示到i号点时经过j个点的最小距离，我们按拓扑序转移即可，最后找到一个最大的x，使得dp[n][x]<=T即可，由于还要输出路径，我们就需要记录一下转移。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 const int maxn=5005; 7 typedef long long int64; 8 int n,m,T,tot,now[maxn],stack[maxn],top,fa[maxn][maxn],prep[maxn],son[maxn],val[maxn],head,tail,list[maxn<<2][2]; 9 int dist[maxn][maxn];10 void add(int u,int v,int w){tot++,prep[tot]=now[u],now[u]=tot,son[tot]=v,val[tot]=w;}11 int main(){12     scanf("%d%d%d",&n,&m,&T);13     tot=0,memset(now,0,sizeof(now));14     for (int u,v,w,i=1;i<=m;i++){15         scanf("%d%d%d",&u,&v,&w);16         add(u,v,w);17     }18     memset(dist,63,sizeof(dist)); dist[1][1]=0;19     head=0,tail=1,list[1][0]=1,list[1][1]=1; int y,z;20     while (head!=tail){21         head++; if (head==20000) head=0;22         y=list[head][0],z=list[head][1];23         for (int i=now[y],so=son[i];i;i=prep[i],so=son[i]){24             if (dist[so][z+1]>dist[y][z]+val[i]){25                 dist[so][z+1]=dist[y][z]+val[i];26                 fa[so][z+1]=y;27                 tail++; if (tail==20000) tail=0;28                 list[tail][0]=so,list[tail][1]=z+1;29             }30         }31     }32     int pos;33     for (int i=n;;i--){
    if (dist[n][i]<=T){pos=i;break;}}34     printf("%d\n",pos); y=n; top=0;35     while (pos){36         stack[++top]=y;37         y=fa[y][pos],pos--;38     }39     for (int i=top;i>=1;i--) printf("%d ",stack[i]);40     puts("");41     return 0;42 }
         
        
       
      

D题是一个贪心题，题意是给你一个序列，最多进行k次操作，每次操作是将某个位置上的数+x或-x，要求输出若干次操作后这个序列变成什么样子，并且要求这个序列中所有元素的乘积最小。

做法：我们先肯定是要把乘积变为负数，怎么变呢，如果是正数，我们要找到绝对值最小的那个数，如果小于0，就一直+x，直到变成>0，否则就一直-x，直到变成<0.之后我们的目标就是让某些数绝对值变大，因为这样才能尽可能小，还是一样的，每次选择绝对值最小的数，把它绝对值变大，这个过程用个堆高效地维护即可，复杂度nlogn.

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #define PI pair
            
              8 #define mp(a,b) make_pair(a,b) 9 using namespace std;10 typedef long long int64;11 const int maxn=240005;12 int n,k,op;13 int64 x,a[maxn],t1,t2;14 priority_queue < PI,vector
             
              ,greater
              
                > heap;15 int main(){16 scanf("%d%d%I64d",&n,&k,&x); op=1;17 for (int i=1;i<=n;i++) scanf("%I64d",&a[i]);18 for (int i=1;i<=n;i++) if (a[i]<0) op=-op;19 if (op==1){20 t1=1LL*maxn*maxn;21 for (int i=1;i<=n;i++) if (abs(a[i])
               
                =0){29 k--,t1-=x;30 }31 a[t2]=t1;32 }33 }34 if (k){35 while (!heap.empty()) heap.pop();36 for (int i=1;i<=n;i++) heap.push(mp(abs(a[i]),i));37 while (k--){38 t1=heap.top().first,t2=heap.top().second; heap.pop();39 if (a[t2]<0) a[t2]-=x;40 else a[t2]+=x;41 heap.push(mp(abs(a[t2]),t2));42 }43 }44 for (int i=1;i<=n;i++) printf("%I64d ",a[i]);45 puts("");46 return 0;47 }
               
              
             
            
           
          
         
        
       
      

E题是一个dp题，还不会写，待填坑......