您的位置: 首页  >  IT文章  >  山东省第三届ACM省赛

山东省第三届ACM省赛

分类: IT文章 • 2022-07-21 12:50:31
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 <iostream>
#include <cstdio>
#include <algorithm>
#include<string.h>
#include <vector>
#include <queue>
#include<time.h>
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> edge;
    vector<int> G[maxn];
    int inq[maxn], d[maxn], p[maxn], a[maxn];
    void init(int n)
    {
        this->n=n;
        for(int i=0; i<n; i++)
            G[i].clear();
        edge.clear();
    }
    void AddEdge(int u, int v, int cap, int cost)
    {
        edge.push_back(Edge(u, v, cap, 0, cost));
        edge.push_back(Edge(v, u, 0, 0, -cost));
        m=edge.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    bool spfa(int s, int t, int& flow, int& cost)
    {
        memset(d, 0x3f, sizeof d);
        memset(inq, 0, sizeof inq);
        d[s]=0, inq[s]=1, p[s]=0, a[s]=oo;

        queue<int> q;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            inq[u]=0;
            for(int i=0; i<G[u].size(); i++)
            {
                Edge& e=edge[G[u][i]];
                if(e.cap>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<b.h;
    return a.h2<b.h2;
}
bool cmp2(node a,node b){
    if(a.h!=b.h)return a.h<b.h;
    return a.h2<b.h2;
}

int test1[]={14,20,20,3,10,28,1,19,3,26,29,17,27,11,5,24,3,20,2,8,8,0,11,0,19,29,
10,23,17,3,14,28,14,8,6,6,8,5,15,1,23,28,17,9,15,20,13,6,3,11,8,6,23,3,1,21,13,20,17,0,16,
14,4,1,18,27,25,21,29,13,19,11,10,22,2,27,0,19,1,8,7,18,7,5,11,22,23,24,22,3,27,3,
17,21,26,8,17,17,17,19,12,28,14,17,28,19,25,12,10,1,30,6,1,1,29,16,0,6,22,27,25,
25,3,0,0,29,8,29,19,24,9,27,15,1,11,28,28,7,0,24,8,17,16,13,14,29,2,12,23,22,12,
25,13,19,21,11,9,10,9,16,16,13,20,22,10,30,29,27,12,23,16,11,22,24,9,15,4,26,4,15,
19,16,16,19,27,27,30,11,27,27,4,22,19,24,29,10,28,27,2,30,29,19,3,8,21,4,2,4,2,
23,13,6,20,21,5,10,2,8,3,2,3,17,10,7,25,16,13,12,10,23,30,27,22,24,6,10,0,0,30,
7,0,1,1,18,29,5,19,10,8,30,30,0,15,3,17,2,12,22,1,8,20,14,2,15,10,17,4,26,23,19,
15,25,30,17,23,13,18,24,15,1,15,14,5,13,18,10,28,11,11,30,15,0,2,28,4,27,29,21,30,
1,29,8,6,1,21,13,8,29,24,13,22,1,3,20,8,7,25,26,21,11,3,3,10,9,24,27,5,5,7,9,16,
17,18,0,5,9,12,10,29,9,20,24,11,4,3,30,12,30,26,6,17,14,20,15,26,17,27,28,15,21,
15,27,12,24,25,24,17,3,25,9,0,3,15,12,28,6,0,3,17,27,7,26,10,9,13,24,4,21,21,19,
20,29,15,15,0,24,22,17,30,2,6,21,12,21,16,24,4,10,25,6,18,26,19,5,7,17,18,7,1,
12,13,15,17,21,14,13,17,9,14,4,6,1,13,12,28,1,0,11,29,22,3,25,3,11,21,12,22,5,18,7,
5,0,12,26,11,17,8,14,0,18,6,7,8,30,23,19,0,26,6,15,23,24,30,29,11,20,2,21,14,
4,20,24,1,15,28,30,14,19,8,22,2,23,3,14,20,30,1,1,1,12,17,12,0,2,1,29,18,17,17,5,
17,21,8,8,23,15,11,2,18,30,12,26,9,13,15,11,30,12,23,21,5,18,12,4,20,8,15,19,19,
16,26,24,8,6,23,11,11,9,4,7,22,27,1,24,1,29,19,12,4,18,25,1,5,4,3,25,25,6,0,3,6,
23,23,15,4,6,21,10,20,25,19,11,4,26,4,28,8,8,22,26,12,6,20,28,24,7,4,11,25,28,23,
0,25,1,3,0,2,10,11,20,4,21,8,15,11,10,6,1,30,2,6,2,6,0,9,19,13,27,30,21,13,18,
17,10,21,27,23,2,5,13,15,10,4,4,18,10,9,5,7,10,24,19,12,2,12,26,6,25,8,18,3,13,19,
16,19,15,28,11,16,8,29,15,13,23,24,2,2,19,0,7,23,14,2,28,22,2,0,26,16,18,11,19,
0,10,19,5,26,8,8,8,13,5,30,20,29,21,30,3,7,29,27,19,28,13,2,15,18,28,13,5,24,13,
15,27,9,29,0,7,16,28,12,1,9,4,8,6,12,11,12,14,22,28,20,14,8,17,25,20,13,16,6,8,
3,7,7,28,17,23,17,13,16,0,19,23,5,17,6,20,21,9,14,30,2,26,7,5,30,24,2,10,23,22,8,
19,4,9,27,29,11,4,13,23,8,18,6,6,1,18,5,17,6,18,13,6,30,6,28,9,22,9,11,3,3,4,25,
29,3,10,19,26,14,11,29,9,23,4,0,23,29,14,2,21,29,18,10,10,3,2,4,16,20,23,2,5,0,
11,10,1,19,14,10,4,15,22,25,8,10,12,25,15,30,5,2,30,10,5,30,7,3,23,23,19,18,3,10,
13,2,30,16,30,2,6,22,30,3,4,28,6,2,22,3,3,5,20,14,16,12,14,28,12
};
int test2[]={
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,
3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,10,
10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,11,11,
11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,12,12,12,12,12,12,12,12,
12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,13,13,13,13,13,13,13,
13,13,13,13,13,13,13,13,13,13,13,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,
14,14,14,14,14,14,14,14,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,
15,15,15,15,15,15,15,15,15,15,15,15,15,15,16,16,16,16,16,16,16,16,16,16,16,16,16,
16,16,16,16,16,16,16,16,16,16,16,16,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,
17,17,17,17,17,17,17,17,17,17,17,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,
18,18,18,18,18,18,18,18,18,18,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,
19,19,19,19,19,19,19,19,19,19,19,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,
20,20,20,20,20,20,20,20,20,20,20,20,21,21,21,21,21,21,21,21,21,21,21,21,21,21,
21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,22,22,22,22,22,22,
22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,23,23,23,23,23,23,23,23,23,23,
23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,24,24,24,24,24,24,24,24,24,
24,24,24,24,24,24,24,24,24,24,24,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25
,25,25,25,25,25,25,25,25,25,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,
27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,28,28,
28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,29,29,29,29,29,29,29,29,29,
29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,30,30,30,30,30,30,30,30,30,30,30,
30,30,30,30,30,30,30,30,30,30,30,30,30
};

int temp;

int f(int N,int M,int K,int b[]){

    int T;
    //int N,M,K;
    //int a[1005],b[1005];
    int i;
    int ca=0;
    int sum;
    //int a2[1005],a3[1005];
    int p1,p2,p3,p4,q1,q2;
    int t1,t2;
    bool use[1005];

    //scanf("%d",&T);

    //while(T--){

        //scanf("%d%d%d",&N,&M,&K);

        //for(i=0;i<N;++i){
        //    scanf("%d",&a[i]);
        //}
        sum=0;
        for(i=0;i<N-1;++i){
            sum=sum+abs(a[i]-a[i+1]);
            temp=sum;

            if(a[i]>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:  "<<i<<"  a2[i].h "<<a2[i].h<<endl;
                cout<<"i:  "<<i<<"  a2[i].h2 "<<a2[i].h2<<endl;
                */
        }
/*
        i=1;
        cout<<"##"<<endl;
        cout<<"i:  "<<i<<"  a2[i].h "<<a2[i].h<<endl;
        cout<<"i:  "<<i<<"  a2[i].h2 "<<a2[i].h2<<endl;
        */
        /*
        i=1;
        cout<<"##"<<endl;
        cout<<"i:  "<<i<<"  a2[i].h "<<a2[i].h<<endl;
        cout<<"i:  "<<i<<"  a2[i].h2 "<<a2[i].h2<<endl;
        */

        sort(a2,a2+(N-1),cmp);
        sort(a3,a3+(N-1),cmp2);
/*
        i=1;
        cout<<"##"<<endl;
        cout<<"i:  "<<i<<"  a2[i].h "<<a2[i].h<<endl;
        cout<<"i:  "<<i<<"  a2[i].h2 "<<a2[i].h2<<endl;
        */
        /*
        i=1;
        cout<<"##"<<endl;
        cout<<"i:  "<<i<<"  a2[i].h "<<a2[i].h<<endl;
        cout<<"i:  "<<i<<"  a2[i].h2 "<<a2[i].h2<<endl;
        */


        //for(i=0;i<M;++i){
        //    scanf("%d",&b[i]);
        //}
        sort(b,b+M);

        p1=0;p2=N-2;
        p3=0;p4=N-2;
        q1=0;q2=M-1;
        memset(use,false,sizeof(use));
        for(i=0;i<K;++i){

            if(p1<0||p2<0||p3<0||p4<0||q1<0||q2<0){
                cout<<"越界"<<endl;
            }
            if(p1>N-2||p2>N-2||p3>N-2||p4>N-2||q1>M-1||q2>M-1){
                cout<<"越界2"<<endl;
            }

            while(use[a2[p1].id]==true){
                ++p1;
            }
            //cout<<"p1 "<<p1<<endl;
            t1=b[q2]-a2[p1].h;
            //cout<<"t1  "<<t1<<endl;
            if(t1<0){
                t1=0;
            }
            while(use[a3[p4].id]==true){
                --p4;
            }

            //cout<<"p4  :"<<p4<<endl;
            t2=a3[p4].h-b[q1];
            //cout<<"t2 "<<t2<<endl;
            if(t2<0){
                t2=0;
            }

            if(t1>t2){
                sum=sum+2*t1;
                use[a2[p1].id]=true;

                //
                //cout<<a2[p1].id<<"###   t1:  "<<t1<<endl;

                ++p1;
                --q2;


            }
            else{
                sum=sum+2*t2;
                use[a3[p4].id]=true;

                //
                //cout<<a3[p4].id<<"else   t2:   "<<t2<<endl;

                --p4;
                ++q1;
            }


            //cout<<"i:"<<i<<",sum:"<<sum<<endl;
        }

        //printf("Case %d: %d
",++ca,sum);

        return sum;

   // }

}


int main()
{

    int ccc[maxn];
    int tot;
    int T, kase=0;
    //scanf("%d", &T);
    T=100;
    T=100;
    srand(time(NULL));
    while(T--)
    {
        int n, m, k, ans=0;

        n=3;
        m=2;
        k=2;

        n=900;
        m=800;
        k=800;
        //scanf("%d%d%d", &n, &m, &k);
        net.init(n+100);
        memset(b, 0, sizeof b);

        for(int i=0; i<n; i++){
            a[i]=rand()%31;

            //a[i]=test1[i];

            //scanf("%d", a+i);
        }


        tot=0;
        for(int i=0; i<m; i++)
        {
            int x;
/*
            x=rand()%31;
            //scanf("%d", &x);
            b[x]++;
            ccc[tot++]=x;

*/
  //          /*

            int fuck=rand()%31;
            b[fuck]++;
            ccc[tot++]=fuck;
    //        */

        }
        for(int i=1; i<n; i++)
        {
            ans+=abs(a[i]-a[i-1]);
            net.AddEdge(0, i, 1, 0);
            for(int j=0; j<=30; j++)
                if(b[j])
                {
                    int dis=abs(a[i]-j)+abs(a[i-1]-j)-abs(a[i]-a[i-1]);
                    net.AddEdge(i, n+j, 1, -dis);
                }
        }
        int S=n+50, T=S+1;
        for(int i=0; i<=30; i++)
            if(b[i])
                net.AddEdge(i+n, T, b[i], 0);
        net.AddEdge(S, 0, k, 0);

        int ans2=net.MinCost(S, T);
        int ans1=ans-ans2;
        //printf("Case %d: %d
", ++kase, );

        //cout<<"贪心："<<endl;
        int tanxin=f(n,m,k,ccc);

        if(ans1!=tanxin){

            cout<<"ans:"<<ans<<endl;
            cout<<"ans2:"<<ans2<<endl;

            cout<<"temp:"<<temp<<endl;
            cout<<tanxin-temp<<endl;

            cout<<"yes"<<endl;
            cout<<"a:"<<endl;
            for(int i=0;i<n;++i){
                cout<<a[i]<<',';
            }
            cout<<endl;

            cout<<"ccc:"<<endl;
            for(int i=0;i<m;++i){
                cout<<ccc[i]<<',';
            }
            cout<<endl;

            cout<<endl;

            cout<<ans1<<"网络流"<<endl;
            cout<<tanxin<<"贪心"<<endl;
            //return 0;

        }
    }


    return 0;
}
/*
yes
a:
14,20,20,3,10,28,1,19,3,26,29,17,27,11,5,24,3,20,2,8,8,0,11,0,19,29,10,23,17,3,1
4,28,14,8,6,6,8,5,15,1,23,28,17,9,15,20,13,6,3,11,8,6,23,3,1,21,13,20,17,0,16,14
,4,1,18,27,25,21,29,13,19,11,10,22,2,27,0,19,1,8,7,18,7,5,11,22,23,24,22,3,27,3,
17,21,26,8,17,17,17,19,12,28,14,17,28,19,25,12,10,1,30,6,1,1,29,16,0,6,22,27,25,
25,3,0,0,29,8,29,19,24,9,27,15,1,11,28,28,7,0,24,8,17,16,13,14,29,2,12,23,22,12,
25,13,19,21,11,9,10,9,16,16,13,20,22,10,30,29,27,12,23,16,11,22,24,9,15,4,26,4,1
5,19,16,16,19,27,27,30,11,27,27,4,22,19,24,29,10,28,27,2,30,29,19,3,8,21,4,2,4,2
,23,13,6,20,21,5,10,2,8,3,2,3,17,10,7,25,16,13,12,10,23,30,27,22,24,6,10,0,0,30,
7,0,1,1,18,29,5,19,10,8,30,30,0,15,3,17,2,12,22,1,8,20,14,2,15,10,17,4,26,23,19,
15,25,30,17,23,13,18,24,15,1,15,14,5,13,18,10,28,11,11,30,15,0,2,28,4,27,29,21,3
0,1,29,8,6,1,21,13,8,29,24,13,22,1,3,20,8,7,25,26,21,11,3,3,10,9,24,27,5,5,7,9,1
6,17,18,0,5,9,12,10,29,9,20,24,11,4,3,30,12,30,26,6,17,14,20,15,26,17,27,28,15,2
1,15,27,12,24,25,24,17,3,25,9,0,3,15,12,28,6,0,3,17,27,7,26,10,9,13,24,4,21,21,1
9,20,29,15,15,0,24,22,17,30,2,6,21,12,21,16,24,4,10,25,6,18,26,19,5,7,17,18,7,1,
12,13,15,17,21,14,13,17,9,14,4,6,1,13,12,28,1,0,11,29,22,3,25,3,11,21,12,22,5,18
,7,5,0,12,26,11,17,8,14,0,18,6,7,8,30,23,19,0,26,6,15,23,24,30,29,11,20,2,21,14,
4,20,24,1,15,28,30,14,19,8,22,2,23,3,14,20,30,1,1,1,12,17,12,0,2,1,29,18,17,17,5
,17,21,8,8,23,15,11,2,18,30,12,26,9,13,15,11,30,12,23,21,5,18,12,4,20,8,15,19,19
,16,26,24,8,6,23,11,11,9,4,7,22,27,1,24,1,29,19,12,4,18,25,1,5,4,3,25,25,6,0,3,6
,23,23,15,4,6,21,10,20,25,19,11,4,26,4,28,8,8,22,26,12,6,20,28,24,7,4,11,25,28,2
3,0,25,1,3,0,2,10,11,20,4,21,8,15,11,10,6,1,30,2,6,2,6,0,9,19,13,27,30,21,13,18,
17,10,21,27,23,2,5,13,15,10,4,4,18,10,9,5,7,10,24,19,12,2,12,26,6,25,8,18,3,13,1
9,16,19,15,28,11,16,8,29,15,13,23,24,2,2,19,0,7,23,14,2,28,22,2,0,26,16,18,11,19
,0,10,19,5,26,8,8,8,13,5,30,20,29,21,30,3,7,29,27,19,28,13,2,15,18,28,13,5,24,13
,15,27,9,29,0,7,16,28,12,1,9,4,8,6,12,11,12,14,22,28,20,14,8,17,25,20,13,16,6,8,
3,7,7,28,17,23,17,13,16,0,19,23,5,17,6,20,21,9,14,30,2,26,7,5,30,24,2,10,23,22,8
,19,4,9,27,29,11,4,13,23,8,18,6,6,1,18,5,17,6,18,13,6,30,6,28,9,22,9,11,3,3,4,25
,29,3,10,19,26,14,11,29,9,23,4,0,23,29,14,2,21,29,18,10,10,3,2,4,16,20,23,2,5,0,
11,10,1,19,14,10,4,15,22,25,8,10,12,25,15,30,5,2,30,10,5,30,7,3,23,23,19,18,3,10
,13,2,30,16,30,2,6,22,30,3,4,28,6,2,22,3,3,5,20,14,16,12,14,28,12,
ccc:
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,
3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,10
,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,11,1
1,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,12,12,12,12,12,12,12,12,
12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,13,13,13,13,13,13,13,13
,13,13,13,13,13,13,13,13,13,13,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,1
4,14,14,14,14,14,14,14,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,
15,15,15,15,15,15,15,15,15,15,15,15,15,15,16,16,16,16,16,16,16,16,16,16,16,16,16
,16,16,16,16,16,16,16,16,16,16,16,16,17,17,17,17,17,17,17,17,17,17,17,17,17,17,1
7,17,17,17,17,17,17,17,17,17,17,17,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,
18,18,18,18,18,18,18,18,18,18,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19
,19,19,19,19,19,19,19,19,19,19,19,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,2
0,20,20,20,20,20,20,20,20,20,20,20,20,21,21,21,21,21,21,21,21,21,21,21,21,21,21,
21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,22,22,22,22,22,22
,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,23,23,23,23,23,23,23,23,23,23,2
3,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,24,24,24,24,24,24,24,24,24,
24,24,24,24,24,24,24,24,24,24,24,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25
,25,25,25,25,25,25,25,25,25,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,2
7,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,28,28,
28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,29,29,29,29,29,29,29,29,29
,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,30,30,30,30,30,30,30,30,30,30,3
0,30,30,30,30,30,30,30,30,30,30,30,30,30,

25090网络流
25086贪心

Process returned 0 (0x0)   execution time : 1.981 s
Press any key to continue.

*/


/*
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define Pr pair<int,int>
#define fread() freopen("data1.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout)

using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const int mod = 1e9+7;
const double eps = 1e-8;

struct Edge
{
    int v,f,w,next;
};

Edge eg[66666];
int head[2333],h[2333],hcnt[2333];
int dis[2333],pre[2333];
bool vis[2333];
int tp,ans,minf;

void Add(int u,int v,int w,int f)
{
    eg[tp].v = v;
    eg[tp].w = w;
    eg[tp].f = f;
    eg[tp].next = head[u];
    head[u] = tp++;
}

bool bfs(int st,int en)
{
    memset(dis,-1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    queue <int> q;
    q.push(st);
    dis[st] = 0;
    minf = INF;
    int u,v,w,f;

    while(!q.empty())
    {
        u = q.front();
        q.pop();
        vis[u] = 0;

        for(int i = head[u]; i != -1; i = eg[i].next)
        {
            v = eg[i].v;
            w = eg[i].w;
            f = eg[i].f;
            if(f && (dis[v] == -1 || dis[v] < dis[u]+w))
            {
                dis[v] = dis[u]+w;
                minf = min(f,minf);
                pre[v] = i;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }

    if(pre[en] == -1) return false;

    ans += dis[en];
    for(int i = pre[en]; i != -1; i = pre[eg[i^1].v])
    {
        eg[i].f -= minf;
        eg[i^1].f += minf;
    }

    return true;
}

int main()
{

    int t,n,m,k,x;
    scanf("%d",&t);
    for(int z = 1; z <= t; ++z)
    {
        scanf("%d%d%d",&n,&m,&k);
        memset(head,-1,sizeof(head));
        memset(hcnt,0,sizeof(hcnt));
        tp = 0;
        ans = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d",&h[i]);
            if(i) ans += abs(h[i]-h[i-1]);
        }
        while(m--)
        {
            scanf("%d",&x);
            hcnt[x]++;
        }

        //n为起点 0~n-2表示初始第i个山爬到i+1山路程 n+1~n+30表示高1~30的山数 n+31表示起点前的一个点(限流) n+32表示终点
        Add(n+33,n+31,0,k);
        Add(n+31,n+33,0,0);
        for(int i = 0; i <= 30; ++i)
        {
            if(!hcnt[i]) continue;
            Add(n+31,n+i,0,hcnt[i]);
            Add(n+i,n+31,0,0);
            for(int j = 0; j < n-1; ++j)
            {
                Add(n+i,j,abs(h[j]-i)+abs(h[j+1]-i)-abs(h[j]-h[j+1]),hcnt[i]);
                Add(j,n+i,-abs(h[j]-i)-abs(h[j+1]-i)+abs(h[j]-h[j+1]),0);
            }
        }
        for(int j = 0; j < n-1; ++j)
        {
            Add(j,n+32,0,1);
            Add(n+32,j,0,0);
        }
        while(bfs(n+33,n+32));
        printf("Case %d: %d
",z,ans);
    }

    return 0;
}



*/
View Code

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

参考：山东省第三届省赛 C 题 – An interesting game(费用流) 

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<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
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-1
void 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<int>q;
    for(int i=0;i<N;i++){
        dis[i]=INF;
        vis[i]=false;
        pre[i]=-1;
    }
    dis[s]=0;
    vis[s]=true;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;
            if(edge[i].cap>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<N2;++i){
            scanf("%d",&X[i]);
        }
        memset(YNum,0,sizeof(YNum));
        for(i=0;i<M;++i){
            scanf("%d",&Y[i]);
            ++YNum[Y[i]];
        }

        sum=0;
        for(i=0;i<N2-1;++i){//初始值
            sum=sum+abs(X[i]-X[i+1]);
        }

        sp=N2+40;

        for(i=0;i<N2-1;++i){//加边
            addedge(sp,i,1,0);//源点到空隙
            for(j=0;j<=30;++j){
                if(YNum[j]){
                    tmp=abs(X[i]-j)+abs(X[i+1]-j)-abs(X[i]-X[i+1]);
                    addedge(i,N2+j,1,-tmp);//空隙到M个山丘
                }
            }
        }

        sp2=N2+41;
        sc=N2+42;
        addedge(sp2,sp,K,0);
        for(i=0;i<=30;++i){
            if(YNum[i]){
                addedge(N2+i,sc,YNum[i],0);
            }
        }

        ma_flow=minCostMaxflow(sp2,sc,mi_cost);

        printf("Case %d: %d
",++ca,sum-mi_cost);
    }

    return 0;
}
View Code

D.

d.好像是按要求输出串

s.没写这个题

c.张

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#define MAX 500
using 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<len; i++)
        {
            for(j=0; j<Len; j++)
                if(str[i]==temp1[j])
                    break;
            if(j<Len) str[i]=temp2[j];
        }
        printf("Case %d: ",coun++);
        for(int i=len-1; i>=0; i--)
            printf("%c",str[i]);
        printf("
");
    }
    return 0;
}
View Code

E.

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

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

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

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

再用DP求最大分数。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

#define MAXN 10010

int 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<n;++i){
            scanf("%d%d%d",&t,&s,&p);
            d[t][p]=s;
            if(t>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
",++ca,dp[ma_t]);
    }

    return 0;
}
View Code

F.

d.串中提取数字

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

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

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
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("%[^
]",str);
        getchar();

        len=strlen(str);

        len1=0;
        len2=0;
        len_num1=0;
        len_num2=0;
        len_num3=0;

        for(i=0;i<len;++i){
            if(str[i]=='i'){
                if(str[i+1]=='n'&&str[i+2]=='c'&&str[i+3]=='h'&&
                   str[i+4]=='e'&&str[i+5]=='s'&&str[i+6]==' '){
                       p1=i;
                       j=i-1;
                       while(str[j]==' '){
                            --j;
                       }
                       while(str[j]!=' '){
                            num1[len_num1++]=str[j--];
                       }
                       while(str[j]==' '){
                            --j;
                       }
                       p3=j;
                   }
            }
            if(str[i]=='*'){
                if(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]='

相关推荐