Codeforces 939A題，B題（水題）

題目鏈接：http://codeforces.com/problemset/problem/939/A

A題

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.

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 «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.

5
2 4 5 1 3

YES

5
5 5 5 5 1

NO

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[i];
        for(int i = 1;i <= n;i++)
            if(a[a[a[i]]] == 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

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.

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 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.

19 3
5 4 10

2 4

28 3
5 6 30

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;
}