- 博客(49)
- 问答 (1)
- 收藏
- 关注
RSS订阅
转载 POJ题目分类推荐 （很好很有层次感）
（有超链接的是写了题解的） POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)初期:一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) ...
2018-08-15 15:51:45
2775
转载 转载 正则表达式
原文链接https://blog.csdn.net/yanbober/article/details/45556185一、正则表达式语法正则表达式包括普通字符（例如字符 a 到 z）、非打印字符（例如\n）、特殊字符（称为"元字符"）、限定符（例如{n,m}）和定位符（例如^）。1.1 普通字符普通字符包括所有大写和小写字母、所有数字、所有标点符号和一些其他符号。1.2 非打印字符非打印字符也可以是正则表达式的组成部分。下表列出了表示非打印字符的转义序列：字符 描述
2020-07-11 17:31:32
181
原创 天题赛题目练习 L1-006连续因子
PTA传送门其实就是暴力，以i=2为连续因子的起始部分一直枚举到以i=根号n为开始的情况，同时从j=i+1枚举结尾到哪个数字停下。因为12！就已经超过了int的范围，所以这个二重循环的循环次数并不多可以暴力。因为要输出最长，且因子数最小的情况所以是j-i+1>n才更新长度和起始位置，不可以是>= 。 ！！！我为什么现在还会被这种题卡。。。#include <b...
2019-03-09 15:47:34
132
原创 hdu1575 矩阵快速幂 模板题
传送门题意：求给定n维方阵的k次幂后的对角线元素和思路：模板题代码如下：#include <bits/stdc++.h>int N;//N个系数，N维矩阵typedef long long ll;using namespace std;struct matrix{ int m[20][20];};matrix ans, base, m;matr...
2018-10-13 00:00:37
388
原创 2018ACM-ICPC焦作网络赛 G.Give Candies
传送门题意：N个糖，N个人，一个人可能有多块糖也可能一个也没有，问有多少种分法。思路：用隔板法的思想，n个隔板代表N个糖被分成n+1堆，即分给n+1个人，那么让n的范围是1~N-1。二项式定理，c(n-1,0)+c(n-1,1)+……+c(n-1,n-1)=2^(n-1) 。所以只要输出2的n-1次方对mod=1000000007取模就好了。关键是n很大很大啊。网上的通...
2018-09-26 18:28:05
196
原创 2018 ICPC Asia Qingdao Regional Contest, Online 青岛，C Halting Problem 模拟 + 卡常
传送门题意：图灵测试是判断一个程序能不能最终停止运行，还是永远循环下去的一个概念。给你n行命令，一个变量r初始时为0，每次add后都对256取模，除了add相加命令外其余的都是判断符不符合某条件来决定跳转去第k行执行命令还是不跳转继续执行下一行命令。如果程序最终会试图执行n+1行输出yes，否则输出no。思路：对每行命令存一下它此时的r的值，当r的值和以前执行这次命令时的值一样，就...
2018-09-17 20:38:05
321
转载 Codeforces Round #506 (Div. 3) C.Maximal Intersection 区间最大交集
传送门 （队友写的题我直接转载了hhh）题意：给你n个用左右端点表示的区间，问在一定去掉并且只去掉一个区间的情况下如何让剩下的区间的交集最长。思路：n个区间最终的交集是由含最大左端点的区间和含最小右端点的区间确定的。 因此只要找出这两个区间，判断一下删掉哪个区间所得的交集更长即可。 注意，还要特判一下，如果最大左端点和最大右端点在一个区间时，直接删除此区间即可。代码如下：...
2018-09-14 22:11:35
360
原创 hdu2067 小兔的棋盘 （卡特兰数模板题）
传送门~题意：从左下角走到右上角的不越过对角线的最短路径的种类数。思路：参见我的那篇卡特兰数全家桶的博客。这道题没说是先往上走再往右还是反过来，所以要输出h[n]*2 。代码如下：#include <iostream>#include <cmath>#include <ctime>#include <cstdio>#...
2018-09-13 17:33:44
226
原创 您好，这是您的卡特兰数全家桶套餐
本文为转载+整理，原博写的超级清楚，感谢~原文地址(们)：https://blog.csdn.net/wu_tongtong/article/details/78161211https://blog.csdn.net/han_xiaoyang/article/details/11938973https://blog.csdn.net/zuzhiang/article/details...
2018-09-13 17:12:35
237
原创 2017ACM-ICPC北京区域赛 E - Cats and Fish
传送门题意：开局三个数，m条鱼，n个猫，x时间，接下来一行是每只猫吃掉一条鱼分别花费的时间。如果有多只猫可以吃鱼先把鱼分给吃的快的猫。问在x分钟后这m条鱼还剩下多少完整的，剩下多少不完整的（猫还没吃完）思路：直接模拟。对每只猫吃鱼时间排序。num表示已吃完的鱼数，ans为正在吃的鱼数，设一个标记数组标记每只猫是不是正在吃鱼，它没有吃鱼才能给它分配新的鱼。对于每一分钟循环每一只猫的吃...
2018-09-11 19:26:23
495
原创 ACM-ICPC 2015 Changchun Preliminary Contest (G.) The Water Problem
传送门题意：找区间最大值思路：签到题，题量很小直接模拟，细心一点别出bug就ok（我竟然还多此一举的ans数组保存答案来优化）#include <stdio.h>#include <iostream>#include <algorithm>#include <string.h>#include <cmath>usi...
2018-09-10 17:46:34
159
原创 ACM-ICPC 2015 Changchun Preliminary Contest （A）. Alisha's Party
传送门题意：有k个人去参加聚会并且拿着一定价值的礼物，主人一共开m次门，并且每次都要等到第ti个人到场才开门，每次开门放进来已经到场的人中的pi个人。谁的礼物贵谁先进来，礼物一样贵的谁先到谁先进。如果开门m次后还有人没进来，就一次性让他们全部进来。题目会给你这k个人到场的顺序和他们拿了多少钱的礼物。给你q次询问，输出第qi个进来的人是谁。思路：很直白的优先队列。push和pop模拟...
2018-09-10 17:41:29
181
原创 UVA1646Edge Case 算大整数的斐波那契
题意：给你一个数字n（n<=10000），问在一个正多边形内，取任意数目的边（可以取0条边）并且这些边没有公共顶点，问有多少种取法。 思路：我在数n=5的情况时数错了，就一直没没找到规律...对着自己算出来的诡异的答案往组合数那边想了半天。突然发现，例子算错了暴风哭泣。这种例子写错找不出规律的智障错误犯了很多次了，以后一定要注意！！！！其实答案就是一个斐波那契数列，比如f...
2018-08-29 15:31:30
273
原创 POJ_4028_GCD Guessing Game 素数分组
vj链接 poj链接 不知道为什么poj点进去题目样例什么都没有。。。题意： 给定一个数N，现在又一个数x，在1~N之间，现在每次可以猜一个数a，返回gcd(x,a),问说最少猜几次可以确定x。思路： 这个题应该可以算是贪心，但是没人知道这样为啥是对的（雾），我们现在来感性认识一下，我们知道对于任意一个数都可以写p1e1p2e2 … 的形式，所以我们在每一次询问都可以确定有些p是否...
2018-08-23 21:36:34
255
原创 POJ_3292_Semi-prime H-numbers重定义素数筛
原题链接题意：H_number是1，5，9……这样间隔为4的数字，假设世界上只有这些数字了。H_prime的因子只有1和它本身（它只能是H_number），H_semi_number有且仅有两个H_prime相乘得到的数。输入一个数H问在1~H的H_number的范围里有多少H_semi_number。思路：其实就是重新定义了素数，自己打表写一个H_prime的素数筛，然后扫一遍记录下来，...
2018-08-23 12:00:00
115
原创 POJ_2635_The Embarrassed Cryptographer同余定理
原题链接题意：给你一个超级大的数K（1e100），这个数是两个大素数相乘得到的。给你一个数L，K的两个素因子中较小的那个如果比L小就输出BAD和那个素因子，否则输出GOOD思路：同余定理。用字符数组储存这个数，按千进制转换后储存在int数组里。 之后同余定理高精度取模。 比如1234%m=(1*1000+2*100+3*10+4)%m=（（（1*10+2）*10+3）*10+4）%m=...
2018-08-22 22:22:52
191
原创 组合数学 POJ 1850 （字符串编号）
原题链接题意： 给出一个严格按字典序升序的字符串（否则非法）每个字符串都比它前一个字符串的对应数字大1。给任意字符串判断是否合法后输出对应的数值。思路： 虽然被归类到poj组合数学里，但是我只有隐隐约约模糊的感觉。直接做做不出来，羞愧。还是看了人家的题解才懂的。对，就是我自己没有清晰的思路//// 这里是dalao很清楚的题解#include &amp;lt;iostream&amp;gt;...
2018-08-22 14:37:23
227
原创 DFS专题_POJ 1321 n皇后变形
原题链接题意：n*n的格子里放k<=n个棋子（不再同一行和同一列）有多少方法。只有标 # 的地方能放棋子。一道蠢题，太蠢了，不要看。#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>using namespace std;in...
2018-08-21 11:20:08
174
原创 Codeforces Round #503 (Div. 2) C. Elections (枚举贪心)
题目链接题意：有n个选民和依次标号的m个政党，每个选民可投一票，也可以花钱收买这个选民让他投你指定的任党派。给你这n个选民原本支持的党派和收买他们的花费，问如何花最少的钱让1号党派胜出（所获选票比其余任意一个党派都多，相等也不可以哦）没什么思路，怎么想都感觉处理各种情况很复杂。研究了别人的代码，发现用的是枚举+贪心。即，从i=1~n枚举1号党在得到i票的情况下胜出的花费，那么此时别的党...
2018-08-20 14:40:35
163
原创 DFS专题_2017CCPC女生赛E题_HDU5706 GirlCat
vj链接题意： 求所给的n行m列又小写字母组成的图里，能组成多少个不同的girl和cat字符串（有一个字母的位置不同就算不同），只能往上下左右走。dfs就可以，1A~代码如下：#include <iostream>#include <cstdio>#include <algorithm>#include <vector>#i...
2018-08-15 19:58:56
244
原创 2017CCPC女生赛B题_HDU5703-Desert
2017ccpc女生赛B题题意： 给你一个数n，n由一些正整数相加构成，有多少中组合方案，输出二进制。比如n=3时，可以为 1，1，1； 1，2； 2，1； 3； 共4种，输出4的二进制100. 可以找规律做，也可以用隔板法，n个1，有n-1个空位，每个空位可以选择是否插入隔板，插入k(0<=k<=n-1)个隔板将n个1分为k+1份。 插入0个隔板则拆成1份，方案数...
2018-08-15 19:21:59
252
原创 DFS专题_POJ 1724 ROADS
poj 1724题目链接题意： 有依次标号的N座城市，R条路（单向），每条路连接两个城市。你只有K元钱，若两城市间有路，给出路的长度和过路的花费。问若城市1出发能到达城市N，走过的最短的道路长度。若无法到达输出-1. 数据： 2<=N<=100 0<=K<=10000 1<=R<=10000 每条路长度L，1<=L<=100 每条路...
2018-08-15 18:22:58
148
原创 DFS专题_UVA572 Oil Deposits
UVA572原文链接 题意： 输入行列数，接下来n行m列每一个字符是‘@’或‘ * ’求@组成的联通块个数。和百练习城堡问题很像。 代码如下：#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#define MAXN 110int...
2018-08-15 15:10:53
84
原创 DFS专题_百练2815：城堡问题
百练2815：城堡问题北大程序设计与算法慕课上的一道题，注意用1，2，4，8这些2的次方数来储存城墙的信息，应联想到二进制的每一位的0或1可以代表那个方向有没有墙。使用和1，2，4，8的按位与就可以。注意运算符顺序！！！一定要随手加括号！！！代码如下：#include &amp;lt;iostream&amp;gt;#include &amp;lt;algorithm&amp;gt;#include &a
2018-08-15 13:04:22
201
转载 poj2480 欧拉函数
题意：给出n（2^31），求∑gcd(i, n) 1&lt;=i &lt;=n。分析：首先所有与n互质的数字x都满足gcd(x,n)=1。我们先计算这种等于1的情况，恰好是n的欧拉函数phi(n)。我们可以将上述情况视为跟n最大公约数为1的情况，现在我们将其推广至最大公约数为p的情况。对于对于所有满足gcd(x,n)=p（p为常数）的x，他们与n拥有相同的gcd，那么他们同时除以p之后，就会变...
2018-08-06 21:17:28
206
转载 欧拉函数euler
对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4，因为1,3,5,7均和8互质。Euler函数通式：euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn)其中p1,p2……pn为x的所有素因数，x是不为0的整数。euler(1)=1（唯一和1互质的数就是1本身）。 欧拉函数的一些性质:1.对于素数...
2018-08-06 16:29:21
642
1
转载 归并排序求逆序数 hdu2018 Multi-University Training Contest 2——1010
原文地址 求逆序数有两种方法：归并排序和树状数组#include&lt;stdio.h&gt;#include &lt;cmath&gt;#include &lt;algorithm&gt;#include &lt;iostream&gt;#define maxn 1000005using namespace std;int a[maxn],temp[maxn]
2018-07-25 14:53:34
215
原创 set应用
Codeforces Round #495 (Div. 2) C题很谜！！怎么想到的！！#include &lt;iostream&gt;#include&lt;cstdlib&gt;#include&lt;cstdio&gt;#include&lt;algorithm&gt;#include&lt;set&gt;#includ
2018-07-24 21:32:34
205
原创 数据结构
线性表（List）:零个或多个数据元素的有限序列。 栈（stack）：限定仅在表尾进行插入和删除操作的线性表。 允许插入和删除的一端称为栈顶（top）另一端是栈底（bottom），栈又称为后进先（Last In First Out）出的线性表，简称LIFO结构。 若存储栈的长度为StackSize则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判...
2018-07-24 21:28:33
82
原创 未解决的诡异问题
诡异的问题，为什么b1和b2不一样？？明明d1和d2的值是相同的#include<iostream>#include<cstdio>#include <cmath>using namespace std;int main(){ float d1,d2; d1=12.9; d1-=8.0; d2=4.9; c...
2018-07-23 15:32:01
90
原创 map简单题（Codeforces Round #496 (Div. 3)___C题）
http://codeforces.com/contest/1005/problem/C#include <iostream>#include <map>using namespace std;int main(){ int n,x,k=0,del=0; map<int,int>c; cin>>n; int a[n]; fo...
2018-07-10 17:07:31
205
转载 STL—— map用法
还有一篇讲map的文章：https://blog.csdn.net/shuzfan/article/details/53115922 应用map的题：http://codeforces.com/contest/1005/problem/Cmap里可以有十几万个不同关键字！！！ map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一...
2018-07-10 15:24:54
100
原创 SOJ 1117 应用string的水题
soj1117string a; cin>>a; cin读入遇到空格就停止！读包含空格的字符串时应 getline(cin,a) 读a直到遇到回车 getline(cin,a,'#');读a直到遇到字符# （也可以换成别的字符）#include <cstdio>#include <cstring>#include <alg...
2018-04-21 16:23:04
119
原创 DFS专题_POJ-2488 (poj分类初级)
poj-2488题意：告诉你你棋盘有几行几列，骑士只能走“日”字格，它可以从任意地方开始走，在任意位置结束。是否存在一条路径让骑士不重不漏地走完所有格子， 如果有多种方式可以不重复走一遍的走完，需要输出按字典序最小的路径。按格式输出这条路径依次经过的那些格子。如果能够不回头走一遍的走完，一定会经过A1点，所以我们应该从A1开始搜索，以确保之后得到的路径字典序是最小的（也就是说如果路径不...
2018-04-11 12:56:45
308
原创 poj-2386 dfs入门水题
poj-2386#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <cstdlib>char mapp[110][110];using namespace std;...
2018-04-11 00:24:09
535
空空如也
poj2159求助 关于字符串的输入问题
2017-09-02
TA创建的收藏夹 TA关注的收藏夹
TA关注的人