玖的数学&算法录
0%

Educational Codeforces Round 124 (Rated for Div. 2)

发表于 更新于
本文字数： 3.8k 阅读时长 ≈ 3 分钟

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
 
int main()
{
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        ll ans=pow(2,n)-1;
        cout<<ans<<endl;
    }
    return 0;
}

特别注意：

使用pow函数需要转下类型，否则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
3
7
15
31
63
127
255
511
1023
2047
4095
8191
16383
32767
65535
131071
262143
524287
1.04858e+006
2.09715e+006
4.1943e+006
8.38861e+006
1.67772e+007
3.35544e+007
6.71089e+007
1.34218e+008
2.68435e+008
5.36871e+008
1.07374e+009

bengbuzhu

鸣谢Hanasaki提供的marnoonrk使用的函数

1
inlint int pw2(int x){return x == 0 ? 1LL : pw2(x - 1) * 2;}

B. Prove Him Wrong

构造，模拟

题意

Recently, your friend discovered one special operation on an integer array a:

  1. Choose two indices i and j (i≠j);
  2. 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
 
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        if(n>19){
            cout<<"NO"<<endl;
        }
        else{
            int j=1;
            cout<<"YES"<<endl;
            for(int i=1;i<=n;i++){
                cout<<j<<" ";
                j*=3;
            }
            cout<<endl;
        }
 
    }
    return 0;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
#define ll long long
const long long INF = 0x3f3f3f3f3f;
using namespace std;
 
 
//c
int main(){
    int t;
    cin>>t;
    while(t--){
        int n; cin>>n;
        ll a[n],b[n];
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=n;i++){
            cin>>b[i];
        }
        ll t1=INF,t2=INF,t3=INF,t4=INF;
        for(int i=1;i<=n;i++){
            t1=min(t1,abs(b[i]-a[1]));
            t2=min(t2,abs(b[i]-a[n]));
            t3=min(t3,abs(a[i]-b[1]));
            t4=min(t4,abs(a[i]-b[n]));
        }
        ll ans=INF;
        {
        ll q=0;
        q+=min(abs(a[1]-b[1]),t1+t3);
        q+=min(abs(a[n]-b[n]),t2+t4);
        ans=min(ans,q);
        }
        {
 
        ll q=0;
        q+=min(abs(a[1]-b[n]),t1+t4);
        q+=min(abs(a[n]-b[1]),t2+t3);
        ans=min(ans,q);
 
        }
 
        cout<<ans<<endl;
    }
 
    return 0;
}

后面三题不太会了（