- 博客(73)
- 资源 (3)
- 收藏
- 关注
RSS订阅原创 SGU 106
题意：给出方程ax+by+c=0,求出有多少对整数解(x,y),满足X1<=x<=X2, Y1<=y<=Y2; 思路： 若a=0,b=0,c=0,为(X2-X1+1)*(Y2-Y1+1); 若a=0,b=0,c!=0或c%gcd(a,b)!=0,则无解； 否则，计算满足条件的x所在区间，满足条件的y所在区间，求两区间交集的元素的个数； 在SGU
2015-11-05 11:59:54
477
原创 poj 1733 Parity game（种类并查集）
题意： 有0或1构成的一段区间总长度为n，m个询问，每次询问一段区间1的个数为奇数还是偶数，问从第一个询问开始，前几个询问正确的个数有几个； 思路： n<=10^9，m<=5000;很多数用不到，所以可以离散化一下； 将和为奇数的区间标记为1，为偶数的区间标记为0； 对于每个询问，合并操作时，如果两区间重合且奇偶性之和与询问所给的奇偶性相同，则该询问正确，否则错误
2015-07-28 11:55:02
1001
原创 poj 1962 Corporative Network（带权并查集）
题意： 在n个站点间建电线；两种操作： I a b表示以a为中心站点建线； E a表示查询以a站点为中心，相连的电线总长度； 思路： 带权并查集；中心站点就是父亲，电线长度为权值；#include<cstdio>#include<cstring>#include<cmath>#include<algorit
2015-07-28 09:37:14
602
原创 运算符重载
重载矩阵加法，减法，乘法；#include<cstdio>#include<cstring>struct node{ int matrix[50][50];};int n;inline node operator +(const node &y,const node &x){ node xx; for(int i=0;i<n;i++) {
2015-06-06 22:05:41
425
原创 poj 1006 中国剩余定理
题意：求数n,是(n+d)%23==p,(n+d)%28==e,(n+d)%33=i;转载请注明出处：http://www.cnblogs.com/dashuzhilin/；思路：中国剩余定理。利用同余的加性，将(n+d)拆成三个数a,b,c， 使a%23==p,a%28==0,a%33==0; 使b%23==0,b%28==e,b%33
2015-04-04 16:51:21
651
原创 poj 2488 暴搜
题意：给定棋盘大小，求是否能马步遍历所有格子，若能遍历按字典序给出遍历序列。思路：搜索过程保存路径。#include#include#includeusing namespace std;int x[8]={-1,1,-2,2,-2,2,-1,1};int y[8]={-2,-2,-1,-1,1,1,2,2};int vis[510][505];int n,m,a[5050]
2015-03-28 19:56:09
355
原创 poj 1094 Sorting It All Out
题意：n个数m组比较，判断三种情况：有环，有序，无序；思路：拓扑排序。初始时度数为0的点数大于1时，无序；度为0个数等于1时，有序；不存在度为0的数时，无序；#include#include#includeusing namespace std;int n,m;int mm[505][505],hh;int q[500010],indegree[500010];int top
2015-03-14 21:18:12
280
转载 图论题大合集
转载出处：http://blog.csdn.net/ffq5050139/article/details/7832991=============================以下是最小生成树+并查集======================================【HDU】1213 How Many Tables 基础并查集★1272 小希的迷宫
2015-03-14 18:14:02
783
原创 hdu 3342 Legal or Not
题意：判断有无环路；思路：拓扑排序；两种写法：结构体+指针：#include#include#includeusing namespace std;int n,m;struct node{ int du; node *next;}q[50010];int topo(){ node *p; int *shu=new int[50010]
2015-03-14 15:41:46
481
原创 hdu 2647 Reward
题意：给出n对员工需求，每队包含两个员工编号，要求前者奖金大于后者，求所有员工的奖金数；思路：拓扑排序判定有无环；#include#include#includeusing namespace std;int n,m;struct node{ int du; node *next;}q[500010];int topo(){ int i,j,k
2015-03-14 13:54:29
580
原创 hdu 1286 找新朋友
题意：求一个数约数为1的个数。思路：裸裸的欧拉函数。#include#include#includeusing namespace std;int eular(int n){ int ans=n; for(int i=2;i*i<=n;i++) { if(n%i==0) { ans-=ans/i;
2015-03-13 23:58:31
607
原创 hdu 2094 产生冠军
题意：给出n对选手姓名，每对表示前者赢后者，求整场比赛是否有冠军；思路：将名字用数字表示，离散化，然后就是裸裸的拓扑排序，只需判断初始时入度为0的是否唯一；#include#include#includeusing namespace std;int n,m,i,j,k,con;int mm[1001][1001],indegree[500010];char s1[500010
2015-03-13 20:48:00
506
原创 hdu 1285 确定比赛名次
题意：给出每两个队伍的胜负关系，求排名。思路：裸裸的拓扑排序。#include#include#includeusing namespace std;int n,m,p1,p2;int indegree[500010],match[505][505],flag;void tuopu(){ int i,j,k,flag=0; for(j=1;j<=n;j++)
2015-03-13 14:18:52
510
原创 zoj 3787 Access System
题意：给出一系列时刻数和一个时长，求不在同一时间段中的最少个数和编号；思路：sort排序，二维的sort，在排序的同时保存每个数的编号;#include#include#includeusing namespace std;int h,m,s;int id[500010];struct node{ int sum,id;}q[500010];int cmp(nod
2015-03-11 20:25:03
603
原创 zoj 3785 What day is that day?
题意：求从1的1次方加到n的n次方的和对7取余所得结果。思路：打表找规律。所谓打表就是把部分所求结果保留下来，通过观察已有数据找到规律，或在程序中直接判定出所求规律。对于这种找周期的题，打表最适合不过了！！！打表程序：#include#includeint a[50010],T,n,m,i,j,k,flag;int work(int n){ int i,sum=1;
2015-03-11 19:33:31
479
原创 hdu 1711 Number Sequence
思路：裸裸的kmp算法；#include#includeint next[5000100],a[5000100],b[5000010];int n,m;void getnext(){ int i=0,j=-1; memset(next,0,sizeof(next)); next[0]=-1; while(i<m) { if(j=
2015-03-11 16:53:48
584
原创 hdu 3911Black And White
题意：给定一个只包含0和1的字符串，每次操作将指定区间中的0变为1,1变为0，求指定区间最长连续1的长度；思路：线段树区间异或，成段更新；#include#include#include#define lson rt<<1#define rson rt<<1|1using namespace std;int sum[500010],lazy[500010];int preb[
2015-03-08 23:54:48
376
原创 hdu 1698 just a hook
题意：一根钩子原来每单位长度价值均为1，每次改变一段区间的价值，求处理后钩子的总价值。思路：线段树区间更新，区间求和，裸裸的模板题。#include#include#includeusing namespace std;int sum[500010],lazy[500010];void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<
2015-03-08 12:51:30
539
原创 poj 2411
题意：1*2的砖块填满n*m的地板思路：i行j列由i-1行j列推得，i-1行j列处竖放得到或i行横放得到；枚举i行横放的方法数和i-1行的状态数；#include#includelong long f[30][1<<12],i,j,height,width,saya=1;void sayatime(int i,int s1,int pos){ if(pos==width)
2015-03-08 00:45:04
505
原创 Codeforces 194B
题意：在n*n的上从左下角开始，每次走n+1个点画一个叉，问回到起点时一共画几个叉；思路：gcd;#include#include#include#includeusing namespace std;long long n,m,num,t,a,b,r;int i,j,k,rcount,shu,flag,yu,len;long long gcd(long long a,lon
2015-02-05 21:38:33
1171
原创 Codeforces 124c Lexicographically Maximum Subsequence
题意：输出给定字符串的字典序最大子串。思路：统计所有出现过的字符，按字典序从大到小取，取完当前后取下一个，直到结尾。#include#include#includeusing namespace std;int n,m,i,j,k,len;char a[500010];int num[50],ch,shu;int main(){ while(scanf("%
2015-02-04 21:43:25
714
原创 CodeForces 222A
题意：给一串数，一种操作，问是所有数字相等的操作数；思路：还是蛮水的，但我看了半天才发现1、2两种操作是一次操作、、、弱爆了、、、判断第k个数开始是否都相等，再判断k之前有几个数不需要删掉的。#include#include#includeusing namespace std;int n,k,i,j,m,flag;int a[500010],rcount;int ma
2015-02-03 14:24:33
709
原创 Zoj 3707 calculate prime s
题意：S[n]与所有S[i](i互质，则为Prime S。求（S[n]/X）%M;思路：由集合性质推得S[i+1]=S[i]+S[i-1],则S[i]是斐波那契数。从第五项开始，每项斐波那契为质数的条件为当且仅当它的项数为质数，因此采用素数打表的方法得到第k个Prime S的斐波那契数的项数。然后用矩阵乘法求出第k个S的值对应的下一个斐波那契数，然后枚举该斐波那契数，直到能被X整除。#in
2015-02-03 12:02:07
893
1
原创 zoj 3710 Friends
题意：每对朋友公共点达到k时才能持久，求能持久的朋友数；思路：统计两点之间的点数，当公共点数达到k时朋友对数加1；#include #include int main() { int t,n,m,k,x,y,ans,sum,i,j,l,flag; int map[101][101]; scanf("%d",&t); while (t--) { scanf(
2015-02-03 11:57:25
380
原创 CodeForces 13C
题意：对于给定数列，每次可做加一减一操作，求使数列非递减所需最少操作。思路：dp.状态转移方程 f[i][j]=min(f[i][j-1],f[i-1][j]+abs(a[i]-b[j])),f[i][j]表示把前i个数变成递增序列，第i个数变成b[j]的最少步数。把序列中的数变成原序列中的数能得到最优解,用反证法可以证明。#include#include#include#incl
2015-02-03 11:32:24
598
原创 zoj 3706 Break Standard Weight
分治的思想，比较水，但题很好#include#include#includeusing namespace std;int t,n,m;int vis[50010];void v(int a,int b){ vis[a]=1;vis[b]=1; vis[a+b]=1;vis[abs(a-b)]=1;}int rmax(int a,int b,int c
2015-02-02 00:16:52
947
原创 zoj 3713 In 7-bit
题意：给t组数据，每组数据一个字符串，对于每组数据先输出其字符串长度len，先将十进制的len转为二进制，取其后7位，前面有1剩余把1放在后七位的前面构成8位，按次序输出，输完len后，字符串转化为16进制输出。关键在于读题。#include#include#includeusing namespace std;char a[5000010];int main(){ i
2015-02-01 23:14:21
910
原创 zoj 3715 Kindergarten Election
#include#include#include#include#define eps 1e-5#define MM 0x3f3f3f3fusing namespace std;int vis[505],f[505],c[505],sum[505],id[505];int cmp(int a,int b){ return c[a]<c[b];}int main(){
2015-02-01 20:16:35
746
3
原创 hdu 5023 A Corrupt Mayor's Performance Art(线段树区间更新)
#include#include#include#includeusing namespace std;int tree[5001000],add[5001000];int color[50];int n,m;void pushup(int pos){ tree[pos]=tree[pos<<1]|tree[pos<<1|1]; //更新父节点}void pushdown
2014-12-07 19:31:41
650
转载 奇葩的代码
下面的六个程序片段主要完成这些事情：输出Hello, World混乱C语言的源代码下面的所有程序都可以在GCC下编译通过，只有最后一个需要动用C++的编译器g++才能编程通过。hello1.c1234567891011 #define _________ } #define
2014-11-27 08:12:09
484
原创 hdu 2544 spfa
#include #include #define MAX 999999999#define N 1001int d[1002],n,m;int edges[1005][1005];int queue[1000001];int SPFA(int s){ int i; bool visit[N] = {false}; int front = 0, rear =
2014-11-16 23:47:46
448
转载 数论题大集合
转自：http://blog.csdn.net/linleiqin/article/details/5639910 1.burnside定理，polya计数法 这个大家可以看brudildi的《组合数学》，那本书的这一章写的很详细也很容易理解。最好能完全看懂了，理解了再去做题，不要只记个公式。 *简单题：（直接用套公式就可以了） pku2409
2014-11-08 23:00:14
593
原创 优化输入输出后的计数排序
当数据太大，内存要求紧，整数范围小时，存在不能用快排的情况，这时可用计数排序。#include#include#includeinline int readint(){ char c=getchar(); while(!isdigit(c)) c=getchar(); int x=0; while(isdigit(c)) { x=x*10+c-'0
2014-11-08 14:09:10
771
转载 hdu 5050 Divided Land(高精度gcd)
#include #include #include #define MAXN 1000using namespace std;struct BigNumber{ int len; int v[MAXN];};bool isSmaller(BigNumber n1,BigNumber n2){ if(n1.len<n2.len) return 1;
2014-10-27 19:50:27
514
转载 训练计划（二）
初期:一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法:
2014-10-26 17:39:54
543
转载 训练计划（一）
两个版本POJ题目推荐(转载)题目均为POJ上的http://acm.pku.edu.cn个别题目的分类并不准确======================================OJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3
2014-10-26 17:38:03
458
转载 状态压缩递推(States Compressing Recursion,SCR)
我们暂时避开状态压缩的定义，先来看一个小小的例题。【引例】 在 n*n(n≤20)的方格棋盘上放置n 个车(可以攻击所在行、列)，求使它们不能互相攻击的方案总数。 【分析】 这个题目之所以是作为引例而不是例题，是因为它实在是个非常简单的组合学问题：我们一行一行放置，则第一行有n 种选择，第二行n-1，……，最后一行只有 1 种选择，根据乘法原理，答案就是
2014-10-06 13:18:39
511
转载 博弈论
首先当然要献上一些非常好的学习资料：基础博弈的小结：http://blog.csdn.net/acm_cxlove/article/details/7854530经典翻硬币游戏小结：http://blog.csdn.net/acm_cxlove/article/details/7854534经典的删边游戏小结：http://blog.csdn.net/acm_cxlove/
2014-10-06 12:44:00
443
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人