0w1

Binary Enumeration

AGC 12 C - Tautonym Puzzle ( Binary Enumeration )

C: Tautonym Puzzle - AtCoder Grand Contest 012 | AtCoder題意: 要求構造一個字串 S,使得 S 有洽 N 個偶數長度 ( ≥ 2 ) 的子序列,使得子序列前半等於子序列後半。資料規模: 1≦|s|≦200 s は 1 から 100 までの整数で表される 100 種類の文字のみからな…

CFR 389 D. Fox and Minimal path ( Binary Enumeration )

Problem - D - Codeforces題意: 給 K,求一個無向圖鄰接矩陣,使得節點 1 到節點 2 的最短路徑恰有 K 個。資料規模: 1 ≤ K ≤ 1e9 輸出的圖的節點數 ≤ 1000解法: 考慮二進制枚舉,需要 *2 就往右連一個菱形,需要 +1 就從節點 1 連到當前的終點。 #include <bits/stdc++.h></bits/stdc++.h>…

CFR 745 D. Hongcow's Game ( Binary Enumeration, Interactive )

Problem - D - Codeforces題意: 有一個 N * N 的矩陣,裡面各自有 0 ~ 1e9 之間的整數,且對角線所有數值必為 0。你可以做詢問,用直列的編號們描述,對方會回答每個行分別對這些直列編號求的最小值。試用 20 次以內的詢問,得出所有行不含對角線的 0,分別…

CFR 732 F. Anton and School ( Ad hoc, Binary Enumeration )

Problem - F - Codeforces前言: Codeforces Round #379 (Div. 2) F. Anton and School - pekempeyのブログ pekempeyさんの記事読んでやっとわかった。題意: 給相同長度的 B 序列和 C 序列。求是否存在一個 A 序列,滿足 不存在則輸出 -1,否則輸出滿足的任…

CFR 147 B. Smile House ( Binary Search, Fast Matrix Multiplication, DP, Binary Enumeration )

Problem - B - Codeforces題意: 給一個圖,邊用四個值表示,( x, y, Cxy, Cyx ),代表 x 至 y 長度是 Cxy,y 至 x 長度是 Cyx。求是否存在一個正環,若存在則輸出最小環的長度。資料規模: 節點數 1 ≤ N ≤ 300 邊數 0 ≤ M ≤ N * ( N - 1 ) / 2 權值 -1e4 ≤ …

TOIJ 1014 打地鼠 ( bitset DP )

1014 - 打地鼠 | TIOJ INFOR Online Judge 挺水的。O( ( n ^ 2 ) * ( 2 ^ n ) ) #include <bits/stdc++.h> using namespace std; const int MAXN = 16 + 2; const int MAXA = 1e8 + 8; const int INF = 2e9; int n; int a[ MAXN ]; int dp[ MAXN ][ 1 << MAXN ]; // last hi</bits/stdc++.h>…

IOI'94 The Clocks ( Binary Enumeration )

PEG Judge - IOI '94 - The Clocks 一開始想用 PFS,後來想一想沒有權重可以直接BFS,寫完丟出去才發現 RE / TLE。。 // Will TLE O( ( ans.size() ) ! ) #include <bits/stdc++.h> using namespace std; struct State{ int clk[ 9 ]; State(){} void read(){ for(int i = 0</bits/stdc++.h>…

UVA 10817 Headmaster's Headache ( 位元DP )

UVa Online Judge 前 m個老師就無選擇給他取下來,其他 n個分開來搜用與不用的情況。哪些課有兩個老師上、一個老師上、或還沒有老師可以上用狀態記錄下來,輪一輪,調一下就應該要水過去了。 碎念:這題真是我永遠的苦痛,TOI考過一模一樣的題目,那時候真菜…

TPC追いコン B - ライツアウト ( Binary Enumeration )

B: ライツアウト - TPC追いコン | AtCoder 定数倍で TLEしまくって諦めた。どうして時間がこんなにきついんだろう。。 1753 -- Flip Game 同じような問題だけど、今度のは bitによる状態の変化を加速するための前処理でやらないと通らない。以下のはギリギリ…