A：很显然对于每个bit位，只要存在一个0，最终都能通过很多次操作后全部变成0.统计全部为1的位数即可。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 2e5 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e16
#define dbg(ax) cout << "now this num is " << ax << endl;

int a[105],tag[35];
int main() {
    int ca;scanf("%d",&ca);
    while(ca--) {
        int n;scanf("%d",&n);
        memset(tag,0,sizeof(tag));
        for(int i = 1;i <= n;++i) {
            scanf("%d",&a[i]);
            for(int j = 0;j <= 30;++j) {
                int g = ((a[i] >> j) & 1);
                if(g == 0) tag[j] = 1;
            }
        }
        int ma = 0; 
        for(int i = 0;i <= 30;++i) {
            if(tag[i] != 1) ma += (1 << i);
        }
        printf("%d\n",ma);
    }


 //   system("pause");
    return 0;
}

View Code

B：每次都放置与前面不同显然最优，这里比较特殊的是以?开头，这时候要第一个字母和前面的问号不一样放置

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 2e5 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e16
#define dbg(ax) cout << "now this num is " << ax << endl;

char s[105];
char cal(char c) {
    if(c == 'B') return 'R';
    else return 'B';
}
int main() {
    int ca;scanf("%d",&ca);
    while(ca--) {
        int n;scanf("%d",&n);
        cin >> s;
        char pre = 'A';
        int len = 0;
        if(s[0] == '?') {
            for(int i = 0;i < n;++i) {
                if(s[i] != '?') {pre = s[i];break;}
                ++len;
            }
            if(pre == 'A') s[0] = 'B';
            else {
                if(len % 2 == 0) s[0] = pre;
                else s[0] = cal(pre);
            }
        }
        for(int i = 1;i < n;++i) {
            if(s[i] != '?') continue;
            s[i] = cal(s[i - 1]);
        }
        cout << s << endl;
    }

   // system("pause");
    return 0;
}
/*
30
7
??BBR??

*/

View Code

C：一开始直接冲哈密尔顿通路去了。仔细一看这个图其实比较特殊。

然后分析一下就可以发现，如果存在到终点的路径，那么一定可以到。

反之也一定到，因为如果存在到1的路径就可以从终点到1开始。

综上所诉，一定存在一种走法满足。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e4 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e16
#define dbg(ax) cout << "now this num is " << ax << endl;

int a[N];
vector<int> ans;
void PR() {
    for(int i = 0;i < ans.size();++i) printf("%d%c",ans[i],i == ans.size() - 1 ? '\n' : ' ');
}
int main() {
    int ca;scanf("%d",&ca);
    while(ca--) {
        int n;scanf("%d",&n);
        for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
        ans.clear();
        if(n == 1) {
            if(a[1] == 0) ans.push_back(1),ans.push_back(2);
            else ans.push_back(2),ans.push_back(1);
            PR();
        }
        else {
            if(a[1] == 1) {
                ans.push_back(n + 1);
                for(int i = 1;i <= n;++i) ans.push_back(i);
                PR();
            }
            else if(a[n] == 0) {
                for(int i = 1;i <= n;++i) ans.push_back(i);
                ans.push_back(n + 1);
                PR();
            }
            else {
                int st = 0;
                for(int i = 1;i < n;++i) {
                    if(a[i] == 0 && a[i + 1] == 1) {
                        st = i;
                        break;
                    }
                }
                if(st != 0) {
                    for(int i = 1;i <= st;++i) ans.push_back(i);
                    ans.push_back(n + 1);
                    for(int i = st + 1;i <= n;++i) ans.push_back(i);
                    PR();
                }   
                //else printf("-1\n");
            }
        }
    }

 //   system("pause");
    return 0;
}

View Code

D1：直接n^2暴力并查集合并判断即可。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e3 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e16
#define dbg(ax) cout << "now this num is " << ax << endl;

int n,m1,m2,fa[N];
namespace UN1{
    int fa[N];
    void init() {
        for(int i = 1;i <= n;++i) fa[i] = i;
    }
    int Find(int x) {
        return x == fa[x] ? x : fa[x] = Find(fa[x]);
    }
    void Merge(int x,int y) {
        x = Find(x),y = Find(y);
        fa[x] = y;
    }
    bool check(int x,int y) {
        x = Find(x),y = Find(y);
        return x != y;
    }
}
namespace UN2{
    int fa[N];
    void init() {
        for(int i = 1;i <= n;++i) fa[i] = i;
    }
    int Find(int x) {
        return x == fa[x] ? x : fa[x] = Find(fa[x]);
    }
    void Merge(int x,int y) {
        x = Find(x),y = Find(y);
        fa[x] = y;
    }
    bool check(int x,int y) {
        x = Find(x),y = Find(y);
        return x != y;
    }
}
int main() {
    scanf("%d %d %d",&n,&m1,&m2);
    UN1::init();
    UN2::init();
    while(m1--) {
        int u,v;scanf("%d %d",&u,&v);
        UN1::Merge(u,v);
    }
    while(m2--) {
        int u,v;scanf("%d %d",&u,&v);
        UN2::Merge(u,v);
    }
    vector<pii> vec;
    for(int i = 1;i <= n;++i) {
        for(int j = i + 1;j <= n;++j) {
            if(UN1::check(i,j) && UN2::check(i,j)) {
                UN1::Merge(i,j);
                UN2::Merge(i,j);
                vec.push_back(pii{i,j});
            }
        }
    }
    printf("%d\n",vec.size());
    for(auto v : vec) printf("%d %d\n",v.first,v.second);
   // system("pause");
    return 0;
}

View Code

D2：这里的思路还是比较抽象的感觉。

枚举每个点和1的连接状态。如果对于当前点v，都和1没有连接。

那么就可以加上Edeg{1,v}这条边。

反之，准备两个容器v1,v2。对于没有和1连接的边，先放入容器。

因为这些边可能由于和{i，i为和1同一并查集的某个点}连接而和1间接连接。

现在我们考虑容器中的两个边x,y。

他们肯定满足都不在1的连通块中，且他们在另一个森林中都和1在同一连通块中。（否则两个点就都在1的连通块中）

即可以看成:

{1 and y} ,{x}

{1 and x} ,{y}

那么就可以建立{x,y}这条边。

所以对于容器中的任意两个点都可以建边。

不过要注意的是，可能两个边连之后，容器中某些边都被合并在1的连通块中了。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e5 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e16
#define dbg(ax) cout << "now this num is " << ax << endl;

int n,m1,m2;
namespace UN1{
    int fa[N];
    void init() {
        for(int i = 1;i <= n;++i) fa[i] = i;
    }
    int Find(int x) {
        return x == fa[x] ? x : fa[x] = Find(fa[x]);
    }
    void Merge(int x,int y) {
        x = Find(x),y = Find(y);
        fa[x] = y;
    }
    bool check(int x,int y) {
        x = Find(x),y = Find(y);
        return x != y;
    }
}
namespace UN2{
    int fa[N];
    void init() {
        for(int i = 1;i <= n;++i) fa[i] = i;
    }
    int Find(int x) {
        return x == fa[x] ? x : fa[x] = Find(fa[x]);
    }
    void Merge(int x,int y) {
        x = Find(x),y = Find(y);
        if(x < y) swap(x,y);
        fa[x] = y;
    }
    bool check(int x,int y) {
        x = Find(x),y = Find(y);
        return x != y;
    }
}
vector<pii> vec;
vector<int> v1,v2;
int main() {
    scanf("%d %d %d",&n,&m1,&m2);
    UN1::init();
    UN2::init();
    while(m1--) {
        int u,v;scanf("%d %d",&u,&v);
        UN1::Merge(u,v);
    }
    while(m2--) {
        int u,v;scanf("%d %d",&u,&v);
        UN2::Merge(u,v);
    }

    for(int i = 2;i <= n;++i) {
        if(UN1::check(1,i) && UN2::check(1,i)) {
            vec.push_back(pii{1,i});
            UN1::Merge(1,i);
            UN2::Merge(1,i);
        }
        else if(UN1::check(1,i)) v1.push_back(i);
        else if(UN2::check(1,i)) v2.push_back(i);
    }
    for(int i = 0,j = 0;i < v1.size() && j < v2.size();) {
        while(i < v1.size() && (!UN1::check(v1[i],1) && !UN2::check(v1[i],1))) {
            ++i;
        }
        while(j < v2.size() && (!UN2::check(v2[j],1) && !UN1::check(v2[j],1))) {
            ++j;
        }
        if(i >= v1.size() || j >= v2.size()) break;
        vec.push_back(pii{v1[i],v2[j]});
        UN1::Merge(v1[i],v2[j]);
        UN2::Merge(v2[j],v1[i]);
        ++i,++j;
    }
    printf("%d\n",vec.size());
    for(auto v : vec) printf("%d %d\n",v.first,v.second);
    //system("pause");
    return 0;
}

View Code

E：这题挺不错的

首先有个很直白的三维dp，但是显然不可能这样做。

设dp[j] - 表示a1 + a2 + ... an == i的方案数。

则有:

$ans =\sum_{a1 = L1}^{r1} \sum_{a2 = L2}^{r2} ... \sum_{an = Ln}^{rn} [gcd(a1,a2...an) = 1] * dp[a1,a2....an]$