- 博客(315)
- 资源 (4)
- 收藏
- 关注
RSS订阅原创 Gym - 102040F - Path Intersection （树链剖分）
类似 hdu3966#include <bits/stdc++.h>using namespace std;const int maxn = 10000+10;struct Edge{ int to,next;} edge[maxn*2];int head[maxn],tot;int top[maxn];int fa[maxn];int deep[max...
2019-08-12 18:55:00
410
原创 HDU - 5547 - Sudoku (dfs)
思路:纯暴力会超时，每次填的时候需要判断当前行列是否满足情况，最后判断2x2的是否满足即可ps：一定不要忘了回溯#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#include <...
2019-08-05 19:06:31
320
原创 HDU - 5546 - Ancient Go （dfs）
题意:点代表空格，相同棋子上下左右相连为一个分量，当一个分量不与点相连的时候这个分量就是死的，题目先把o死的分量去除，再把x死的分量去除，这之后再下一个x问能不能使一个o分量dead，最后这个就是判断有没有o分量所连的点只有一个思路:搜索三次即可#include <iostream>#include <cstdio>#include <cmat...
2019-08-05 18:44:24
273
原创 HDU - 6386 - Age of Moyu (BFS分层+DFS 或者 最短路+set)
题意:连续相同类型的边花费为1，走不同的边花费加一，求最少花费BFS：维护当前最少花费，每次往外扩展一步即可最短路:set记录到达改点的边的类型都有哪些(距离相同)，如果出现更小的则清空，否则若相同，加入集合。 在进行距离更新时判断一下set里有没有当前类型的边即可BFS#include <bits/stdc++.h>using namespace std;...
2019-08-01 16:57:52
242
原创 Gym - 101170F - Free Weights (二分)
思路:二分重量，判断删除后大于重量的哑铃是否相等#include <bits/stdc++.h>using namespace std;int n;const int maxn = 1e6 +10;set<int> se;int a[maxn];int b[maxn];vector<int>v;bool check(int id){...
2019-07-31 15:42:27
177
原创 POJ - 1236 Network of Schools (tarjan)
题意:一个点能影响到之后的所有点，问最少给几个点施加影响能使所有的点都收到影响以及最少连几条线能使得给一个点施加影响就能使所有点都受到影响思路:第一个问就是求强连通分量的数量第二问，我们需要求没有入度和没有出度的联通分量各有多少，取最大值即可。因为我们必须保证所有的联通分量间可达#include <iostream>#include <algorithm&...
2019-07-29 09:25:46
153
原创 Gym - 101350G - Snake Rana (容斥)
思路:学习了网上大部分思路，总结如下:多加零行零列,这样相当于n+1行，m+1列，一共能形成的长方形数，就是从行中挑两条线，从列中挑两条线相交形成的一矩形然后减去包含奇数个炸弹点的矩形区域，加上包含偶数个炸弹点的区域。区域用左下和右上点表示，然后行的两条线就是从最小行以下和最大行以上挑选了，列同理#include <bits/stdc++.h>using names...
2019-07-26 17:03:07
145
原创 Gym - 101350I - Mirrored String II （马拉车）
题意：求最长回文子串，但每个字母也必须是回文的思路：马拉车，但奇数长度的回文串需要特判#include <bits/stdc++.h>using namespace std;const int maxn = 1100;const int inf= 0x3f3f3f3f;int n,m;set<char> se;char s[maxn];ch...
2019-07-26 16:12:32
188
原创 Gym - 101350E - Competitive Seagulls (博弈)
思路:第一次取，使得左右两端一样，这样，我们一直模仿b取就会获胜。耻辱啊，记录下吧#include <bits/stdc++.h>using namespace std;int main(){ int t; cin>>t; while(t--) { int n; cin>>n;...
2019-07-26 16:04:54
198
原创 Gym - 100829C - The Fox and the Owl(模拟&& 思维)
题意：给你一个数n，求位数和比n的位数和大一的且与n最接近的的比n小的数。思路：见注释#include <bits/stdc++.h>using namespace std;string s,ss;const int maxn = 1e5+10;const int inf =0x3f3f3f3f;int a[maxn];bool judge(int in...
2019-04-21 18:02:19
182
原创 HDU - 5438 - Ponds (拓扑排序&&并查集)
题意：题意：有n个池塘和m个管道；每个池塘的价值是v， 现在要删除池塘，删除的池塘必须是最多只连接一个管道，否则会爆炸；求最后相连的池塘是奇数个的价值总和是多少。思路：拓扑排序后求和#include <bits/stdc++.h>using namespace std;const int maxn = 1e4+ 7;typedef long long ll;c...
2019-04-21 17:15:35
204
原创 HDU - 6228 - Tree (dfs)
思路：若想某个点被访问，则这个点的左右两端都得有不小于k个点。因此，dfs，得出某个点的一端点的数量，判断即可#include<bits/stdc++.h>using namespace std;const int maxn =2e5+10;int n,k,h[maxn],ans;vector<int> g[maxn];int dfs(int m)...
2019-04-19 19:48:48
174
原创 POJ - 1696 - Space Ant （极角排序）
思路：先找左下点，然后排序找其右下第一个点，重复即可#include <iostream>#include <cmath>#include <algorithm>using namespace std;const double eps = 1e-8;int pos;int sgn(double x){ if(fabs(x) <...
2019-04-17 20:18:21
271
原创 HDU - 1811 - Rank of Tetris (并查集&&拓扑排序)
思路：先把‘=’的数合并成一个，然后拓扑排序，如果拓扑过程中可选择点的数量超过一个，则信息不完全。如果有环，说明冲突，那么num就不会到0.#include <bits/stdc++.h>using namespace std;const int maxn = 1e4 + 10;int n,m,fa[maxn],X[maxn * 2],Y[maxn * 2];i...
2019-04-17 19:38:04
161
原创 HDU - 1426 - Sudoku Killer (dfs)
思路：dfs即可，赋值前先判断是否可以#include <bits/stdc++.h>using namespace std;struct point{ int x, y;}p[81];int num, flag, G[10][10];int judge(int n, int k){ int i, j, x, y; for(i = 0;...
2019-04-17 12:05:23
193
原创 HDU - 1142 - A Walk Through the Forest (最短路+dfs)
题意：终点到B和A有多少条路径，且终点到B的距离小于A#include <bits/stdc++.h>using namespace std;const int maxn = 1e3 + 10;const int inf = 0x3f3f3f3f;int G[maxn][maxn];int dis[maxn];bool vis[maxn];int p[maxn...
2019-04-16 19:29:10
175
原创 ZOJ - 4067 - Books （思维）
题意：能买则买，不买看下一个，给出一共卖了多少，问这个人最多可能有多少钱思路：注意价格为0不需要付钱，所以需要提前计算0的个数。然后买前几个书，加上后面最低价钱的书就是答案#include <cstdio>#include <algorithm>using namespace std;typedef long long ll;const int m...
2019-04-10 20:34:16
315
原创 ZOJ - 4057 - XOR Clique （思维）
题意：求一个最大团，使得其中任意两个数的异或都比这俩数要小。思路:只要二进制位数一样，异或的值都比这俩数要小；二分查找减少时间复杂度。队友代码：#include <bits/stdc++.h>#define _for(i,a,b) for(int i=a;i<b;++i)#define _rep(i,a,b) for(int i=a;i<=b;...
2019-04-10 20:10:34
188
原创 ZOJ - 4056 - Press the Button (模拟)
题意：问有效press次数，有效是指灯亮的时候有效思路：模拟时间器#include <bits/stdc++.h>using namespace std;typedef long long ll;ll a,b,c,d,t, v;ll shinetime_;long long cnt;int main(){ int T; cin>&g...
2019-04-10 19:51:08
307
原创 ZOJ - 4049 - Halting Problem (模拟)
题意：按照题意模拟，如果能进行到n+1步，则yes，否则如果无限循环，则no；思路：记录一下每一步对应的状态，如果重复访问，则重复。一定要用bool类型！！！#include <bits/stdc++.h>using namespace std;const int maxn = 1e4 + 3;int t,n;int v[maxn];int k[maxn...
2019-04-10 19:01:13
214
原创 HihoCoder - 1871 - Heshen's Account Book （字符串模拟）
题意：寻找不能有前导字母和后续字母且不能有前导0的数字，上一行的末尾如果能和下一行连起来，要一起算。思路：把所有字符串连接起来一起处理。坑点：单独的0要算一个数字；如果没有数字，则不需要输出空行。#include <bits/stdc++.h>using namespace std;const int maxn = 200+10;const int N = ...
2019-04-03 20:35:51
267
原创 HihoCoder - 1878 - Palindromes （规律）
题意： 输入n，打印第n个回文数，n最多10万位。思路：构造似乎不太可能，因为位数太多了，于是考虑n和回文数之间的联系，即打表找规律。发现，如果首位不是1，那么回文数首位分别为首位减一，中间的数为n剩下数进行回文操作。如果首位是1，又分为第二位是0和不是0的情况，是0的话，那么把n除去首位进行回文化即可，否则，所求回文数首尾位为9（也就相当于之前首位为10的情况），其余如旧进行回文化。...
2019-04-03 19:10:32
295
原创 L2-2 玩转二叉树 （25 分)
L2-2玩转二叉树（25分)给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。输入格式：输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。输出格式：在一行中输出该树反转后的...
2019-03-26 10:21:53
433
原创 天梯赛练习 L2-1 排座位 （25 分) （并查集）
布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。输入格式：输入第一行给出3个正整数：N（≤100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：宾客1 宾...
2019-03-26 10:14:00
159
原创 HDU - 1595 - find the longest of the shortest （最短路）
题意：去掉一条边的最短路中最长的是多少。不需要全部枚举，只需枚举最短路中的边即可，因为去掉一条边相当于距离无限大，最短路还是原来的，只有改变最短路中的边才有可能改变最短路的大小。#include <bits/stdc++.h>using namespace std;const int maxn = 1010;const int inf = 0x3f3f3f3f;i...
2019-03-14 16:36:02
217
原创 二叉搜索树
判断两序列是否为同一二叉搜索树序列耻辱题啊。建树时一定要传引用！建树时一定要传引用！建树时一定要传引用！若两个树的前序遍历和中序遍历都相同，则他们是同一棵树。给出两个方法：#include <bits/stdc++.h>using namespace std;string s1,s2,str;string str1,str2;typedef str...
2019-03-14 08:48:06
159
原创 HDU - 2102 - A计划 (BFS)
题意：两层地图，只有通过时空传输机才能在两层之间移动，问能否在规定时间移动到'P'#include <iostream>#include <queue>#include <string.h>using namespace std;const int maxn = 100 + 10;char G[2][maxn][maxn];int n,m,...
2019-03-12 17:08:42
155
原创 POJ - 2955 - Brackets(区间dp)
思路：dp[i][j] 表示 i到j内的最大匹配数。更新：如果s[i] 和 s[j] 相匹配，则dp[i][j] = dp[i+1][j-1] + 2；#include <iostream>#include <string.h>using namespace std;const int maxn =110;int dp[maxn][maxn];str...
2019-03-12 16:11:25
117
原创 NCPC 2014 H Clock Pictures（KMP）
题意：给出两个时钟上相对于某个固定位置的n个点的距离，判断两钟是否是同一时刻。思路：排序后，找相邻之差，然后kmp匹配。#include <bits/stdc++.h>using namespace std;const int maxn = 2e5 + 10;int a[maxn],b[maxn];int next_[maxn],n;int dvalue1[2*ma...
2019-03-12 09:31:53
225
原创 CSU1576---Catalan Square(卡特兰数&&大整数)
思路：关于卡特兰数：递推公式：C(n)=C(n-1)*((4*n-2)/(n+1));import java.math.BigInteger;import java.util.*;public class Main { public static void main(String[] args) { String s, L; BigInteger Catalan[]...
2019-03-12 08:22:35
300
原创 HDU - 6222 - Heron and His Triangle （规律）
打表：#include <bits/stdc++.h>using namespace std;int a[101];int main(){ for(long long i = 4 ; i < 1000000000000; i++) { double p = 1.0 * 3 * i / 2.0; int ans =...
2019-03-10 14:27:59
144
原创 HRBUST - 1818 - 石子合并问题--直线版 （区间dp）
题意：相邻石堆可以合并，每次合并花费为石子数和，问最终合并为一堆时的花费最少和最多分别是多少思路：先枚举区间长度，在枚举端点。端点将区间分为两个，然后合并。dpn[i][j] = min(dpn[i][j],dpn[i][k] + dpn[k+1][j]+sum[j]-sum[i-1]);表示 在该长度内任意两个区间合并所求的最小值。#include <iostre...
2019-03-08 11:24:19
359
原创 HYSBZ - 2763 - 飞行路线 （最短路）
题意：在可选择k个边花费为0的情况下求最短路思路：最短路dis数组增加一维表示使用免费的次数，判断最短路时，分两种情况，使用免费次数或不使用。#include <bits/stdc++.h>using namespace std;const int inf = 0x3f3f3f;const int maxn = 1e5 + 10;struct Edge//邻接表{...
2019-03-07 20:42:43
367
原创 ACM---差分
差分就是将数列中的每一项分别与前一项数做差，例如：一个序列1 2 5 4 7 3，差分后得到1 1 3 -1 3 -4 -3这里注意得到的差分序列第一个数和原来的第一个数一样（相当于第一个数减0）差分序列最后比原序列多一个数（相当于0减最后一个数）性质：1、差分序列求前缀和可得原序列2、将原序列区间[L,R]中的元素全部+1，可以转化操作为差分序列L处+1，R+1处-1...
2019-02-13 19:25:19
8241
2
原创 HDU - 5887- Herbs Gathering（搜索/剪枝）
题意：n个物品，时间限制m；给出每个物品的价值和时间；求在m限制内，最多的价值。 #include <bits/stdc++.h>using namespace std;const int maxn = 200;typedef long long ll;struct Node{ ll x,y; bool operator < (...
2019-02-08 22:07:27
298
原创 UVALive - 8292 - Best Rational Approximation （二分）
//从最大最小开始二分，直到分母超m，取两边较小#include <bits/stdc++.h>using namespace std;int main(){ double p; int t,k,m; cin>>t; while(t--) { cin>>k >>m>>p;...
2019-02-06 21:38:31
195
原创 UVALive - 8290-Capsules(dfs)
题意：给出方格大小以及某一些已填数字，需要我们自己填数字，要求，相同数字不相邻，包括斜的，在给定的区域内刚好用够1-n几个数字思路：搜索即可#include <bits/stdc++.h>using namespace std;const int maxn = 100;int ma[maxn][maxn],indexx[maxn][maxn],number[ma...
2019-02-03 22:39:08
229
原创 HTML+CSS ----- css样式设置小技巧
水平居中设置-行内元素我们在实际工作中常会遇到需要设置水平居中的场景，比如为了美观，文章的标题一般都是水平居中显示的。这里我们又得分两种情况：行内元素 还是 块状元素 ，块状元素里面又分为定宽块状元素，以及不定宽块状元素。今天我们先来了解一下行内元素怎么进行水平居中？如果被设置元素为文本、图片等行内元素时，水平居中是通过给父元素设置 text-align:center 来实现的。(父元...
2019-02-03 20:45:23
188
原创 HTML+CSS ----- CSS代码缩写，占用更少的带宽/单位和值
盒模型代码简写还记得在讲盒模型时外边距(margin)、内边距(padding)和边框(border)设置上下左右四个方向的边距是按照顺时针方向设置的：上右下左。具体应用在margin和padding的例子如下：margin:10px 15px 12px 14px;/*上设置为10px、右设置为15px、下设置为12px、左设置为14px*/通常有下面三种缩写方法:1、如果top...
2019-02-03 20:07:03
220
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人