正文

Codeforces 987 K预处理BFS 3n,7n+1随机结论题/不动点逆序对 X&Y=0连边DFS求连通块数目

IP云
IP云V管理员/4 阅读
12/01
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

A 

/*Huyyt*/

#include<bits/stdc++.h>

#define mem(a,b) memset(a,b,sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = 1e9 + ;

const int gakki =  +  +  +  + 1e9;

const int N =  + ;

int n, K;

ll sum[N][N];

ll a[N];

bool dp[N][N];

map<string, int> mp2;

map<int, string> mp;

int visit[];

int main()

{

        ios_base::sync_with_stdio();

        cin.tie();

        mp2["purple"] = ;

        mp2["green"] = ;

        mp2["blue"] = ;

        mp2["orange"] = ;

        mp2["red"] = ;

        mp2["yellow"] = ;

        mp[] = "Power";

        mp[] = "Time";

        mp[] = "Space";

        mp[] = "Soul";

        mp[] = "Reality";

        mp[] = "Mind";

        int n;

        cin >> n;

        for (int i = ; i <= n; i++)

        {

                string now;

                cin >> now;

                visit[mp2[now]]++;

        }

        cout <<  - n << endl;

        for (int i = ; i <= ; i++)

        {

                if (!visit[i])

                {

                        cout << mp[i] << endl;

                }

        }

        return ;

}

B 

/*Huyyt*/

#include<bits/stdc++.h>

#define mem(a,b) memset(a,b,sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = 1e9 + ;

const int gakki =  +  +  +  + 1e9;

const int N =  + ;

int main()

{

        ios_base::sync_with_stdio();

        cin.tie();

        ll x, y;

        cin >> x >> y;

        if (x == y || x ==  && y ==  || x ==  && y == )

        {

                cout << "=" << endl;

                return ;

        }

        if (x ==  || y == )

        {

                if (x == )

                {

                        cout << "<" << endl;

                }

                else

                {

                        cout << ">" << endl;

                }

                return ;

        }

        if (max(x, y) <= )

        {

                ll ansx = ;

                for (int i = ; i <= y; i++)

                {

                        ansx *= x;

                }

                ll ansy = ;

                for (int i = ; i <= x; i++)

                {

                        ansy *= y;

                }

                if (ansx > ansy)

                {

                        cout << ">" << endl;

                }

                else

                {

                        cout << "<" << endl;

                }

                return ;

        }

        if (x > y)

        {

                cout << "<" << endl;

        }

        else

        {

                cout << ">" << endl;

        }

        return ;

}

C 

/*Huyyt*/

#include<bits/stdc++.h>

#define mem(a,b) memset(a,b,sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = 1e9 + ;

const int gakki =  +  +  +  + 1e9;

const int N =  + ;

int num[];

ll cost[];

ll dp[][];

int main()

{

        ios_base::sync_with_stdio();

        cin.tie();

        int n;

        cin >> n;

        for (int i = ; i <= n; i++)

        {

                cin >> num[i];

        }

        for (int i = ; i <= ; i++)

        {

                for (int j = ; j <= ; j++)

                {

                        dp[i][j] = LLONG_MAX;

                }

        }

        for (int i = ; i <= n; i++)

        {

                cin >> cost[i];

                dp[i][] = cost[i];

        }

        for (int i = ; i <= n; i++)

        {

                for (int j = i - ; j >= ; j--)

                {

                        for (int k = ; k <= ; k++)

                        {

                                if (dp[j][k - ] != LLONG_MAX&&num[i]>num[j])

                                {

                                        dp[i][k] = min(cost[i] + dp[j][k - ], dp[i][k]);

                                }

                        }

                }

        }

        ll anser = LLONG_MAX;

        for (int i = ; i <= n; i++)

        {

                anser = min(anser, dp[i][]);

        }

        if (anser == LLONG_MAX)

        {

                cout << - << endl;

        }

        else

        {

                cout << anser << endl;

        }

        return ;

}

D. Fair

题意:

给你N个点M条边的连通图(100000) 和K个特殊地方(100) S个目标地(100)

每个特殊的地方有某种特产 问你从1到N每个点要拿S个特产的最少的花费

解:

给每个特产都建一个超级点 然后BFS 处理出1到N每个点到每种特产的最小距离

然后贪心取前S个即可 复杂度nklogk 

/*Huyyt*/

#include<bits/stdc++.h>

#define mem(a,b) memset(a,b,sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = 1e9 + ;

const int gakki =  +  +  +  + 1e9;

const int N = 1e5 + ;

int p[N];

vector<int> g[N];

int ans[N];

int dist[N];

int que[N];

int dp[N][];

int getl, getr;

int main()

{

        ios_base::sync_with_stdio();

        cin.tie();

        int n, m, k, s;

        cin >> n >> m >> k >> s;

        for (int i = ; i <= n; i++)

        {

                cin >> p[i];

        }

        int u, v;

        for (int i = ; i <= m; i++)

        {

                cin >> u >> v;

                g[u].pb(v);

                g[v].pb(u);

        }

        for (int i = ; i <= k; i++)

        {

                getl = ;

                getr = ;

                mem(dist, );

                for (int j = ; j <= n; j++)

                {

                        if (p[j] == i)

                        {

                                dist[j] = ;

                                que[++getr] = j;

                        }

                }

                while (getl <= getr)

                {

                        int len = g[que[getl]].size();

                        for (int w = ; w < len; w++)

                        {

                                int to = g[que[getl]][w];

                                if (!dist[to])

                                {

                                        dist[to] = dist[que[getl]] + ;

                                        que[++getr] = to;

                                }

                        }

                        getl++;

                }

                for (int j = ; j <= n; j++)

                {

                        dp[j][i] = dist[j] - ;

                }

        }

        for (int i = ; i <= n; i++)

        {

                sort(dp[i] + , dp[i] +  + k);

        }

        for (int i = ; i <= n; i++)

        {

                for (int j = ; j <= s; j++)

                {

                        ans[i] += dp[i][j];

                }

        }

        for (int i = ; i <= n; i++)

        {

                cout << ans[i] << " ";

        }

        cout << endl;

        return ;

}

E. Petr and Permutations

题意:

给你1到N的一种排列 A会选3n次每次随机一对位置交换 B会选7n+1次

问你给你的数列是A得到的可能性大还是B的可能性大

①:

可以猜到结论 观察可以得知3n和7n+1的奇偶性永远是不同的

所以我们计算原数列所需要的最小交换次数 当这个次数与A奇偶性相同就是A 反之则是B

(因为要与原数列相同的话在最小交换次数基础上要加偶数次) 

/*Huyyt*/

#include<bits/stdc++.h>

#define mem(a,b) memset(a,b,sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = 1e9 + ;

const int gakki =  +  +  +  + 1e9;

const int N = 1e6 + ;

int par[N], hs[N];

int sz[N];

int num[N];

int cnt;

void init(int n)

{

        for (int i = ; i <= n; i++)

        {

                par[i] = i, hs[i] = i, sz[i] = ;

        }

}

int find(int x)

{

        return par[x] == x ? x : par[x] = find(par[x]);

}

void unite(int x, int y)

{

        x = find(x);

        y = find(y);

        if (x != y)

        {

                par[x] = y, sz[y] += sz[x];

        }

}

int visit[N];

int main()

{

        ios_base::sync_with_stdio();

        cin.tie();

        int n;

        cin >> n;

        init(n);

        for (int i = ; i <= n; i++)

        {

                cin >> num[i];

        }

        for (int i = ; i <= n; i++)

        {

                if (num[i] != i)

                {

                        unite(i, num[i]);

                }

        }

        for (int i = ; i <= n; i++)

        {

                par[i] = find(i);

        }

        ll anser = ;

        for (int i = ; i <= n; i++)

        {

                if (!visit[par[i]])

                {

                        anser += sz[par[i]] - ;

                        visit[par[i]] = ;

                }

        }

        //cout << anser << endl;

        if (anser %  ==  * n % )

        {

                cout << "Petr" << endl;

        }

        else

        {

                cout << "Um_nik" << endl;

        }

        return ;

}

②:

也可以用不动点+逆序对分情况处理

当n不小于20000时 考察不动点的数量  n小于20000时取逆序对的数量判断奇偶性 

int main()

{

    int i,j,a1,a2;

    _(n);

    fo(i,n)

        _(a[i]);

    fo(i,n)

        an+=(a[i]==i);

    if(n>=)

        puts(an>=?"Petr":"Um_nik");

    else

    {

        fo(i,n)

        fo1(j,i+,n)

            if(a[j]<a[i])

                ans++;

        puts((ans+n)%?"Um_nik":"Petr");

    }

}

F. AND Graph

题意:

给你0 - 2 n -1范围中的m个数 (n<=22)

如果两个数字A i A j 两个&的值为0 则这两个点之间有一条边 问你最后的连通块有几个

解:

暴力题.. 假设有X,Y两个数 X的二进制恰好是Y的基础上多出一位1  比如 101 与 001 我们称X为Y的祖先 Y是X的子孙

这样能与祖先X相连的点 肯定能和Y相连 这样X,Y其实就通过对立数间接相连

所以我们每次DFS一个数的时候 把X全部子孙找出来 也把所有对立数(包括子孙的)找出来 他们肯定就是一个连通块

因为N最大是22 所以我们可以直接暴力循环枚举 开两个bool 数组 num[i]为true表示i是被选中的数 而vis[i]为true表示i被DFS过了 

/*Huyyt*/

#include<bits/stdc++.h>

#define mem(a,b) memset(a,b,sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};

const int mod = 1e9 + ;

const int gakki =  +  +  +  + 1e9;

const int N = ( << ) + ;

int n, m, now;

int anser;

bool num[N], vis[N];

void dfs(int x)

{

        if (vis[x])  //如果之前已经DFS到过

        {

                return ;

        }

        vis[x] = true;

        for (int i = ; i < n; i++)

                if (x & ( << i))  //DFS每个二进制比X少一位1的数保证main循环中不会被循环到

                {

                        dfs(x ^ ( << i));

                }

        if (num[x])  //如果X是存在的 找所有X对立面的数

        {

                dfs(( << n) -  - x);

        }

}

int main()

{

        cin >> n >> m;

        for (int i = ; i <= m; i++)

        {

                scanf("%d", &now);

                num[now] = true;

        }

        for (int i = ( << n) - ; i >= ; i--)

                if (!vis[i] && num[i])  //如果有存在的数且没有被DFS到

                {

                        anser++;  //连通块答案数+1

                        dfs(( << n) -  - i); //DFS全部与i连通的数

                }

        cout << anser << endl;

        return ;

}

Codeforces 987 K预处理BFS 3n,7n+1随机结论题/不动点逆序对 X&Y=0连边DFS求连通块数目的更多相关文章
  1. 图-用DFS求连通块- UVa 1103和用BFS求最短路-UVa816。

    这道题目甚长, 代码也是甚长, 但是思路却不是太难.然而有好多代码实现的细节, 确是十分的巧妙. 对代码阅读能力, 代码理解能力, 代码实现能力, 代码实现技巧, DFS方法都大有裨益, 敬请有兴趣者 ...

  2. C. Edgy Trees Codeforces Round #548 (Div. 2) 并查集求连通块

    C. Edgy Trees time limit per test 2 seconds memory limit per test 256 megabytes input standard input ...

  3. 中矿新生赛 H 璐神看岛屿【BFS/DFS求联通块/连通块区域在边界则此连通块无效】

    时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 32768K,其他语言65536K64bit IO Format: %lld 题目描述 璐神现在有张n*m大小的地图,地图上标明了陆地(用 ...

  4. Codeforces Round #222 (Div. 1) Maze —— dfs（连通块）

    题目链接:http://codeforces.com/problemset/problem/377/A 题解: 有tot个空格(输入时统计),把其中k个空格变为wall,问怎么变才能使得剩下的空格依然 ...

  5. K - Ancient Messages(dfs求联通块)

    K - Ancient Messages Time Limit:3000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu Subm ...

  6. Educational Codeforces Round 1D 【DFS求联通块】

    http://blog.csdn.net/snowy_smile/article/details/49924965 D. Igor In the Museum time limit per test ...

  7. 求连通块个数 - BFS、DFS、并查集实现

    本文基于leetcode的200.岛屿数量(题目

  8. 求连通块的面积 - BFS、DFS实现

    本文以Leetcode中695.岛屿的最大面积题目为基础进行展开(题目

  9. Codeforces Round #375 (Div. 2)——D. Lakes in Berland（DFS连通块）

    D. Lakes in Berland time limit per test 2 seconds memory limit per test 256 megabytes input standard ...

随机推荐
  1. c#端口扫描器wpf+socket

    布局如下 <Window x:Class="PortTest.MainWindow" xmlns="http://schemas.microsoft.com/win ...

  2. 正向代理与反向代理以及Nginx【总结】(转)

    今天在了解Nginx的时候,涉及到反向代理的问题,看到一篇博文写的清晰明了,转载记录一下,后续继续学习,再次感谢博主的分享. 原文地址:https://www.cnblogs.com/Anker/p/ ...

  3. web开发(三) 会话机制，Cookie和Session详解

    在网上看见一篇不错的文章,写的详细. 以下内容引用那篇博文.转载于<http://www.cnblogs.com/whgk/p/6422391.html>,在此仅供学习参考之用. 一.会话 ...

  4. Counter() most_common()

    1 不仅可以统计list中元素的出现次数,也可以对str中的元素进行统计 # collections包中的Counter用于统计str list 中元素出现次数 from collections im ...

  5. ASP.NET MVC 开发随笔（二）

    1.目前在局部视图中使用多个model时候,发现使用IEnumerable的时候,读取不了原来model的内容,所以采用List发现没问题 2． 如果想在JS中使用Razor,则需要在Razor添加& ...

  6. Java servlet和JSP的区别和联系

    Java servlet技术:在Java代码中嵌入HTML JSP技术:HTML输出时比较便捷,就在HTML中嵌入Java代码 Java servlet技术:擅长编写Java代码 JSP技术:擅长页面 ...

  7. SI_WorkShop_V4安装手册

    V4安装手册 第一步 启动workshopV4 解压workshopV4.rar,在解压后的目录中双击eclipse.exe启动workshopV4,启动画面如下图所示:(注:解压后第1次启动速度会慢 ...

  8. Java SE 8 docs——Static Methods、Instance Methods、Abstract Methods、Concrete Methods和field

    一.Static Methods.Instance Methods.Abstract Methods.Concrete Methods ——Static Methods:静态方法 ——Instance ...

  9. Redis 入门 3.2.2 命令

    Redis 入门 3.2 字符串类型 3.2.2 命令 1. 获得符合规则的键名列表 SET key value GET key   SET和GET是Redis中最简单的两个命令,他们实现的功能和编程 ...

  10. 错误：expected initializer before "***"

    今天写了一个程序,编译时报了一个错误:expected initializer before "***"报错的语句只是程序开头的一个变量定义语句,怎么会有这样的错误呢,琢磨了半天也 ...

相关阅读

目录[+]