Problem Description: Given some constraints formed with two variables, and operator of OR, AND, or XOR, you are to find whether there exists a solution to satisfy all the constraints.Constraints: 1 ≤ N ≤ 1000 (number of variables) 1 ≤ M ≤ …

Problem Description: Two players take turn in playing a game on a 1 x N board. When it is a player's turn, he puts a marker on a grid that had no marker. If after a movement there are 3 consecutive markers on the board, the player who made…

Problem Description: There are N piles of stones, each with no more than 100 stones. Two players play this game, when it is one's turn, one should: Select a non-empty pile, remove at least one stone, then take arbitrary number of stones fr…

Problem Description: Three colors of beads are available. Count the number of different circular necklace that could be formed. Two necklaces are identical iff after some rotation or flip, each position has the same color of bead.Constrain…

Problem Description: There are N switches and N technicians. Each technician has a list of valves, and if he were hired, he would flip the switch of each of them in his list. It is known that for any technician i, it is impossible to repla…

Problem Description: f(x) = 1, if x = 0 B ** f(x - 1), otherwise Given B, I, and N, find the last N digits of f(I).Constraints: Solution: We want to find . For any , we can observe that in , we can always find some such that . We will recu…

Problem Description: You have a for loop that looks like this: for (value_type i = A; i != B; i += C) ; , where value_type is K-bits unsigned integer data type. You want to know whether the loop will reach an end, and if it will, the numbe…

Problem Description: Given N, M, find the last non-zero digit in N! / (N - M)!.Constraints: 0 ≤ M ≤ N ≤ 2e7Solution: We can find a and k such that in O(lg x) time, given that e is 2 or 5 (because they are prime, we can apply Wilson's theor…

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

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

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

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[…

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

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

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

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

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

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…

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…

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…

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…

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…

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, …

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…