pku专题

PKU Campus 2011 B A Problem about Tree lca倍增

B:A Problem about Tree 总时间限制: 1000ms 内存限制: 65536kB 描述 Given a tree with Nvertices and N- 1 edges, you are to answer Qqueries on "which vertex isY's parent if we choose Xas the ro

PKU Online Judge 1054

PKU Online Judge / 练习题目排名状态提问 1054:Cube 查看提交统计提问总时间限制: 1000ms 内存限制: 131072kB 描述 Delayyy君很喜欢玩某个由Picks编写的方块游戏，游戏在一个由单位格组成的棋盘上进行。游戏的主角是一个6个面互不相同的小方块，每次可以向上下左右中的某个方

PKU Online Judge 1055:Tree

1055:Tree 查看提交统计提问总时间限制: 2000ms 内存限制: 131072kB 描述在信息学竞赛中，我们经常要遇到树这种结构。一棵树中除根结点外有且仅有一个父亲，而可能有很多儿子。所以，当我们要生成一棵树的时候，我们通常使用以下算法：对树中的每个点定义一个深度。第 1 个节点的深度为 1，第 i 个点的深度就是 Fatheri的

pku 1024

这是别人的代码，效率很高，在status上的第一页，看了人家的自己就不想写了，就写篇分析吧。。。 #include <iostream>const int gsize = 20 ; // 图的大小，实际上测试数据较弱，20就够了。int minPath , wallNo , W , H , Dx,Dy;struct Point { int val[2]; // pt[x][y].va

pku 2989

极大团问题： #include <stdio.h>#include <map>using namespace std;#define MAXN 129int n, m, cnt;struct f_int{unsigned int a,b,c,d;f_int(){a=b=c=d=0;}void operator <<(int s){switch(--s/32){ca

PKU__ACMnbsp;题目总结（转）

ACM基本算法分类、推荐学习资料和配套pku习题2008-04-12 15:15一.动态规划参考资料：刘汝佳《算法艺术与信息学竞赛》《算法导论》推荐题目： http://acm.pku.edu.cn/JudgeOnline/problem?id=1141 简单 http://acm.pku.edu.cn/JudgeOnline/problem?id=2288 中

【可视化笔记-VRVIS SWUST-2018】《城市移动数据知微探秘》_陆旻等_PKU

入坑论文1——《城市移动数据知微探秘》下载链接：度盘，密码20ho 本文通过可视化与可视分析技术，将数据转换为图形等用户可交互的方式，让人们理解城市这一主题，并且探索城市中不同人群的行为对城市造成的影响。何为“城市”：引用微软亚研院：城市计算城市计算是一个交叉学科，是计算机科学以城市为背景，跟城市规划、交通、能源、环境、社会学和经济等学科融合的新兴领域。更具体的说，城市计算是一

(pku 1014) (hdu 1059) (zoj 1049) Dividing muhanshu

(pku 1014) (hdu 1059) (zoj 1049) Dividing 前几天看了刘老师关于母函数的课件,顺便找几个题目来热热身.看了1059的题目以后,很快我就把他和母函数联系起来了,于是就动手写了程序,没想到提交就wa掉了,后来发现是在多项式计算的地方出现了问题.后来一个师姐看我做这个题目,她也去动手做了起来.她用的是贪心的思想,开始问她是怎么做的时候,wa想的巧,可是

PKU上的几个背包问题总结(总结了网上的很多文章，在此致谢)

基础知识可先参考背包九讲背包相关的几个题目：1014 1742 1276 1882 3211 PKU 1742:http://www.cppblog.com/Onway/articles/122075.html 引用：我觉得这个题目跟pku 1276 cash machine和pku 1882 stamps都有点像。首先与1276 cash machine一样，都是

[PKU 3378]Crazy Thairs(平衡树)

【题目大意】： N个数（N<=50000），求5个互相不逆序的数的组合有多少个。【题目分析】：这个题的重要的地方在于要统计的是长度为5的正序序列的个数，我们就可以通过正序对个数的求法来类比出来正确的方法。正序的求法我们是在平衡树中记录size，通过rank操作来进行的。其实进行一下扩展就可以得到正确的方法。我们开4个平衡树，然后rank的含义也随之改变，第一个求的就是以当前节点为尾的

pku线段树20题（mark）

难度系数分为从1 到 5 （只对初学者有用对大牛来讲这些题的难度系数都是0..) http://acm.pku.edu.cn/JudgeOnline/problem?id=1151 Atlantis 扫描线+离散化+线段树这是经典的扫描线求矩形面积交很好过没什么陷阱如果头一次接触扫描线那么难度系数大概算3吧如果熟练掌握扫描线难度系数为1 难度系数 ***

ACM基本算法分类、推荐学习资料和配套pku习题

一.动态规划参考资料：刘汝佳《算法艺术与信息学竞赛》《算法导论》推荐题目： http://acm.pku.edu.cn/JudgeOnline/problem?id=1141 简单 http://acm.pku.edu.cn/JudgeOnline/problem?id=2288 中等，经典TSP问题 http://acm.pku.edu.cn/JudgeOnline/p

PKU_ACM_1164_The Castle

http://acm.pku.edu.cn/JudgeOnline/problem?id=1164 原题类似于迷宫搜索的简单题 import java.io.*;import java.util.*;public class Main{ static Room[][] matrix; static int row; static int col; pu

PKU_ACM_1035_Spell checker

1035_Spell checker 原题连接简单的字符串操作问题 import java.io.*;import java.util.*;public class Main{ static ArrayList<Item> dicts = new ArrayList<Item>(); public static void main(String[] ar

PKU OJ 1019 Number Sequence

终于0MS AC了，时间复杂度为O（1）我的感觉是：算法虽然有点复杂，但很容易想到，编程时细心点很快就能AC #include<stdio.h>#include<math.h>long pow10(long n){ if(n==0)return 1; else if(n==1)return 10; else if(n==2)return 100; else if(n==3)return 10

Pku oj 3617 Best Cow Line(贪心）

Best Cow Line Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 16209 Accepted: 4575 Description FJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual"Farmer of the Year" comp

Pku oj 1182 食物链（带权并查集）

食物链 Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 63605 Accepted: 18675 Description 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。

Pku oj 3264 Balanced Lineup（RMQ）

Balanced Lineup Time Limit: 5000MS Memory Limit: 65536KTotal Submissions: 46162 Accepted: 21674Case Time Limit: 2000MS Description For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000)

pku 2440 DNA

2440 DNA 递推题；通常有几种方式来做这种题：1.小范围内找到规律2.直接分析出规律进一步，有的题可能还要转化成矩阵乘法，然后分治的在nlgn 时间内解决。有的由于数值太大，会要求取模，这时很可能会出现循环节。 http://acm.pku.edu.cn/JudgeOnline/problem?id=2229也是一道递推的题目，我的想法是与二进制有关，奇数直接去掉末位1(-1)，

pku 2148 Cow Exhibition

2184 Cow Exhibition 0－1背包问题变形，选定一个值作状态后，另一值可被标识。如果有更多信息需记录（信息量－1）的数组应该可以的。http://acm.pku.edu.cn/JudgeOnline/problem?id=1717 Dominos这道题也是一道类似的题目，还可以用搜索来做。把有利的值统统加入，同时记下可能使不符合的元素，做一次排除，找到正确的最优值。 0－1背包

pku 3414 pots

3414 Pots 经典倒水问题，要求最短，宽搜，ax + by = c 有解条件c = 0 (mod gcd(a,b)) #include < iostream > #define MAX_LEN 10001 using namespace std; int a,b,c; bool black[ 101 ][ 101 ] = ... {false} ; struct

pku 1177 picture

一道经典的离散化的题目，有论文可以参考。基本思想，在某个方向进行映射，将连续的坐标（或其它）离散化，在另一个方向以某种方式做题目所需的统计，包括离散化，线段树式统计或其它。优化可以考虑映射方式（减少循环），减小坐标范围（优化插入及更新），主要是通过去重。很可能同时涉及线段树的操作。

pku 1870 bee breeding

想到坐标的转换是重点。参看pku 2265 bee maja #include < iostream > #include < cmath > #include < algorithm > using namespace std; // 1 is inlayer 0 // east ,west ,... void getPos( int & x, int & y,

pku 2455 Sticks Problem

这道题是月赛题，有解题报告的。用的是分治的做法。当时想到了，但总感觉有点不够完美，所以没做，原来是没有正确估算时间复杂度…… #include <iostream>#include <algorithm>#define N 50001using namespace std;int n;int a[N];int b[N];int bst;void getLong(int l

pku 1771Elevator Stopping Plan

有两道Elevator Stopping Plan，做了一道，另一道也顺便过了方法是二分+贪心一旦时间确定了，就可以用贪心来处理，只要保证每个人在时限之内到达，如果成功就进一步缩时间，不能就放宽时限。还有一道也是这样做的。 3388 Japanese puzzle,二分枚举最大行数，一旦行数确定了，就可以用贪心的方式，看能否达到。 http://acm.pku.edu.cn/Judg

pku 2312 Battle City

Dijkstra变种，实际上就是一个PFS了，BFS也能过。注意一点，这是个二维的，提供了一种二维上的解决此类问题的方法。另，如果贪心性质有问题，也不妨试试这个方法，不断的找最优值，点不置黑，可再次入队……呵呵，我好像说到另一题上去了。