A. Bachgold Problem
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Bachgold problem is very easy to formulate. Given a positive integer n represent it as a sum of maximum possible number of prime numbers. One can prove that such representation exists for any integer greater than 1.
Recall that integer k is called prime if it is greater than 1 and has exactly two positive integer divisors — 1 and k.
Input
The only line of the input contains a single integer n (2?≤?n?≤?100?000).
Output
The first line of the output contains a single integer k — maximum possible number of primes in representation.
The second line should contain k primes with their sum equal to n. You can print them in any order. If there are several optimal solution, print any of them.
Examples
input
5
output
2
2 3
input
6
output
3
2 2 2

題意：給一個(gè)數(shù)n，要求最多的素?cái)?shù)個(gè)數(shù)，使得這些素?cái)?shù)之和等于n.
比如5 = 2 + 3（數(shù)字可以重復(fù)）。
要想素?cái)?shù)個(gè)數(shù)最多，每個(gè)素?cái)?shù)的值就應(yīng)該越小，最小的素?cái)?shù)是2，其次是3.
我們發(fā)現(xiàn)所有的偶數(shù)都是2的倍數(shù)，因此所有的偶數(shù)都可以寫為數(shù)個(gè)2相加的形式。大于1的奇數(shù)在減掉一個(gè)3之后都會(huì)變成偶數(shù)。
因此，我們可以先判定這個(gè)數(shù)的奇偶性，再對(duì)其進(jìn)行處理。

官方題解：

We need represent integer number N (1?<?N) as a sum of maximum possible number of prime numbers, they don’t have to be different.
If N is even number, we can represent it as sum of only 2 - minimal prime number. It is minimal prime number, so number of primes in sum is maximal in this case.
If N is odd number, we can use representing of N?-?1 as sum with only 2 and replace last summand from 2 to 3.
Using of any prime P?>?3 as summand is not optimal, because it can be replaced by more than one 2 and 3.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 100000+5;

int n;
vector<int> ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    int k = 0;
    ans.clear();
    if (n % 2 == 1) {//n是奇數(shù);
        n -= 3;
        ++k;
        ans.push_back(3);
    }

    while (n) {
        n -= 2;
        ++k;
        ans.push_back(2);
    }

    cout << k << "\n";
    int cnt = 0;
    for (auto const &elem : ans) {
        if (cnt > 0) cout << " ";
        cout << elem;
        ++cnt;
    }

    cout << endl;
    return 0;
}

B. Parallelogram is Back
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Long time ago Alex created an interesting problem about parallelogram. The input data for this problem contained four integer points on the Cartesian plane, that defined the set of vertices of some non-degenerate (positive area) parallelogram. Points not necessary were given in the order of clockwise or counterclockwise traversal.
Alex had very nice test for this problem, but is somehow happened that the last line of the input was lost and now he has only three out of four points of the original parallelogram. He remembers that test was so good that he asks you to restore it given only these three points.
Input
The input consists of three lines, each containing a pair of integer coordinates xi and yi (?-?1000?≤?xi,?yi?≤?1000). It's guaranteed that these three points do not lie on the same line and no two of them coincide.
Output
First print integer k — the number of ways to add one new integer point such that the obtained set defines some parallelogram of positive area. There is no requirement for the points to be arranged in any special order (like traversal), they just define the set of vertices.
Then print k lines, each containing a pair of integer — possible coordinates of the fourth point.
Example
input
0 0
1 0
0 1
output
3
1 -1
-1 1
1 1
Note
If you need clarification of what parallelogram is, please check Wikipedia page:
https://en.wikipedia.org/wiki/Parallelogram

題意：已知一個(gè)平行四邊形三個(gè)頂點(diǎn)的坐標(biāo)，求第四個(gè)頂點(diǎn)有多少種可能性且每種可能性的坐標(biāo)。

這是從網(wǎng)上搜到的關(guān)于此題的一種做法：

總結(jié)求平行四邊形第四個(gè)頂點(diǎn)坐標(biāo)的定理
任意兩個(gè)頂點(diǎn)橫坐標(biāo)之和減去第三個(gè)頂點(diǎn)橫坐標(biāo)的差就是第四個(gè)頂點(diǎn)的橫坐標(biāo)；
任意兩個(gè)頂點(diǎn)縱坐標(biāo)之和減去第三個(gè)頂點(diǎn)縱坐標(biāo)的差就是第四個(gè)頂點(diǎn)的縱坐標(biāo)。
符合要求的點(diǎn)共有3個(gè)。

官方題解：

Denote the input points as A, B, C, and the point we need to find as D.
Consider the case when the segments AD and BC are the diagonals of parallelogram. Vector AD is equal to the sum of two vectors AB + BD = AC + CD. As in the parallelogram the opposite sides are equal and parallel, BD = AC, AB = CD, and we can conclude that AD = AB + AC. So, the coordinates of the point D can be calculated as A + AB + AC = (Ax?+?Bx?-?Ax?+?Cx?-?Ax,?Ay?+?By?-?Ay?+?Cy?-?Ay) = (Bx?+?Cx?-?Ax,?By?+?Cy?-?Ay).
The cases where the diagonals are BD and AC, CD and AB are processed in the same way.
Prove that all three given points are different. Let's suppose it's wrong. Without losing of generality suppose that the points got in cases AD and BD are equal.
Consider the system of two equations for the equality of these points:
Bx?+?Cx?-?Ax?=?Ax?+?Cx?-?Bx
By?+?Cy?-?Ay?=?Ay?+?Cy?-?By
We can see that in can be simplified as
Ax?=?Bx
Ay?=?By
And we got a contradiction, as all the points A, B, C are distinct.

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

struct node {
    int x, y;
} a[4];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    for (int i = 0;i < 3;++i) {
        cin >> a[i].x >> a[i].y;
    }

    cout << 3 << "\n";

    int ansx1 = a[0].x + a[1].x - a[2].x;
    int ansy1 = a[0].y + a[1].y - a[2].y;

    int ansx2 = a[1].x + a[2].x - a[0].x;
    int ansy2 = a[1].y + a[2].y - a[0].y;

    int ansx3 = a[0].x + a[2].x - a[1].x;
    int ansy3 = a[0].y + a[2].y - a[1].y;

    cout << ansx1 << " " << ansy1 << "\n";
    cout << ansx2 << " " << ansy2 << "\n";
    cout << ansx3 << " " << ansy3 << endl;  
    return 0;
}

C. Voting
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
There are n employees in Alternative Cake Manufacturing (ACM). They are now voting on some very important question and the leading world media are trying to predict the outcome of the vote.
Each of the employees belongs to one of two fractions: depublicans or remocrats, and these two fractions have opposite opinions on what should be the outcome of the vote. The voting procedure is rather complicated:
Each of n employees makes a statement. They make statements one by one starting from employees 1 and finishing with employee n. If at the moment when it's time for the i-th employee to make a statement he no longer has the right to vote, he just skips his turn (and no longer takes part in this voting).
When employee makes a statement, he can do nothing or declare that one of the other employees no longer has a right to vote. It's allowed to deny from voting people who already made the statement or people who are only waiting to do so. If someone is denied from voting he no longer participates in the voting till the very end.
When all employees are done with their statements, the procedure repeats: again, each employees starting from 1 and finishing with n who are still eligible to vote make their statements.
The process repeats until there is only one employee eligible to vote remaining and he determines the outcome of the whole voting. Of course, he votes for the decision suitable for his fraction.
You know the order employees are going to vote and that they behave optimal (and they also know the order and who belongs to which fraction). Predict the outcome of the vote.
Input
The first line of the input contains a single integer n (1?≤?n?≤?200?000) — the number of employees.
The next line contains n characters. The i-th character is 'D' if the i-th employee is from depublicans fraction or 'R' if he is from remocrats.
Output
Print 'D' if the outcome of the vote will be suitable for depublicans and 'R' if remocrats will win.
Examples
input
5
DDRRR
output
D
input
6
DDRRRR
output
R
Note
Consider one of the voting scenarios for the first sample:
Employee 1 denies employee 5 to vote.
Employee 2 denies employee 3 to vote.
Employee 3 has no right to vote and skips his turn (he was denied by employee 2).
Employee 4 denies employee 2 to vote.
Employee 5 has no right to vote and skips his turn (he was denied by employee 1).
Employee 1 denies employee 4.
Only employee 1 now has the right to vote so the voting ends with the victory of depublicans.

題意：有兩個(gè)派別的人要對(duì)某事進(jìn)行選舉，'D'代表這個(gè)人屬于D派別，'R'代表這個(gè)人屬于R派別。每個(gè)人都按順序上臺(tái)。某個(gè)人上臺(tái)后可以宣布底下某一個(gè)人無權(quán)參加選舉，之后輪到那個(gè)人時(shí)就只能跳過；也可以什么都不做。問最后哪個(gè)派別的人會(huì)獲勝（另一個(gè)派別沒有人有權(quán)利參加選舉）。

由于是按順序進(jìn)行的，所以靠前的人有優(yōu)勢(shì)決定別人是否有選舉的權(quán)利。每個(gè)人都希望自己的派別最終獲勝，肯定會(huì)讓對(duì)方派別的某個(gè)人沒有選舉權(quán)利，少掉一個(gè)對(duì)手。但是這道題要考慮最優(yōu)的情況。
比如：DRDR，如果第一個(gè)D選擇讓最后一個(gè)R沒有選舉權(quán)利，那么第一個(gè)R可以讓它之后的D沒有選舉權(quán)利，因此最后就只剩一個(gè)D。
但如果第一個(gè)D讓它之后的R沒有選舉權(quán)利，那么之后的D就可以得到保護(hù)，并且可以再讓它之后的R沒有選舉權(quán)利，從而又增加了一次讓對(duì)手少掉一人的機(jī)會(huì)。
因此這道題的方法就是，當(dāng)輪到某人時(shí)讓它之后最靠近它的對(duì)手失去選舉權(quán)利。
可以用兩個(gè)隊(duì)列模擬D和R派別人數(shù)的變化。

官方題解：

We will emulate the process with two queues. Let’s store in the first queue the moments of time when D-people will vote, and in the second queue - the moments of time of R-people. For every man where will be only one element in the queue.
Now compare the first elements in the queues. The man whose moment of time is less votes first. It’s obvious that it’s always profitable to vote against the first opponent. So we will remove the first element from the opponent’s queue, and move ourselves to the back of our queue, increasing the current time by n - next time this man will vote after n turns.
When one of the queues becomes empty, the corresponding party loses.

#include <iostream>
#include <cstring>
#include <vector>
#include <string>
#include <queue>
using namespace std;

queue<int> qd;
queue<int> qr;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    string str;
    cin >> str;

    for (int i = 0;i < str.length();++i) {
        if (str[i] == 'D') qd.push(i);
        else qr.push(i);
    }

    int i = 0;
    while (!qd.empty() && !qr.empty()) {
        int fd = qd.front();
        int fr = qr.front();

        if (fd < fr) {//小的先做決策;
            qr.pop();//對(duì)方下一個(gè)被淘汰;
            qd.pop();//等待下一輪;
            qd.push(fd+n);
        }
        else {
            qd.pop();
            qr.pop();
            qr.push(fr+n);
        }
    }

    if (!qd.empty()) cout << 'D' << endl;
    else cout << 'R' << endl;
    return 0;
}

D. Leaving Auction
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
There are n people taking part in auction today. The rules of auction are classical. There were n bids made, though it's not guaranteed they were from different people. It might happen that some people made no bids at all.
Each bid is define by two integers (ai,?bi), where ai is the index of the person, who made this bid and bi is its size. Bids are given in chronological order, meaning bi?<?bi?+?1 for all i?<?n. Moreover, participant never makes two bids in a row (no one updates his own bid), i.e. ai?≠?ai?+?1 for all i?<?n.
Now you are curious with the following question: who (and which bid) will win the auction if some participants were absent? Consider that if someone was absent, all his bids are just removed and no new bids are added.
Note, that if during this imaginary exclusion of some participants it happens that some of the remaining participants makes a bid twice (or more times) in a row, only first of these bids is counted. For better understanding take a look at the samples.
You have several questions in your mind, compute the answer for each of them.
Input
The first line of the input contains an integer n (1?≤?n?≤?200?000) — the number of participants and bids.
Each of the following n lines contains two integers ai and bi (1?≤?ai?≤?n,?1?≤?bi?≤?10^9,?bi?<?bi?+?1) — the number of participant who made the i-th bid and the size of this bid.
Next line contains an integer q (1?≤?q?≤?200?000) — the number of question you have in mind.
Each of next q lines contains an integer k (1?≤?k?≤?n), followed by k integers lj (1?≤?lj?≤?n) — the number of people who are not coming in this question and their indices. It is guarenteed that lj values are different for a single question.
It's guaranteed that the sum of k over all question won't exceed 200?000.
Output
For each question print two integer — the index of the winner and the size of the winning bid. If there is no winner (there are no remaining bids at all), print two zeroes.
Examples
input
6
1 10
2 100
3 1000
1 10000
2 100000
3 1000000
3
1 3
2 2 3
2 1 2
output
2 100000
1 10
3 1000
input
3
1 10
2 100
1 1000
2
2 1 2
2 2 3
output
0 0
1 10
Note
Consider the first sample:
In the first question participant number 3 is absent so the sequence of bids looks as follows:
1 10
2 100
1 10?000
2 100?000
Participant number 2 wins with the bid 100?000.
In the second question participants 2 and 3 are absent, so the sequence of bids looks:
1 10
1 10?000
The winner is, of course, participant number 1 but the winning bid is 10 instead of 10?000 as no one will ever increase his own bid (in this problem).
In the third question participants 1 and 2 are absent and the sequence is:
3 1?000
3 1?000?000
The winner is participant 3 with the bid 1?000.

題意：有數(shù)個(gè)人（人數(shù)<=n）在拍賣場(chǎng)競(jìng)價(jià)，一共有n次喊價(jià)（可能有些人沒有參與），每次給出喊價(jià)人的編號(hào)以及他/她給出的價(jià)錢（價(jià)格只能一次比一次高）。之后會(huì)有q次詢問，每次詢問給一個(gè)數(shù)字，表明有多少個(gè)人被除去，在剩余的人中求出是誰獲得了勝利，并求出獲勝的最小金額。

這道題有幾種情況：
最后所有人都被除去了，那么最終結(jié)果就是0 0.
最后只剩下一個(gè)人，這個(gè)人肯定就是勝利者，而他/她之前報(bào)的最小的金額就是最終的結(jié)果。
最后多于1個(gè)人，那么就要找到當(dāng)前最大金額的競(jìng)價(jià)人，將他/她之前的報(bào)價(jià)同第二大的最高報(bào)價(jià)作比較，找出剛剛大于此報(bào)價(jià)的最小價(jià)格。

官方題解：

For every man at the auction we will save two values: his maximum bid and the list of all his bids. Then save all men in the set sorted by the maximal bid.
Now, when the query comes, we will remove from the set all men who left the auction, then answer the query, and then add the men back. The total number of deletions and insertions will not exceed 200000.
How to answer the query. Now our set contains only men who has not left.
If the set is empty, the answer is 0 0. Otherwise, the maximal man in the set is the winner. Now we have to determine the winning bid. Let’s look at the second maximal man in the set.
If it doesn’t exist, the winner takes part solo and wins with his minimal bid.
Otherwise he should bid the minimal value that is greater than the maximal bid of the second man in the set. This is where we need a list of bids of the first maximal man. We can apply binary search and find the maximal bid of the second man there.

這道題開始我不太明白，后來看了別人的代碼后才稍稍理解。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
using namespace std;
const int N = 200000+5;

int n;
set<pair<int, int> > pos;//競(jìng)價(jià)人的編號(hào)和當(dāng)前該競(jìng)價(jià)人給出的最大競(jìng)價(jià)價(jià)格(排序);
vector<int> lst[N];//每個(gè)人的所有競(jìng)價(jià)價(jià)格(從小到大);
int del[N];//要去掉的競(jìng)價(jià)人的編號(hào);
int mx[N];//每個(gè)競(jìng)價(jià)人給出的最大競(jìng)價(jià)額;
bool vis[N];//當(dāng)前哪些編號(hào)的競(jìng)價(jià)人參與了競(jìng)價(jià), 有人可能沒參加;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    int a, b;
    for (int i = 1;i <= n;++i) {
        cin >> a >> b;
        lst[a].push_back(b);
        vis[a] = true;
        mx[a] = max(b, mx[a]);
    }

    for (int i = 1;i <= n;++i) {
        if (vis[i]) {
            pos.insert({mx[i], i});//價(jià)格在前, 之后set會(huì)自動(dòng)對(duì)價(jià)格排序;
        }
    }

    int q;
    cin >> q;
    for (int i = 1;i <= q;++i) {
        int num;//每次要去掉多少人;
        cin >> num;
        for (int j = 1;j <= num;++j) {
            cin >> del[j];
            if (vis[del[j]]) {
                pos.erase({mx[del[j]], del[j]});
            }
        }

        if (pos.size() == 0) {//全部被去掉了;
            cout << 0 << " " << 0 << endl;
        }
        else if (pos.size() == 1) {//僅剩一個(gè)人;
            cout << (pos.begin())->second << " " << lst[pos.begin()->second].at(0) << endl;//取最小值;
        }
        else {
            auto it1 = pos.end();
            auto it2 = pos.end();

            --it1;
            --it1;//第二大競(jìng)價(jià)人;
            --it2;//第一大競(jìng)價(jià)人;
            int tmpnum = it1->first;//第二大競(jìng)價(jià)人的價(jià)格;
            int tmppos = it2->second;//第一大競(jìng)價(jià)人的編號(hào);

            auto it = upper_bound(lst[tmppos].begin(), lst[tmppos].end(), tmpnum);//找出第一大競(jìng)價(jià)人所有報(bào)價(jià)里面剛好大于第二大競(jìng)價(jià)人的價(jià)格;
            cout << tmppos << " " << *it << endl;
        }

        for (int j = 1;j <= num;++j) {//數(shù)據(jù)還原;
            if (vis[del[j]]) {
                pos.insert({mx[del[j]], del[j]});
            }
        }
    }
    return 0;
}

還有一道還沒看，以后有時(shí)間的話在做一做。