解法：Segment Tree(RMQ)セグツリやるだけUSACOの問題。Range Minimum QueryとRange Maximum Queryを同時に処理する。計算量O(Q lg N). #include <cstdio> #include <algorithm> #include <climits> using namespace std; typedef pair<int,int> P; int n,q,seg[2][121072],nn; P query(int a,int </int,int></climits></algorithm></cstdio>…

想定解は二次元累積和なのですが二次元BITの練習のため二次元BITで解いてみた。 本番では絶対こんな手法は使わない。 計算量はO(K*logM*logN)でだいたいO(10^7)ぐらいなので間に合う。 #include <bits/stdc++.h> using namespace std; int bit[3][1010][1010]; int m,n,k; i</bits/stdc++.h>…

以前バケット法でも解けますとか言ってたので解いた。第7回日本情報オリンピック 春合宿 1日目 「インフルエンザ」 (Flu) - intさわだんのBlack History 第7回日本情報オリンピック 春合宿 1日目 「インフルエンザ」 (Flu) - intさわだんのBlack Historyバケ…

例の平方分割で解ける問題バケットのサイズを色々試してみた。B = 1100 → TLE (>20000MS) B = 1000 → 11735MS B = 900 → 11782MS B = 850 → 11829MS B = 800 → 11157MS B = 700 → 12235MS結果B = 800が一番早い（？） #include <cstdio> #include <vector> #include <algorithm> using n</algorithm></vector></cstdio>…

詳しくは蟻本p99参照クラスカルやるだけ。unionfindとkruskalなんも見ないで実装できたのでgood. #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 20003; const int MAX_E = 50003; int par[MAX_N]; int rank[MAX_N]; struct edge{int from,to,</algorithm></cstdio>…

昨日の夜POJ落ちてたが復旧していた。SegmentTreeつかわなくてもできそうだが練習のため使用。LanguageをG++ではTLEになったがC++にしたら通った。 POJの闇である。 #include <cstdio> #include <climits> #include <algorithm> #include <utility> #include <iostream> //http://poj.org/problem?id=2823 us</iostream></utility></algorithm></climits></cstdio>…

頭が悪い。解法： priority_queueと、二分探索をもちいた。 おそらくJOI解説とほとんどおんなじ。 気が向いたら詳しく説明します。priority_queue、大きいほうからでてくるのすっかり忘れてましたね #include <cstdio> #include <utility> #include <queue> #include <vector> #include <algorithm> usin</algorithm></vector></queue></utility></cstdio>…

問題概要 学生の数(n)、クエリの数(m)が与えられる。各クエリはn以下の二つの整数があり二人の学生は同じ宗教であることを示している。 学校内で予想できる最大の宗教の数はいくつかもとめる。 解法 Union-Findやるだけ 自分が親であるのをカウント。これも…

union find参考にさせていただきました。 http://d.hatena.ne.jp/sndr/20121221/1356071878 #include <cstdio> #include <iostream> using namespace std; int par[200003];//親 int rank[200003];//木の深さ void init(int n){ for(int i = 0;i < n;i++){ par[i] = i; rank[i]</iostream></cstdio>…

顕著なunion-find実行速度遅すぎる。 #include <cstdio> #include <iostream> using namespace std; int par[1002];//親 int rank[1002];//木の深さ void init(int n){ for(int i = 0;i < n;i++){ par[i] = i; rank[i] = 0; } } int find(int x){ if(par[x] == x){ return x; }</iostream></cstdio>…