#628 DIV2 题解

组样例,每组样例给一个,构造一组,使得。

2
2
14
1 1
6 4

直接输出和。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int t = 0;
    scanf("%d", &t);
    while(t--) {
        ll x = 0;
        scanf("%lld", &x);
        printf("1 %lld\n", x - 1);
    }
    return 0;
}

组样例,每组给一个和个数 。将同一个序列重复次得到一个新序列,问可以从新序列中严格最长上升子序列长度为多少。

2
3
3 2 1
6
3 1 4 1 5 9
3
5

重复次,对于原序列就有次选择的机会。每次按照从小到大的选,只要没有重复的数,总是能得到一个长度的上升子序列,所以就是求去重之后的长度。

#include <bits/stdc++.h>
using namespace std;

int a[maxn];
map<int, int> mii;

int main(){
    int t = 0;
    scanf("%d", &t);
    while(t--) {
        mii.clear();
        int n = 0, cnt = 0;
        scanf("%d", &n);
        for(int i = 1;i <= n;i++) {
            scanf("%d", a + i);
            if(mii.count(a[i]) == 0) cnt++;
            mii[a[i]]++;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

给一颗个点的树,用到给每条边编号,每个编号只能用一次,,表示到的简单路径上最小未出现过的编号,为使最大的尽可能小,输出一种编号的方案。

6
1 2
1 3
2 4
2 5
5 6
0
3
2
4
1

首先如果是一条链的话,怎么编号都是无所谓的,这样所有的编号都会出现。

若不是链,则一定会出现下图的结果。

这样从任意点去其他一个点时,总是有一条边是无法经过,如果把最下的三个编号放上去,则这三个数中总是有一个数是,而数又是最小的三个,所以这就是一种合法的方案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5+5;

pii E[maxn];
int deg[maxn], flag[maxn];

int main(){
    int n = 0, tag = 0;
    memset(flag, -1, sizeof(flag));
    scanf("%d", &n);
    for(int i = 1;i < n;i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        E[i] = {u, v};
        deg[u]++, deg[v]++;
    }
    for(int i = 1;i <= n;i++) {
        if(deg[i] >= 3) {
            tag = i; break;
        }
    }
    if(tag == 0) {
        for(int i = 1;i < n;i++) {
            printf("%d\n", i - 1);
        }
    } else {
        int cnt = 0, num = 0;
        for(int i = 1;i <= n;i++) {
            if(E[i].first == tag || E[i].second == tag) {
                flag[i] = cnt++;
            }
            if(cnt == 3) break;
        }
        for(int i = 1;i < n;i++) {
            if(flag[i] == -1) {
                printf("%d\n", cnt++);
            } else {
                printf("%d\n", flag[i]);
            }
        }
    }
    return 0;
}

给一个和,构造一个最短的数组,使得数组所有元素的异或和为,和为。若没有输出-1。

in: 2 4
out: 
2
3 1
in: 1 3
out:
3
1 1 1

首先记,显然不行,当只考虑二进制最低位时,异或和加法等价,所以,的奇偶性应该相同,所以时也不行。

然后开始构造合法的情况,考虑让数组第一个数,显然,但不一定等于,我们知道对于任意,有。考虑让,而总是偶数,这样用三个数,总是能构造出来异或和为,和为。

考虑能不能把数组个数减小一点,可以把不加在上(去掉),而是直接加在上,但是这里是不能随便加的,当的二进制表示的所有是1的地方,在的二进制表示中恰好是0,这样加进去不会不会产生进位,同时和异或时会重新得到。这样的情况下长度被我们缩短到了。

之后考虑一点细节,到时,,直接输出即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100;

int flag[maxn];

int main(){
    ll u, v;
    scanf("%lld %lld", &u, &v);
    ll d = v - u;
    if(v == u && v != 0) {
        puts("1");
        printf("%lld\n", u);
    }
    else if(v == 0 && u == 0) {
        puts("0");
    } else if(d % 2 == 1 || d < 0) {
        puts("-1");
    } else {
        ll tmp = u, ans = 0;
        int cnt = 0, f = 0;
        while(tmp) {
            flag[cnt++] = tmp % 2;
            tmp /= 2;
        }
        cnt = 0, tmp = d / 2ll;
        while(tmp) {
            flag[cnt++] += tmp % 2;
            tmp /= 2;
        }
        for(int i = 0;i < 64;i++) {
            if(flag[i] >= 2) {
                f = 1; break;
            }
        }
        if(f == 1) {
            puts("3");
            printf("%lld %lld %lld\n", u, d / 2ll, d / 2ll);
        } else {
            puts("2");
            printf("%lld %lld\n", u + d / 2ll, d / 2ll);
        }
    }
    return 0;
}

给一个和个数,,,,每个不超过7个因子,找一个长度最小的非空子序列,使得序列中的所有数的积是一个完全平方数,输出序列长度。

3
1 4 6
1
4
2 3 6 6
2

因为因子个数不超过7个,所以最多能有两个不相同的质因数。考虑形式的数,它要凑成一个完全平方数,我们期待的是有一个,注意到和,都是需要一个来凑成平方数,所以次数是偶数的质因子是没有作用,这个时候对于每个,把其中的次数是偶数的质因子全部拿掉,所有的数都可以表示为

当存在1时,答案很显然就是这个1,所以长度就为1。

当遇到时,将和0号点连边。

当遇到时,将和连边。

之后的问题就是寻找一个最小环,输出最小环长度即可。

固定一个点找最小环的话直接可以做到,边权都是1,所以需要的时间,但这里再移动固定的点的话就会是平方的复杂度肯定会超时。

注意到连边的时候中有一个一定是,也就是,所以只需要移动以下的质数来寻找最小环即可,若没找到则输出-1。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 1e6+5;
#define INF 0x3f3f3f3f

int a[maxn], prime[maxn], pp[maxn], pos[maxn];
pii pr[maxn];
bool is_prime[maxn];

int sieve(int n){
    int p = 0;
    for(int i = 0;i <= n;i++) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for(int i = 2;i <= n;i++){
        if(is_prime[i]) prime[p++] = i;
        for(int j = 0;j < p;j++){
            if(prime[j] * i > n) break;
            is_prime[prime[j] * i] = false;
            if(i % prime[j] == 0) break;
        }
    }
    return p;
}
vector<int> G[maxn];
int dis[maxn], vis[maxn], flag[maxn], pre[maxn];
int bfs(int u) {
    queue<int> q;
    memset(vis, 0, sizeof(vis));
    dis[u] = 0, vis[u] = 1;
    q.push(u);
    while(q.size()) {
        int v = q.front();
        q.pop();
        for(int i = 0;i < G[v].size();i++) {
            int to = G[v][i];
            if(vis[to] == 0) {
                vis[G[v][i]] = 1;
                dis[to] = dis[v] + 1;
                pre[to] = v;
                q.push(to);
            } else {
                if(to == pre[v]) continue;
                return dis[v] + dis[to] + 1;
            }
        }
    }
    return INF + 5;
}

int main(){
    int n;
    scanf("%d", &n);
    int cnt = sieve(1000000 + 5);
    for(int i = 0;i < cnt;i++) {
        pos[prime[i]] = i;
    }
    for(int i = 0;i < 200;i++) {
        pp[i] = prime[i] * prime[i];
    }
    for(int i = 1;i <= n;i++) {
        scanf("%d", a + i);
        for(int j = 0;j < 200;j++) {
            while(a[i] % pp[j] == 0) {
                a[i] /= pp[j];
            }
            if(a[i] < prime[j]) break;
        }
        if(is_prime[a[i]]) flag[a[i]] = 1;
        else {
            flag[a[i]] = 2;
            for(int j = 0;j < 200;j++) {
                if(a[i] % prime[j] == 0) {
                    pr[a[i]] = {prime[j], a[i] / prime[j]}; break;
                }
            }
        }
    }
    for(int i = 1;i <= n;i++) {
        if(a[i] == 1) {
            puts("1"); return 0;
        } else {
            if(flag[a[i]] == 1) {
                int u = pos[a[i]] + 1;
                G[u].push_back(0), G[0].push_back(u);
            } else {
                int u = pos[pr[a[i]].first] + 1, v = pos[pr[a[i]].second] + 1;
                G[u].push_back(v), G[v].push_back(u);
            }
        }
    }
    int ans = INF;
    for(int i = 0;i < 200;i++) {
        ans = min(ans, bfs(i));
    }
    if(ans == INF) {
        puts("-1"); return 0;
    }
    printf("%d\n", ans);
    return 0;
}

给一张个点条边的图,问图中存不存在大小为的独立集,或者长度大于的简单环。输出其中一种可以,若要输出独立集,先输出1,再输出独立集中元素, 若要输出简单环先输出2再输出环的长度,再输出环中元素。

6 6
1 3
3 4
4 2
2 6
5 6
5 1
1
1 6 4
6 8
1 3
3 4
4 2
2 6
5 6
5 1
1 4
2 5
2
4
1 5 2 4

首先直接,利用一个栈来保存过的路径,当一个点产生回边时,检查这条回边的两个端点在原树上距离是否大于等于(因为环的长度还需要再加上1)。有则直接找到了环。没有则记录下到该点的深度。

之后可以将每个点的深度模一个,

若,之间有一条回边。则在第一步的时候就会被判环了,因为两者之间的距离等于。所以在模数相同的情况下,,可以放在一个独立集之中,而由于,是任意的,所以所有模结果相同的数都可以放在一个独立集中,而因为模数是,一共有个点,所以总存在一个独立集中元素个数是符合条件的。找到一个符合条件的输出即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;

vector<int> G[maxn];
vector<int> st;
vector<int> ans[maxn];
int res, vis[maxn], ins[maxn], dep[maxn];

int fun(int n) {
    for(int i = 1; i <= n;i++) {
        if(1ll * i * i >= n) return i;
    }
}

void dfs(int u) {
    st.push_back(u); ins[u] = 1;
    for(int i = 0;i < G[u].size();i++) {
        int v = G[u][i];
        if(dep[v] == 0) {
            dep[v] += dep[u] + 1;
            dfs(v);
        } else {
            if(dep[u] - dep[v] + 1 >= res) {
                puts("2");  printf("%d\n", dep[u] - dep[v] + 1);
                int len = st.size(), cnt = 0;//assert(len - 1 >= dep[v] - 1);
                for(int i = len - 1;i >= 0;i--) {
                     cnt++; printf("%d", st[i]);
                    if(cnt == dep[u] - dep[v] + 1) {
                        puts(""); break;
                    } else {
                        printf(" ");
                    }
                }
                exit(0);
            }
        }
    }
    st.pop_back();
    ins[u] = 0;
}

void dfs2(int u, int num) {
    if(vis[u]) return;
    vis[u] = 1;
    ans[num % (res - 1)].push_back(u);
    for(int i = 0;i < G[u].size();i++) {
        int v = G[u][i];
        dfs2(v, num + 1);
    }
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    res = fun(n);
    for(int i = 1;i <= m;i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    dep[1] = 1;
    dfs(1); dfs2(1, 1);
    puts("1");
    for(int i = 0;i < res;i++) {
        if(ans[i].size() >= res) {
            int len = ans[i].size(), cnt = 0;
            for(int j = 0;j < res;j++) {
                printf("%d%c", ans[i][j], j == res - 1 ? '\n' : ' ');
            }
            exit(0);
        }
    }
    return 0;
}

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:E

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 水果Fruit(母函数) - HDU 2152

    转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常
  • leetcode题解 | 78. 子集

    这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

    ACM算法日常
  • 力扣 526.优美的排序(next_permutation?)

    链接:https://leetcode-cn.com/problems/beautiful-arrangement

    ACM算法日常
  • 09-排序3 Insertion or Heap Sort (25分)

    Insertion sort iterates, consuming one input element each repetition, and growin...

    AI那点小事
  • P2658 汽车拉力比赛

    题目描述 博艾市将要举行一场汽车拉力比赛。 赛场凹凸不平,所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500),每个单元格的海拔范围在0到10^9之...

    attack
  • 1545 最简单排序

    个人博客:double.win 1545 最简单排序  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

    attack
  • vs---错误收集并自己解决后归纳

    1。C++编译时,出现这样的错误 d:\program files\microsoft visual studio\vc98\include\stdio.h(3...

    Gxjun
  • leetcode 204题求素数个数

    Count the number of prime numbers less than a non-negative number, n

    用户1539362
  • cf1000F. One Occurrence(线段树 set)

    首先把询问离线,预处理每个数的\(pre, nxt\),同时线段树维护\(pre\)(下标是\(pre\),值是\(i\)),同时维护一下最大值

    attack
  • 洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

    具体来说,每次比较当前后缀和\(S_0\)的lcp,如果长度\(< N\)的话就从不合法的位置继续匹配

    attack

扫码关注云+社区

领取腾讯云代金券