携程第二场 Poj 1182 食物链(带权并查集) Poj 1948 Triangular Pastures Poj（dp二维背包） 1740 A New Stone Game（博弈）

╰半橙微兮° 2022-08-26 13:24 6阅读 0赞

携程的第二场好多原题，网上好多题解。。。

一开场就被第一题坑了，很容易看出用并查集处理比较好，但没能理清关系，最后比赛时找了份题解。。。第三题想复杂了，及时发现数据规模比较小，暴力即可。第四题又是我很不擅长的博弈。。。。

第一题和 Poj 1182 一样，输入稍有不同

分析参见：[POJ-1182 食物链 - 飘过的小牛 - 博客频道 - CSDN.NET][POJ-1182 _ - _ - _ - CSDN.NET]

[【POJ1182】食物链，思路+数据+代码，可能是史上关于这道题最详细的解题报告 - c0de4fun的完美算(nei)法(he)教室-我们仍不知道，那天调用的驱动的名字。][POJ1182_ - c0de4fun_nei_he_-]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define N 10010
    
    struct node
    {
    	int pre;
    	int relation;
    };
    node p[N];
    
    int find(int x) //查找根结点
    {
    	int temp;
    	if (x == p[x].pre)
    		return x;
    	temp = p[x].pre; //路径压缩
    	p[x].pre = find(temp);
    	p[x].relation = (p[x].relation + p[temp].relation) % 3; //关系域更新
    	return p[x].pre; //根结点
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while (T--)
        {
            int n,k;
            memset(p,0,sizeof(p));
            int ope, a, b;
            int root1, root2;
            int sum = 0; //假话数量
            scanf("%d%d", &n, &k);
            for(int i = 1; i <= 10001; ++i) //初始化
            {
                p[i].pre = i;
                p[i].relation = 0;
            }
            for(int i = 1; i <= k; ++i)
            {
                scanf("%d%d%d", &ope, &a, &b);
                if(a > n || b > n) //条件2
                {
                    sum++;
                    continue;
                }
                if(ope == 2 && a == b) //条件3
                {
                    sum++;
                    continue;
                }
                root1 = find(a);
                root2 = find(b);
                if(root1 != root2) // 合并
                {
                    p[root2].pre = root1;
                    p[root2].relation = (3 + (ope - 1) +p[a].relation - p[b].relation) % 3;
                }
                else
                {
                    if(ope == 1 && p[a].relation != p[b].relation)
                    {
                        sum++;
                        continue;
                    }
                    if(ope == 2 && ((3 - p[a].relation + p[b].relation) % 3 != ope - 1))
                    {
                        sum++;
                        continue;
                    }
                }
            }
            printf("%d\n", sum);
        }
    	return 0;
    }

第二题与 Poj 1948 Triangular Pastures 一样

还有一种解法可以参考：[POJ 1948 Triangular Pastures\[二维01背包\]\_对酒当歌\_新浪博客][POJ 1948 Triangular Pastures_01]

dp\[i\]\[j\]表示能否构成两边长度为 i 和 j 的三角形（第三边长度为 tot -i-j ）

#include<cmath>
    #include<cstdio>
    #include<cstring>
    #define upmax(a,b) ((a)=(a)>(b)?(a):(b))
    
    const int N=805;
    bool dp[N][N];
    int data[45],n;
    
    int main ()
    {
        int i,j,k;
        while (~scanf("%d",&n),n)
        {
            int tot=0,ans=-1;
            for (i=1;i<=n;i++)
            {
                scanf("%d",&data[i]);
                tot+=data[i];
            }
            memset(dp,false,sizeof(dp));
            dp[0][0]=true;
            int half=tot>>1;
            for (i=1;i<=n;i++)
                for (j=half;j>=0;j--)
                    for (k=j;k>=0;k--)
                        if (j>=data[i] && dp[j-data[i]][k] || k>=data[i] && dp[j][k-data[i]])
                            dp[j][k]=true;
            for (i=half;i>=1;i--)
                for (j=i;j>=1;j--)
                    if (dp[i][j])
                    {
                        k=tot-i-j;
                        if (i+j>k && i+k>j && j+k>i)
                        {
                            double p=1.0*(i+j+k)/2;
                            int tmp=(int)(sqrt(p*(p-i)*(p-j)*(p-k))*100);
                            upmax(ans,tmp);
                        }
                    }
            printf("%d\n",ans);
        }
        return 0;
    }

第三题 直接暴力……

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    int n,m;
    
    struct poly
    {
        int x1,y1,x2,y2;
        int r,g,b;
    
    
        void get()
        {
            scanf("%d%d",&x1,&y1);
            scanf("%d%d",&x2,&y2);
            scanf("%d%d%d",&r,&g,&b);
        }
    
        void print()
        {
            printf("%d %d %d\n",r,g,b);
        }
    
    
        int ok(int x,int y)
        {
            return x>=x1&&x<=x2&&y>=y1&&y<=y2;
        }
    
    };
    
    poly a[1005];
    
    int main()
    {
        while(cin>>n>>m)
        {
            int i;
            for(i=1;i<=n;i++) a[i].get();
            for(i=1;i<=m;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                int j;
                for(j=n;j>=1;j--) if(a[j].ok(x,y))
                {
                    a[j].print();
                    break;
                }
                if(j==0) puts("255 255 255");
            }
        }
    }

第四题 Poj 1740 A New Stone Game

两份参考题解：[POJ 1740 A New Stone Game(博弈) - 将狼踩尽 19891101 - 博客园][POJ 1740 A New Stone Game_ - _ 19891101 -]

[POJ 1740 -- A New Stone Game ( 楼天城之男人系列 )\_snuc\_新浪博客][POJ 1740 -- A New Stone Game _ _ _snuc]

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    int n,a[105];
    
    int main()
    {
        while(cin>>n)
        {
            if(0==n) break;
            int i;
            for(i=1;i<=100;i++) a[i]=0;
    
            for(i=1;i<=n;i++)
            {
                int x;
                cin>>x;
                a[x]++;
            }
            for(i=1;i<=100;i++) if(a[i]&1) break;
            if(i>100) puts("Lose");
            else puts("Win");
        }
    }

[POJ-1182 _ - _ - _ - CSDN.NET]: http://blog.csdn.net/niushuai666/article/details/6981689
[POJ1182_ - c0de4fun_nei_he_-]: http://blog.csdn.net/c0de4fun/article/details/7318642/
[POJ 1948 Triangular Pastures_01]: http://blog.sina.com.cn/s/blog_7d7a71f70100st6z.html
[POJ 1740 A New Stone Game_ - _ 19891101 -]: http://www.cnblogs.com/jianglangcaijin/archive/2012/12/13/2817259.html
[POJ 1740 -- A New Stone Game _ _ _snuc]: http://blog.sina.com.cn/s/blog_55a8a96d010005eb.html