[一个脑洞] Candy?'s 不饱和度

2023-11-22 05:10
文章标签 脑洞 饱和度 candy

本文主要是介绍[一个脑洞] Candy?'s 不饱和度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

update 2017.7.10

Candy?'s 不饱和度

题目背景

化学老师让同学们出题!昌老师担任有机组组长!

Candy?出了一道数不饱和度的题目,昌老师不会做所以拒绝接受!!!

于是Candy?又出了一道\(Polya定理\) 数卤代烃个数的题目,然后把原来这道题扔给了你。


题目内容

你有一个有多个环的烷烃的键线式,求他的不饱和度。

值得注意的是,键线式的C原子并没有标出来,并且线可能是直线、斜线或者曲线,上面的C原子数目不定。

下面有几个例子,其中X表示线,0表示空:

  1. 1 7
    XXXXXXX

    是一个饱和链烃,不一定有几个C,不饱和度是0.
  2. 4 7
    XXXXXXX
    XOOOOOX
    XOOOOOX
    XXXXXXX

    最简单的情况就是一个4个C的环烷烃,不饱和度为1.

  3. 3 7
    XXXXX00
    0X0X0X0
    00XXXXX

    这是一个有两个环的烃,不饱和度是2

    它可能张这个样子

    cc

  4. 4 7
    000X000
    00X0X00
    0X000X0
    0XXXXX0

    她的不饱和度是1,样子自行脑补,我懒得画了。


输入输出 & 数据规模

输入一个n行m列的矩阵,X表示线,0表示空,是一个有机物的键线式。输出他的不饱和度

\(n,m < 1000\)


样例

Sample Input

4 7
XXXXXXX
XOOOOOX
XOOOOOX
XXXXXXX

Sample Output

1

下面是题解和标程

meow


题解

最初的想法来自2016.6.26

那时候觉得复杂环式结构的烷烃不饱和度好神奇,从图论的角度考察了一下,还写了一篇周记。

一年后做化学题又想到了这个东西,拿着它去考灰哥有没有忘记我的周记,结果他随手用了另一种方法,好快好有趣,貌似正确性有待商榷。我尝试卡了一下,发现好像只有平面图成立,然后证明了一下成功了。

后来我发现那就是欧拉公式,并且我的证明和他一模一样,如果我早出生是不是可以叫Candy?公式.......

扔定理就跑:

定理1:任意一个烷烃可以看成无向简单图\(G(V,E)\),那么他的不饱和度为
\[ \mid E\mid - \mid V\mid +1 \]
其中\(V\)是点集,\(E\)是边集

定理2:如果由烷烃得到的图\(G\)是平面图,那么
\[ 它把平面划分成的区域数(除去最外围平面) = \mid E\mid - \mid V\mid +1 \]
平面图就是能画在平面上使得边仅在顶点处相交的图。

证明去看欧拉公式的吧,不想写。

这样一来对于化学题,一眼就看出不饱和度了。

但是出成OI题的话,如果标出C的位置可以用数分子式的方法很快水过去,所以才变成不确定C原子,这样的话就需要得到上面的定理然后搜一下0组成的连通块数就好了,小心外圈的0没有连起来

大多数人应该不会这个方法吧,昌老师就不会

Candy? : 你怎么知道这个方法的 (惊恐)

某冰 : 不就应该是这样吗 (一脸鄙视)


标程

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 105;int n, m, ans;
char s[N][N]; int dfc, vis[N][N];
inline bool valid(int x, int y) {return x >= 0 && y >= 0 && x <= n && y <= m && s[x][y] != 'X' && !vis[x][y];}
void dfs(int x, int y) {vis[x][y] = dfc; if(valid(x-1, y)) dfs(x-1, y);if(valid(x+1, y)) dfs(x+1, y);if(valid(x, y-1)) dfs(x, y-1);if(valid(x, y+1)) dfs(x, y+1);
}
int main() {freopen("in", "r", stdin);scanf("%d %d", &n, &m);for(int i=1; i<=n; i++) scanf("%s", s[i]+1);n++; m++;for(int i=0; i<=n; i++) for(int j=0; j<=m; j++) if(s[i][j] != 'X' && !vis[i][j]) dfc++, dfs(i, j);printf("%d", dfc-1);
}

转载于:https://www.cnblogs.com/candy99/p/7137959.html

这篇关于[一个脑洞] Candy?'s 不饱和度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/407734

相关文章

CF C. Candy Store

原题链接:Problem - C - Codeforces 题意:多测,先给出n代表n种糖果,每种糖果分别给出数量和单价,可以将糖果平均分成若干袋,每一袋的的价格是一袋糖果数量×单价,对于每一种糖果都求出一袋的价格,对于每种糖果都需要用标签贴出一袋的价格,但是如果相邻的糖果价格相同,那么就可以用一个标签来代表价格,问最少使用几个标签。 思路:如果一段糖果价格是一样的,那么设置价格为cost。因

[开源]Qt图片调整之饱和度调节

原理较简单不作详述   QImage AdjustSaturation(QImage Img, int iSaturateValue){int red, green, blue, nRed, nGreen, nBlue;int pixels = Img.width() * Img.height();unsigned int *data = (unsigned int *)Img.bits()

POJ 3083Children of the Candy Corn(DFS*2+BFS)

题目地址:http://poj.org/problem?id=3083 这道题整体思路并不难,但一些细节方面有点难想。。主要是容易写的太麻烦,太乱。。虽然我的代码也比较长,但是思路还是挺清晰的(基本就是把上一段的复制下来稍微改改。。)。但是有些细节方面一开始想错了,导致调试了很长时间。主要思路是记录4个方向然后改变方向走。 题目意思是输出往左绕的步数与往右绕的步数,还有最短步数。前两个用DFS

codeforces #436 A Feed with Candy(贪心)

题目地址:http://codeforces.com/contest/436/problem/A 自己笨的要死。。。WA了好多次,还是看题解才明白了。。。一直在纠结该先选0好还是先选1好,但是就是没想到可以枚举这两种情况都试一试。。。 分别枚举这两种情况,然后每次选的时候从另一种糖果里从可以够到的糖果里选出m最大的那个,贪心就可以了。 代码如下: #include <iostream>

723. Candy Crush

https://leetcode.com/problems/candy-crush/description/ 题目大意:就是消消乐,横竖数字相同且连起来大于3的消掉. 解题思路:暴力法,遍历每个位置,然后检查是否有横竖连续大于3的,有就将该位置记录在to_crash中.然后对 to_crash中的点进行处理,直到to_Crash为空.画图模拟比较好理解. 代码: class Solutio

Codeforces 400C Inna and Huge Candy Matrix(模拟)

题目链接:Codeforces 400C Inna and Huge Candy Matrix 题目大意:给出n,m,x,y,z和p,表示在一个n*m的矩阵上有p块糖果,给出p块糖果的坐标,然后将整个矩阵顺时针旋转x次,镜像翻转y次,逆时针旋转z次,然后按照顺序输出操作完后糖果的坐标。 解题思路:模拟,注意旋转完,n和m要交换,翻转不用,然后如果纯模拟肯定超时,很容易发现旋转4次等

hdu 5291 Candy Distribution(dp)

题目链接:hdu 5291 Candy Distribution 每次先计算出dp[0],然后根据dp[0]的数值可以用o(1)的复杂度算出dp[1],以此类推。总体复杂度为o(200 * 80000),可以接受。 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;cons

【脑洞大开】Typora Plugin给你的Typora插上翅膀

很厉害的插件,好几个都是我想有但是没有支持的插件,比如标签页,全局关键字高亮 目前支持的功能: 序号插件功能1window_tab标签页管理2search_multi全局多关键字搜索3multi_highlighter多关键字高亮4collapse_paragraph章节折叠5collapse_list列表折叠6collapse_table表格折叠7md_padding中英文混排优化8slash

SICP学习笔记——丘奇计数与“数”的本质【脑洞大开】

丘奇计数与“数”的本质 学习SICP有一段时间了,对Lambda表达式以及过程为参数等特性的强大并没有概念,直到看到习题2.6中提到的丘奇计数(Church counting),才有种脑洞大开,恍然大悟的赶脚,便迫不及待的和大家分享一下——尼玛,原来“数”还可以这样玩! 首先,题目抛砖引玉,丢出了两个定义,一个是0的定义:   (define zero(lambda (f)(lambda (x)

激活函数原函数和导数的绘制及饱和度-- 021

微信公众号:python宝关注可了解更多的python相关知识。若有问题或建议,请公众号留言; 内容目录 一、激活函数简介二、Sigmoid三、tanh四、ReLU      五、其它激活函数及饱和度 一、激活函数简介     深度学习的发展一般分为三个阶段,感知机-->三层神经网络-->深度学习(表示学习)。早先的感知机由于采用线性模型,无法解决异或问题,表示能力受到限制。为此三层神经网络