Educational Codeforces Round 124 (Rated for Div. 2)
A.Playoff
模拟
题意
有2^n athletes compete
When athletes x and y compete, the winner is decided as follows:
- if x+y is odd, the athlete with the lower index wins (i. e. if x<y, then x wins, otherwise y wins);
- if x+y is even, the athlete with the higher index wins.
The first line contains one integer tt (1≤t≤30) — the number of test cases.
Each test case consists of one line containing one integer nn (1≤n≤30).
第一轮必定是奇加偶,因此取更小奇数位,第二轮是奇加奇,因此取更高奇数位,以此类推,不难发现规律是
$$result=2^{n}-1$$
1 |
|
特别注意:
使用pow函数需要转下类型,否则
1 | 1 |
bengbuzhu
B. Prove Him Wrong
构造,模拟
题意
Recently, your friend discovered one special operation on an integer array a:
- Choose two indices i and j (i≠j);
- Set ai=aj=|ai−aj|
- For every array aa of nn integers, where 1≤ai≤10^9, you can find a pair of indices (i,j) such that the total sum of aa will decrease after performing the operation.
For each test case, if there is no counterexample array a of size n, print NO.
Otherwise, print YES followed by the array a itself (1≤ai≤10^9). If there are multiple counterexamples, print any.
首先约定
$$a_j>a_i$$
根据题意
$$a_i=|a_{i}-a_{j}|$$
$$a_j=|a_{i}-a_{j}|$$
相加得
$$2|a_i-a_j|=a_i+a_j$$
问:是否不存在i,j使得
$$2|a_j-a_i|<a_i+a_j$$
那么实际上就是考虑
$$a_{j}<3a_{i}$$
通过简单的计算得到,当n>19的时候,会超出a的范围,因此直接报NO即可
1 |
|
C. Fault-tolerant Network
模拟
Computers in the first row has grades a1,a2,…,ana1,a2,…,an and in the second row — b1,b2,…,bnb1,b2,…,bn.
Initially, all pairs of neighboring computers in each row are connected by wire (pairs (i,i+1) for all 1≤i<n, so two rows form two independent computer networks.
Your task is to combine them in one common network by connecting one or more pairs of computers from different rows. Connecting the i-th computer from the first row and the j-th computer from the second row costs |ai−bj|.
测试数据
The first line contains a single integer t (1≤t≤10^4) — the number of test cases. Next t cases follow.
The first line of each test case contains the single integer nn (3≤n≤2⋅10^5) — the number of computers in each row.
The second line contains n integers a1,a2,…,an (1≤ai≤10^9) — the grades of computers in the first row.
The third line contains n integers b1,b2,…,bn (1≤bi≤10^9) — the grades of computers in the second row.
It’s guaranteed that the total sum of nn doesn’t exceed 2⋅10^5
题意
两台电脑是否可以连成一个环,有以下的方法:
- 1.a的首与b的首连接(a[1]—>b[1])
- 2.a的首与b的非首连接(a[1]—>b[n])
- 3.a的非首部分与b的首连接(a[n]—>b[1])
- 4.a的非首部分与b的非首部分连接(a[n]—>b[n])
1 |
|
后面三题不太会了(