佛奴儿

未归档

/ 注册

全部文章 / 未归档（共985篇）

hihocoder 1175 拓扑排序二

hihocoder 对于一个节点i来说，如果我们能够先计算出它所有前驱节点的病毒数量，就可以直接推算出它最后的病毒数量了，但是怎么来计算所有前驱节点呢？这就要从图的性质入手了。我们现在的网络是没有环的，对于任意一个节点i，当它将自己所有的病毒都传送出去之后，它自身的病毒数量就不会改变了。那么我们不...

2018-06-13

0 440

hihocoder 1174 [BFS /拓扑排序判断是否有环]

hihocoder 1174 [算法]：计算每一个点的入度值deg[i]，这一步需要扫描所有点和边，复杂度O(N+M)。把入度为0的点加入队列Q中，当然有可能存在多个入度为0的点，同时它们之间也不会存在连接关系，所以按照任意顺序加入Q都是可以的。从Q中取出一个点p。对于...

2018-06-11

0 337

湖南师范大学2018年大学生程序设计竞赛新生赛 A 齐神和心美的游戏【hash】

【链接】：A 【题意】：给你n个数的序列和k。判断是否可以三个数组成k（同一个数可以拿多次）【分析】：每个数vis记录一下。2层循环。两数之和不超过k以及剩下的数出现在序列中那么ok。【代码】： #include <bits/stdc++.h> #define ll long lo...

2018-06-09

0 485

Wannafly挑战赛17 A 走格子【矩阵行走/模拟】

【链接】：A 【分析】：可以设置方向数组和标记数组。当不合法（越界/访问过）就转向，转向可以用now=（now+1）%4 【代码】： #include <bits/stdc++.h> #define ll long long #define pb push_back #define i...

2018-06-09

0 349

CF984 C. Finite or not?【数论/GCD】

【链接】：CF 【题意】：n组样例，对于每组样例，给你三个数p q b，问你p/q在b进制下是不是一个有限小数，是的话输出Finite，否则输出Infinite。【分析】：b的过程是对q约分，那么只要b包含q全部的因子即可。考虑1/q，一定是一个小于等于1的数，考虑将小数转化为b进制的过程，每次将...

2018-06-09

0 344

循环小数与费马小定理

循环小数与费马小定理 17/05/29 22:30:51 | Snakes 背景　　题目出自之前亮灯问题、杨辉三角与Sierpinski三角形提及的生日题中的第三、四、五题。题目　　第三题　证明：对于任意非\(2, 5\)倍数正整数\(n\)且满足\(n>1\)，均存在正整数\(k, ...

2018-06-09

0 387

CF982 C Cut 'em all!【树/DFS/思维】

【链接】：CF982C 【题意】：有一颗树，你需要切掉一些边，使这颗树分拆成若干个节点为偶数的联通分量，最多能切掉几条边。若不能切,输出-1。【分析】： 1.若点数n为奇数，因为奇数不可能分为偶数，那么一定输出-1 2.若点数n为偶数，偶数=偶数+偶数。就从顶点1开始，当作父顶点开始dfs。d...

2018-06-09

0 421

子树的结点个数

有一个棵树，树上有 n 个结点。结点的编号分别为 1…n，其中 1 是树的根结点。现在希望你帮忙计算每个结点作为根结点的子树分别有多少结点。输入格式第一行输入一个数字 n，代表树上结点的个数。（2≤n≤1000）接下来的 n−1 行，每行俩个数字 a，b，代表结点 a 到结点 b 有一条边。输...

2018-06-09

0 554

CF988 D. Points and Powers of Two【hash/数学推理】

【链接】：CF 【题意】：从一堆数中选一个最大子集，使得任意两个数相减的绝对值都是2的幂。【分析】：首先很难的一点，需要想到子集最多只能有三个，四个及以上的子集一定不存在（可以证明）。当有三个元素时，则必有其中两对元素之差相等。【代码】： #include<bits/stdc++.h...

2018-06-07

0 363

回溯法练习【BFS/DFS】

1.N皇后问题 2.油田问题 3.素数环问题 4.马踏棋盘问题 5.图的m着色问题 6.01背包问题 7.TSP问题【Code-1:输出N皇后方案和个数】 #include<bits/stdc++.h> using namespace std; typedef long long ...

2018-06-05

0 395