GitHub - BigDeviltjj/poj: cpp solutions to some poj problems

poj

following solutions are lost:

1182(three union-find)

1185(dp)

1986(tarjan)

some algorithms and problems

line segment tree: total area and perimeter of overlaped rectangles
妈个鸡poj1187搞了3天才把思路终于搞明白，网上解题报告实在太烂了（明明是我自己太蠢了555555），直接看代码很难理解dp的原理。这里记录下：

dp[i][j][k][d]代表{}有i个，[]有j个，()有k个可以组成深度小于等于d的方案个数。那么dp[i][j][k][d]转移函数可以写作a × b，a和b分别代表两个子串，a代表第一个子串，子串就是{[]}这样没有拼接的串，剩下的好多个子串>的合并为b，那么我们只需要穷举子串a最外边的括号的可能性，比如当a最外边为()时，那么这种情况下就有$ \sum_{k_1} dp[0][0][k_1-1][d-1] \times dp[i][j][k-k_1][d] $ 个可能的情况，可以理解为当a最外边括号为（）时，那么a里面的所有括号也必定是（），那么乘法左边就代表a的（）里面所有的可能性，由于这个不算最外层的（），所以深度小于等于d-1，而右边代表b的所有可能性，同理也可以穷举[]和{}和里面的情况。

难以理解的点在于，为什么这种转移函数可以保证没有重复也没有遗漏。这也是困扰我这么久的主要问题。最主要的原因在于这个小于等于d已经包含了这一状态的所有情况，而左边的穷举状态每次都是唯一的，换言之，乘法左边的项是穷举了在d-1情况下的所有的只有一个嵌入式括号的可能性，这当然可以保证无重复。

感觉自己写的也不是很容易让不懂的人看懂，有啥疑问可以提issue哈。

some tips

add #define _CRT_SECURE_NO_WARNINGS to prevent warning of scanf in visual studio

a great oi website oi-wiki

Name		Name	Last commit message	Last commit date
Latest commit History 53 Commits
.gitignore		.gitignore
1006.cpp		1006.cpp
1011_dfs.cpp		1011_dfs.cpp
1017_greedy.cpp		1017_greedy.cpp
1054_enumerate.cpp		1054_enumerate.cpp
1062_spfa.cpp		1062_spfa.cpp
1064_binary_split.cpp		1064_binary_split.cpp
1083_segment_tree.cpp		1083_segment_tree.cpp
1088_dfs.cpp		1088_dfs.cpp
1089_tanxin.cpp		1089_tanxin.cpp
1090_dp_highres.cpp		1090_dp_highres.cpp
1091_number.cpp		1091_number.cpp
1101_bfs.cpp		1101_bfs.cpp
1112_supplementary_graph_color_dp.cpp		1112_supplementary_graph_color_dp.cpp
1113_Convex_hull.cpp		1113_Convex_hull.cpp
1184_dfs.cpp		1184_dfs.cpp
1191_dp.cpp		1191_dp.cpp
1308_union_set.cpp		1308_union_set.cpp
1321_dfs.cpp		1321_dfs.cpp
1322_dp.cpp		1322_dp.cpp
1330_dfs.cpp		1330_dfs.cpp
1330_rmq.cpp		1330_rmq.cpp
1459_network_flow_dinic.cpp		1459_network_flow_dinic.cpp
1595.cpp		1595.cpp
1703_union_set.cpp		1703_union_set.cpp
1703_union_set_exclusive.cpp		1703_union_set_exclusive.cpp
1742_multi_bag.cpp		1742_multi_bag.cpp
1753_dp.cpp		1753_dp.cpp
1789_kruskal.cpp		1789_kruskal.cpp
1789_prim.cpp		1789_prim.cpp
1836_dp_ez.cpp		1836_dp_ez.cpp
1840_hash_table.cpp		1840_hash_table.cpp
1860_bellman_ford_circle.cpp		1860_bellman_ford_circle.cpp
1925_dp.cpp		1925_dp.cpp
1961_kmp.cpp		1961_kmp.cpp
2029_ez.cpp		2029_ez.cpp
2186_scc.cpp		2186_scc.cpp
2388_partition.cpp		2388_partition.cpp
2482_line_segment_tree.cpp		2482_line_segment_tree.cpp
2516_minimum_cost_maximum_flow.cpp		2516_minimum_cost_maximum_flow.cpp
2528_segment_tree.cpp		2528_segment_tree.cpp
2531_dfs.cpp		2531_dfs.cpp
2983_difference_constraints_to_spfa.cpp		2983_difference_constraints_to_spfa.cpp
3041_Hungarian.cpp		3041_Hungarian.cpp
3096_water.cpp		3096_water.cpp
3253.cpp		3253.cpp
3253_Huffman_code_heap.cpp		3253_Huffman_code_heap.cpp
3254_dp_state_compress.cpp		3254_dp_state_compress.cpp
3264_rmq.cpp		3264_rmq.cpp
3267_dp_xuebuhui.cpp		3267_dp_xuebuhui.cpp
3280_interval_dp.cpp		3280_interval_dp.cpp
3295.cpp		3295.cpp
3321_tree_array.cpp		3321_tree_array.cpp
3349_hash.cpp		3349_hash.cpp
3352_bcc.cpp		3352_bcc.cpp
3373_dfs_pruning.cpp		3373_dfs_pruning.cpp
3411_dfs.cpp		3411_dfs.cpp
P1083_segment_tree.cpp		P1083_segment_tree.cpp
P1110 [ZJOI2007]_multiset.cpp		P1110 [ZJOI2007]_multiset.cpp
P1120_dfs.cpp		P1120_dfs.cpp
P1129 [ZJOI2007]_bipartite_graph.cpp		P1129 [ZJOI2007]_bipartite_graph.cpp
P1131 [ZJOI2007]_tree.cpp		P1131 [ZJOI2007]_tree.cpp
P1169 [ZJOI2007]_dp.cpp		P1169 [ZJOI2007]_dp.cpp
P1197_union.cpp		P1197_union.cpp
P1198_ST.cpp		P1198_ST.cpp
P1227_water.cpp		P1227_water.cpp
P1337_gradient_descent.cpp		P1337_gradient_descent.cpp
P1437_dp.cpp		P1437_dp.cpp
P1441.cpp		P1441.cpp
P1514_dfs.cpp		P1514_dfs.cpp
README.md		README.md
kick_start_round_D_2019_X_or_What_moni.cpp		kick_start_round_D_2019_X_or_What_moni.cpp
poj_1067_betti_therom.cpp		poj_1067_betti_therom.cpp
poj_1128_topo_dfs.cpp		poj_1128_topo_dfs.cpp
poj_1132.cpp		poj_1132.cpp
poj_1142.cpp		poj_1142.cpp
poj_1144_cut_point_tarjan.cpp		poj_1144_cut_point_tarjan.cpp
poj_1183.cpp		poj_1183.cpp
poj_1186.cpp		poj_1186.cpp
poj_1186_correct.cpp		poj_1186_correct.cpp
poj_1187_dp.cpp		poj_1187_dp.cpp
poj_1189_ez_dp.cpp		poj_1189_ez_dp.cpp
poj_1190_dfs_prune.cpp		poj_1190_dfs_prune.cpp
poj_1417_union_set_dp.cpp		poj_1417_union_set_dp.cpp
poj_1482_bfs.cpp		poj_1482_bfs.cpp
poj_1952_dp_longest_decreasing_list.cpp		poj_1952_dp_longest_decreasing_list.cpp
template.cpp		template.cpp

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Repository files navigation

poj

some algorithms and problems

some tips

About

Releases

Packages

Languages

BigDeviltjj/poj

Folders and files

Latest commit

History

Repository files navigation

poj

some algorithms and problems

some tips

About

Resources

Stars

Watchers

Forks

Releases

Packages 0

Languages

Packages