ID	Title	Hint
A	Impasse (+)
B	Chess
C	An interesting game	最小费用最大流
D	n a^o7 !
E	Fruit Ninja I	dp
F	Pixel density	无
G	Mine Number	dfs
H	The Best Seat in ACM Contest	无
I	Pick apples	贪心，背包
J	Fruit Ninja II	积分

 

 

 

 

 

 

 

 

 

B.

d.国际象棋？就是求能被0~16个棋子吃掉的棋子分别有几个。

s.当时有点思路，感觉对。但是时间好像不大够，也没敲。

用二分查找，查询周围16个位置有棋子没，能不能把它吃掉。

棋子个数n <= 10^5。

10^5*16*log(10^5)<=4*10^7

 

C.

d.

s.这个题感觉也可以，不知道为啥wa了。

感觉直接暴力贪心就行啊，题意理解错了吗？

c.上个刁丝测试代码。。。数据比较大的时候可以找到不同的，但是还是不懂为什么贪心不行。。

#include 
        
         #include 
         
          #include 
          
           #include
           
            #include 
            
             #include 
             
              #include
              
               using namespace std;const int maxn=2200;const int oo=0x3f3f3f3f;struct Edge{ int u, v, cap, flow, cost; Edge(int u, int v, int cap, int flow, int cost):u(u), v(v), cap(cap), flow(flow), cost(cost) {}};struct MCMF{ int n, m, s, t; vector
               
                 edge; vector
                
                  G[maxn]; int inq[maxn], d[maxn], p[maxn], a[maxn]; void init(int n) { this->n=n; for(int i=0; i
                 

q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); inq[u]=0; for(int i=0; i

e.flow && d[e.v]>d[u]+e.cost) { d[e.v]=d[u]+e.cost; p[e.v]=G[u][i]; a[e.v]=min(a[u], e.cap-e.flow); if(!inq[e.v]) { q.push(e.v); inq[e.v]=1; } } } } if(d[t]==oo)return false; flow+=a[t]; cost+=d[t]*a[t]; int u=t; while(u!=s) { edge[p[u]].flow+=a[t]; edge[p[u]^1].flow-=a[t]; u=edge[p[u]].u; } return true; } int MinCost(int s, int t) { int flow=0, cost=0; while(spfa(s, t, flow, cost)); return cost; }} net;int a[maxn], b[maxn];struct node{ int h; int id; int h2;}a2[1005],a3[1005];bool cmp(node a,node b){ if(a.h!=b.h)return a.h

a[i+1]){ a2[i].h=a[i]; a2[i].h2=a[i+1]; a3[i].h=a[i+1]; a3[i].h2=a[i]; a2[i].id=i; a3[i].id=i; } else{ a2[i].h=a[i+1]; a2[i].h2=a[i]; a3[i].h=a[i]; a3[i].h2=a[i+1]; a2[i].id=i; a3[i].id=i; } /* cout<<"i: "<

<<" a2[i].h "<

<

N-2||p2>N-2||p3>N-2||p4>N-2||q1>M-1||q2>M-1){ cout<<"越界2"<

t2){ sum=sum+2*t1; use[a2[p1].id]=true; // //cout<

<<"### t1: "<

<

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

s.正宗解法，最小费用流

参考： 

ps：参考的这个代码比较快，600ms。 我的好像得1000多。。。

大意：有n个山坡，排成一排，为了增加难度，现在要从m个山坡中挑选k个，插入到原有的n个山坡中，两个原有的山坡中只能插入一个山坡，原有山坡的两侧不能插入。使插入k个山坡后的难度最大，总的难度是相邻两个山坡差值绝对值的和。

思路：训练赛的时候根本没往图论上想，当时想贪心不太可能，还以为是dp。

如果把原问题看做是原有山坡的排列中，两个相邻山坡中间的间隙和m个山坡做匹配的话，就可以看做是，最大流量为k时，最大费用是多少，费用流可以搞。对于最大费用，可以先把费用取负值，求出最小费用后再取负值，就是最大费用。匹配的费用是插入之后的难度的增加量，最大费用加上原山坡的难度，就是答案。

因为n和m的范围是[2, 1000]，直接建图会TLE，发现插入的m个山坡的范围只有[0, 30]，这么小的数据范围一定能优化答案，把插入山坡的高度看做结点，建图。

设置源点S，超级源点SS，汇点T。

S对所有间隙连边，容量1，费用0.

所有间隙对所有高度连边，容量1，费用是难度增加量的相反数.

所有高度对T连边，容量为此高度的个数，费用0.

SS对S连边，容量k，费用0.

答案就是原图的难度-最小费用。

c.最小费用最大流

/*SPFA版费用流最小费用最大流，求最大费用最大流只需要取相反数，结果取相反数即可。点的总数为N，点的编号0~N-1*/#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;const int MAXN=1500;const int MAXM=80000;const int INF=0x3f3f3f3f;struct Edge{    int to,next,cap,flow,cost;}edge[MAXM];int head[MAXN],tol;int pre[MAXN],dis[MAXN];bool vis[MAXN];int N;//节点总个数，节点编号从0~N-1void init(int n){    N=n;    tol=0;    memset(head,-1,sizeof(head));}void addedge(int u,int v,int cap,int cost){    edge[tol].to=v;    edge[tol].cap=cap;    edge[tol].cost=cost;    edge[tol].flow=0;    edge[tol].next=head[u];    head[u]=tol++;    edge[tol].to=u;    edge[tol].cap=0;    edge[tol].cost=-cost;    edge[tol].flow=0;    edge[tol].next=head[v];    head[v]=tol++;}bool spfa(int s,int t){    queue
             
              q; for(int i=0;i
              
               edge[i].flow&&dis[v]>dis[u]+edge[i].cost){ dis[v]=dis[u]+edge[i].cost; pre[v]=i; if(!vis[v]){ vis[v]=true; q.push(v); } } } } if(pre[t]==-1)return false; else return true;}//返回的是最大流，cost存的是最小费用int minCostMaxflow(int s,int t,int &cost){ int flow=0; cost=0; while(spfa(s,t)){ int Min=INF; for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){ if(Min>edge[i].cap-edge[i].flow) Min=edge[i].cap-edge[i].flow; } for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){ edge[i].flow+=Min; edge[i^1].flow-=Min; cost+=edge[i].cost*Min; } flow+=Min; } return flow;}int main(){ int T; int N2,M,K; int X[1005],Y[1005]; int YNum[40]; int i,j; int sp,sp2;//源点，源点2 int sc;//汇点 int sum; int tmp; int mi_cost; int ma_flow; int ca=0; scanf("%d",&T); while(T--){ scanf("%d%d%d",&N2,&M,&K); init(N2+50); for(i=0;i
              
             
            
           
          
         
        

 

D.

d.好像是按要求输出串

s.没写这个题

c.张

#include 
        
         #include 
         
          #include 
          
           #include 
           
            #define MAX 500using namespace std;int main (){    char temp1[MAX],temp2[MAX],str[MAX];    strcpy(temp1," n5!wpuea^o7!usimdnaevoli");    strcpy(temp2," usimdnaevolin5!wpuea^o7!");    int Len = strlen(temp1);    int T;    scanf("%d",&T);    getchar();    int coun=1;    while(T--)    {        gets(str);        int len=strlen(str);        for(int i=0,j=0; i
            
             =0; i--)            printf("%c",str[i]);        printf("\n");    }    return 0;}
            
           
          
         
        

 

E.

d.水果忍者，水果从上向下掉落，并且只能水平切。

给你n个水果的出现时间，出现的水平位置，和他是否是好水果，切到好水果+1，切到坏水果-1，连续切到三个以上好水果分数加倍。

两刀之间的间隔大于等于m，求能求得的最大分数。

s.先求出每一秒出手能得到的最大的得分，很简单。

再用DP求最大分数。

#include
        
         #include
         
          #include
          
           using namespace std;#define MAXN 10010int d[MAXN][210];//d[i][j]标志i秒j位置水果int dp[MAXN];//dp[i]表示前i秒获得的最大分数int main(){    int T;    int n,m;    int t,s,p;    int i,j;    int ma_t;//最大时间    int ma_p[MAXN];//每秒最大位置    int sum,num,ma;//    int ma_sum[MAXN];//每秒可获得的最大分数    int ca=0;    scanf("%d",&T);    while(T--){        scanf("%d%d",&n,&m);        memset(d,-1,sizeof(d));        ma_t=0;        memset(ma_p,0,sizeof(ma_p));        for(i=0;i
           
            ma_t){                ma_t=t;            }            if(p>ma_p[t]){                ma_p[t]=p;            }        }        memset(ma_sum,0,sizeof(ma_sum));        for(i=1;i<=ma_t;++i){
      //先求出每秒可获得的最大分数            sum=0;            num=0;            ma=0;            for(j=1;j<=ma_p[i];++j){                if(d[i][j]==0){                    ++num;                }                else if(d[i][j]==1){                    if(num>=3){                        sum=sum+num*2;                    }                    else{                        sum=sum+num;                    }                    if(sum>ma){                        ma=sum;                    }                    num=0;                    --sum;                    if(sum<0){                        sum=0;                    }                }            }            if(num>0){                if(num>=3){                    sum=sum+num*2;                }                else{                    sum=sum+num;                }                if(sum>ma){                    ma=sum;                }            }            ma_sum[i]=ma;        }        memset(dp,0,sizeof(dp));        for(i=1;i<=m;++i){            dp[i]=max(dp[i-1],ma_sum[i]);//不出手，和出手        }        for(i=m+1;i<=ma_t;++i){            dp[i]=max(dp[i-1],dp[i-m-1]+ma_sum[i]);        }        printf("Case %d: %d\n",++ca,dp[ma_t]);    }    return 0;}
           
          
         
        

 

F.

d.串中提取数字

s.比较坑的是里面空格只要一个就行了

c.当时臃肿的代码。虽然长，但是思路还可以

#include
        
         #include
         
          #include
          
           #include
           
            using namespace std;char str[12345];char str1[12345];char str2[12345];char num1[12345];char num2[12345];char num3[12345];int main(){    int T;    int i;    int len;    int len1,len2;    int p1,p2;    int p3,p4;    int len_num1,len_num2,len_num3;    int j;    double a,a1,a2,b,b1,b2,c,c1,c2;    int p5;    double Dp;    double ans;    int ca=0;    int p6,p7;    /*                   num1         num2 num3    The new iPad  0009.7 inches 2048*1536 PAD               p3        p1         p2    p4    0009.7        2048*1536        p5    p6,07是考虑了后面的小数点，实际好像后面只能是整数    */    scanf("%d",&T);    getchar();    while(T--){        scanf("%[^\n]",str);        getchar();        len=strlen(str);        len1=0;        len2=0;        len_num1=0;        len_num2=0;        len_num3=0;        for(i=0;i
            
             =1&&'0'<=str[i-1]&&str[i-1]<='9'){                    if('0'<=str[i+1]&&str[i+1]<='9'){                        p2=i;                        j=i-1;                        while(str[j]!=' '){                            num2[len_num2++]=str[j--];                        }                        j=i+1;                        while(str[j]!=' '){                            num3[len_num3++]=str[j++];                        }                        while(str[j]==' '){                            ++j;                        }                        p4=j;                    }                }            }        }        for(i=0;i<=p3;++i){            if(str[i]!=' '){                break;            }        }        str1[len1++]=str[i++];        for(;i<=p3;++i){            if(str[i]==' '&&str1[len1-1]==' '){                continue;            }            str1[len1++]=str[i];        }        str1[len1]='\0';        for(i=p4;i
             
              =0;--i){ if(str2[i]!=' '){ len2=i+1; break; } } str2[i+1]='\0'; p5=-1; for(i=0;i
             
            
           
          
         
        

 

G.

d.类似于扫雷的游戏，这里不是周围8个位置，而是上下左右加它自己5个位置。给出周围多少个雷的数组，求出雷的分布。

s.dfs。先确定第一行，下面的每个位置只看上面的位置即可。

#include
        
         #include
         
          using namespace std;int d[25][25];char g[25][25];int n,m;int dir[][2]={
      {-1,0},{
      1,0},{
      0,-1},{
      0,1},{
      0,0}};bool stop;void dfs(int r,int c);void f1(int r,int c){    int i;    int a,b;    g[r][c]='*';    for(i=0;i<5;++i){        a=r+dir[i][0];        b=c+dir[i][1];        if( 0<=a&&a
         
        

 

H.

d.在一个N*M（N,M<=20）的矩阵中，某个位置的值取决于上下左右和它自己，求出所有位置的值。

s.双重循环，直接求一遍就行了。

#include
        
         #include
         
          #include
          
           using namespace std;int dir[4][2]={
      {-1,0},{
      1,0},{
      0,-1},{
      0,1}};int main(){    int T;    int N,M;    int s[25][25];    int v[25][25];    int i,j;    int a,b;    int ma,ma_i,ma_j;    int ca=0;    int k;    scanf("%d",&T);    while(T--){        scanf("%d%d",&N,&M);        for(i=0;i
           
            =N||b>=M){                        v[i][j]-=1;                        continue;                    }                    if(s[a][b]>s[i][j]){                        v[i][j]=v[i][j]+(s[a][b]-s[i][j]);                    }                    else{                        v[i][j]=v[i][j]-(s[i][j]-s[a][b]);                    }                }            }        }        ma=v[0][0];        ma_i=0;        ma_j=0;        for(i=0;i
            
             =ma){                    ma=v[i][j];                    ma_i=i;                    ma_j=j;                }            }        }        printf("Case %d: %d %d %d\n",++ca,ma,ma_i+1,ma_j+1);    }    return 0;}
            
           
          
         
        

 

I.

d.比较直接的一个完全背包，但是大小有这么大V <= 100,000,000

s.很显然，直接来会爆内存了。

但是这个题物品大小不大1 <= S<= 100。然后很萎缩的5000以上贪心，剩余的用完全背包。。。

为什么过了？

#include
        
         #include
         
          #include
          
           #include
           
            using namespace std;struct node{    long long S;    long long P;    double q;}a[3];bool cmp(node a,node b){    return a.q>b.q;}int main(){    int T;    long long V;    long long sum;    long long dp[6000];    long long tmp;    int i,j;    int ca=0;    scanf("%d",&T);    while(T--){        scanf("%lld%lld",&a[0].S,&a[0].P);        a[0].q=(double)(a[0].P)/a[0].S;        //cout<
            
             <
             
              =5000){ break; } } sum=sum+a[0].S*i; memset(dp,0,sizeof(dp)); for(i=0;i<3;++i){ for(j=a[i].S;j<=sum;++j){ tmp=dp[j-a[i].S]+a[i].P; if(tmp>dp[j]){ dp[j]=tmp; } } } for(i=sum;;--i){ if(dp[i]>0){ break; } } printf("Case %d: %lld\n",++ca,((V-sum)/a[0].S)*a[0].P+dp[i]); } return 0;}
             
            
           
          
         
        

 

J.

d.好像是积分求椭球体的体积。

c.王

#include 
        
         #include 
         
          #include 
          
           using namespace std;int main(){    int T;    scanf("%d",&T);    int i;    for(i=1; i<=T; i++)    {        int a,b,h;        scanf("%d%d%d",&a,&b,&h);        double V;        V=(4.0/3)*M_PI*a*b*b;        if(h>=b)        {            printf("Case %d: %.3lf\n",i,V);        }        else        {            double v=M_PI*a*b*(b-h)-M_PI*(1.0*a/b)*(1.0/3)*(b*b*b-h*h*h);            if(V-v-v>0)                printf("Case %d: %.3lf\n",i,V-v);            else                printf("Case %d: %.3lf\n",i,v);        }    }    return 0;}