0w1

POJ

POJ 1006 Biorhythms ( CRT, ExtGCD )

1006 -- Biorhythms題意: 細節不好說明,但總之給 p, i, e, d,滿足聯立模方程式: ( x + d ) % 23 = p ( x + d ) % 28 = e ( x + d ) % 33 = i 求 x。解法: 就是一個中國剩餘定理模板。28 非質數,如果要用尤拉定理搞要先求 phi 函數才能求模逆元,但最近…

POJ 3866 Exclusive Access 2 ( Dilworth Theorem, DP, bitmask )

3866 -- Exclusive Access 2題意: 給一個 N 個無向邊的圖。求一種方案使所有邊定向,並有最短的最長路徑 ( 即不存在環 )。無法到達的點對之間的路徑長不須考慮。資料規模: N ≤ 100 節點為 [ L, Z ] 間的大寫英文字母,數量不超過 15。 TL: 5000 ms ML: 655…

POJ 1065 Wooden Sticks ( Dilworth theorem, LIS )

1065 -- Wooden SticksDilworth Theorem題意: T 筆測資。給 N 個座標,求排序後最少的相鄰對數滿足右邊的點不在以左邊的點為原點的第一象限 ( 在線上也算第一象限 )。資料規模: The input consists of T test cases. The number of test cases (T) is give…

POJ 2127 Greatest Common Increasing Subsequence ( DP )

2127 -- Greatest Common Increasing Subsequence題意: 給兩個數列 A, B,長度分別為 N, M,求最長公共遞增子序列。資料規模: 元素大小在 int32 範圍 N, M ≤ 500 TL: 2000 ms解法: 顯然可以定義 O( N^3 ) 的 dp,但這裡考慮 O( N^2 )。 dp[ i ][ j ] : B[…

POJ 1180 Batch Scheduling ( Slope Optimization DP )

1180 -- Batch Scheduling題意: 有 N 個工作,用 T[ i ], F[ i ] 描述第 i 個工作需要花費的時間,以及單位時間的價值。第 i + 1 個工作不能在第 i 個工作完成之前被完成。每次可以選擇 k 個,未完成的工作中編號最小的工作,花費其 T 的總和,令之 P,的時…

POJ 1456 Supermarket ( Greedy + Union Find )

1456 -- Supermarket 很顯然要從最貴的開始放,而且是放到離他期限最近的時間點。我們需要快速查詢 lastDay[ i ],代表第 i天( 含 )之前最晚的還沒有賣東西的時間,又因為這件事可以指來指去 i.e. lastDay[ 5 ] = 3 AND lastDay[ 3 ] = 1 -> lastDay[ 5 ] = …

POJ 1182 Food Chain ( Union Find )

1182 -- 食物链 這題解法我覺得很特別,是要維護哪些情報有相互證明的關係,哪些情報有相互排斥的關係,哪些情報沒有關係。這些都可以透過並查集的一些小技巧解決。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 4; const int MAXK = 1e5 + 5; in</bits/stdc++.h>…

POJ 2019 Cornfields ( 2D Segment Tree )

2019 -- Cornfields ふぁぁ、初めての二次元セグメント木AC。楽しかったです。でも僕はポインタの書き方にしかなれないから、メモリを静態に宣告しなければTLEしてしまいます。でもMAXMEMをちゃんと十分( RE )で多すぎない( MLE ) ように工夫するのは難しい…

POJ 1631 Bridging signals ( Easy LIS )

POJ

1631 -- Bridging signals tozangezan.hatenablog.com tozangezanさんのブログでセグメント木の問題をたくさんもらいました、ありがとうございます。でもこれだけは。。。LISだけじゃないの?と自分を疑いながらとりあえずか書いてみました。ACしました。ま…

Persistent segment tree

2104 -- K-th Number Given n ≤ 1e5 numbers a1, a2 .., an, then there are m ≤ 1e5 queries [ l, r ], for each query, answer the k-th minimum number among al, a(l + 1) .., ar. First we discretize the integers so that there are at most 1e5 inte…

POJ 3260 The Fewest Coins ( Knapsack multiple & complete DP )

3260 -- The Fewest Coins n ≤ 100 types of currency exists, each value v[i] ≤ 120, and I have c[i] ≤ 100 of them. Answer the minimum sum of coins that I have to give and take, when I am to buy a product of T ≤ 10000 dollars. This is basical…

Lowest common ancestor

I have finally started to understand the LCA algorithm for transforming to RMQ. Here are the basic steps for static LCA queries: 1. DFS from any node as the root for the tree, making timestamps as it goes ( called the Euler's tour ). 3 bas…

POJ 1236 Network of Schools IOI 1996

1236 -- Network of Schools Given a network, answer at least how many nodes we need to spread information to let the whole graph know, and the minimum directed edges required to add so the whole graph becomes an SCC. The first query is just…

Monotonous slope optimization DP

This optimization is also called "Convex Hull Trick" because it is either maintaining an upper convex hull ( decreasing slopes ) or a lower convex hull. Also note that there are problems that do not necessarily have to be monotonous but st…

Introduction to deque optimizations

A deque ( double ended queue ) is a data structure that supports push/ pop from both ends with constant time complexity. It can be used to optimize algorithms that deal with monotonous properties. The first time I saw this data structure, …

Introduction to stack optimizations

Stacks can be used to maintain for monotonous properties, can optimize for many problems, but only if you can discover the monotony in the problem. Here are some problems for exercise from the ant book. 3250 -- Bad Hair Day POJ 3250 Bad Ha…