2014 CodingTrip

1001：食物链（poj1182），直接贴代码，稍作可过

并查集

  1 //
  2 //  main.cpp
  3 //  携程1
  4 //
  5 //  Created by zhang on 14-4-11.
  6 //  Copyright (c) 2014年 apple. All rights reserved.
  7 //
  8 
  9 #include <iostream>
 10 #include <cstring>
 11 #include <cstdio>
 12 #include <cstdlib>
 13 #include <cmath>
 14 #include <string>
 15 #include <vector>
 16 #include <list>
 17 #include <map>
 18 #include <queue>
 19 #include <stack>
 20 #include <bitset>
 21 #include <algorithm>
 22 #include <numeric>
 23 #include <functional>
 24 
 25 using namespace std;
 26 const int maxk=100010;
 27 int N,K;
 28 int D[maxk],X[maxk],Y[maxk];
 29 int par[3*maxk],rankh[3*maxk];
 30 
 31 void init(int n)
 32 {
 33     for(int i=0;i<n;i++)
 34     {
 35         par[i]=i;
 36         rankh[i]=0;
 37     }
 38 }
 39 int find(int x)
 40 {
 41     if (par[x]==x)
 42     {
 43         return x;
 44     }
 45     else return par[x]=find(par[x]);
 46 }
 47 
 48 void unite(int x,int y)
 49 {
 50     x=find(x);
 51     y=find(y);
 52     if(x==y) return;
 53     
 54     if(rankh[x]<rankh[y])
 55     {
 56         par[x]=y;
 57     }
 58     else
 59     {
 60         par[y]=x;
 61         if(rankh[x]==rankh[y]) rankh[x]++;
 62     }
 63 }
 64 
 65 bool same(int x,int y)
 66 {
 67     return find(x)==find(y);
 68 }
 69 
 70 int main()
 71 {
 72     //freopen("Users/apple/Desktop/携程1/携程1.in","r",stdin);
 73     //freopen("Users/apple/Desktop/携程1/携程1.out","w",stdout);
 74     int T;
 75     scanf("%d",&T);
 76     while (T--) {
 77         
 78     scanf("%d%d",&N,&K);
 79     init(3*N);
 80     for(int i=0;i<K;i++)
 81     {
 82         scanf("%d %d %d",&D[i],&X[i],&Y[i]);
 83     }
 84     
 85     int ans=0;
 86     for(int i=0;i<K;i++)
 87     {
 88         int t=D[i];
 89         int x=X[i]-1,y=Y[i]-1;
 90         
 91         if(x<0||N<=x||y<0||N<=y)
 92         {
 93             ans++;
 94             continue;
 95         }
 96         if(t==1)
 97         {
 98             if(same(x,y+N)||same(x,y+2*N))
 99             {
100                 ans++;
101             }
102             else
103             {
104                 unite(x,y);
105                 unite(x+N,y+N);
106                 unite(x+2*N,y+2*N);
107             }
108         }
109         else
110         {
111             if (same(x,y)||same(x,y+2*N))
112                 ans++;
113             else
114             {
115                 unite(x,y+N);
116                 unite(x+N,y+2*N);
117                 unite(x+2*N,y);
118             }
119         }
120     }
121     
122     printf("%d
",ans);
123     }
124     return 0;
125 }

1001

1002： dp[i][j] 表示第一条边为i, 第二条边的长度为 j 是否可行。然后对所有可行的三条边的组合求最大三角形面积即可。

三角形面积：海伦公式

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 
 8 using namespace std;
 9 
10 const int INF = 2000;
11 const int MAXL = 2000;
12 const int MAXN = 50;
13 
14 int n;
15 int a[MAXN];
16 int ans;
17 bool dp[MAXL][MAXL];
18 
19 int my_abs(int x) {
20     return x > 0 ? x : -x;
21 }
22 
23 double Area(double x, double y, double z) {
24     double p = (x+y+z)/2;
25     return sqrt(p*(p-x)*(p-y)*(p-z));
26 }
27 
28 bool check(int x, int y, int z) {
29     int t[3] = {x, y, z};
30     sort(t, t+3);
31     if (t[0]+t[1] <= t[2]) return false;
32     return true;
33 }
34 
35 int main() {
36     #ifdef Phantom01
37         freopen("1002.txt", "r", stdin);
38     #endif // Phantom01
39 
40     while (scanf("%d", &n)!=EOF) {
41         if (0==n) break;
42 
43         int sum = 0;
44         for (int i = 0; i < n; i++) {
45             scanf("%d", &a[i]);
46             sum += a[i];
47         }
48         memset(dp, false, sizeof(dp));
49         dp[0][0] =true;
50 
51         for (int k = 0; k < n; k++)
52             for (int i = sum - a[k]; i >= 0; i--)
53                 for (int j = sum - a[k]; j >= 0; j--) {
54                     dp[i+a[k]][j] = dp[i][j] || dp[i+a[k]][j];
55                     dp[i][j+a[k]] = dp[i][j] || dp[i][j+a[k]];
56                 }
57         ans = -1;
58         for (int i = 1; i <= sum; i++)
59             for (int j = 1; j <= sum; j++) if (dp[i][j]) {
60                 if (check(i, j, sum-i-j))
61                     ans = max((int)(Area(i, j, sum-i-j)*100), ans);
62             }
63         printf("%d
", ans);
64     }
65 
66     return 0;
67 }

1002

1003：二维线段树可做，不过因为数据范围比较小，逆序枚举所以矩形，看该点最后落在哪个矩形中。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 const int MAXN = 1050;
 8 
 9 int x[MAXN*2], y[MAXN*2];
10 int x1[MAXN], x2[MAXN], y1[MAXN], y2[MAXN], R[MAXN], G[MAXN], B[MAXN];
11 int n, m;
12 int cntx, cnty;
13 
14 bool check(int px, int py, int k) {
15     if (x1[k]<=px&&px<=x2[k] && y1[k]<=py&&py<=y2[k])
16         return true;
17     return false;
18 }
19 
20 int main() {
21     #ifdef Phantom01
22         freopen("1003.txt", "r", stdin);
23     #endif // Phantom01
24 
25     while (scanf("%d%d", &n, &m)!=EOF) {
26         if (0==n&&0==m) break;
27         cntx = cnty = 0;
28         for (int i = 0 ; i < n; i++) {
29             scanf("%d%d%d%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i], &R[i], &G[i], &B[i]);
30         }
31         for (int i = 0; i < m; i++) {
32             int px, py;
33             bool flag = false;
34             scanf("%d%d", &px, &py);
35             for (int j = n-1; j >= 0; j--)
36                     if (check(px, py, j)) {
37                 flag = true;
38                 printf("%d %d %d
", R[j], G[j], B[j]);
39                 break;
40             }
41             if (!flag) puts("255 255 255");
42         }
43     }
44 
45     return 0;
46 }

1003

1004：可以证明，只有对称的时候后手能赢

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
    int n, i;
    int a[12];
    while(scanf("%d", &n), n) {
        for(i = 0; i < n; ++i) scanf("%d", a+i);
        sort(a, a+n);
        int cnt = 1;
        bool flag = 0;
        for(i = 1; i < n; ++i) {
            if(a[i] == a[i-1]) cnt++;
            else {
                if(cnt&1) {
                    flag = 1;
                    break;
                }
                else cnt = 1;
            }
        }
        if(!flag) puts("Lose");
        else puts("Win");
    }
    return 0;
}

1004