A题

题目大意：给出一棵树，一开始节点值均为0，先要求完成在线操作：将某子树所有节点值取反，或者查询某子树总点权。

题解：很基础的线段树题，既然两个操作都是子树操作，那么就先树链剖分一下，将子树操作转变成线段树上的区间操作，区间翻转操作就等同于区间长度减去区间总权值，码量适中，水过。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N=500010;char op[5];int p[N],tot,x,d[N],num[N],ed=0,u,w,n,m,i,v[N],vis[N],f[N],g[N],nxt[N],size[N],son[N],st[N],en[N],dfn,top[N],t;char ch;void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}void dfs(int x){    size[x]=1;    for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){        f[v[i]]=x,d[v[i]]=d[x]+1;        dfs(v[i]),size[x]+=size[v[i]];        if(size[v[i]]>size[son[x]])son[x]=v[i];    }}void dfs2(int x,int y){	  if(x==-1)return;    st[x]=++dfn;top[x]=y;    if(son[x])dfs2(son[x],y);    for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]);    en[x]=dfn;}struct node{int l,r,a,b,tag,val,len;}T[N];void up(int x){T[x].val=T[T[x].l].val+T[T[x].r].val;}void addtag(int x,int tag){    T[x].tag+=tag;    if(tag&1)T[x].val=(T[x].b-T[x].a+1)-T[x].val;}void pb(int x){    if(T[x].l){addtag(T[x].l,T[x].tag);addtag(T[x].r,T[x].tag);}    T[x].tag=0;}void build(int l,int r){    int x=++tot;    T[x].a=l;T[x].b=r;T[x].tag=T[x].l=T[x].r=T[x].val=0;    if(l==r)return;    int mid=(l+r)>>1;    T[x].l=tot+1;build(l,mid);    T[x].r=tot+1;build(mid+1,r);}void change(int x,int a,int b,int p){    if(T[x].a>=a&&T[x].b<=b){addtag(x,p);return;}    if(T[x].tag)pb(x); int mid=(T[x].a+T[x].b)>>1;    if(mid>=a&&T[x].l)change(T[x].l,a,b,p);    if(mid
         
          =a&&T[x].b<=b)return T[x].val;    if(T[x].tag)pb(x);int mid=(T[x].a+T[x].b)>>1,res=0;    if(mid>=a&&T[x].l)res+=query(T[x].l,a,b);    if(mid
         
        
       
      
     

B题

题目大意：一门课的书有 N 章内容要复习，每天可以复习一章，但是有 M 个限制条件：一些功课不能在固定的天数复习，问方案数。

题解：限位排列，利用回溯的性质去重，然后用容斥原理计算即可。

#include 
     
      #include 
      
       using namespace std;const int mod=55566677;int m,n,a[25],b[25],va[60],C[60]={1},vb[60];int GetAns(int x,int t){    if(x==m){        if(t%2)return(mod-C[n-t])%mod;        else return C[n-t];    }int tmp=GetAns(x+1,t);    if(!va[a[x]]&&!vb[b[x]]){        va[a[x]]=vb[b[x]]=1;        tmp=(tmp+GetAns(x+1,t+1))%mod;        va[a[x]]=vb[b[x]]=0;    }return tmp;}int main(){    for(int i=1;i<60;i++)C[i]=C[i-1]*1LL*i%mod;    while(~scanf("%d%d",&n,&m)){        for(int i=0;i
      
     

C题

题目大意：一门课的书有 N 章内容要复习，每天可以复习一章，但是第 i 章不能在第 i 天或第 i + 1 天复习（最后一章则对应最后一天和第一天），问不同的复习方案数

题解：在棋盘格上将禁位逐行标号，那么禁位上的非重选取就是一个2n的圆排列中选取k个非相邻元素的排列组合问题，在禁位上的非重选取能够解决了之后就转化为容斥原理了。在计算的时候取模除法要注意计算乘法逆元。

#include 
     
      using namespace std;typedef long long LL;const int mod=1000000007;int a[100005],r[100005];int main(){    a[1]=a[2]=0; r[1]=a[3]=1;    for(int i=4;i<100005;i++){        r[i-2]=r[mod%(i-2)]*LL(mod-mod/(i-2))%mod;        a[i]=((i-2ll)*i%mod*a[i-1]%mod+(a[i-2]*LL(i)+(i&1?4:mod-4))%mod)*r[i-2]%mod;    }for(int n;~scanf("%d",&n);printf("%d\n",a[n]));    return 0;}
     

D题　

题目大意：古代某统治者要修建一些棺材，其中第 i 个棺材大小为 s[i]，修建需要花费 t[i] 天，如果在剩余 x 天的时候开始修建并且能够及时完成，则能获得 x * s[i] 的报酬，总共有 T 天可用，问最大能获得的报酬为多少

题解：Noip2012国王游戏的即视感，计算任意排列相邻两个棺材前后顺序对总报酬的影响，发现只与相邻两个棺材的s1*t2和s2*t1大小关系有关，于是按照这个条件排序，获得完成棺材的最佳顺序，由于时间的限制，棺材的修建可能不能全部完成，那么在既成的顺序上做一遍动态规划，一遍简单的01背包过后就能够获得答案了。

#include 
     
      #include 
      
       #include 
       
        using namespace std;struct data{int t,v;}a[3005];int dp[10005],n,T,ans;bool cmp(data a,data b){return a.t*b.v
        
         =a[i].t;j--)dp[j]=max(dp[j],dp[j-a[i].t]+a[i].v*(T-j+a[i].t));        for(int i=1;i<=T;i++)ans=max(ans,dp[i]);        printf("%d\n",ans);    }return 0;}
        
       
      
     

E题

题目大意：n 个人，每人各自从 1 到 m 中选出一个数字，相邻的两个人若是选择了同一个数字，那么该数字必须大于 k，求方案数

题解：对与每个人来说，如果上一个人选的数字小于等于k，如果他选取小于k的数，那么他只有k-1种选择，如果选择大于k的数，那么他有m-k种选择，如果上一个人选择的数字大于k，那么他选取小于k的数有k种选择，否则只有m-k种选择

     a[i] = a[i - 1] * (k - 1) + b[i - 1] * k 

    b[i] = a[i - 1] * (m - k) + b[i - 1] * (m - k)

根据递推式构造矩阵，快速幂求解即可

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define mode 1000000007typedef long long ll; class Mart{public:    int n,m;    ll data[5][5];    Mart(int a,int b){n=a;m=b;memset(data,0,sizeof(data));}    Mart mul(Mart b){        Mart a(n,b.m);        for(int i=0;i
         
          >1;    }return c;}int main(){    int m,k,n;    while(~scanf("%d%d%d",&n,&m,&k)){  	    Mart a(2,2);  	    a.data[0][0]=m-k;  	    a.data[0][1]=m-k;	      a.data[1][0]=k;	      a.data[1][1]=max(k-1,0);	      a=Qm(a,n); Mart b(2,1);	      b.data[0][0]=1;	      b.data[1][0]=0;	      a=a.mul(b);	      ll ans=(a.data[0][0]%mode+a.data[1][0]%mode)%mode;	      cout<
          
           <
          
         
        
       
      
     

F题

题目大意：给出空间中的一些点，在这些位置上各有 F[i] 朵花，最多可以从这个位置移出 L[i] 朵花，问最小移动半径 R 是多少时，能够把所有位置上的花移动到位置 1（移动半径内的两个顶点可以完成花的直接移动）

题解：因为每个点都有限制移出的花朵数目，于是很自然地想到拆点，将每个顶点拆分为两个节点，点间设置流量上限为L[i]，现在要求最小的移动半径，使得该图满流。求最小代价使得目标达成这个条件非常的眼熟，代价最小化，那么二分答案，检验是否满流即可。

#include 
     
      #include 
      
       #include 
       
         using namespace std; const int N=30010,inf=~0U>>2;const double EPS=1e-10;struct edge{int t,f;edge*nxt,*pair;}*g[N],*d[N],pool[N],*cur=pool;struct data{int x,y,z,f,l;}point[105];int sum,cnt,cas,i,u,v,cost,n,m,S,T,h[N],gap[N],maxflow;double l,r;int min(int x,int y){return x
        
         t=t;p->f=w;p->nxt=g[s];g[s]=p;    p=cur++;p->t=s;p->f=0;p->nxt=g[t];g[t]=p;    g[s]->pair=g[t];g[t]->pair=g[s];}int sap(int v,int flow){    if(v==T)return flow;    int rec=0;    for(edge*p=d[v];p;p=p->nxt)if(h[v]==h[p->t]+1&&p->f){        int ret=sap(p->t,min(flow-rec,p->f));        p->f-=ret;p->pair->f+=ret;d[v]=p;        if((rec+=ret)==flow)return flow;    }if(!(--gap[h[v]]))h[S]=T;    gap[++h[v]]++;d[v]=g[v];    return rec;}double cal(data a,data b){    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);}int check(double x){    maxflow=0; int base=n+1;    for(cur=pool,i=(S=1);i<=(T=base+n+1);i++)g[i]=d[i]=NULL,h[i]=gap[i]=0;    point[base].l=inf;    for(i=2;i<=n+1;i++)add(S,i,point[i].f);    for(i=2;i<=n+1;i++)add(i,i+base,point[i].l);    for(i=2;i<=n;i++)for(int j=i+1;j<=n+1;j++){        if(cal(point[i],point[j])
         
          1;i--){            scanf("%d%d%d%d%d",&point[i].x,&point[i].y,&point[i].z,&point[i].f,&point[i].l);            sum+=point[i].f;        }r=100000,l=0;        while(fabs(l-r)>EPS){    	      double mid=(l+r)/2;    	      if(check(mid))r=mid;    	      else l=mid;	    }if(r==100000)puts("-1");		else printf("%.8lf\n",r);    }return 0;}
         
        
       
      
     

G题

题目大意：n 个人排成一排，每个人有两个值 rp[i] 和 gf[i]，现要把这 n 个人划分成若干段，要求各段的 max(rp) 加起来不超过 Rlimit，并使得最大的 gf子段和 最小

题解：别的不说看到gf分段和，那么就先算个gf的前缀和s备用，最大的gf子段和最小，眼熟，相当眼熟，又是二分答案，那么就是验证在每段的gf值不超过mid的情况下是否可以做到各段最大值之和不超过Rlimit，检验的dp方程很显然

    dp[i+1]=rp_max+dp[j](gf[i,j]<=mid)

观察到rp在选取时，只有单调递减的rp值在会有决策意义，于是可以用单调队列优化dp，减少无意义的决策。

在更新dp值的时候，队列中dp[q[k]] + rp[q[k+1]]也是需要被考虑到的，所以同时用平衡树维护队列中元素的插入删除和最小值查询。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N=40005; int n,m;int s[N],gf[N],rp[N],dp[N];multiset
         
           S;void pop_back(deque
          
           & u){ if(u.size()>1)S.erase(S.find(dp[u[u.size()-2]+1]+rp[u.back()])); u.pop_back();}void pop_front(deque
           
            & u){ if(u.size()>1)S.erase(S.find(dp[u.front()+1]+rp[u[1]])); u.pop_front();}bool check(int x){ S.clear(); deque
            
             u; for(int i=0,j=0;i
             
              x)j++; while(u.size()&&u.front()
              
               1)S.insert(dp[u[u.size()-2]+1]+rp[u.back()]); dp[i+1]=rp[u.front()]+dp[j]; if(S.size())dp[i+1]=min(*S.begin(),dp[i+1]); }return dp[n]<=m;}int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=0;i
              
             
            
           
          
         
        
       
      
     

H题

题目大意：ZJU ACM ICPC 暑假集训结束，为了庆祝这兴奋的一刻，教练 Navi 和 Fancy 决定 BG 参加集训的 N 个小朋友们。他们去了楼外楼吃自助，每个人要花费 W 元，但每 K 个人可以免费一个人，Navi 和 Fancy 会平摊此次 BG 的花销，问他们俩每人要支付多少钱

题解：H题作为签到题，还是有一定水准的，注意是N+2个人去吃饭，注意W是小数，同时注意精度存在误差，需要EPS。

#include 
     
      double w;double eps=1e-6;int n,k,t,ans;int main(){    while(~scanf("%d%lf%d",&n,&w,&k)){        n+=2; t=n/k;        ans=100*(n-t)*(w+eps);        ans=(ans+1)/2;        printf("%d.%02d\n",ans/100,ans%100);    }return 0;}
     

I题

题目大意：有一个数列，要求选出 M 个区间，每个区间长度在 [L, R] 内，使得选出的那些数字的平均值尽可能大

题解：分数规划，每次将数组中的数减去求出平均值，做一次动态规化，根据结果重新调整自己的选择，迭代计算直到结果最优。

需要特别注意的是负数的取整是要上取整的，在计算答案的时候要特殊处理。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long LL;const LL INF=1000000000000000007ll;typedef pair
         
           PIL;int n,m,l,r,a[100005];LL dp[15][100005],sum[100005],pfx[100005];PIL pt[15][100005];bool check(LL&S,LL&N){    for(int i=0;i
          
           u; for(int i=1;i<=n;i++){ while(u.size()&&i-u.front().first>r)u.pop_front(); int k=i-l; if(k>=0&&dp[x-1][k]!=-INF){ LL tmp=dp[x-1][k]-sum[k]; while(u.size()&&tmp>u.back().second)u.pop_back(); u.push_back(PIL(k,tmp)); }dp[x][i]=dp[x][i-1],pt[x][i]=pt[x][i-1]; if(u.size()){ int pos=u.front().first; LL tmp=u.front().second+sum[i]; if(tmp>dp[x][i]){ dp[x][i]=tmp; pt[x][i]=pt[x-1][pos]; pt[x][i].first+=i-pos; pt[x][i].second+=pfx[i]-pfx[pos]; } } } }if(!dp[m][n])return 1; return N=pt[m][n].first,S=pt[m][n].second,0;}LL GetAns(LL S,LL N){ if(S>=0)return S/N; return -((-S+N-1)/N);}int main(){ while(~scanf("%d%d%d%d",&n,&m,&l,&r)){ for(int i=0;i
          
         
        
       
      
     

J题

题目大意：植物大战肥羊，现在有一大波肥羊入侵，地图中有的地方肥羊不能走，有的地方通过需要一秒，有的地方通过需要两秒，有的地方可以放置植物防御（神奇的塔防游戏），然后你现在有两种植物可以种植：一种是可以攻击一整行肥羊的植物，但是只能朝向一个方向，而且确定方向之后就不能改，一种是范围攻击，能攻击到一定曼哈顿距离内的肥羊，这两种植物还可以升级，升级之后能加伤害，当然升级也需要一定的费用，肥羊在入侵的时候，会选择最短路，现在告诉你每只肥羊入侵的时间和血量，求最佳布防，即在防御肥羊的情况下消耗最小

题解：首先，肥羊的入侵是最短路，所以，路线是确定的，那么我们广搜一下记录路径，对于每个可以设置塔防的位置，我们分别计算每种植物的伤害和代价，伤害怎么来的？就是肥羊在他攻击范围的滞留时间乘上单位时间的伤害，那么根据保存路径算出滞留时间就好了。

可是那么多肥羊，该怎么处理呢，嘛，其实既然他们路线是一样的，植物又是群体攻击，那么只要能防御血量最多的肥羊，就能防御所有的肥羊了，好咯，现在有伤害值，和代价值，要求总伤害达到阈值。怎么做？分组背包问题。复杂的塔防问题迎刃而解。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef pair
         
           PII;typedef pair
          
            TPL;#define mp make_pairconst int mr[]={0,-1,1,0},mc[]={1,0,0,-1};char a[35][35];bool v[35][35];int n,m,p,dp[35][35],tim[9][35][35],hp[1024],at[1024],w[1025];bool check(int x,int y){return(x>=1&&y>=1&&x<=n&&y<=m&&v[x][y]);}int main(){ while(~scanf("%d%d%d",&n,&m,&p)){ int sr=0,sc=0,tr=0,tc=0; for(int i=1;i<=n;i++){ scanf("%s",a[i]+1); for(int j=1;j<=m;j++){ if(a[i][j]=='s')a[sr=i][sc=j]='.'; if(a[i][j]=='t')a[tr=i][tc=j]='.'; } }for(int i=0;i
           
             q; memset(dp,63,sizeof(dp)); dp[tr][tc]=1; memset(v,0,sizeof(v)); for(q.push(mp(tr,tc));q.size();q.pop()){ int r=q.front().first,c=q.front().second; v[r][c]=0; for(int o=0;o<4;o++){ int dr=r+mr[o],dc=c+mc[o]; if(!dr||!dc||dr>n||dc>m||a[dr][dc]=='x'||a[dr][dc]=='k')continue; int cost=dp[r][c]+(a[dr][dc]=='w')+1; if(cost
            
             n||dc>m||a[dr][dc]=='x'||a[dr][dc]=='k')continue; int cost=dp[sr][sc]-(a[sr][sc]=='w')-1; if(cost==dp[dr][dc]){sr=dr,sc=dc;break;} } }memset(tim,0,sizeof(tim)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)if(a[i][j]=='k'){ for(int l=1;l<9;l++){ tim[l][i][j]=tim[l-1][i][j]; for(int x=0;x
             
              n||dc>m||a[dr][dc]=='x'||a[dr][dc]=='k')break; if(v[dr][dc])now+=(a[dr][dc]=='w')+1; }tim[0][i][j]=max(tim[0][i][j],now); } }int R1,S1,T1,U1,V1,W1,L1,R2,S2,T2,U2,V2,W2,L2,X2; scanf("%d%d%d%d%d%d%d",&R1,&S1,&T1,&U1,&V1,&W1,&L1); scanf("%d%d%d%d%d%d%d%d",&R2,&S2,&T2,&U2,&V2,&W2,&L2,&X2); memset(w,63,sizeof(w));w[0]=0; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]=='k'){ vector
              
                u; for(int x=0;x
               
                1000000000) puts("Happy summer holiday!"); else printf("%d\n",w[V]); }return 0; }
               
              
             
            
           
          
         
        
       
      
     

就快要省赛了，要更努力一些了，队友说的话还是很有道理的，人还是要有梦想的，万一实现了呢。

所以，竭尽全力。