【BZOJ】1064:[Noi 2008]仮面舞踏会(判環+gcd+特殊なテクニック)
5071 ワード
http://www.lydsy.com/JudgeOnline/problem.php?id=1064
あることを思いつくと书けなくなる...
リングを探すgcdです..怖いですね.
そこで問題解を拝みました.
私の考えとあまり差がありません.の
まず、この3つの状況を発見します.
1、単一の鎖または複数の単一の鎖の任意の2つが連続するセグメントにのみ交差する単一の鎖ブロック.最大の答えは$sum|単鎖|+sum|単鎖ブロック種の最も長い鎖|$,最小の答えは3である.
2、リング.ループの長さは最大答えの倍数であるため,gcdをとると符号差(1回目アクセスと2回目アクセスの符号差)と見なすこともできる.
3、単一鎖は少なくとも2つの異なる連続するセグメントに交差する.彼らのラベル差(1回目のアクセスと2回目のアクセスのラベル差)は最大答えの倍数です.
最大答えはすべての場合の最大答えのgcdです.最小解答が1つ目の場合のみ3であり,そうでなければ最大解答の>=3の最小因数である.
もし私たちが直接やると面倒ですが、状況2と状況3はどう計算しますか?
解決策はとても巧みです!http://hi.baidu.com/lydrainbowcat/item/f3fdc53164770bd76d15e980
これは有向図で、私たちはそれを無方向図に変えて、それでは任意の点からすべて環の大きさと情況の3の記号の差を得ることができるのではありませんか..
このような1辺の重み値は1である、逆辺の重み値は-1である.
このような場合2と場合3は符号差のgcdである.
ケース1は、上記の方法でケース2を処理する際に最長チェーンの長さを見つければよい、すなわち、max{num}-min{num}+1
最後に答えを分類して議論します.
Description
年に一度の仮面舞踏会が始まり、棟棟も興味津々で今年の舞踏会に参加した.今年のマスクは主催者が特別にカスタマイズしたものだ.ダンスパーティーに参加する人はみな入場時に自分の好きな仮面を選ぶことができる.各マスクには番号があり、主催者はこの番号をマスクを持っている人に教えます.舞踏会をより神秘的にするため、主催者はマスクをk(k≧3)類に分け、特殊な技術を用いて各マスクの番号をマスクに表示し、i類マスクをかぶった人だけがi+1類マスクをかぶった人の番号を見ることができ、k類マスクをかぶった人は1類マスクをかぶった人の番号を見ることができる.舞踏会に参加した人は何種類の仮面があるか分からないが、棟棟棟は特に好奇心を持って、自分で何種類の仮面があるかを計算したいと思って、人ごみの中で情報を収集し始めた.棟が収集した情報は、何番目の仮面をかぶった人が何番目の仮面の番号を見たかだ.2番目の仮面をかぶった人が5番目の仮面の番号を見たように.棟棟自身もいくつかの番号を見ることができ、彼も自分のマスク番号に基づいて情報を補充します.誰もが自分が見たすべての番号を覚えているわけではないので、棟が収集した情報は完全性を保証することはできません.今計算してください.棟が現在得ている情報によると、せいぜいどれだけの種類の仮面がありますか.主催者側はk≧3と宣言しているので、この情報も考慮しなければなりません.
Input
1行目は2つの整数n,mを含み,1つのスペースで区切られ,nは主催者が全部で何個の仮面を用意したか,mは棟が何個の情報を収集したかを示す.次にm行、行ごとに2つのスペースで区切られた整数a,bは、a番目のマスクをかぶった人がb番目のマスクの番号を見たことを示す.同じ数のa,bは入力ファイルに複数回現れる可能性がある.
Output
2つの数を含み、1番目の数は最大可能なマスククラス数、2番目の数は最小可能なマスククラス数である.すべてのマスクを少なくとも3種類に分けてこれらの情報が満たされない場合、棟が収集した情報に誤りがあると判断し、2つの−1を出力する.
Sample Input
【入力サンプル一】
6 5
1 2
2 3
3 4
4 1
3 5
【入力サンプル2】
3 3
1 2
2 1
2 3
Sample Output
【出力サンプル一】
4 4
【出力サンプル2】
-1 -1
HINT
100%のデータは、n≦100000、m≦100000を満たす.
Source
あることを思いつくと书けなくなる...
リングを探すgcdです..怖いですね.
そこで問題解を拝みました.
私の考えとあまり差がありません.の
まず、この3つの状況を発見します.
1、単一の鎖または複数の単一の鎖の任意の2つが連続するセグメントにのみ交差する単一の鎖ブロック.最大の答えは$sum|単鎖|+sum|単鎖ブロック種の最も長い鎖|$,最小の答えは3である.
2、リング.ループの長さは最大答えの倍数であるため,gcdをとると符号差(1回目アクセスと2回目アクセスの符号差)と見なすこともできる.
3、単一鎖は少なくとも2つの異なる連続するセグメントに交差する.彼らのラベル差(1回目のアクセスと2回目のアクセスのラベル差)は最大答えの倍数です.
最大答えはすべての場合の最大答えのgcdです.最小解答が1つ目の場合のみ3であり,そうでなければ最大解答の>=3の最小因数である.
もし私たちが直接やると面倒ですが、状況2と状況3はどう計算しますか?
解決策はとても巧みです!http://hi.baidu.com/lydrainbowcat/item/f3fdc53164770bd76d15e980
これは有向図で、私たちはそれを無方向図に変えて、それでは任意の点からすべて環の大きさと情況の3の記号の差を得ることができるのではありませんか..
このような1辺の重み値は1である、逆辺の重み値は-1である.
このような場合2と場合3は符号差のgcdである.
ケース1は、上記の方法でケース2を処理する際に最長チェーンの長さを見つければよい、すなわち、max{num}-min{num}+1
最後に答えを分類して議論します.
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mkpii make_pair<int, int>
#define pdi pair<double, int>
#define mkpdi make_pair<double, int>
#define pli pair<ll, int>
#define mkpli make_pair<ll, int>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define error(x) (!(x)?puts("error"):0)
#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }
#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; }
const int N=100015;
int ihead[N], cnt, m, n, num[N], q[N], vis[N], cir, sum, ans;
struct dat { int next, to, w; }e[N*10*2];
void add(int u, int v, int w) { e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v; e[cnt].w=w; }
inline const int gcd(const int &a, const int &b) { return b?gcd(b, a%b):a; }
int main() {
read(n); read(m);
for1(i, 1, m) { int u=getint(), v=getint(); add(u, v, 1); add(v, u, -1); }
for1(k, 1, n) if(!vis[k]) {
int front=0, tail=0;
q[tail++]=k;
int mx=0, mn=0;
while(front!=tail) {
int x=q[front++]; if(front==N) front=0;
mx=max(mx, num[x]);
mn=min(mn, num[x]);
for(int i=ihead[x]; i; i=e[i].next) {
int y=e[i].to;
if(vis[y]) cir=gcd(cir, abs(num[x]+e[i].w-num[y])), mx=max(mx, num[y]);
else {
q[tail++]=y; if(tail==N) tail=0;
num[y]=num[x]+e[i].w;
vis[y]=1;
}
}
}
sum+=mx-mn+1;
}
if(cir && cir<3) return puts("-1 -1"), 0;
if(cir) { int i=3; while(cir%i) ++i; printf("%d %d
", cir, i); return 0; }
if(sum<3) return puts("-1 -1"), 0;
printf("%d 3
", sum);
return 0;
}
Description
年に一度の仮面舞踏会が始まり、棟棟も興味津々で今年の舞踏会に参加した.今年のマスクは主催者が特別にカスタマイズしたものだ.ダンスパーティーに参加する人はみな入場時に自分の好きな仮面を選ぶことができる.各マスクには番号があり、主催者はこの番号をマスクを持っている人に教えます.舞踏会をより神秘的にするため、主催者はマスクをk(k≧3)類に分け、特殊な技術を用いて各マスクの番号をマスクに表示し、i類マスクをかぶった人だけがi+1類マスクをかぶった人の番号を見ることができ、k類マスクをかぶった人は1類マスクをかぶった人の番号を見ることができる.舞踏会に参加した人は何種類の仮面があるか分からないが、棟棟棟は特に好奇心を持って、自分で何種類の仮面があるかを計算したいと思って、人ごみの中で情報を収集し始めた.棟が収集した情報は、何番目の仮面をかぶった人が何番目の仮面の番号を見たかだ.2番目の仮面をかぶった人が5番目の仮面の番号を見たように.棟棟自身もいくつかの番号を見ることができ、彼も自分のマスク番号に基づいて情報を補充します.誰もが自分が見たすべての番号を覚えているわけではないので、棟が収集した情報は完全性を保証することはできません.今計算してください.棟が現在得ている情報によると、せいぜいどれだけの種類の仮面がありますか.主催者側はk≧3と宣言しているので、この情報も考慮しなければなりません.
Input
1行目は2つの整数n,mを含み,1つのスペースで区切られ,nは主催者が全部で何個の仮面を用意したか,mは棟が何個の情報を収集したかを示す.次にm行、行ごとに2つのスペースで区切られた整数a,bは、a番目のマスクをかぶった人がb番目のマスクの番号を見たことを示す.同じ数のa,bは入力ファイルに複数回現れる可能性がある.
Output
2つの数を含み、1番目の数は最大可能なマスククラス数、2番目の数は最小可能なマスククラス数である.すべてのマスクを少なくとも3種類に分けてこれらの情報が満たされない場合、棟が収集した情報に誤りがあると判断し、2つの−1を出力する.
Sample Input
【入力サンプル一】
6 5
1 2
2 3
3 4
4 1
3 5
【入力サンプル2】
3 3
1 2
2 1
2 3
Sample Output
【出力サンプル一】
4 4
【出力サンプル2】
-1 -1
HINT
100%のデータは、n≦100000、m≦100000を満たす.
Source