guojiaqi007-CSDN博客

转载九度 oj 题目1548：平面上的点

http://ac.jobdu.com/problem.php?pid=1548code from http://www.lai18.com/content/477808.html#include #include #include using namespace std;#define ms(x,y) memset(x,y,sizeof(x))#define i

2017-03-13 23:01:49 386

原创 pat 1020. Tree Traversals (25)

1020. Tree Traversals (25)时间限制400 ms内存限制65536 kB代码长度限制16000 B判题程序Standard作者CHEN, YueSuppose that all the keys in a binary tree

2017-03-12 12:39:54 296

转载 pat 1043. Is It a Binary Search Tree (25)

1043. Is It a Binary Search Tree (25)时间限制400 ms内存限制65536 kB代码长度限制16000 B判题程序Standard作者CHEN, YueA Binary Search Tree (BST) is r

2017-03-09 20:20:12 295

转载 pat 1042. Shuffling Machine (20)

1042. Shuffling Machine (20)时间限制400 ms内存限制65536 kB代码长度限制16000 B判题程序Standard作者CHEN, YueShuffling is a procedure used to randomi

2017-03-09 17:47:34 199

原创 pat 1042. Shuffling Machine (20)

https://www.patest.cn/contests/pat-a-practise/1042hash 一下顺序，然后就是dp了。#include #include using namespace std;#define rep(i,j,k) for(int i=j;i<=k;i++)#define inone(i) scanf("%d",&i)const int

2017-03-09 12:07:33 277

转载九度 oj 题目1549：货币问题

http://ac.jobdu.com/problem.php?pid=1549参考了http://www.voidcn.com/blog/newchan/article/p-4594278.html贪心，用大面值肯定比用小面值张数少#include #include #include using namespace std;#define ms(x,y) memset(x,

2017-03-08 23:07:47 274

转载九度 oj 题目1550：分糖果

http://ac.jobdu.com/problem.php?pid=1550默认给最少“1”，如果a[i] > a[i-1], 比前面多给一个。如果 a[i] 参考了http://blog.csdn.net/xiexingshishu/article/details/20319825#include #include using namespace std;#def

2017-03-08 22:35:37 282

转载九度 oj 题目1552：座位问题

http://ac.jobdu.com/problem.php?pid=1552动归，分最后一个是男还是女讨论。注意当总共有0人以男结尾的排列是1种情况。 #include #define inone(i) scanf("%d",&i)const int maxn = 1e3 + 10;int m[maxn], f[maxn], n;void init(){ f[

2017-03-08 20:30:49 240

转载九度 oj 题目1554：区间问题

http://ac.jobdu.com/problem.php?pid=1554copy from http://blog.csdn.net/u013491262/article/details/21406351把sum[1~i] = sum[i], sum[i] 是以a[i]为最后一个元素的前缀和， Map以前缀和为key，具有相同的前缀和的idx的vector 为va

2017-03-08 16:15:16 293

原创九度 oj 题目1555：重复子串

http://ac.jobdu.com/problem.php?pid=1555这道题觉得还可以再优化，暂时先水过了。#include #include #include using namespace std;#define rep(i,j,k) for(int i=j;i<=k;i++)string s;int cal(string s){ set uniq;

2017-03-08 14:39:46 343

原创九度 oj 题目1010：A + B

http://ac.jobdu.com/problem.php?pid=1010#include #include #include #include #include using namespace std;map Map;int get(string s){ string a; istringstream is(s); int res = 0; while

2017-03-08 14:00:09 248

原创九度 oj 题目1009：二叉搜索树

http://ac.jobdu.com/problem.php?pid=1009#include #include #include using namespace std;#define rep(i,j,k) for(int i=j;i<=k;i++)#define inone(i) scanf("%d",&i)//typedef struct nd { int v;

2017-03-08 12:36:10 296

原创九度 oj 题目1008：最短路径问题

http://ac.jobdu.com/problem.php?pid=1008这道题告诉我们 INT_MAX, 慎用，dijkstra 有时加溢出了，你都不知道#include //#include #include using namespace std;#define rep(i,j,k) for(int i=j;i<=k;i++)#define inone(i)

2017-03-08 11:29:10 347

原创九度 oj 题目1006：ZOJ问题

http://ac.jobdu.com/problem.php?pid=1006#include #include #include using namespace std;#define rep(i,j,k) for(int i=j;i<=k;i++)bool ac(string s){ //cout << s << endl; int len = s.size()

2017-03-08 10:05:03 241

转载 pat 1026. Table Tennis (30)

https://www.patest.cn/contests/pat-a-practise/1026根据http://blog.csdn.net/jtjy568805874/article/details/50809719 修改#include #include using namespace std;#define inthree(i,j,k) scanf("%d%d%d"

2017-03-06 13:17:06 266

转载 pat 1048. Find Coins (25)

https://www.patest.cn/contests/pat-a-practise/1048参考了http://blog.csdn.net/jtjy568805874/article/details/50858073水题，想了dp，二分。后来看了题解才发现好简单。#include #define inone(i) scanf("%d",&i)#d

2017-03-05 21:52:02 188

原创 pat 1023. Have Fun with Numbers (20)

https://www.patest.cn/contests/pat-a-practise/1023#include #include #define rep(i,j,k) for(int i=j;i<=k;i++)const int maxn = 100;char s[maxn];int b[maxn], c[maxn], len, x;bool flag;int main(

2017-03-05 20:01:54 276

转载 pat 1021. Deepest Root (25)

https://www.patest.cn/contests/pat-a-practise/1021照抄了http://blog.csdn.net/jtjy568805874/article/details/50805402里面用到了求树的半径的方法，1）用任何一个点dfs 找到最深的深度，所有深度最深的node 是半径上的点。2）再用任意一个半径上的点dfs，找到

2017-03-05 17:40:40 267

转载 pat-top 1017. The Best Peak Shape (35)

https://www.patest.cn/contests/pat-t-practise/1017这道题首先自己写了一个O(n^2)的dp 过了。#include #include #include #include using namespace std;#define rep(i,j,k) for(int i=j;i<=k;i++)#define per(i,j

2017-03-05 15:16:09 2150

转载 pat-top 1016. Uniqueness of MST (35)

https://www.patest.cn/contests/pat-t-practise/1016照抄了 http://blog.csdn.net/jtjy568805874/article/details/60338730确定是否唯一是难点，在每新加一个边时，先看同等权值的边可否加入，并对所有可加入的边进行计数，最后如果边数小于n，不小于则最小生成树不唯一。#inc

2017-03-05 11:48:38 640

转载 pat-top 1015. Letter-moving Game (35)

https://www.patest.cn/contests/pat-t-practise/1015这道题开始想用bfs，但是状态转移和visit不好确定。看了http://blog.csdn.net/jtjy568805874/article/details/53610545，才知道用dp很简单。也是采用了逆向思维，想如何从 t 装变为 s，过程是把t的前半部分tHead

2017-03-05 10:16:17 374

原创九度 oj 题目1171：C翻转

http://ac.jobdu.com/problem.php?pid=1171#include #include using namespace std;#define rep(i,j,k) for(int i=j;i<=k;i++)#define inone(i) scanf("%d",&i)#define infour(a,b,c,d) scanf("%d%d%d%d"

2017-03-04 17:50:16 354

原创九度 oj 题目1073：杨辉三角形

http://ac.jobdu.com/problem.php?pid=1073#include #include #define inone(i) scanf("%d",&i)#define rep(i,j,k) for(int i=j;i<=k;i++)const int maxn = 1e6;int n;int dp[2][maxn];int get(int i,

2017-03-04 15:23:56 252

原创九度 oj 题目1072：有多少不同的面值组合？

http://ac.jobdu.com/problem.php?pid=1072#include const int n = 15;const int v = 8 * 5 + 10 * 4 + 18 * 6;const int a[n+1] = { 0,8,8,8,8,8,10,10,10,10,18,18,18,18,18,18 };#define rep(i,j,k) fo

2017-03-04 14:43:40 254

转载 pat-top 1014. Circles of Friends (35)

https://www.patest.cn/contests/pat-t-practise/1014照抄了http://blog.csdn.net/jtjy568805874/article/details/53610228这道题开始时想用并查集，但是如何计算半径很复杂。解题思路：对每个节点进行bsf得到最大半径（所有bfs得最大深度），然后bfs可以得到最大团（

2017-03-04 14:23:30 440

转载 pat-top 1013. Image Segmentation (35)

https://www.patest.cn/contests/pat-t-practise/1013这道题自己的想法是算出一个个mst，然后看每个MST的最长边是否可以分解。但是没想出好的dfs模型后来看了http://blog.csdn.net/jtjy568805874/article/details/53435235，逆向思维，从搭建compoent的角度出发。去填边，正

2017-03-03 21:14:49 2353

转载 pat-top 1012. Greedy Snake (35)

https://www.patest.cn/contests/pat-t-practise/1012参考了http://blog.csdn.net/jtjy568805874/article/details/52517821#include #include #include #include using namespace std;const int ma

2017-03-03 17:27:17 519

转载 pat-top 1010. Lehmer Code (35)

https://www.patest.cn/contests/pat-t-practise/1010离散化+树状数组code from http://blog.csdn.net/jtjy568805874/article/details/50898105#include #include using namespace std;const int max

2017-03-03 11:48:06 275

原创树状数组

参考了http://baike.baidu.com/item/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84原数组：a[], 树状数组：c[];1.最重要的概念：c[n] = a[n] + a[n-1] + a[n-2] +...+ a[n-2^k-1]. k是n的二进制末尾0的个数。 c[n] 的物理意义是从n到n的二进制下最后一个1所覆盖的

2017-03-03 10:44:42 168

转载 pat-top 1009. Triple Inversions (35)

https://www.patest.cn/contests/pat-t-practise/1009这道题首先用了一个简单的dp：const int maxn = 1e5 + 2;int lar[maxn];int a[maxn];int main(){ int n, k, ans = 0; scanf("%d", &n); for (int i = 0; i <

2017-03-03 09:36:03 284

转载 pat-top 1008. Airline Routes (35)

https://www.patest.cn/contests/pat-t-practise/1008参考了https://zh.wikipedia.org/wiki/Tarjan%E7%AE%97%E6%B3%95code 来自于http://blog.csdn.net/jtjy568805874/article/details/50759540题意是求在有向图中的两个点是否在

2017-03-02 15:25:11 452

转载 pat-top 1006. Tree Traversals - Hard Version (35)

https://www.patest.cn/contests/pat-t-practise/1006code 来自于http://blog.csdn.net/jtjy568805874/article/details/50759512dfs 在中序遍历序列中穷举 root 的位置，因为root可能会被替换，所以使用数组存储树。#include #include #i

2017-03-01 21:39:08 2345 1

原创 pat 1016. Phone Bills (25)

https://www.patest.cn/contests/pat-a-practise/1016#include #include #include #include #include #include #define _CRT_SECURE_NO_WARNINGSusing namespace std;typedef struct item { int typ

2017-03-01 13:29:05 210

原创九度oj 题目1457：非常可乐

http://ac.jobdu.com/problem.php?pid=1457#include #include #include #include using namespace std;bool visit[101][101][101];int n, m, s;typedef struct status { int a,b,c; int steps; void

2017-02-28 22:05:31 461

转载 pat 1040. Longest Symmetric String (25)

https://www.patest.cn/contests/pat-a-practise/1040参考了：https://segmentfault.com/a/1190000003914228http://blog.csdn.net/jtjy568805874/article/details/50856440#include #include #inc

2017-02-27 17:07:13 185

转载 pat 1013. Battle Over Cities (25)

https://www.patest.cn/contests/pat-a-practise/1013代码来自http://blog.csdn.net/jtjy568805874/article/details/50791941#include #include #include using namespace std;typedef struct edge { i

2017-02-27 10:33:22 170

原创 pat 1012. The Best Rank (25)

https://www.patest.cn/contests/pat-a-practise/1012使用基数排序部分代码参考了：http://blog.csdn.net/jtjy568805874/article/details/50782867#include int wc[4][102];int ids[1000001];int scor[2001][4]

2017-02-27 09:52:43 221

转载 pat 1011 1011. World Cup Betting (20)

https://www.patest.cn/contests/pat-a-practise/1011代码来自 http://blog.csdn.net/jtjy568805874/article/details/50782588#include #include using namespace std;double x, y, z, ans = 1;int mai

2017-02-27 08:34:45 166

转载 pat 1010. Radix (25)

https://www.patest.cn/contests/pat-a-practise/1010代码来自http://blog.csdn.net/jtjy568805874/article/details/50782565#include #include #include using namespace std;typedef unsigned long l

2017-02-27 08:17:56 307

原创 pat 1007. Maximum Subsequence Sum (25)

https://www.patest.cn/contests/pat-a-practise/1007#include #include int main(){ int a[10000],n,maxSum=INT_MIN,maxBegin,maxEnd=0,sum=INT_MIN,begin = 0; scanf("%d", &n); for (int i = 0; i

2017-02-25 11:56:24 154

空空如也

空空如也