2020-03-15发表2020-12-20更新ICPC/CCPC / Contests / Codeforces11 分钟读完 (大约1676个字)

Codeforces Round #628 (Div.2)

A. EhAb AnD gCd

Solution

输出 $1$ 和 $x-1$ 即可。

Code

>folded

#include<algorithm>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

int T, x;

int main(){
    read(T);
    while(T--){
        read(x);
        printf("%d %d\n", 1, x-1);
    }
    return 0;
}

B. CopyCopyCopyCopyCopy

Solution

排序去重后输出长度。

Code

>folded

#include<algorithm>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 100005;

int T, n, a[N];

int main(){
    read(T);
    while(T--){
        read(n);
        for(int i = 1; i <= n; i++)
            read(a[i]);
        sort(a+1, a+n+1);
        printf("%ld\n", unique(a+1, a+n+1) - (a+1));
    }
    return 0;
}

C. Ehab and Path-etic MEXs

Solution

考虑 $0,1$ 同时出现的路径，只需要保证 $2$ 不在该路径上。实现上，找一个度数大于 $2$ 的节点，把与之相连的边依次赋为 $0,1,2\cdots$ 即可达到目的。

Code

>folded

#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 100005;

int n, ans[N], now;
bool b[N];

struct Edge{
    int nxt, to, id;
}edge[N<<1];
int head[N], edgeNum, deg[N];
void addEdge(int from, int to, int id){
    edge[++edgeNum] = (Edge){head[from], to, id};
    head[from] = edgeNum;
    deg[to]++;
}

int main(){
    memset(ans, -1, sizeof ans);
    read(n);
    for(int i = 1; i < n; i++){
        int u, v; read(u, v);
        addEdge(u, v, i), addEdge(v, u, i);
    }
    int mark = 0;
    for(int i = 1; i <= n; i++)
        if(deg[i] > 2)
            mark = i;
    if(mark)
        for(int i = head[mark]; i; i = edge[i].nxt)
            ans[edge[i].id] = now++;
    for(int i = 1; i < n; i++){
        if(ans[i] == -1)
            ans[i] = now++;
        printf("%d\n", ans[i]);
    }
    return 0;
}

D. Ehab the Xorcist

Solution

我们有性质：$a\oplus b \leq a+b$，证明不难：$a+b$ 可以表达为 $a\oplus b$ 作为当前位、$a\& b$ 作为进位，即 $a+b=a\oplus b+((a\& b)<<1)$，所以加法比异或多了进位，当然更大。

$u>v$ 时：由上述性质，无解；
$u=v$ 时：特判掉 $u=v=0$ 的情况，然后输出 $u$ 就好；
$u<v$ 时：
- $v$ 奇 $u$ 偶，无解，因为 $u$ 只能分解为偶数个偶数和偶数个奇数之和，它们的异或一定是偶数；
- $v$ 偶 $u$ 奇，无解，因为 $u$ 只能分解为若干个偶数和奇数个奇数之和，它们的异或一定是奇数；
- $u,v$ 同奇偶，由于 $u,\frac{v-u}{2},\frac{v-u}{2}$ 是满足条件的解，但是若前两项可以合并（$u+\frac{v-u}{2}=u\oplus\frac{v-u}{2}$），则合并后输出。

Code

>folded

#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

LL u, v;

int main(){
    read(u, v);
    if(u > v)   return puts("-1"), 0;
    if(u == 0 && v == 0)    return puts("0"), 0;
    if(u == v){
        puts("1");
        printf("%lld\n", u);
        return 0;
    }
    if((v - u) % 2 == 0){
        LL w = (v - u) >> 1;
        if(u + w == (u ^ w)){
            puts("2");
            printf("%lld %lld\n", u + w, w);
        }
        else{
            puts("3");
            printf("%lld %lld %lld\n", u, w, w);
        }
        return 0;
    }
    puts("-1");
    return 0;
}

E. Ehab’s REAL Number Theory Problem

Solution

【参考官方题解】首先，如果一个数有完全平方因数，除掉后不影响答案。然后为方便起见，特判掉存在完全平方数或存在两个数相等的情况。

由于每个数最多 $7$ 个因数，所以每个数最多有 $2$ 个质因数，即每个数都只能是 $p$ 或 $p\cdot q$ 两种情况（ $p,q$ 质数）。以所有质数和 $1$ 为点，对于 $p$ 连接 $1,p$ 两点，对于 $p\cdot q$ 连接 $p,q$ 两点，则问题转化为寻找图中的最小环。从每个点分别 $bfs$ 可以求出包含这个点的最小环大小，但这是 $O(n^2)$ 的；事实上，我们只需要从数字小于 $\sqrt{\max(a_i})$ 的点出发 $bfs$ 即可，因为一个环一定包含数字小于 $\sqrt{\max(a_i)}$ 的点。

Code

>folded

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

const int N = 200005;
const int M = 1000005;

bool notP[M];
int pList[M] = {0, 1}, pID = 1, fun[M] = {0, 1};
void Euler(int n){
    notP[0] = notP[1] = 1;
    for(int i = 1; i <= n; i++){
        if(!notP[i])	pList[++pID] = i, fun[i] = pID;
        for(int j = 2; j <= pID; j++){
            if(1ll * i * pList[j] > n)	break;
            notP[i * pList[j]] = 1;
            if(i % pList[j] == 0)	break;
        }
    }
}

int n, a[N], ans = 1e9, maxx, dis[M];
vector<int> edge[M];
pii d[N];

inline pii getDiv(int &x){
    pii res(0, 0);
    for(int i = 2; pList[i] * pList[i] <= x; i++){
        if(x % pList[i] == 0){
            int cnt = 0;
            while(x % pList[i] == 0){
                cnt ^= 1;
                x /= pList[i];
            }
            if(cnt){
                if(!res.first)  res.first = pList[i];
                else    res.second = pList[i];
            }
        }
    }
    if(x > 1){
        if(!res.first)  res.first = x;
        else    res.second = x;
    }
    if(res.first && !res.second)
        res.second = res.first, res.first = 1;
    x = res.first * res.second;
    return res;
}

int main(){
    Euler(1000000);
    read(n);
    for(int i = 1; i <= n; i++){
        read(a[i]);
        int sq = sqrt(a[i]);
        if(sq * sq == a[i]) return puts("1"), 0;
        d[i] = getDiv(a[i]);
        maxx = max(maxx, a[i]);
    }
    sort(a+1, a+n+1);
    for(int i = 1; i < n; i++)
        if(a[i] == a[i+1])
            return puts("2"), 0;
    for(int i = 1; i <= n; i++) {
        int fi = fun[d[i].first], se = fun[d[i].second];
        edge[fi].pb(se), edge[se].pb(fi);
    }
    for(int i = 1; pList[i] * pList[i] <= maxx; i++){
        for(int j = 1; j <= pID; j++)   dis[j] = -1;
        queue<pii> q;
        q.push(mp(i, 0));
        dis[i] = 0;
        while(!q.empty()){
            pii cur = q.front(); q.pop();
            for(auto to: edge[cur.first]){
                if(to == cur.second)    continue;
                if(dis[to] == -1){
                    dis[to] = dis[cur.first] + 1;
                    q.push(mp(to, cur.first));
                } else  ans = min(ans, dis[to] + dis[cur.first] + 1);
            }
        }
    }
    if(ans == 1e9)  puts("-1");
    else    printf("%d\n", ans);
    return 0;
}

F. Ehab’s Last Theorem

Solution

【参考官方题解】$dfs$ 并考虑 $dfs$ 树，若某祖先到当前点的路径与返祖边构成了一个长度大于等于 $\lceil\sqrt n\rceil$ 的圈，输出即可；否则，当前点的返祖边一定不超过 $\lceil\sqrt n\rceil-2$ 条，如果其邻域内其他点都没被纳入独立集里，就把它纳入独立集里。如此，若 $dfs$ 结束后没有找到圈，我们一定找到了足够大的独立集，因为每个点最多阻碍了 $\lceil\sqrt n\rceil-1$ 个点。

Code

>folded

#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)

const int N = 100005;

int n, m, sq;
vector<int> ans;
bool inans[N];

struct Edge{
    int nxt, to;
}edge[N<<2];
int head[N], edgeNum;
void addEdge(int from, int to){
    edge[++edgeNum] = (Edge){head[from], to};
    head[from] = edgeNum;
}

int dep[N], fa[N];
void dfs(int x, int f, int depth){
    dep[x] = depth, fa[x] = f;
    bool ok = true;
    for(int i = head[x]; i; i = edge[i].nxt){
        if(edge[i].to == f) continue;
        if(dep[edge[i].to]){
            if(dep[x] - dep[edge[i].to] + 1 >= sq){
                printf("2\n%d\n", dep[x] - dep[edge[i].to] + 1);
                int now = x;
                while(now != edge[i].to){
                    printf("%d ", now);
                    now = fa[now];
                }
                printf("%d\n", edge[i].to);
                exit(0);
            }
        } else  dfs(edge[i].to, x, depth + 1);
        if(inans[edge[i].to])   ok = false;
    }
    if(ok)  ans.push_back(x), inans[x] = 1;
}

int main(){
    read(n, m);
    sq = ceil(sqrt(n));
    for(int i = 1; i <= m; i++){
        int u, v; read(u, v);
        addEdge(u, v), addEdge(v, u);
    }
    dfs(1, 0, 1);
    puts("1");
    for(int i = 0; i < sq; i++)
        printf("%d ", ans[i]);
    return 0;
}

Codeforces Round #628 (Div.2)

http://xyfjason.github.io/blog-xcpc/2020/03/15/Codeforces-Round-628-Div-2/

作者

xyfJASON

发布于

2020-03-15

更新于

2020-12-20

许可协议

#Codeforces

Codeforces Round #628 (Div.2)

A. EhAb AnD gCd

Solution

Code

B. CopyCopyCopyCopyCopy

Solution

Code

C. Ehab and Path-etic MEXs

Solution

Code

D. Ehab the Xorcist

Solution

Code

E. Ehab’s REAL Number Theory Problem

Solution

Code

F. Ehab’s Last Theorem

Solution

Code

作者

发布于

更新于

许可协议

评论

分类

最新文章

标签