Codeforces Round #736 (Div. 2)(A,B,C题解)
A. Gregor and Cryptography
A. Gregor and Cryptography
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Gregor is learning about RSA cryptography, and although he doesn’t understand how RSA works, he is now fascinated with prime numbers and factoring them.
Gregor’s favorite prime number is P. Gregor wants to find two bases of P. Formally, Gregor is looking for two integers a and b which satisfy both of the following properties.
Pmoda=Pmodb, where xmody denotes the remainder when x is divided by y, and
2≤a<b≤P.
Help Gregor find two bases of his favorite prime number!
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤1000).
Each subsequent line contains the integer P (5≤P≤109), with P guaranteed to be prime.
Output
Your output should consist of t lines. Each line should consist of two integers a and b (2≤a<b≤P). If there are multiple possible solutions, print any.
Example
inputCopy
2
17
5
outputCopy
3 5
2 4
Note
The first query is P=17. a=3 and b=5 are valid bases in this case, because 17mod3=17mod5=2. There are other pairs which work as well.
In the second query, with P=5, the only solution is a=2 and b=4.
题意：
给你一个大于5的质数P，求满足Pmoda == Pmodb的两个大于等于2小于P的整数，如果存在多种结果，输出其中一种
思路：
首先我们知道大于5的质数P都是奇数，P对2取余为1，而P对P-1取余也为1
代码：
void solve()
{
int t;
scanf("%d",&t);
while(t--){
int p;
scanf("%d",&p);
cout<<"2 "<<p-1<<endl;
}
}
B.Gregor and the Pawn Game
B. Gregor and the Pawn Game
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
There is a chessboard of size n by n. The square in the i-th row from top and j-th column from the left is labelled (i,j).
Currently, Gregor has some pawns in the n-th row. There are also enemy pawns in the 1-st row. On one turn, Gregor moves one of his pawns. A pawn can move one square up (from (i,j) to (i?1,j)) if there is no pawn in the destination square. Additionally, a pawn can move one square diagonally up (from (i,j) to either (i?1,j?1) or (i?1,j+1)) if and only if there is an enemy pawn in that square. The enemy pawn is also removed.
Gregor wants to know what is the maximum number of his pawns that can reach row 1?
Note that only Gregor takes turns in this game, and the enemy pawns never move. Also, when Gregor’s pawn reaches row 1, it is stuck and cannot make any further moves.
Input
The first line of the input contains one integer t (1≤t≤2?104) — the number of test cases. Then t test cases follow.
Each test case consists of three lines. The first line contains a single integer n (2≤n≤2?105) — the size of the chessboard.
The second line consists of a string of binary digits of length n, where a 1 in the i-th position corresponds to an enemy pawn in the i-th cell from the left, and 0 corresponds to an empty cell.
The third line consists of a string of binary digits of length n, where a 1 in the i-th position corresponds to a Gregor’s pawn in the i-th cell from the left, and 0 corresponds to an empty cell.
It is guaranteed that the sum of n across all test cases is less than 2?105.
Output
For each test case, print one integer: the maximum number of Gregor’s pawns which can reach the 1-st row.
Example
inputCopy
4
3
000
111
4
1111
1111
3
010
010
5
11001
00000
outputCopy
3
4
0
0
Note
In the first example, Gregor can simply advance all 3 of his pawns forward. Thus, the answer is 3.
In the second example, Gregor can guarantee that all 4 of his pawns reach the enemy row, by following the colored paths as demonstrated in the diagram below. Remember, only Gregor takes turns in this “game”!
In the third example, Gregor’s only pawn is stuck behind the enemy pawn, and cannot reach the end.
In the fourth example, Gregor has no pawns, so the answer is clearly 0.
题意：
一个n*n的棋盘，第一行存在对手的棋子，第n行存在自己的棋子，对手棋子不能动，自己的棋子有两种动法：1，若棋子处于（i，j）位置且（i-1，j）不存在对手棋子，便可以移动到（i-1，j）；2，若棋子在（i，j）位置，且（i-1，j）存在对手棋子，那么如果（i-1，j-1）或者（i-1，j+1）存在对手棋子，便可移动到相应位置，且吃掉对方棋子，求有多少棋子可以到达第一行
思路：
对于棋盘来说只需要考虑第一行和第n行棋子存在情况，遍历第n行是否存在自己的棋子，若存在，再判断第一行对应位置是否存在对手棋子或自己棋子，若不存在，则直接到达第一行，若存在对手棋子，则需要判断两侧是否有对手棋子，有则可以移动到第一行，否则不能
代码：
void solve()
{
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
string fi ,sc;
cin>>fi>>sc;
int sum = 0;
for(int i = 0 ; i < n ; i++){
if(sc[i] == '1'){
if(fi[i] == '0'){
fi[i] = '2';
sum ++;
}else if(fi[i] != '0'){
if(i-1 >= 0&&fi[i-1] == '1'){
fi[i-1] = '2';
sum ++;
}else if(fi[i+1] == '1' && i + 1 < n){
fi[i+1] = '2';
sum++;
}
}
}
}
cout<<sum<<endl;
}
}
C.Web of Lies
C. Web of Lies
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
When you play the game of thrones, you win, or you die. There is no middle ground.
Cersei Lannister, A Game of Thrones by George R. R. Martin
There are n nobles, numbered from 1 to n. Noble i has a power of i. There are also m “friendships”. A friendship between nobles a and b is always mutual.
A noble is defined to be vulnerable if both of the following conditions are satisfied:
the noble has at least one friend, and
all of that noble’s friends have a higher power.
You will have to process the following three types of queries.
Add a friendship between nobles u and v.
Remove a friendship between nobles u and v.
Calculate the answer to the following process.
The process: all vulnerable nobles are simultaneously killed, and all their friendships end. Then, it is possible that new nobles become vulnerable. The process repeats itself until no nobles are vulnerable. It can be proven that the process will end in finite time. After the process is complete, you need to calculate the number of remaining nobles.
Note that the results of the process are not carried over between queries, that is, every process starts with all nobles being alive!
Input
The first line contains the integers n and m (1≤n≤2?105, 0≤m≤2?105) — the number of nobles and number of original friendships respectively.
The next m lines each contain the integers u and v (1≤u,v≤n, u≠v), describing a friendship. No friendship is listed twice.
The next line contains the integer q (1≤q≤2?105) — the number of queries.
The next q lines contain the queries themselves, each query has one of the following three formats.
1 u v (1≤u,v≤n, u≠v) — add a friendship between u and v. It is guaranteed that u and v are not friends at this moment.
2 u v (1≤u,v≤n, u≠v) — remove a friendship between u and v. It is guaranteed that u and v are friends at this moment.
3 — print the answer to the process described in the statement.
Output
For each type 3 query print one integer to a new line. It is guaranteed that there will be at least one type 3 query.
Examples
inputCopy
4 3
2 1
1 3
3 4
4
3
1 2 3
2 3 1
3
outputCopy
2
1
inputCopy
4 3
2 3
3 4
4 1
1
3
outputCopy
1
Note
Consider the first example. In the first type 3 query, we have the diagram below.
In the first round of the process, noble 1 is weaker than all of his friends (2 and 3), and is thus killed. No other noble is vulnerable in round 1. In round 2, noble 3 is weaker than his only friend, noble 4, and is therefore killed. At this point, the process ends, and the answer is 2.
In the second type 3 query, the only surviving noble is 4.
The second example consists of only one type 3 query. In the first round, two nobles are killed, and in the second round, one noble is killed. The final answer is 1, since only one noble survives.
题意：
有n个贵族编号1-n，其中有m对朋友，若一贵族他至少有一个朋友，且他的编号小于他所有的朋友，那么他就是被定义为弱势贵族，我们有三种操作：1.u，v成为朋友，满足之前不是朋友；2.u，v不再为朋友，保证之前是朋友；3，进行一个流程 ：重复清除弱势的所有贵族，清除后的贵族将不再存在，友谊也不存在，而新贵族就有可能变得弱势，知道没有弱势贵族为止，输出未被清除的贵族
思路：
对于每次进程，最后剩下的贵族一定是编号比他所有朋友大的，只需要用一个数组来记录每一个贵族有多少比自己强势的贵族数量即可，每次新增一个数组值为1的贵族，则代表多一个进程中会变弱势的贵族，多一个需要被清除的贵族，最后维护这个数组，用总的贵族数-需要清除的贵族数
代码：
int arr[N] = {0};
void solve()
{
int n,m;
scanf("%d %d",&n,&m);
int ans = 0;
while(m--){
int u,v;
scanf("%d %d",&u,&v);
if(u > v) swap(u,v);
arr[u]++;
if(arr[u] == 1) ans++;
}
int t;
scanf("%d",&t);
while(t--){
int q;
scanf("%d",&q);
if(q == 1){
int u,v;
scanf("%d %d",&u,&v);
if(u > v) swap(u,v);
arr[u]++;
if(arr[u] == 1) ans++;
}else if(q == 2){
int u,v;
scanf("%d %d",&u,&v);
if(u > v) swap(u,v);
arr[u]--;
if(arr[u] == 0) ans--;
}else{
printf("%d\n",n-ans);
}
}
}
|