Problem Description: There are T standalone test cases in this problem. In the beginning, there are A units of bacteria. For any moment t with x units of bacteria, we know that moment t + 1 would have x**x units of bacteria. Given A, B, C,…

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…

Problem Description: Given a non-negative integer N, find the number of i, such that C(N, i) % 2 == 0 and 0 ≤ i ≤ N.Constraints: 0 ≤ N ≤ 1e18Solution: According Lucas's theorem, since we are considering modulo 2, we can observe that i can …

Problem Description: There are K kinds of colors, each with at least one instance of object. There are C[i] number of instances of color i. You are to arrange them into a ring, and you want to know how many different kinds of rings could b…

Problem Description: There are 6 kinds of coins, with units 1, 5, 10, 50, 100, 500, respectively. You have infinite number of each of them. You are to deal with T test cases, and in each case you will be given a value M, where you should o…

#include <iostream> #include <cmath> #include <algorithm> #include <complex> #include <vector> #include <iomanip> using namespace std; namespace kika { // using cod = complex<double>; typedef complex<double> cod; const double EPS = 1e-9; const double PI = acos(-1); int dcmp(double x) { if (abs(x) < …</double></double></iomanip></vector></complex></algorithm></cmath></iostream>

Problem - 444C - Codeforces題意： 給長度 N 的數列 A[]。初始時 A[ i ] = i, for all 1 ≤ i ≤ N。 M 筆詢問，兩種形式： 1 l r x：將 [ l, r ] 都塗色為 x 2 l r：輸出 [ l, r ] 的貢獻總和 初始時所有元素的貢獻為 0。 當一個元素由 u 變為 v 時，增加貢…

Problem - 522D - Codeforces題意： 給你長度 N 的數列 A[]。 M 筆詢問，問 [ L, R ] 中，最近的相同元素距離是多少。若不存在，輸出 -1。制約： 1 ≤ N, M ≤ 5e5 abs( A[ i ] ) ≤ 1e9解法： 可以很快想到，給每一個位置 i 紀錄前一個 A[ i ] 的位置 pre[ i ]…

Problem - 566D - Codeforces題意： 給你 N 個人，初始時他們自己一個組。 Q 筆詢問，三種形式： 1 x y：merge( x, y ) 2 x y：merge( x, x + 1, ..., y ) 3 x y：print "YES" if group( x ) == group( y ) else "NO"制約： 1 ≤ N ≤ 2e5 1 ≤ Q ≤ 5e5解法： …

Problem - C - Codeforces題意： 給你 N 次多項式 F()。 係數的絕對值不能超過 K。 問你修改一個值之後，F( 2 ) = 0 的方案數。 特別的，A[ N ] != 0。制約： 1 ≤ N ≤ 2e5 abs( K ) ≤ 1e9解法： 哈希水掉。 原本不能暴力算的原因只是因為數字會太大，不過哈…

Problem - D - Codeforces題意： 給長度 N 的字串，以及定數 K。 對於 i = [ 0 .. N - 1 ]，問是否存在字串 A 和 B，使得 A + B + A + B .. + A = S[ 0 .. i ]，其中 A 重複 K + 1 次，B 重複 K 次。 A, B 可為空字串。制約： 1 ≤ N, K ≤ 1e6解法： KMP 真是…

F: Lotus Leaves - AtCoder Regular Contest 074 | AtCoder題意： H * W 的棋盤。 起點 S，終點 T。這兩個點都有葉子。 其他葉子用 'o' 描述。 每次可以選擇同行或同列的 'o' 移動到那裡。 問最少要移除多少葉子才能使 S 不能到達 T。無解輸出 -1。制約： 2≤…

E: RGB Sequence - AtCoder Regular Contest 074 | AtCoder題意： N 個格子一排。 有三種顏色可以塗。 M 條限制，表示 [ L, R ] 中要有 X 種顏色。 求方案數模 1e9 + 7。制約： 1≤N≤300 1≤M≤300 1≤li≤ri≤N 1≤xi≤3解法： dp[ i ][ j ][ k ]：第 { 1, 2, 3 } …

D: 3N Numbers - AtCoder Regular Contest 074 | AtCoder題意： 給長度 3 * N 的數列 A[]。刪除 N 個元素後，希望前 N 個元素總和 - 後 N 個元素總和最大。制約： N ≤ 1e5 1 ≤ A[ i ] ≤ 1e9解法： 考慮一條線，從 N 掃描到 2 * N。 這條線會將數列分成兩塊，…

C: Chocolate Bar - AtCoder Regular Contest 074 | AtCoder題意： 把巧克力沿著線切，分成三個非空的塊。 問最大和最小的塊的面積差最小是多少。制約： 2 ≤ H, W ≤ 1e5解法： 只可能有兩種切法 | | | 或 | -。90 度旋轉再做一樣的事情。 第一刀切下去之後顯…

https://www.hackerearth.com/challenge/competitive/may-circuits-17/algorithm/zulu-visits-wonderla-1/題意： N 層的地下迷宮，M 種物品。 在時間 x，你能拿第 i 個物品若且唯若所有 Level 比 Level[ i ] 小的物品的過期時間不早於 x，並且 x + Time[ i ]…

https://www.hackerearth.com/problem/algorithm/zulu-and-alarm-clock-1/題意： T 筆測資。 N 個鬧鐘，K 個時間。 你要把 K 個鬧鐘調成這 K 個時間。 你可以上下調整時、秒、分，會進位退位。 問最小調整次數。制約： 1≤T≤2 1≤N≤50 1≤K≤17解法： 可以用遮罩…

Problem - 492D - Codeforces題意： 甲 1 / X 秒攻擊一次，乙 1 / Y 秒攻擊一次。 對於第 i 隻怪獸，其耐打 A[ i ] 次，問最後一擊是誰的。制約： 1 ≤ N ≤ 1e5 1 ≤ X, Y ≤ 1e6 1 ≤ A[ i ] ≤ 1e9解法： 二分搜打死怪獸的最早時間。 只要知道這個時間，判斷一…

Problem - 611D - Codeforces題意： 給你一個大數。要求分割成若干個數字，滿足嚴格遞增，而且沒有領導 0。 問方案數對 1e9 + 7 取模。制約： 1 ≤ N ≤ 5000 保證第一個字符不為 '0'。解法： dp[ i ][ j ]：最後一個數字是 S[ i : j ] 時的方案數。 想知道 dp…

Problem - 1C - Codeforces題意： 有一個正 N 邊形，給你其中三個點，問最小可能面積。制約： 保證最佳的 N 不超過 100。解法： 用餘弦定理求的三個角分別多少。 用正弦定理求外接圓半徑。 枚舉 N，如果三個圓心角都是 360 度 / N 的整數倍，那麼就能直接算…

Problem - 491C - Codeforces題意： 給你長度 N 的字串 A 以及字串 B。 你可以做一組字母對字母的一對一映射，使得同位置相符的字符數量最多。制約： 1 ≤ N ≤ 2e6 1 ≤ K ≤ 52解法： MCMF 亂流。 映射前映射後。 源點建弧到映射前的容量是 1，費用是映射前的…

Problem - 62E - Codeforces題意： 給一個多角形柱體形成的網路，問最大流是多少。 起點是上面的面的所有點，匯點是下面的面的所有點。制約： 2 ≤ N ≤ 5 2 ≤ M ≤ 1e5 解法： 顯然不能暴力跑網路流算法。 考慮用 dp 求解。 最大流不好求，求最小割。 考慮水平…

Problem - 434D - Codeforces題意： 有 N 個二次函數，以及 M 條不等式。 你想要最大化所有二次函數的輸出的總和。 對於第 i 個二次函數，參數範圍是 [ L[ i ], R[ i ] ] 的整數。 第 i 條不等式表示 X[ U[ i ] ] ≤ X[ V[ i ] ] + D[ i ]。 問最大輸出總和。…

Problem - 811D - Codeforces題意： 給一張地圖，有些是炸彈，走上去馬上死。 起點在左上角，目標是 'F'。 你可以上下左右移動，但是上和下的控制可能是反的，左右也是。 互動走到 F。 操作數不可超過 2 * N * M。制約： 1 ≤ N, M ≤ 100 保證有至少一條路徑…

Problem - 811C - Codeforces 題意： 給長度 N 的數列 A[]。你想要取出若干個連續數列，使得每個數列中相異元素的 XOR 和，之和最大。 但是有個條件，如果某個元素 x 在取出的某個數列裡，那麼所有元素 x 都必須在該數列中。制約： 1 ≤ N ≤ 5000 0 ≤ A[ i ] …

Problem - 513F2 - Codeforces題意： 有個 N * M 棋盤，有些格子是障礙。 有一個怪盜，以及 Males 個男生，Females 個女生。 這些人都會用 r, c, t 表示座標位置以及移動一單位距離所需要的時間。 問至少要多少時間，才能使每個人都恰好和一位異性在同一個格…

Problem - 739E - Codeforces題意： 你有 A 個普通球，B 個超級球。 有 N 隻神奇寶貝。 對於第 i 隻神奇寶貝，如果用普通球，抓到的機率是 P[ i ]; 如果用超級球，抓到的機率是 U[ i ]。 對於同一隻神奇寶貝，兩種球都只能至多丟一次。 問最佳策略下，期望可…

Problem - 78E - Codeforces題意： 在 N * N 的地圖上，有一些格子是障礙物，有些有若干個科學家，有些有若干個氧氣筒。 在時刻 0，某個障礙物腐朽瓦解，發出毒氣，並向相鄰非障礙物的格子以一單位時間一格的速率擴散。 科學家只要移動到有氧氣筒的地方，就…