黑马程序员技术交流社区

标题: 【上海校区】Codeforces 939A题，B题 [打印本页]

---

作者: 梦缠绕的时候    时间: 2019-11-13 13:37
标题: 【上海校区】Codeforces 939A题，B题
A题

A. Love Triangle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
As you could know there are no male planes nor female planes. However, each plane on Earth likes some other plane. There are n planes on Earth, numbered from 1 to n, and the plane with number i likes the plane with number fi, where 1 ≤ fi ≤ n and fi ≠ i.

We call a love triangle a situation in which plane A likes plane B, plane B likes plane C and plane C likes plane A. Find out if there is any love triangle on Earth.

Input
The first line contains a single integer n (2 ≤ n ≤ 5000) — the number of planes.

The second line contains n integers f1, f2, ..., fn (1 ≤ fi ≤ n, fi ≠ i), meaning that the i-th plane likes the fi-th.

Output
Output «YES» if there is a love triangle consisting of planes on Earth. Otherwise, output «NO».

You can output any letter in lower case or in upper case.

Examples
input
Copy
5
2 4 5 1 3
output
Copy
YES
input
Copy
5
5 5 5 5 1
output
Copy
NO
Note
In first example plane 2 likes plane 4, plane 4 likes plane 1, plane 1 likes plane 2 and that is a love triangle.

In second example there are no love triangles.

思路：题目大意就是1号喜欢2号，2号喜欢3号，3号喜欢1号，如何去表示呢？用数组来下标来表示，例如a[1]=2，表示1号喜欢2号，同理a[2] = 3,表示2号喜欢3号，a[3] = 1,表示3号喜欢1号。现在的遇到的困难是，如何去表示这三者的关系。请先看AC代码：

复制代码
#include<iostream>
using namespace std;
int n,a[5001];

int main()
{
    while(cin >> n)
    {
        int flag = 0;//设一个标记
        for(int i = 1;i <= n;i++)
            cin >> a;
        for(int i = 1;i <= n;i++)
            if(a[a[a]] == i)//只要有满足条件的马上跳出循环，立刻结束
                flag = 1;
        if(flag == 1)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}
复制代码
a[1]=2,a[2]=3,a[3]=1，这是一组满足条件的三角恋关系，我们拿这个例子来分析。a[1]=2说明1号喜欢2号，我们马上判断2号喜欢的是谁,我们想要知道2号喜欢谁，把a[1]=2（1号喜欢2号）中的2号放入数组a中，即a[a[1]]，因为a[1]=2，a[a[1]]等价于a[2]，这表示的是2号喜欢的是谁，同理，a[2]=3，如何表示3号喜欢谁呢?再把a[a[1]]放入数组a中，即a[a[a[1]]]（即为3号喜欢的是谁），判断3号是否喜欢1号，如果是，则三者满足三角恋的条件，否则不满足，继续判断。好好理解下，理解后就不难了。

B题

题目链接：http://codeforces.com/problemset/problem/939/B

B. Hamster Farm
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Dima has a hamsters farm. Soon N hamsters will grow up on it and Dima will sell them in a city nearby.

Hamsters should be transported in boxes. If some box is not completely full, the hamsters in it are bored, that's why each box should be completely full with hamsters.

Dima can buy boxes at a factory. The factory produces boxes of K kinds, boxes of the i-th kind can contain in themselves ai hamsters. Dima can buy any amount of boxes, but he should buy boxes of only one kind to get a wholesale discount.

Of course, Dima would buy boxes in such a way that each box can be completely filled with hamsters and transported to the city. If there is no place for some hamsters, Dima will leave them on the farm.

Find out how many boxes and of which type should Dima buy to transport maximum number of hamsters.

Input
The first line contains two integers N and K (0 ≤ N ≤ 1018, 1 ≤ K ≤ 105) — the number of hamsters that will grow up on Dima's farm and the number of types of boxes that the factory produces.

The second line contains K integers a1, a2, ..., aK (1 ≤ ai ≤ 1018 for all i) — the capacities of boxes.

Output
Output two integers: the type of boxes that Dima should buy and the number of boxes of that type Dima should buy. Types of boxes are numbered from 1 to K in the order they are given in input.

If there are many correct answers, output any of them.

Examples
input
Copy
19 3
5 4 10
output
Copy
2 4
input
Copy
28 3
5 6 30
output
Copy
1 5
思路：题目给的数据范围很大很大，注意用long long！！！判断总仓鼠总数除以某个盒子的容量取余（即%的就行），能被整除最好，说明这个盒子刚好能装满所有的仓鼠。这里要设置一个很大的数，比题目所给的盒子容量最大值还要大1（我设为temp）
然后依次判断总仓鼠数对盒子容量取模的值会不会大于temp，会的话执行接下来的操作，不会的话则跳过，具体在代码中解释。
AC代码
复制代码
#include<iostream>
using namespace std;
long long n,k;//注意用long long！！！

int main()
{   
    while(cin >> n >> k)
    {
        long long temp = 1e18 + 1,flag = 0,heshu = 0,x;//long long！temp的初始值要设定好
        for(int i = 1;i <= k;i++)//从第一个盒子开始
        {
            cin >> x;
            if(temp > n % x)//目的是取最小余数的那一项
            {
                temp = n % x;//满足条件则不断更新临时变量temp的值，一直到余数temp最小为止
                flag = i;//用flag记录此时满足条件的是第几个盒子
                heshu = n / x;//记录所需要盒子的数目
            }
        }
        cout << flag << " " << heshu << endl;
    }
    return 0;
}
复制代码

---

作者: 梦缠绕的时候    时间: 2019-11-13 13:38
有任何问题欢迎在评论区留言

---

作者: 梦缠绕的时候    时间: 2019-11-13 13:38
或者添加学姐微信
DKA-2018

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2