CodingTrip-携程编程大赛(预赛第二场)

1001-剪刀石头布

Problem Description

现有M个人一起玩剪刀石头布,以1-M编号,每人出一种,出过不再改变,但是我们并不知道它到底是哪一种。 (其中石头赢剪刀,剪刀赢布,布赢石头,一样则平)
裁判用两种说法对这M个人所构成的输赢关系进行描述:
一:”1 A B”,表示第A个人和第B个人出的一样。
二:”2 A B”,表示第A个人赢第B个人。

裁判对M个人,用以上两种说法,连说N句话,其中有真的、也有假的。
一句话出现以下情况,就是假话,否则就是真话。
1) 该句话与之前的某些真话冲突;
2) 该句话中A或B比M大;
3) 该句话表示A赢A。

  • 点击题目阅读更多内容 请根据给定的M和N,输出假话数。
    其中(1 <= M <= 10,000),(0 <= N <= 10,000)

    Input

    第1行是一个自然数K,代表有K组数据。
    每组数据以一个空行分隔,其中每组数据的第1行是两个自然数M、N,以空格分开。
    每组数据的第2行至N+1行,每行是三个自然数X,A,B,三个数之间用空格分开,X(1或2)表示说法的种类。

    Output

    每组数据对应一行,每行有一个整数,代表假话数。

    Sample Input

    3
    43 11
    1 4 3
    2 3 3
    1 4 1
    1 4 4
    2 3 3
    1 2 2
    2 1 4
    1 1 1
    2 1 4
    2 3 4
    2 3 2
    66 9
    2 3 1
    2 4 4
    2 1 2
    2 4 3
    2 4 2
    2 2 3
    1 3 2
    1 2 1
    1 1 1
    6 7
    2 3 7
    2 1 2
    2 4 4
    1 2 1
    1 3 2
    1 2 3
    2 1 3

    Sample Output

    5
    4
    3

    题解:

    并查集,和poj上食物链是一样的,前两天刚看过。

    源代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    #include<stdio.h>
    #include<stdlib.h>
    #define MAX 200000
    int a[MAX],b[MAX],c[MAX];
    void init(int n)
    {

    for(int i=1; i<=n; i++)
    {
    a[i]=i;
    b[i]=0;
    c[i]=1;
    }
    }
    int findd(int x,int& w)
    {

    if(a[x]!=x)
    {
    a[x]=findd( a[x],w);
    b[x]=(b[x]+w)%3;
    w=b[x];
    }
    else w=0;
    return a[x];
    }

    int findx(int x)
    {

    int aa,w;
    if(x==a[x])
    return b[x];
    aa=findd(x,w);
    return (b[aa]+b[x])%3;
    }

    void suan(int x,int y,int d)
    {

    int aa,bb,w;
    aa=findd(x,w);
    bb=findd(y,w);
    if(aa==bb)return;
    if(c[aa]>=c[bb])
    {
    b[bb]=(((b[x]+d)%3-b[y]%3)+3)%3;
    c[aa]+=c[bb];
    a[bb]=aa;
    }
    else
    {
    b[aa]=((b[y]%3-(b[x]+d)%3)+3)%3;
    c[bb]+=c[aa];
    a[aa]=bb;
    }
    }

    int main()
    {

    int n,k,tx,ty,x,y,w,d,m,aa=0;
    scanf("%d",&k);
    while(k--)
    {
    aa=0;
    scanf("%d%d",&n,&m);
    init(n);
    while(m--)
    {
    scanf("%d%d%d",&d,&x,&y);
    if(x>n||y>n||(d==2&&x==y))
    {
    aa++;
    continue;
    }
    tx=findd(x,w);
    ty=findd(y,w);
    if(tx==ty)
    {
    tx=findx(x);
    ty=findx(y);
    if(d==1&&tx%3!=ty%3)aa++;
    else if(d==2&&(tx+1)%3!=ty)aa++;
    }
    else suan(x,y,d-1);
    }
    printf("%d\n",aa);
    }
    return 0;
    }

1002-携程员工运动会场地问题

Problem Description

携程每年要举行员工运动会,现在需要搭建三角形的场地给运动员们自由活动。
现在有N (3 <= N <= 40)个栅栏段(每个栅栏长度Li (1 <= Li <= 40)),必须刚好用掉所有的栅栏拼成一个最大面积的三角形活动区域,
求这个最大面积。

Input

  • 第一行: 整数 N ,表示有多少个栅栏
  • 第 2..N+1行: 共N 行, 每行中包括一个整数, 表示 一个栅栏的长度.( 多个栅栏的长度可以出现相同).
  • 第N+3行:第二组数据。

每组数据隔一空行,文件末尾以0结尾。

Output

每行输出一个截取后的整数,即最大面积乘以100后的整数。 如果无法构成,输出 -1。

Sample Input

5
1
1
3
3
4
5
12
37
1
4
3
0

Sample Output

692
-1

题解:

动态规划,记录能够构成的三边长(其实是两条边),然后判断可行的话用海伦公式算面积,取面积最大值。

源代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<stdio.h>
#include<math.h>
#include<string.h>
int d[1000][1000],i,j,k,l,h,m,n,a[50],sum,ans,now;
int main()
{


double s;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
sum=0;
ans=-1;
for(i=1; i<=n; i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
h=sum/2;
memset(d,0,sizeof(d));
d[0][0]=1;
for(i=1; i<+n; i++)
{
for(j=h; j>=0; j--)
{
for(k=j; k>=0; k--)
{
if(j>=a[i]&&d[j-a[i]][k]==1||k>=a[i]&&d[j][k-a[i]]==1)
d[j][k]=1;
}
}
}
for(i=h; i>=1; i--)
{
for(j=i; j>=1; j--)
{
if(d[i][j]==1)
{
k=sum-i-j;
if(i+j>k&&i+k>j&&j+k>i)
{
s=(i+j+k)*1.0/2;
now=(int)(sqrt(s*(s-i)*(s-j)*(s-k))*100);
if(now>ans)
ans=now;
}
}
}
}
printf("%d\n",ans);
}
return 0;
}

1003-位图像素的颜色

Problem Description

有一个在位图上画出矩形程序,一开始位图都被初始化为白色(RGB颜色表示为R=G=B=255)。该程序能够按照顺序绘出N个矩形。新绘制的矩形能够覆盖位图上原有的颜色。程序执行完毕后,需要查询M个点的颜色,输出这些点的RGB值。
每组数据都是在初始化后开始绘制。

Input

第一行包含参数N和M,分别表示矩形个数和需要查询的像素个数(1 ≤N, M≤ 1000 );
剩下N行每行包含7个参数x1, y1, x2, y2, r, g, b,表示绘制一个(x1,y1),(x2,y2)为顶点的矩形,填充颜色为RGB(r, g, b),其中x1≤x2, y1≤y2数据在整型范围;0≤ r,g,b ≤ 255;
最后M行分别包含参数X和Y,表示需要查询的像素位置。
如果某行N=M=0就表示输入结束。

Output

对于每个用例,按行输出查询的像素的RGB值,每行包含3个整数,分别表示RGB值。

Sample Input

1 2
0 0 2 3 127 196 200
1 2
3 0
2 3
8 16 32 64 0 255 128
8 48 32 64 255 0 0
12 47
13 48
14 64
0 0

Sample Output

127 196 200
255 255 255
0 255 128
255 0 0
255 0 0

题解:

简单的查找,有一年noip出过类似的题。我苦逼的把题意看错了,以为坐标给的是x,y和矩形的两边长,结果WA了两遍……

源代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int a[10010],b[10010],g[10010],k[10010],r[10010],gg[10010],bb[10010];
int main()
{

int i,j,l,m,n,flag;
int x,y;
while(scanf("%d%d",&n,&m)!=EOF)
{
for (i=1; i<=n; i++)
{
scanf("%d%d%d%d",&a[i],&b[i],&g[i],&k[i]);
scanf("%d%d%d",&r[i],&gg[i],&bb[i]);
}
for(i=1; i<=m; i++)
{
scanf("%d%d",&x,&y);
flag=0;
for (j=n; j>=1; j--)
{
if (g[j]>=x&&k[j]>=y&&a[j]<=x&&b[j]<=y)
{
printf("%d %d %d\n",r[j],gg[j],bb[j]);
flag=1;
break;
}
}
if(flag==0)
{
printf("255 255 255\n");
}
}
}
return 0;
}