A - Choose Two Numbers
给出两个数组，长度分别为$ n、m(1 \le n \le 100、1 \le m \le 100)$，找出两个分别属于两个数组的数，使得它们的和不在两个数组里

暴力

裸暴力，手滑了两发白给。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n,m;
int a[300],b[300];
bool mp[1000];

int main() {
    mst(mp,0);
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i = 1;i <= n;i++) cin>>a[i],mp[a[i]] = 1;
    cin>>m;
    for(int i = 1;i <= m;i++) cin>>b[i],mp[b[i]] = 1;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            if(mp[a[i] + b[j]] == 0) {
                cout<<a[i]<<" "<<b[j]<<endl;
                return 0;
            }
        }
    }
    return 0;
}

B - Make Product Equal One
给定一个数组$a$,其长度为$n$，每次可以花费1的代价使得一个数加1或者减1，求出最小的代价使得变化后所有数的乘积为1

贪心
会影响最终数值的是-1的地方，那么先统计一下小于等于-1以及等于0的数有多少个
先把小于等于-1的数变到-1的代价求出来，以及大于等于1的数变到1的代价求出来
最后再判断小于等于-1的数的个数是不是奇数，以及等于0的数是不是大于0，分类讨论一下即可

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
int n;
ll a[maxn];
ll ans = 0;
int cnt1 = 0,cnt2 = 0;

int main() {
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i = 1; i<= n;i++) {
        cin>>a[i];
        if(a[i] <= -1) {
            cnt1 ++;
            ans += (-1LL) - a[i];
        }
        else if(a[i] == 0) cnt2++;
        else {
            ans += a[i] - 1LL;
        }
    }
    if(cnt1 % 2 == 1) {
        if(cnt2 > 0) ans += cnt2;
        else ans += 2;
    }
    else ans += cnt2;
    cout<<ans<<"\n";
    return 0;
}

C - Almost Equal
给出一个数$n(1 \le n \le 1e5)$,然后问能不能将$1 - 2n$的$2n$个数排成一个环，使得在环上任意取$n$个连续的数所得到的和$sum_i$两两之间的差值小于等于1，如果可以，输出环的方案

数学
一开始看了样例猜了一下是不是只有n = 1和n = 3的情况下才能得到。。交了一发的确WA了
然后冷静分析.jpg
这$2n$个数每个数在加的情况下最多只能被取到$n$次，而且最后连续的$n$个数的和的情况就只有$x、x+1$的形式
那么可以得到一个方程$nx + n(x + 1) = n^2 \cdot (1 + 2n)$
得到$x = \frac {n - 1} {2} + n ^ 2$
也就是说只有在n是奇数的情况下才可以得到这个环，偶数的时候直接输出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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int n;
int ans[2 * maxn];
int pos1,pos2;

void check() {
    for(int i = 1;i <= 2 * n;i++) {
        int tmp = 0,pos;
        for(int j = 0;j < n;j++) {
            pos = i + j;
            if(pos > 2 * n) pos = pos % (2 * n);
            tmp += ans[pos];
        }
        cout<<tmp<<endl;
    };
}

int main() {
    ios::sync_with_stdio(0);
    cin>>n;
    if(n % 2 == 0) cout<<"NO\n";
    else {
        cout<<"YES\n";
        pos1 = 2;
        pos2 = n + 1;
        for(int i = 2;i < 2 * n;i += 2) {
            int x = i / 2;
            if(x % 2 == 1) {
                ans[pos2++] = i;
                ans[pos2++] = i + 1;
            }
            else {
                ans[pos1++] = i;
                ans[pos1++] = i + 1;
            }
        }
        ans[1] = 1;
        ans[2 * n] = 2 * n;
        cout<<1;
        for(int i = 2;i <= 2 * n;i++) cout<<" "<<ans[i];
        cout<<"\n";
    }
    return 0;
}

D - Shortest Cycle
给出$n(1 \le n \le 1e5)$个数$a_i(1 \le a_i \le 1e18)$，如果两个数$a_i$和$a_j$的与运算不为0的话，这两个数之间就存在一条边，求出最小的环的长度

dfs 位运算

本来一开始都快想到正解了但是又想偏了。。想了个假算法
最开始的想法：
考虑到如果暴力建边的话就是$n^2$的，但是可以利用位的信息来建图，可以降到$O(64n)$建图
两个数之间有路径，也就是说它们在某个位上同时为1，那么就可以开一个不定长数组，表示某一位上为1的数的编号，按位运算就可以得到这个数组
每次遍历的时候可以之间遍历这个数组得到当前点连接的边，就可以dfs一下。。
但是我TLE11。。改了之后又WA12
极限提交但是没过，白给。
然后看了一下别人的代码。。。特判了某个位为1的个数大于等于3的时候直接输出3，然后小于200的时候直接暴力建图跑bfs。。这里没想到
那么也就是说只要大于$64 \cdot 3$的情况下，暴力建图是可行的

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
int n;
ll a[maxn];
int cnt[100];
vector<ll> all;
ll dist[200][200],ans = INF;
ll mp[200][200];

void floyd() {
    for(int k = 0;k < (int)all.size();k++) {
        for(int i = 0;i < k;i++) {
            for(int j = i + 1;j < k;j++) {
                ans = min(ans,dist[i][j] + mp[i][k] + mp[j][k]);
            }
        }
        for(int i = 0;i < (int)all.size();i++) {
            for(int j = 0;j < (int)all.size();j++) {
                dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i = 1;i <= n;i++) {
        cin>>a[i];
        ll tmp = a[i];
        for(int j = 0;tmp != 0;j++) {
            if(tmp & 1) cnt[j]++;
            tmp >>= 1;
        }
        if(a[i] != 0) all.push_back(a[i]);
    }
    for(int i = 0;i <= 64;i++) {
        if(cnt[i] >= 3) {
            cout<<"3\n";
            return 0;
        }
    }
    for(int i = 0;i < (int)all.size();i++) {
        for(int j = 0;j < i;j++) {
            if((all[i] & all[j]) != 0) {
                dist[i][j] = dist[j][i] = 1;
                mp[i][j] = mp[j][i] = 1;
            }
            else {
                dist[i][j] = dist[j][i] = INF;
                mp[i][j] = mp[j][i] = INF;
            }
        }
    }
    floyd();
    if(ans == INF) cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}