- 博客(106)
- 收藏
- 关注
RSS订阅原创 2020牛客多校第二场G_Greater and Greater
题目大意：给定两个数字串A，B，长度分别为n和m，n>=m；问A里面有几个字串S，满足Si>=Bi,(1<=i<=m);a1 a2 a3 a4 a5 a6 a7 b1 b2 b3 1) a1 a2 a3 b1 b2 b3 2) a2 a3 a4 b1 b2 b3 3) a3 a4 a5 b1 b2 b3 4) a4 a5 a6 b1 b2 b3 5) a5 a6 .
2020-07-14 14:10:15
277
原创 M-value-The 2019 ICPC Asia-East Continent Final
题目链接（牛客网复现赛）**知识点：按底数分集合处理+二进制枚举大佬的解析/*选择第i个，选择第j个，如果i^k==j;那么就要减去bj但是可以发现，对于2来说，3不会形成上面的影响；但是4会对2产生影响；2：2，4，8，16，32……3：3，9，27…-----把这些数分成若干集合:但是所选的数x>sqrt（n）的时候有一部分x对后面的数不产生影响，要把这部分数筛...
2020-01-15 22:35:53
339
原创 A Magic Lamp HDU - 3183
这个题方法很简单啊，可是没有考虑0 1这个例子，就wr了整整一下午写个博客纪念一下/*线段树维护区间最小值贪心：每次找可行区域的最小值*/#include<cstdio>#include<cstring>#include<algorithm>#include<string>using namespace std;const ...
2019-11-18 17:18:31
116
原创 博弈论习题
vj题目汇总一，威佐夫博弈：（1）HDU 1527（入门）（2） HDU 2177 （进阶1）（3）51Nod 1185（进阶2）注：进阶1中提处理了输出威佐夫博弈的第一种可行方案的问题；进阶2处理了威佐夫博弈中（黄金比例*大数）精度会损失的问题；补充：威佐夫博弈中，非奇异局势可以通过一步找到奇异局势。二，Nim（尼姆）博弈：Nim博弈：（1）HDU 1850 判断是否获胜...
2019-10-29 21:16:06
437
原创 基于双向循环链表实现的队列
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef bool status;typedef int elmetype;typedef struct node{ elmetype date; struct node *next,*front...
2019-10-27 13:23:00
303
1
原创 数据结构——基于顺序表实现的栈stack
注意：（1）如果我们需要通过函数修改顺序表内的信息，需要传递引用（2）如果我们只是读取顺序表内的内容，只需要传递指针（3）函数返回值使用bool类型，用来返回状态，而其他的值可以使用引用的方式传进来；//stack://(1)creat a stack//(2)destroy a stack//(3)judge empty//(4)push//(5)pop//(6)getto...
2019-10-26 17:03:30
158
原创 Stone Game, Why are you always there? HDU - 2999+（sg函数，博弈论）
先说一下题意：首先给你一个n，然后给你n个数，这n个数，是你可以选择的操作，就是你每次可以连续取的石子数；然后给你一个m，表示有m个k，每个k表示有k个连续的石子，每次进行操作，每次只能连续移动n个数中的值，问谁最后不可以取； #include<cstdio>#include<cstring>#include<algorithm>using n...
2019-10-25 17:49:07
186
原创 Georgia and Bob POJ - 1704
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int num=1e3+10;int a[num];int main(){ int t,n,c,ans; scanf("%d",&t); while(t--) { scanf...
2019-10-24 21:01:36
94
原创 Climbing the Hill HDU - 4315+（阶梯博弈，哈哈，懂了懂了）
题目大意： 给你n个人的位置，以及国王的位置k，从小到大排序后，国王的位置在第k个； 把国王送到低端的人获胜，Alice先，Bob后； 解析过程： 第一个思路是讨论[1,k]和[k+1,n]的情况，然后再综合讨论； 提交的代码wa了，想了想有许多状态没有考虑； 把这个游戏转化成这个样子，再原有基础上，任何人不能超过1这个点，也就是不能爬到最 上面。（也就是这个题的思路了Georgi...
2019-10-24 19:35:37
130
原创 Game HDU - 3389 +（都说这个题是阶梯博弈，什么是阶梯博弈啊？）
题目链接阶梯博弈的链接这道题的思路就有点奇怪，可能是我还没有理解；#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int num=1e5+10;int main(){ int t,n,ans,a; scanf("%d",&t)...
2019-10-24 19:34:53
155
原创 Eight+Poj1072+(康托展开+bfs)
20191024ac之前，超时了n发，怎么改怎么超，程序员日 ac的第一道题。超时原因：（1）map判重（2）同时使用了康托展开和反康托展开，用一个一位数组代替后者，即可；知识点：(1）康托展开（2）string记录路径解题框架：1，读入数据，有太多空格，建议采用scanf一个个读入，scanf遇到空格和回车会停止的；记录初始状态下的x的位置；2，计算出初始状态的hash值，...
2019-10-24 11:36:30
170
原创 Power Calculus+ dfs迭代加深
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int num=2*1e3+10;int n,cnt;bool vis[num];int date[num],f[num];bool dfs(int d,int s){ if(d==cnt...
2019-10-23 14:32:23
117
原创 对于数据量小的数据可以打表输入到文件里
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int main(){ freopen("ans_table.txt", "w", stdout); //就是它 for(int i=1;i<=10;i++) printf("%d,",i);//输...
2019-10-22 22:08:04
91
原创 Find The Multiple+搜索
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;LL n;//题目要求每一位的数字是1或者0；//那么问题是如何寻找呢？//搜索树的如何画呢？ 1->10,1->11;10->100,10-&...
2019-10-22 14:38:31
109
原创 Football Game POJ - 2315（Nim问题的变形，NIMK问题）
//Football Game POJ - 2315#include<map>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int num=1...
2019-10-22 13:53:52
150
原创 Nim or not Nim? HDU - 3032
打表找规律：下面代码里体现了如何打表在题目的规则下：x的子问题包括：[0,x-1]以及（1，x-1），（2，x-2）……………；#include<map>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long ...
2019-10-22 11:23:55
110
原创 A Multiplication Game HDU - 1517+dfs+map+sg函数
dfs更新sg函数，数据long long，采用map处理；//sg函数打表，递归实现过程 #include<map>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int num=10...
2019-10-19 14:51:32
116
原创 大数处理整理
1，大数相乘，溢出long long，快速乘法2，long long 和double 相乘出现的精度损失问题//1//快速乘法//简单版本LL mul(LL a,LL b,LL mod){ LL ans=0; while(b) { if(b&1) ans=(ans+a)%mod; a=(a+a)%mod; b>>=1; } return an...
2019-10-19 11:37:07
94
原创 日常小bug001
void dfs(int n,int len2){if(len>6) return ;dfs(n,len++);}dfs(1,2);//这个神奇的程序会一直循环//赋值时会发生len2=len++;//这样就递归死了
2019-10-17 20:07:26
116
原创 c++里的技巧函数
1，atoi();将字符串转化为int类型的整数https://www.runoob.com/cprogramming/c-function-atoi.html
2019-10-17 18:33:12
107
原创 数电实验_时分秒计数器——终极版
//时分秒计数器（对秒脉冲计数），加上复位、校时功能，加秒矩阵,加显示译码，增加用32768Hz震荡信号CP计数，终极版module clk18(CP,RST,Ch,Cm,Hc,Sh,Sl,W,ddo,pin_50, pin_51);input pin_50, pin_51; //input CP,RST,Ch,Cm,Hc; //32768Hz震荡信号CP，复位，小时校时，分钟校时，...
2019-10-15 08:50:57
1860
原创 ATM+bzoj+Trajan算法+spfa求最短路
题目链接在新的bzoj平台上，目前这道题没有ac的人。我的代码也卡在了12，13的样例上，在网上找了很多的代码，除了一位大佬（卡在12上），其余都是卡在了12，13上。#include<queue>#include<cstdio>#include<cstring>#include<algorithm>using namespace std...
2019-10-12 16:20:32
88
原创 BZOJ1654 奶牛舞会+tarjan算法（入门题目）+判断图中有几个环
题目大意：判断图中有几个环#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int num=10010;/******************/struct node{ int u,v,next;}e[num*5];int hea...
2019-10-12 12:16:41
223
原创 P2860 [USACO06JAN]冗余路径Redundant Paths+tarjan算法+构建全环图
#include<map>#include<vector>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int num=5010;/*------------------*/struct node{ int...
2019-10-12 11:37:32
286
1
原创 P1262 间谍网络+Trajan 缩点（有向图）
题目链接#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int num=3010;const int inf=0x3f3f3f3f;/*------------------*/struct node{ int u,v,next;}...
2019-10-11 16:59:48
109
原创 受欢迎的牛+Trajan缩点+树形dp
题目链接：题目解析：题目数据：100%的数据N<=10000,M<=50000；显然这个图里面会有环，而我们可以做的是：判断这个点是否是其它点的子节点；因此：要把这个图转化为树；用到Trajan算法；在这道题中：可能会出现如下情况：a-->b<--c; | | V（箭头） d 就是有a ，c这两个入度为0的点； 所以要用一个...
2019-10-11 09:42:11
130
原创 HDU2422_考研路茫茫——空调教室_Tarjan缩点+树形dp/判断联通块数量
考研路茫茫——空调教室的题目链接题目数据：N和M(0<N<=10000,0<M<20000)一开始以为是树的重心，结果一直提示超内存，后来看了看题，发现不对，m>n-1啊,不可能是树；肯定有环；但是我们破坏环中的任意一条边，都不会满足题意。所以我们寻找的那条边肯定不在环里，而分开之后，在一个环里的那些点不会分开，所以可以见一个环变成一个点；这样就可以把...
2019-10-10 18:12:35
146
原创 树形dp+01背包例题
树形dp+01背包#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int num=210;struct node{ int v,next;}e[num];struct point{ int p,w;}a[num];i...
2019-10-08 20:13:33
141
原创 Travelling+HDU3001+状压dp+旅行商问题
题目链接题目大意：n个点，m条耗时无向路，问：任意取一点作为起点,最多经过一个点两次，遍历所有的点，需要的最短的时间。数据大小：n<=10；解题方法：状态dp每个点会经过0，1，2次，是只能经过一次的旅行商问题的升级版；二进制可以使用1<<n；这也是这个题和二进制的区别。#include<cstdio>#include<cstring>...
2019-09-24 15:38:21
123
原创 二维并查集+bfs预处理
qduoj598二维并查集+bfs预处理要点：1，将二维转化为一维（1，1） （1，2） （1，3）（2，1） （2，2） （2，3）（3，1） （3，2） （3，3）转化为：1 2 34 5 67 8 9计算函数：int point(int x,int y){ return (x-1)*m+y;}2，bfs进行预处理：不用对所有的满足mp[i][j]=='...
2019-09-24 11:57:22
185
原创 杨辉三角形中的秘密
1，杨辉三角形的第i列满足：（i>=0）C(0,i) C(1,i) … C(i,i)即是一组全排列公式。2，第i行奇数的个数等于将#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;LL solve(LL...
2019-09-23 20:06:12
249
原创 Pebbles HDU - 2167
//无优化，时间：748ms#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int st[16][1<<16],top[16];int mp[16][16][(1<<15)+10];bool vis[16];int a[16][...
2019-09-21 15:30:13
133
原创 Poj3140求树重心
//编译错了两次，原因：abs(a),a不能是LL类型#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const LL inf=1e17;const int num_e=2*1e6+10;struct nod...
2019-09-20 21:15:43
73
原创 Tree Cutting POJ - 2378+Poj3107+求树的重心
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int inf=1e8;const int num=1e4+10;struct node{ int v,next;}e[2*num];int head[2*num],cnt;int...
2019-09-20 20:14:24
110
原创 HDU2196_Computer_求树上的每一个点可以达到的最大距离
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int num=1e4+10;struct node{ int v,next,w;}e[2*num];int head[2*num],cnt;int dp[num][2];void...
2019-09-20 18:59:40
159
原创 Hdu2196（树形dp，只有代码)
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int num=6*1e3+10;struct node{ int v,next;}e[num];int head[num],p[num],cnt;int a[num];int d...
2019-09-20 17:07:08
77
原创 Halloween Costumes LightOJ - 1422(只有代码)
dp[i][j]表示第i天到第j天达到的最小值；因为前面某一天的选择对后面会造成影响，对于这样的问题，我们从后往前dp；转移方程：（1） 第i天和[i+1,j]天里的衣服都不同，dp[i][j]=dp[i+1][j]+1;（2） 第i天和第k天，i+1<=k<=j，存在相同的，那么如果第i天的衣服留下，第k天就可以不加新衣服了，此时：dp[i][j]=min(dp[i+1][...
2019-09-20 15:36:34
85
原创 Palindrome subsequence+区间dp（只有代码）
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;const int mod=10007;const int num=1010;int dp[num][num];char a[num];int main(...
2019-09-19 22:37:17
75
原创 Light bulbs+ICPC Asia Shanghai 2019+差分+离散化
题目链接时间限制：1000ms；空间限制：8192K；数据大小:1<=T<=1e3;1<=n<=1e6;1<=m<=1e3;题目大意：《自己读一下就可以理解》写线段树会超内存，不做处理写差分会超时；解决方法：记录并离散化需要差分处理的点；离散化后处理差分数组；依据离散化后的差分数组处数据；#include<cstdio>...
2019-09-15 21:00:03
121
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人