NYIST_2013寒假ACM集训队练习赛（2）

た入场券 2022-09-20 11:20 143阅读 0赞

集训第二周周四，做出来了7道题目，题目非常水，还有几道没有A出来的也不难，完了花点时间水一下，a过的题目贴在这里。没有a的后面补上。

比赛链接：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=39441\#overview][http_acm.hust.edu.cn_vjudge_contest_view.action_cid_39441_overview] 密码：nyist

I - I

**Time Limit:**1000MS **Memory Limit:**32768KB **64bit IO Format:**%I64d & %I64u

Submit [Status][] [Practice][] [HDU 1242][]

Description

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N \* M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.  
  
Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.  
  
You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

Input

First line contains two integers stand for N and M.  
  
Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend.  
  
Process to the end of the file.

Output

For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."

Sample Input

7 8
    #.#####.
    #.a#..r.
    #..#x...
    ..#..#.#
    #...##..
    .#......
    ........

Sample Output

这是一道搜索题目，一眼就看出来，但是没有想到用优先队列wa了一次，因为他求得是一个最短的步数，优先队列来进行广搜bfs，不然会出现时间长的先到达

#include <cstdio>
    #include <queue>
    const int N = 300;
    using namespace std;
    int m,n;
    char map[N][N];
    struct Node
    {
        int x,y;
        int step;
        friend bool operator<(Node n1,Node n2)
        {
            return n1.step>n2.step;
        }
    };
    int dx[6]={0,0,1,-1};
    int dy[6]={1,-1,0,0};
    int Bfs(int sta,int stb,int ena,int enb)
    {
        priority_queue<Node> q;   
        Node tmd,tmp;
        tmd.x=sta,tmd.y=stb,tmd.step=0;
        q.push(tmd);
        while(!q.empty())
        {
            tmd=q.top();q.pop();   //初始片段搜索结束条件的地方
            if(tmd.x==ena&&tmd.y==enb)
                return tmd.step;
            for(int i=0;i<4;i++)
            {
                tmp.x=tmd.x+dx[i];
                tmp.y=tmd.y+dy[i];
                if(map[tmp.x][tmp.y]=='x')
                    tmp.step=tmd.step+2;
                else
                    tmp.step=tmd.step+1;
                if(map[tmp.x][tmp.y]!='#'&&tmp.x>=0 &&tmp.y>=0 &&tmp.x<m&&tmp.y<n)
                { //注意上面的搜索条件，是！=‘#’ 错在了这里
                    q.push(tmp);
                    map[tmp.x][tmp.y]='#';
                }
            }
        }
        return -1;
    }
    int main()
    {
        while(~scanf("%d%d",&m,&n))
        {
            int sta,stb,ena,enb;
            getchar();
            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    scanf("%c",&map[i][j]);
                    if(map[i][j]=='a')
                    {
                        sta=i,stb=j;
                    }
                    if(map[i][j]=='r')
                    {
                        ena=i,enb=j;
                    }
                }
                getchar();
            }
            int ans=Bfs(sta,stb,ena,enb);
            if(ans==-1)
                printf("Poor ANGEL has to stay in the prison all his life.\n");
            else
                printf("%d\n",ans);
    
        }
        return 0;
    }

H - H

**Time Limit:**3000MS **Memory Limit:**32768KB **64bit IO Format:**%I64d & %I64u

Submit [Status][Status 1] [Practice][Practice 1] [HDU 1496][]

Description

Consider equations having the following form:  
  
a\*x1^2+b\*x2^2+c\*x3^2+d\*x4^2=0  
a, b, c, d are integers from the interval \[-50,50\] and any of them cannot be 0.  
  
It is consider a solution a system ( x1,x2,x3,x4 ) that verifies the equation, xi is an integer from \[-100,100\] and xi != 0, any i ∈\{1,2,3,4\}.  
  
Determine how many solutions satisfy the given equation.

Input

The input consists of several test cases. Each test case consists of a single line containing the 4 coefficients a, b, c, d, separated by one or more blanks.  
End of file.

Output

For each test case, output a single line containing the number of the solutions.

Sample Input

1 2 3 -4
    1 1 1 1

Sample Output

39088
    0

哈希的思想。

#include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    int v[3001000];
    int main()
    {
        int a,b,c,d;
        while(~scanf("%d%d%d%d",&a,&b,&c,&d))
        {
            if(a>0&&b>0&&c>0&&d>0||a<0&&b<0&&c<0&&d<0)
            {
                printf("0\n");continue;
            }
            int ans=0;
            memset(v,0,sizeof(v));
            for(int i=1;i<=100;i++)
            {
                for(int j=1;j<=100;j++)
                    v[a*i*i+b*j*j+1000000]++;
            }
            for(int i=1;i<=100;i++)
            {
                for(int j=1;j<=100;j++)
                    ans+=v[-c*i*i-d*j*j+1000000];
            }
            printf("%d\n",ans*16);
        }
        return 0;
    }

K - K

**Time Limit:**2000MS **Memory Limit:**262144KB **64bit IO Format:**%I64d & %I64u

Submit [Status][Status 2] [Practice][Practice 2] [CodeForces 278C][]

Description

The "BerCorp" company has got *n* employees. These employees can use *m* approved official languages for the formal correspondence. The languages are numbered with integers from 1 to *m*. For each employee we have the list of languages, which he knows. This list could be empty, i. e. an employee may know no official languages. But the employees are willing to learn any number of official languages, as long as the company pays their lessons. A study course in one language for one employee costs 1 berdollar.

Find the minimum sum of money the company needs to spend so as any employee could correspond to any other one (their correspondence can be indirect, i. e. other employees can help out translating).

Input

The first line contains two integers *n* and *m* (2 ≤ *n*, *m* ≤ 100) — the number of employees and the number of languages.

Then *n* lines follow — each employee's language list. At the beginning of the *i*\-th line is integer *k**i* (0 ≤ *k**i* ≤ *m*) — the number of languages the *i*\-th employee knows. Next, the *i*\-th line contains *k**i* integers — *a**ij* (1 ≤ *a**ij* ≤ *m*) — the identifiers of languages the *i*\-th employee knows. It is guaranteed that all the identifiers in one list are distinct. Note that an employee may know zero languages.

The numbers in the lines are separated by single spaces.

Output

Print a single integer — the minimum amount of money to pay so that in the end every employee could write a letter to every other one (other employees can help out translating).

Sample Input

Input

5 5
    1 2
    2 2 3
    2 3 4
    2 4 5
    1 5

Output

Input

8 7
    0
    3 1 2 3
    1 1
    2 5 4
    2 6 7
    1 3
    2 7 4
    1 1

Output

Input

2 2
    1 2
    0

Output

并查集，有一组比较特殊的数据，就是所有的都为0.那么说出的是n

#include <cstdio>
    #include <cstring>
    int father[1200],rank[1200],sum;
    void makeset()
    {
        int i;
        for(i=0; i<1200; i++)
        {
            father[i]=i;
            rank[i]=1;
        }
    }
    int find(int x)
    {
        return father[x] != x ? father[x]=find(father[x]) : x;//状态压缩、
    }
    void Union(int x,int y)
    {
        x=find(x);
        y=find(y);
        if(x==y)
            return;
        if(rank[x]>rank[y])
        {
            father[y]=x;
            rank[x]+=rank[y];
        }
        else
        {
            father[x]=y;
            rank[y]+=rank[x];
        }
    }
    int k[1200];
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            makeset();int ans=0,count=0;
            memset(k,0,sizeof(k));
            for(int cas=0;cas<n;cas++)
            {
                int q,x,y;
                scanf("%d",&q);
                if(q==0)
                    count++;
                if(q>0)
                {
                    scanf("%d",&x);k[x]++;
                    for(int i=1;i<q;i++)
                    {
                        scanf("%d",&y);k[y]++;
                        Union(x,y);
                    }
                }
            }
            for(int i=1;i<=m;i++)
                if(k[i]==0)
                    ans++;
            for(int i=1;i<=m;i++)
            {
                if(father[i]==i)
                    count++;
            }
            //printf("%d %d\n",ans,m);
            if(ans==m)
            {
                printf("%d\n",n);continue;
            }
            printf("%d\n",count-ans-1);
        }
        return 0;
    }

A - A

**Time Limit:**500MS **Memory Limit:**32768KB **64bit IO Format:**%lld & %llu

Submit [Status][Status 3]

Description

Sometimes I feel angry to arrange contests, because I am too lazy. Today I am arranging a contest for AIUB students. So, I made a plan. While they will be busy with the contest, as a punishment I will cover their rooms with dusts. So, when they will be back, they will surely get angry, and it will cause them some pain.

So, at first, I will make up my mind, that means I will fix the amount of dusts for each student. This amount may not be same for all. Now you are given the amount of dust unit for each student. You have to help me finding the total dust unit I have to collect to cause them pain.

But there is a problem, my random function which generates dust units for students has a bug, it sometimes returns negative numbers. If a student gets negative number, I think he is lucky, so I will not cause him any pain with dusts.

Input

Input starts with an integer **T (≤ 100)**, denoting the number of test cases.

Each case starts with a blank line. The next line contains an integer **N (1 ≤ N ≤ 1000)**, means that there are **N** students. The next line will contain **N** integers separated by spaces which denote the dust unit for all students. The dust unit for any student will not contain more than two digits.

Output

For each case print the case number and the total required dust units.

Sample Input

1 5 10

1 99

Sample Output

Case 1: 16

Case 2: 100

#include <cstdio>
    #include <cstring>
    #include <string>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        int T,n;
        scanf("%d",&T);
        for(int cas=1;cas<=T;cas++)
        {
            int ans=0,x;
            scanf("%d",&n);
            for(int i=0;i<n;i++)
            {
                scanf("%d",&x);
                if(x>=0)
                    ans+=x;
            }
            printf("Case %d: %d\n",cas,ans);
        }
        return 0;
    }

D - D

**Time Limit:**2000MS **Memory Limit:**262144KB **64bit IO Format:**%I64d & %I64u

Submit [Status][Status 4] [Practice][Practice 3] [CodeForces 110B][]

Description

Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya recently learned to determine whether a string of lowercase Latin letters is lucky. For each individual letter all its positions in the string are written out in the increasing order. This results in 26 lists of numbers; some of them can be empty. A string is considered lucky if and only if in each list the absolute difference of any two adjacent numbers is a lucky number.

For example, let's consider string "zbcdzefdzc". The lists of positions of equal letters are:

<ul< ul="">

*  b: 2
 *  c: 3, 10
 *  d: 4, 8
 *  e: 6
 *  f: 7
 *  z: 1, 5, 9
 *  Lists of positions of letters a, g, h, ..., y are empty.
    
    This string is lucky as all differences are lucky numbers. For letters z: 5 - 1 = 4, 9 - 5 = 4, for letters c: 10 - 3 = 7, for letters d: 8 - 4 = 4.
    
    Note that if some letter occurs only once in a string, it doesn't influence the string's luckiness after building the lists of positions of equal letters. The string where all the letters are distinct is considered lucky.
    
    Find the lexicographically minimal lucky string whose length equals *n*.

Input

The single line contains a positive integer *n* (1 ≤ *n* ≤ 105) — the length of the sought string.

Output

Print on the single line the lexicographically minimal lucky string whose length equals *n*.

Sample Input

Input

Output

abcda

Input

Output

abc

Hint

The lexical comparison of strings is performed by the < operator in modern programming languages. String *a* is lexicographically less than string*b* if exists such *i* (1 ≤ *i* ≤ *n*), that *a**i* < *b**i*, and for any *j* (1 ≤ *j* < *i*) *a**j* = *b**j*.

#include <cstdio>
    #include <cstring>
    #include <string>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            string s;
            for(int i=1;i<=n;i++)
            {
                if(i%4==1)
                    printf("a");
                else if(i%4==2)
                    printf("b");
                else if(i%4==3)
                    printf("c");
                else
                    printf("d");
            }
            printf("\n");
        }
        return 0;
    }

B - B

**Time Limit:**500MS **Memory Limit:**32768KB **64bit IO Format:**%lld & %llu

Submit [Status][Status 5] [Practice][Practice 4] [LightOJ 1053][]

Description

You are building a house. You'd prefer if all the walls have a precise right angle relative to the ground, but you have no device to measure angles. A friend says he has a great idea how you could ensure that all walls are upright: All you need to do is step away a few feet from the wall, measure how far away you are from the wall, measure the height of the wall, and the distance from the upper edge of the wall to where you stand. You friend tells you to do these measurements for all walls, then he'll tell you how to proceed. Sadly, just as you are done, a timber falls on your friend, and an ambulance brings him to the hospital. This is too bad, because now you have to figure out what to do with your measurements yourself.

Given the three sides of a triangle, determine if the triangle is a right triangle, i.e. if one of the triangle's angles is **90** degrees.

Input

Input starts with an integer **T (≤ 200)**, denoting the number of test cases.

Each test case consists of three integers **1 ≤ a, b, c ≤ 40000** separated by a space. The three integers are the lengths of the sides of a triangle.

Output

For each case, print the case number and **"yes"** or **"no"** depending on whether it's a right angle or not.

Sample Input

36 77 85

40 55 69

Sample Output

Case 1: yes

Case 2: no

#include <cstdio>
    #include <algorithm>
    int a[5];
    int main()
    {
        int T;
        scanf("%d",&T);
        for(int i=1;i<=T;i++)
        {
            scanf("%d%d%d",&a[0],&a[1],&a[2]);
            std::sort(a,a+3);
            printf("Case %d: ",i);
            if(a[0]*a[0]+a[1]*a[1]==a[2]*a[2])
                printf("yes\n");
            else
                printf("no\n");
        }
    }

C - C

**Time Limit:**500MS **Memory Limit:**32768KB **64bit IO Format:**%lld & %llu

Submit [Status][Status 6] [Practice][Practice 5] [LightOJ 1182][]

Description

Given an integer **n**, first we represent it in binary. Then we count the number of ones. We say **n** has odd parity if the number of one's is odd. Otherwise we say **n** has even parity. **21 = (10101)2** has odd parity since the number of one's is **3**. **6 = (110)2** has even parity.

Now you are given **n**, we have to say whether **n** has even or odd parity.

Input

Input starts with an integer **T (≤ 1000)**, denoting the number of test cases.

Each case contains an integer **n (1 ≤ n < 231)**.

Output

For each case, print the case number and **'odd'** if **n** has odd parity, otherwise print **'even'**.

Sample Input

Sample Output

Case 1: odd

Case 2: even

#include <cstdio>
    #include <algorithm>
    int a[5];
    int main()
    {
        int T;
        scanf("%d",&T);
        for(int i=1;i<=T;i++)
        {
            int n,ans=0;
            scanf("%d",&n);
            while(n)
            {
                if(n%2)
                    ans++;
                n/=2;
            }
            if(ans%2)
                printf("Case %d: odd\n",i);
            else
                printf("Case %d: even\n",i);
    
        }
    }

[http_acm.hust.edu.cn_vjudge_contest_view.action_cid_39441_overview]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=39441#overview
[Status]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=39441#status//I/0
[Practice]: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21153
[HDU 1242]: http://acm.hdu.edu.cn/showproblem.php?pid=1242
[Status 1]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=39441#status//H/0
[Practice 1]: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18464
[HDU 1496]: http://acm.hdu.edu.cn/showproblem.php?pid=1496
[Status 2]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=39441#status//K/0
[Practice 2]: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=37258
[CodeForces 278C]: http://codeforces.com/problemset/problem/278/C
[Status 3]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=39441#status//A/0
[Status 4]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=39441#status//D/0
[Practice 3]: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=22988
[CodeForces 110B]: http://codeforces.com/problemset/problem/110/B
[Status 5]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=39441#status//B/0
[Practice 4]: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26770
[LightOJ 1053]: http://www.lightoj.com/volume_showproblem.php?problem=1053
[Status 6]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=39441#status//C/0
[Practice 5]: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26895
[LightOJ 1182]: http://lightoj.com/volume_showproblem.php?problem=1182