Codeforces Round 896 (Div. 2)

Make It Zero

思维题目，要使得1-n全部变成一样的，偶数的话两次1-n就可以解决了，因为数字都是相同的

奇数的话可以拆分成偶数做

只需要两次1-n-1，然后两次n-1-n即可

解释：

显然有一个性质 对一段子序列做操作以后 那么这段子序列都会变成 相同的数

那么根据这个性质 我们可以构造 一个算法

我们可以通过 选中 [1,n] 来让所有的 数都变成相同的

那么 有一个性质： 一个数 异或 自己偶数次 为0,一个数 异或 自己奇数次 为自身

因此上面是正确的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve()
{
    int n;cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    if(n&1)
    {
        cout<<"4\n";
        cout<<1<<" "<<n<<"\n"<<1<<" "<<n-1<<"\n"<<n-1<<" "<<n<<"\n"<<n-1<<" "<<n<<"\n";
    }
    else
    {
        cout<<"2\n";
        cout<<1<<" "<<n<<"\n"<<1<<" "<<n<<"\n";
    }
}

2D Traveling

显而易见要么直接走直线

要么计算a到关键点的最小值和b在关键点的最小值

注意a,b可能本身就是关键点

可以证明没有更加优秀的贪心思路

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
void solve()
{
    int n,k,a,b;cin>>n>>k>>a>>b;
    vector<vector<int>>g(n);
    a--,b--;
    vector<int>x(n),y(n);
    for(int i=0;i<n;i++)
    {
       cin>>x[i]>>y[i]; 
    }
    int ans=abs(x[a]-x[b])+abs(y[a]-y[b]);
    int m1=1e10,m2=m1;
    if(a<k)m1=0;
    if(b<k)m2=0;
    for(int i=0;i<k;i++)
    {
        if(i!=a)
        {
            m1=min(m1,abs(x[a]-x[i])+abs(y[a]-y[i]));
        }
        if(i!=b)
        {
            m2=min(m2,abs(x[b]-x[i])+abs(y[b]-y[i]));
        }
    }
    cout<<min(ans,m1+m2)<<"\n";
}

Fill in the Matrix

这样子是最优秀的如果可以这样

\(M= \begin{pmatrix} 0&1&\cdots&m-2&m-1\\ 1&2&\cdots&m-1&0\\ 2&3&\cdots&0&1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ m-2&m-1&\cdots &m-4 & m-3\\ 0&1&\cdots&m-2&m-1\\ 0&1&\cdots&m-2&m-1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&1&\cdots&m-2&m-1\\ \end{pmatrix}\)

当m=1的时候，可以发现只有一列，只能是0，该列是MEX=1,对所有列的结果求MEX=0

当n>m-1的时候，因为后面都是相同的行，通过计算得到MEX=m

不然的话就是直接是n+1，最后是n+1。

直接进行构造就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve() 
{
    int n, m;
    cin >> n >> m;
    if(m == 1) cout << 0 << '\n';
    else if(n > m - 1) cout << m << '\n';
    else cout << n + 1 << '\n';
    for(int i=0;i<min(n,m-1);i++)
    {
        for(int j=0;j<m;j++)
        {
            cout << (i + j) % m << ' ';
        }
        cout << '\n';
    }
    for(int i=min(n,m-1);i<n;i++){
        for(int j=0;j<m;j++) 
            cout << j << ' ';
        cout << '\n';
    }
}

Candy Party (Easy Version)

首先想要均分糖果，那么必须满足糖果总数 \(sum\) 是人数 \(n\) 的倍数。

然后我们再取平均值，令 \(s=\frac{sum} n\)。

因为每个人必须收到一次糖果且只能送出一次糖果，所以对于每一个 \(a_i\)，我们首先需要满足 \(a_i-s\) 可以被表示为 \(2^x-2^y\)。

令 \(k=|a_i-s|\)。

以二进制的方式来看，\(\operatorname{lowbit}(k)\) 应该就是其中一个二次幂，是给出的还是收到的糖果数要看 \(a_i\) 和 \(s\) 的大小关系，那么 \(k+\operatorname{lowbit}(k)\) 就应该是另外一个二次幂。

所以，如果 \(k+\operatorname{lowbit}(k)\) 不是二次幂，就可以肯定无解。

那么我们再统计每个人需要接受和送出的糖果数的个数，如果接受和送出的糖果数的个数也不相等，那么就无解，否则，有解。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
#define rep(i,a,n) for(ll i=a;i<=n;i++)
#define frep(i,a,n) for(ll  i=a;i>=n;i--)
using ll=long long;
using namespace std;
ll t;
ll lowbit(ll x)
{
    return x&(-x);
}
const int N=2e5+100;
ll a[N];
ll sum;
ll k,low;
ll n;
map<ll,ll>m1,m2;
bool Totoro()
{
cin>>n;
sum=0;
m1.clear();
m2.clear();
rep(i,1,n)
{
    cin>>a[i];
    sum+=a[i];
}
if(sum%n)
{
    return 1;
}
sum/=n;
rep(i,1,n)
{
    a[i]-=sum;
    k=abs(a[i]);
    low=lowbit(k);
    k+=low;
    if(k!=lowbit(k))
    {
        return 1;
    }
    else if(a[i]>0)
    {
++m1[k];
++m2[low];
    }
    else if(a[i]<0)
{
    ++m1[low];
    ++m2[k];
}
}
for(auto i=m1.begin(),j=m2.begin();i!=m1.end()&&j!=m2.end();i++,j++)
{
    if(i->second!=j->second)
    {
        return 1;
    }
}
return 0;
}
int main()
{
cin>>t;
while(t--)
{
    if(Totoro())
    {
        cout<<"NO"<<'\n';
    }
    else
    {
        cout<<"YES"<<'\n';
    }
}
}

以下代码来自于互联网：

有一种不使用lowbit的方法，也就是直接枚举 其实速度上不会差距太大 直接计算即可

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int sum = 0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        sum += a[i];
    }
    if(sum % n != 0) {
        cout << "NO\n";
        return;
    }
    sum /= n;
    vector<int> cnt(32);
    for(int i=1;i<=n;i++){
        bool f = false;
        for(int j=0;j<32;j++){
            for(int k=0;k<32;k++){
                if(a[i] - (1ll << j) + (1ll << k) == sum){
                    f = true;
                    cnt[j] ++;
                    cnt[k] --;
                }
            }
        }
        if(!f){
            cout << "NO\n";
            return;
        }
    }
    for(int i=31;i>=0;i--){
        if(cnt[i] > 0){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

Hard版本就是把呢不能就是说可以给一共元素\(2^p\),或者从别人那里进行得到

实际上我们可以先考虑这种情况，并根据这种i情况进行cnt数组的更新，然后进行判断。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int sum = 0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        sum += a[i];
    }
    if(sum % n != 0) {
        cout << "NO\n";
        return;
    }
    sum /= n;
    vector<int> cnt(32), pl(32), pn(32);
    for(int i=1;i<=n;i++){
        bool f = false;
        for(int j=0;j<32;j++){
            if(a[i] - (1ll << j) == sum){
                f = true;
                pl[j] ++;
            }else if(a[i] + (1ll << j) == sum){
                f = true;
                pn[j] ++;
            }
        }
        if(f) continue;
        for(int j=0;j<32;j++){
            for(int k=0;k<32;k++){
                if(a[i] - (1ll << j) + (1ll << k) == sum){
                    f = true;
                    cnt[j] ++;
                    cnt[k] --;
                }
            }
        }
        if(!f){
            cout << "NO\n";
            return;
        }
    }
    for(int i=31;i>=0;i--){
        if(pl[i] < 0 || pn[i] < 0){
            cout << "NO\n";
            return;
        }
        cnt[i] += (pl[i] - pn[i]);
        if(i == 0) break;
        if(cnt[i] < 0){
            pl[i - 1] +=cnt[i];
            cnt[i - 1]+=cnt[i];
        }else{
            pn[i - 1] -= cnt[i];
            cnt[i - 1] += cnt[i];
        }
    }
    cout << (cnt[0] == 0 ? "YES\n" : "NO\n");
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}