CUIT MAGICIAN UNION 2017 TRAININ

第一题 Expanding Rods POJ 1905 题解算法:二分搜索

#include <cstdio>
#include <string>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <stdlib.h>
#include <map>
#define maxn 101001
#define ll long long
#define eps 1e-6
#define biaoji printf("\n!!\n");
using namespace std;

int main()
{
    double l,n,C;
    while(scanf("%lf%lf%lf",&l,&n,&C)!=EOF)
    {
        if(l == -1 && n == -1 && C == -1){
            break;
        }

        double l1 = ( 1 + n * C ) * l;
        double L = 0.0 , R = 0.5*l , h;
        while(R-L>eps)
        {
            h = ( L + R )/2;
            double r = ( 4 * h * h + l * l ) / ( 8 * h );
            if( 2 * r * asin(l/(2*r)) < l1 ) L = h;
            else R = h;
        }
        printf("%.3f\n",h);
    }
    return 0;
}

第二题 Frogger POJ 2253 题解算法：最小生成树kruskal

#include <cstdio>
#include <string>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <stdlib.h>
#include <map>
#define maxn 101001
#define ll long long
#define eps 1e-6
#define biaoji printf("\n!!\n");
using namespace std;

int pre[1010];

int Find(int x)
{
    if(pre[x] == x) return x;
    return pre[x] = Find(pre[x]);
}

void Union(int a,int b)
{
    int A = Find(a);
    int B = Find(b);
    if( A != B)
    {
        pre[B] = A;
    }
}

struct Node
{
    double x,y;
    int id;
}node[1010];

struct NODE
{
    int u,v;
    double dis;
}road[1001000];

bool cmp(NODE a,NODE b)
{
    return a.dis < b.dis;
}


double getdis(Node a,Node b)
{
    double dis = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
    return dis;
}

int main()
{
    int n,cas=1;
    while(scanf("%d",&n) && n)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf",&node[i].x,&node[i].y);
            node[i].id = 1;
        }

        int cnt = 0;
        for(int i = 1; i <= n; i++)
        {
            for(int j = i + 1 ; j <= n ; j++)
            {
                road[cnt].u = i,road[cnt].v = j;
                road[cnt].dis = getdis(node[i],node[j]);
                cnt++;
            }
        }
        sort(road,road+cnt,cmp);
        for( int i = 1 ; i <= n ; i++)
        {
            pre[i] = i;
        }

        double mindis;
        for( int i = 0 ; i < cnt ;i++)
        {
            if(Find(1) != Find(2))
            {
                Union(road[i].u,road[i].v);
                mindis = road[i].dis;
            }
            else
            {
                break;
            }
        }
        printf("Scenario #%d\n",cas++);
        printf("Frog Distance = %.3f\n",mindis);
        printf("\n");
    }
    return 0;
}

第三题 Anton and Classes codeforces 785B 题解算法:暴力

#include <cstdio>
#include <string>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <stdlib.h>
#include <map>
#define maxn 101001
#define ll long long
#define eps 1e-6
#define biaoji printf("\n!!\n");
using namespace std;

struct CH
{
    int STA,END;
}chess[200200];

struct pro
{
    int STA,END;
}program[200200];

bool cmp1(CH a,CH b)
{
    return a.END < b.END;
}

bool cmp2(CH a,CH b)
{
    return a.STA > b.STA;
}

bool cmp3(pro a,pro b)
{
    return a.END < b.END;
}

bool cmp4(pro a,pro b)
{
    return a.STA > b.STA;
}

int main()
{
    int n,m;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&chess[i].STA,&chess[i].END);
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&program[i].STA,&program[i].END);
    }
    sort(chess,chess+n,cmp1);
    sort(program,program+m,cmp4);
    int maxtime = program[0].STA - chess[0].END;
    sort(chess,chess+n,cmp2);
    sort(program,program+m,cmp3);
    maxtime = max(maxtime,chess[0].STA - program[0].END);
    if(maxtime < 0) maxtime = 0;
    printf("%d\n",maxtime);
    return 0;
}

第三题优化代码（Come from fold）

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<map>
#define ll long long int
#define pi acos(-1)
#define mod 1000000007
#define inf 0x7fffffff
using namespace std;

int main()
{
    int m,n,a,b;
    int max1=0,min1=inf,max2=0,min2=inf;
    int maxxA=0,maxxB=0;
    scanf("%d",&m);
    for(int i=0; i<m; i++)
    {
        scanf("%d%d",&a,&b);
        if(a>max1)max1=a;
        if(b<min1)min1=b;
    }
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        if(a>max2)max2=a;
        if(b<min2)min2=b;
    }
    if(max2>min1)maxxA=max2-min1;
    if(max1>min2)maxxB=max1-min2;
    printf("%d\n",max(maxxA,maxxB));
    return 0;
}

第四道题 Pots POJ3414 题解算法:BFS

#include <cstdio>
#include <string>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <stdlib.h>
#include <map>
#include <iostream>
#define maxn 101001
#define ll long long
#define eps 1e-6
#define biaoji printf("\n!!\n");
using namespace std;

int tem2;
int A,B,C;
int pp[1000];
int vis[110][110];

struct node
{
    int a,b;
    int pos;
    int prepos;
    int str;
    int step;
} pre[100100];

void bfs()
{
    node x;
    int pos = 0 ;
    x.a = 0;
    x.b = 0;
    x.prepos = -1;
    x.step = 0;
    x.str = 0;
    x.pos=0;
    pre[pos++] = x;
    vis[x.a][x.b] = 1;
    queue<node>Q;
    Q.push(x);

    memset(vis,0,sizeof(vis));
    while(!Q.empty())
    {
        node tem = Q.front();
        Q.pop();

        /*cout<<" x.a : "<<tem.a<<endl;
        cout<<" x.b : "<<tem.b<<endl;
        cout<<" x.prepos : "<<tem.prepos<<endl;
        cout<<" x.pos : "<<tem.pos<<endl;
        cout<<" x.str : "<<tem.str<<endl;
        cout<<" x.step : "<<tem.step<<endl;*/
        if(tem.a == C || tem .b == C)
        {
            cout << tem.step << endl;
            tem2=0;
            pp[tem2++] = tem.str;
            int xx = tem.prepos;
            while(pre[xx].prepos!= -1)
            {
                pp[tem2++] = pre[xx].str;
                xx = pre[xx].prepos;
            }
            for(int i = tem2 - 1 ; i >= 0; i --)
            {
                if(pp[i] == 1){printf("FILL(1)\n");}
                if(pp[i] == 2){printf("FILL(2)\n");}
                if(pp[i] == 3){printf("DROP(1)\n");}
                if(pp[i] == 4){printf("DROP(2)\n");}
                if(pp[i] == 5){printf("POUR(1,2)\n");}
                if(pp[i] == 6){printf("POUR(2,1)\n");}
            }
            return ;
        }
        else
        {
            node tem3;
            if(tem.a != A)
            {
                tem3.a = A;
                tem3.b = tem.b;
                if(vis[tem3.a][tem3.b] == 0)
                {
                    vis[tem3.a][tem3.b] = 1;
                    tem3.prepos = tem.pos;
                    tem3.str = 1;
                    tem3.step = tem.step+1;
                    tem3.pos = pos;
                    pre[pos++] = tem3;
                    Q.push(tem3);
                }
            }
            if(tem.b != B)
            {
                tem3.a = tem.a;
                tem3.b = B;
                if(vis[tem3.a][tem3.b] == 0)
                {
                    vis[tem3.a][tem3.b] = 1;
                    tem3.prepos = tem.pos;
                    tem3.pos = pos;
                    tem3.str = 2;
                    tem3.step = tem.step + 1;
                    pre[pos++] = tem3;
                    Q.push(tem3);
                }

            }
            if(tem.a != 0)
            {
                tem3.a = 0;
                tem3.b = tem.b;
                if(vis[tem3.a][tem3.b] == 0)
                {
                    vis[tem3.a][tem3.b] = 1;
                    tem3.prepos = tem.pos;
                    tem3.pos = pos;
                    tem3.str = 3;
                    tem3.step = tem.step + 1;
                    pre[pos++] = tem3;
                    Q.push(tem3);
                }
            }
            if(tem.b != 0)
            {
                tem3.a = tem.a;
                tem3.b = 0;
                if(vis[tem3.a][tem3.b] == 0)
                {
                    vis[tem3.a][tem3.b] = 1;
                    tem3.prepos = tem.pos;
                    tem3.pos = pos;
                    tem3.str = 4;
                    tem3.step = tem.step + 1;
                    pre[pos++] = tem3;
                    Q.push(tem3);
                }

            }
            if(tem.b != B && tem.a != 0 )
            {
                if(tem.b + tem.a <= B)
                {
                    tem3.a = 0;
                    tem3.b = tem.a + tem.b;
                }
                else if(tem.b + tem.a > B)
                {
                    tem3.b = B;
                    tem3.a = tem.a - (B - tem.b);
                }
                if(vis[tem3.a][tem3.b] == 0)
                {
                    vis[tem3.a][tem3.b] = 1;
                    tem3.prepos = tem.pos;
                    tem3.pos = pos;
                    tem3.str = 5;
                    tem3.step = tem.step + 1;
                    pre[pos++] = tem3;
                    Q.push(tem3);
                }
            }
            if(tem.a != A && tem.b != 0)
            {
                if(tem.b + tem.a <= A)
                {
                    tem3.a = tem.a + tem.b;
                    tem3.b = 0;
                }
                else if(tem.b + tem.a > A)
                {
                    tem3.b = tem.b - ( A - tem.a );
                    tem3.a = A;
                }
                if(vis[tem3.a][tem3.b] == 0)
                {
                    vis[tem3.a][tem3.b] = 1;
                    tem3.prepos = tem.pos;
                    tem3.pos = pos;
                    tem3.str = 6;
                    tem3.step = tem.step + 1;
                    pre[pos++] = tem3;
                    Q.push(tem3);
                }
            }
        }

    }
    printf("impossible\n");
    return ;

}


void solve()
{
    scanf("%d%d%d",&A,&B,&C);
    bfs();
}

int main()
{
    int casenum = 1;
    while(casenum--)
    {
        solve();
    }
    return 0;
}

第五题 Marriage Match IV HDU 3416
我没有做出来，应该是最大流和最短路的混合，自己去做吧。