SWUST ACM訓練問題部分問題解hdu 1384&&hdu 3666&&hdu 4786&&uva 1395&&uva 1151
14564 ワード
トレーニングテーマのWebサイト:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=99765#problem/A パスワード:acm 2015
B - Intervals (hdu1384)
題意:n区間の各区間の範囲を[l,r]とし、num個の整数を確定させ、このnum個の整数がi番目の区間[li,ri]に少なくともCi個の共通の数があるようにする.問題はまずあなたに1つの数nをあげて、それからn行はあなたに3つの数li,ri,Ciを教えて、numの最小値を出力します.n<=50000,0<=li,ri<=50000,1<=Ci<=ri-li+1;
解析:区間が最大で50000までしかないため、0から50000までの数のうち、この数を選択しないことを0で表し、1はこの数を選択することを表すが、0~iの間にどれだけの1があるかをsum[i]で表すことができる(率直に言えばいくつかの数を選択し、0~iの距離と大まかに見ることができる).
(1)sum[bi]-sum[ai-1]>=Ci,ai,biが区間を表す[ai,bi]
(2) 0<=sum[i]-sum[i-1]<=1
すなわち、sum[i]-sum[i-1]>=0
sum[i-1]-sum[i]>=-1
上の不等式を知っていれば、図を作ることができます.ai-1からbiにはCiの値を持つエッジがあり、iからi-1には-1の値を持つエッジがあり、i-1からiには0の値を持つエッジがあります.
この問題のコード://この問題にループがない場合、ループを判定しなくてもいい
C - THE MATRIX PROBLEM (hdu 3666)
問:n＊mの行列と、区間上下境界L,Uと、n個の数a 1,a 2,a 3,…,anとm個の数b 1,b 2,b 3,…,bmを見つけて、行列の中のi行目の数にaiを乗じて得られた値の範囲を[L,U]内にすることができますか.そして、行列の中のj列目の数をbjで割って得られた値の範囲も[L,U]内にあります.
第1の動作n,m,L,Uを入力
次のn*mの行列Aij
分析:差分制約の問題をするには、まず関係(2つの不定数の減算が値以上またはそれ以下)を見つけなければなりません.問題の意味によって、私たちは簡単に次の関係を得ることができます.
(1)L<=Aij*ai<=U(最初の要件)
(2) L<=Aij/bj <=U (2番目の要件)
上の2つの式を見ると、差分制約の不等式関係と一致しないようですが、対数をとることで2つの数を加算または2つの数を減算することができ、対数を取ることで次の変形を得ることができます.
(1) log(L) <= log(Aij) +log(ai) <=log(U)
(2) log(L) <= log(Aij) - log(bj) <=log(U)
ハハハ、2式加算で2*log(L)<=2*log(Aij)+log(ai)-log(bj)<=2*log(U)が得られる
移項可得:2*log(L)-2*log(Aij)<=log(ai)-log(bj)<=2*log(U)-2*log(Aij)
では、iからj+nの間にエッジを作ることができます.エッジ長は上式の値です.具体的にはコードを見てください.しかし、この問題カードのキューは、一般的な方法でポイント判定ループ会TLEよりも多く、ここでは以下の2つの方法で最適化することができます.
1.点数がnの場合、そのうちの1つの点のエンキュー回数がsqrt(n)より大きい場合、ループがある.
2.すべてのポイントのエンキュー回数がk*nより大きい場合、ループがあり、kは一般的に2.....
コードは次のとおりです.
F - Fibonacci Tree (hdu 4786 )
题意:あなたに1つの図をあげて、図の中の辺の色は白色(1が表します)あるいは黒色(0が表します)で、あなたに1本の木を探し当てることができるかどうかを闻いて、この木の中の白い辺の総数量の値をFib数にさせます.点数nと変数mはいずれも1 e 5以下の数である.
分析:これは最小生成木の変形問題で、Kruskalで解いて、私達は2回の最小生成木を求めて白辺の数量の上下限を得ることができて、更にこの区間内にfibの数があるかどうかを判断して、初めて私達は黒辺を主として最小生成木を並べ替えて、白辺の数量の下限を得て、更に白辺を主として並べ替えて最小生成木を求めて白辺の数量の上限を得ます.なお、最初の図が連通していない場合、出力No.
コードは次のとおりです.
G - Slim Span (uva 1395)
标题:n(n<=100)ノードの図を与え、スリム度(最大エッジマイナス最小エッジの値)ができるだけ小さい生成ツリーを求め、この値を出力する.解析:Kruskalアルゴリズムによれば,最小エッジ重みを列挙し,最小生成ツリーを求めることで,最大エッジ重みから最小エッジ重みを減算する最小値を暴力的に算出できる.
コード:
H - Buy or Build (UVA 1151)
标题:2次元平面にn個の点があり、各点の座標を教えてあげます.あなたの任務は各点を連通させることです.では、いくつかの辺を新築することができます.各辺の費用は2点のユークリッド距離の平方で、q(0<=q<=8)のコースを返します.i番目のコースを選択すると、このコースのすべての点が相互に連通し、i番目のコースの費用はciになります.
分析:qの範囲を見ると、バイナリ列挙で選択したコースがどれらなのか考えやすくなります.Kruskalアルゴリズムによると、i番目のコースを選択すると、i番目のコースのすべてのポイントのfatherがすべてのポイントに統一されることがわかります.long longで注意してください.
コードは次のとおりです.
B - Intervals (hdu1384)
題意:n区間の各区間の範囲を[l,r]とし、num個の整数を確定させ、このnum個の整数がi番目の区間[li,ri]に少なくともCi個の共通の数があるようにする.問題はまずあなたに1つの数nをあげて、それからn行はあなたに3つの数li,ri,Ciを教えて、numの最小値を出力します.n<=50000,0<=li,ri<=50000,1<=Ci<=ri-li+1;
解析:区間が最大で50000までしかないため、0から50000までの数のうち、この数を選択しないことを0で表し、1はこの数を選択することを表すが、0~iの間にどれだけの1があるかをsum[i]で表すことができる(率直に言えばいくつかの数を選択し、0~iの距離と大まかに見ることができる).
(1)sum[bi]-sum[ai-1]>=Ci,ai,biが区間を表す[ai,bi]
(2) 0<=sum[i]-sum[i-1]<=1
すなわち、sum[i]-sum[i-1]>=0
sum[i-1]-sum[i]>=-1
上の不等式を知っていれば、図を作ることができます.ai-1からbiにはCiの値を持つエッジがあり、iからi-1には-1の値を持つエッジがあり、i-1からiには0の値を持つエッジがあります.
この問題のコード://この問題にループがない場合、ループを判定しなくてもいい
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define maxn 50010
#define inf 1e9
using namespace std;
int num,p[maxn],n;
struct node
{
int en,va,next;
}E[maxn*10];
void init()
{
num=0;
memset(p,-1,sizeof(p));
}
void add(int st,int en,int va)
{
E[num].en=en;
E[num].va=va;
E[num].next=p[st];
p[st]=num++;
}
int dis[maxn];
bool inq[maxn];
void spfa(int st,int en)
{
for(int i=0;i<=en;i++)
{
dis[i]=-inf;
inq[i]=false;
}
queue<int> q;
q.push(st);
dis[st]=0;
inq[st]=true;
while(q.size())
{
int x=q.front();
q.pop();
inq[x]=false;
for(int i=p[x];i!=-1;i=E[i].next)
{
int y=E[i].en;
int len=dis[x]+E[i].va;
if(len>dis[y])
{
dis[y]=len;
if(!inq[y])
{
q.push(y);
inq[y]=true;
}
}
}
}
}
int main()
{
while(scanf("%d",&n)==1)
{
init();
int st=inf,en=-1;// ，
for(int i=1;i<=n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
a++,b++;/// 0，
st=min(st,a-1);/// minn， minn-1， a-1
en=max(en,b);
add(a-1,b,c);
}
for(int i=st;i<=en;i++)
{
add(i,i-1,-1);
add(i-1,i,0);
}
spfa(st,en);
printf("%d
",dis[en]);
}
return 0;
}
C - THE MATRIX PROBLEM (hdu 3666)
問:n＊mの行列と、区間上下境界L,Uと、n個の数a 1,a 2,a 3,…,anとm個の数b 1,b 2,b 3,…,bmを見つけて、行列の中のi行目の数にaiを乗じて得られた値の範囲を[L,U]内にすることができますか.そして、行列の中のj列目の数をbjで割って得られた値の範囲も[L,U]内にあります.
第1の動作n,m,L,Uを入力
次のn*mの行列Aij
分析:差分制約の問題をするには、まず関係(2つの不定数の減算が値以上またはそれ以下)を見つけなければなりません.問題の意味によって、私たちは簡単に次の関係を得ることができます.
(1)L<=Aij*ai<=U(最初の要件)
(2) L<=Aij/bj <=U (2番目の要件)
上の2つの式を見ると、差分制約の不等式関係と一致しないようですが、対数をとることで2つの数を加算または2つの数を減算することができ、対数を取ることで次の変形を得ることができます.
(1) log(L) <= log(Aij) +log(ai) <=log(U)
(2) log(L) <= log(Aij) - log(bj) <=log(U)
ハハハ、2式加算で2*log(L)<=2*log(Aij)+log(ai)-log(bj)<=2*log(U)が得られる
移項可得:2*log(L)-2*log(Aij)<=log(ai)-log(bj)<=2*log(U)-2*log(Aij)
では、iからj+nの間にエッジを作ることができます.エッジ長は上式の値です.具体的にはコードを見てください.しかし、この問題カードのキューは、一般的な方法でポイント判定ループ会TLEよりも多く、ここでは以下の2つの方法で最適化することができます.
1.点数がnの場合、そのうちの1つの点のエンキュー回数がsqrt(n)より大きい場合、ループがある.
2.すべてのポイントのエンキュー回数がk*nより大きい場合、ループがあり、kは一般的に2.....
コードは次のとおりです.
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<vector>
#include<algorithm>
#define maxn 50010
#define inf 1e5
using namespace std;
int num,p[maxn],n,m;
struct node
{
int en,next;
double va;
}E[maxn*10];
void init()
{
num=0;
memset(p,-1,sizeof(p));
}
void add(int st,int en,double va)
{
E[num].en=en;
E[num].va=va;
E[num].next=p[st];
p[st]=num++;
}
double dis[maxn];
int cnt[maxn];
bool inq[maxn];
bool spfa()
{
for(int i=0;i<=n+m;i++)
{
dis[i]=inf;
cnt[i]=0;
inq[i]=false;
}
queue<int> q;
q.push(1);
dis[1]=0.0;
cnt[1]++;
inq[1]=true;
while(q.size())
{
int x=q.front();
q.pop();
inq[x]=false;
for(int i=p[x];i!=-1;i=E[i].next)
{
int y=E[i].en;
double len=dis[x]+E[i].va;
if(len<dis[y])
{
dis[y]=len;
if(!inq[y])
{
q.push(y);
cnt[y]++;
if(cnt[y]>(int)sqrt(n+m)) return false;
inq[y]=true;
}
}
}
}
return true;
}
int main()
{
double L,U;
while(scanf("%d%d%lf%lf",&n,&m,&L,&U)!=EOF)
{
init();
double l=2.0*log(L),u=2.0*log(U);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
double x;
scanf("%lf",&x);
x=2.0*log(x);
add(j,i+m,u-x);
add(i+m,j,x-l);
}
}
if(spfa()) puts("YES");
else puts("NO");
}
return 0;
}
F - Fibonacci Tree (hdu 4786 )
题意:あなたに1つの図をあげて、図の中の辺の色は白色(1が表します)あるいは黒色(0が表します)で、あなたに1本の木を探し当てることができるかどうかを闻いて、この木の中の白い辺の総数量の値をFib数にさせます.点数nと変数mはいずれも1 e 5以下の数である.
分析:これは最小生成木の変形問題で、Kruskalで解いて、私達は2回の最小生成木を求めて白辺の数量の上下限を得ることができて、更にこの区間内にfibの数があるかどうかを判断して、初めて私達は黒辺を主として最小生成木を並べ替えて、白辺の数量の下限を得て、更に白辺を主として並べ替えて最小生成木を求めて白辺の数量の上限を得ます.なお、最初の図が連通していない場合、出力No.
コードは次のとおりです.
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 1e8
using namespace std;
int fa[110000];
bool Fi[110000];
struct node
{
int st,en,co;
}E[110000];
int find(int x)
{
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
bool cmp1(node a,node b)//
{
return a.co<b.co;
}
bool cmp2(node a,node b)//
{
return a.co>b.co;
}
void init()// fib
{
memset(Fi,false,sizeof(Fi));
int a=1,b=2,c;
Fi[a]=Fi[b]=true;
while(1)
{
c=a+b;
if(c>100000) break;
Fi[c]=true;
a=b,b=c;
}
}
int main()
{
int T;
scanf("%d",&T);
init();// fib
for(int ca=1;ca<=T;ca++)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&E[i].st,&E[i].en,&E[i].co);
int ans1=0,ans2=0;
sort(E+1,E+m+1,cmp1);///
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int fx=find(E[i].st),fy=find(E[i].en);
if(fx!=fy)
{
if(E[i].co) ans1++;
fa[fx]=fy;
}
}
int fg=1,tem=find(1);
for(int i=2;i<=n;i++)
{
if(find(i)!=tem)
{
fg=0;
break;
}
}
if(!fg)
{
printf("Case #%d: No
",ca);
continue;
}///
sort(E+1,E+m+1,cmp2);//
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int fx=find(E[i].st),fy=find(E[i].en);
if(fx!=fy)
{
if(E[i].co) ans2++;
fa[fx]=fy;
}
}
fg=0;
for(int i=ans1;i<=ans2;i++)
{
if(Fi[i])
{
fg=1;
break;
}
}
if(fg) printf("Case #%d: Yes
",ca);
else printf("Case #%d: No
",ca);
}
return 0;
}
G - Slim Span (uva 1395)
标题:n(n<=100)ノードの図を与え、スリム度(最大エッジマイナス最小エッジの値)ができるだけ小さい生成ツリーを求め、この値を出力する.解析:Kruskalアルゴリズムによれば,最小エッジ重みを列挙し,最小生成ツリーを求めることで,最大エッジ重みから最小エッジ重みを減算する最小値を暴力的に算出できる.
コード:
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 1e8
using namespace std;
int fa[110];
int n,m;
struct node
{
int st,en,len;
}E[110000];
int find(int x)
{
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
bool cmp(node a,node b)
{
return a.len<b.len;
}
int Kruskal(int pos)
{
for(int i=1;i<=n;i++) fa[i]=i;
int minn=E[pos].len,maxx=0;
for(int i=pos;i<=m;i++)
{
int fx=find(E[i].st),fy=find(E[i].en);
if(fx!=fy)
{
maxx=max(maxx,E[i].len);
fa[fx]=fy;
}
}
int fg=1,tem=find(1);/// ， ， -1
for(int i=2;i<=n;i++)
{
if(find(i)!=tem)
{
fg=0;
break;
}
}
if(!fg) return -1;
return maxx-minn;
}
int main()
{
while(scanf("%d%d",&n,&m),n||m)
{
for(int i=1;i<=m;i++)
scanf("%d%d%d",&E[i].st,&E[i].en,&E[i].len);
sort(E+1,E+m+1,cmp);
int ans=1e9;
int x=Kruskal(1);//
if(x==-1)
{
puts("-1");
continue;
}
ans=min(ans,x);
for(int i=2;i<=m-n+2;i++)/// n-1， n-1
{
int x=Kruskal(i);
if(x!=-1) ans=min(ans,x);
}
printf("%d
",ans);
}
return 0;
}
H - Buy or Build (UVA 1151)
标题:2次元平面にn個の点があり、各点の座標を教えてあげます.あなたの任務は各点を連通させることです.では、いくつかの辺を新築することができます.各辺の費用は2点のユークリッド距離の平方で、q(0<=q<=8)のコースを返します.i番目のコースを選択すると、このコースのすべての点が相互に連通し、i番目のコースの費用はciになります.
分析:qの範囲を見ると、バイナリ列挙で選択したコースがどれらなのか考えやすくなります.Kruskalアルゴリズムによると、i番目のコースを選択すると、i番目のコースのすべてのポイントのfatherがすべてのポイントに統一されることがわかります.long longで注意してください.
コードは次のとおりです.
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#define inf 1e8
#define LL long long
using namespace std;
vector<int> v[10];
int w[10];
int fa[1100];
int n,m;
struct node
{
int st,en,len;
}E[1100000];
struct Node
{
int x,y;
}V[1100];
int find(int x)
{
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
bool cmp(node a,node b)
{
return a.len<b.len;
}
int get(Node a,Node b)//
{
return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
LL Kruskal()
{
LL ans=0;
for(int i=1;i<=m;i++)
{
int fx=find(E[i].st),fy=find(E[i].en);
if(fx!=fy)
{
ans+=E[i].len;
fa[fx]=fy;
}
}
return ans;
}
int main()
{
int q,T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&q);
for(int i=0;i<q;i++) v[i].clear();
for(int i=0;i<q;i++)
{
int num,x;
scanf("%d%d",&num,&w[i]);
while(num--)
{
scanf("%d",&x);
v[i].push_back(x);
}
}
for(int i=1;i<=n;i++)
scanf("%d%d",&V[i].x,&V[i].y);
m=0;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
m++;
E[m].st=i,E[m].en=j,E[m].len=get(V[i],V[j]);
}
}
sort(E+1,E+m+1,cmp);///
for(int i=1;i<=n;i++) fa[i]=i;
LL ans=Kruskal();///
for(int i=1;i<(1<<q);i++)
{
LL tem=0;///
for(int j=1;j<=n;j++) fa[j]=j;
for(int j=0;j<q;j++)
{
if(!(i&(1<<j))) continue;
tem+=w[j];
int x=find(v[j][0]);
for(int k=1;k<v[j].size();k++)/// ，Kruskal ，
{
int y=find(v[j][k]);
if(y!=x)
{
fa[y]=x;
}
}
}
ans=min(ans,tem+Kruskal());/// ，
}
printf("%lld
",ans);
if(T) printf("
");
}
return 0;
}