0w1

POI

POI 18 Stage 3 Meteors ( Parallel Binary Search, Fenwick Tree )

http://main.edu.pl/en/archive/oi/18/met題意: 有 M 個環狀的地,每個地屬於一個人。有 K 次隕石事件,每次會在某一連續區間 [ L[ i ], R[ i ] ] 每個地分別降下有 W[ i ] 單位的隕石。有 N 個人,每個人有最少需要收集的隕石量 P[ i ]。要求分別輸出每個…

POI 21 Stage 1 Couriers ( Persistent Segment Tree )

http://main.edu.pl/en/archive/oi/21/kur題意: 給一個長度 N 的數列,接著 M 筆詢問 [ L, R ] 中是否有個數字是絕對多數,有的話輸出該數字。資料規模: N, M ≤ 5e5 1 ≤ P ≤ N TL: 12000 ms ML: 128 MB解法: 一個持久化裸題,但記憶體卡得比較緊,要用離…

POI 2 Stage 3 Job Scheduling ( Greedy, Math )

http://main.edu.pl/en/archive/oi/2/sze題意: 有 N 個工作,假設當前時間已經過 T 單位,那麼工作 i 需要花費的時間為 A[ i ] * T + B[ i ]。一次只能做一個工作,問最短時間完成的工作序列。資料規模: In the first line of the standard input there is…

POI 2 Stage 3 Step Traversing a Tree ( DFS )

http://main.edu.pl/en/archive/oi/2/obc題意: 給一棵樹,求一個序列,可以不重複拜訪所有節點,而且相鄰節點距離不超過 3。資料規模: In the first line of the standard input there is a positive integer n, not greater than 5000 - it is the number…

POI 2 Stage 3 Coding of Permutations ( Fenwick Tree, Binary Search )

http://main.edu.pl/en/archive/oi/2/kod題意: 給一個序列 B,問是否有一個 [ 1, | B | ] 的排列 A,使得 B[ i ] 等於 A[ 0, i ) 中比 A[ i ] 大的數字的數量。輸出方案。資料規模: In the first line of the standard input there is a positive integer …

POI 2 Stage 2 Board Covering ( Bipartite Matching )

http://main.edu.pl/en/archive/oi/2/sza題意: 給一個 N * N 的棋盤,X, Y, Z 三塊為不用覆蓋的,求是否可以用 2 * 1 ( 可旋轉 ) 的東西覆蓋滿棋盤,可以的話輸出方案。資料規模: In the only line of the standard input there are written four numbers …

POI 2 Stage 2 Triangles ( Ad hoc, Math, Fibonacci )

http://main.edu.pl/en/archive/oi/2/tro題意: 給很多邊的長度,問是否可以構成三角形,可以的話輸出方案。資料規模: In the standard input there is a finite sequence of at least three positive integers not greater then 1e9, terminated by the nu…

POI 2 Stage 2 Mudstock Bis ( Tree, DP )

http://main.edu.pl/en/archive/oi/2/mud題意: 首都在 ( 0, 0 ) 的位置,有 M 個人在首都裡。接著有 L 條線,每條線有若干個城市,依序用線上和前一個 ( 第一個城市和首都 ) 的距離以及人數描述。要求選一個點使得所有人到該點的總花費最小,一個人行走一單…

POI 2 Stage 2 The Right-Turn Drivers' Club ( DP, BFS )

http://main.edu.pl/en/archive/oi/2/kpk題意: 給一張圖,有若干障礙物,給始點和終點,問是否可以不左轉不倒回從始點走到終點,可以的話輸出最短路徑的方案。資料規模: In the first line of the standard input there are two integers separated by a s…

POI 2 Stage 1 Palindromes ( DP, Hash )

http://main.edu.pl/en/archive/oi/2/pal題意: 給一個字串,問最多和最少可以拆分成幾個偶數長度迴文,存在的話輸出方案。資料規模: The standard input contains one word consisting of at least 1 and at most 200 small letters of English alphabet. …

POI 2 Stage 1 Trees ( DFS )

http://main.edu.pl/en/archive/oi/2/drz題意: 這裡限制樹的每個節點的兒節點必須是 0 或者 2,否則不稱做樹。 給編號由小到大的葉節點的深度,求樹是否存在,存在的話輸出每個節點的父節點編號,以及樹的括號序列表示。資料規模: In the first line of th…

POI 19 Fibonacci Representation ( DP )

http://main.edu.pl/en/archive/oi/19/rozIDDFSで頑張ろうとしたが、当たり前にもTLEした。 24 / 100。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MAXK = 4e17 + 4; int maxd; vector< ll > fib; bool dfs(ll k, int d){ if( k == 0 )</bits/stdc++.h>…