|
|
2010年12月8日
2010年7月8日
樹的直徑是指樹的最長簡單路。求法: 兩遍BFS :先任選一個起點BFS找到最長路的終點，再從終點進行BFS，則第二次BFS找到的最長路即為樹的直徑； 原理: 設起點為u,第一次BFS找到的終點v一定是樹的直徑的一個端點 證明: 1) 如果u 是直徑上的點，則v顯然是直徑的終點(因為如果v不是的話，則必定存在另一個點w使得u到w的距離更長，則于BFS找到了v矛盾) 2) 如果u不是直徑上的點，則u到v必然于樹的直徑相交(反證),那么交點到v 必然就是直徑的后半段了 所以v一定是直徑的一個端點，所以從v進行BFS得到的一定是直徑長度 相關題目有TOJ1056，TOJ3517. TOJ 1056(Labyrinth): 大意是一個由‘#’和'.'構成的迷宮，'.'表示可行，‘#’表示不可行，問可行的最長的路的長度是多少。
#include <cstdio>
#include <cstring>
#include <queue>
#define M 1002
using namespace std;
int r,c;
char map[M][M];
bool flag[M][M];
int move[4][2]={-1,0,1,0,0,-1,0,1}; // 分別表示上下左右
int maxt;
struct Node{
int x,y,num;
};
Node ans;
bool legal(int x,int y){ //判斷該點是否越界及是否可走
if(x >=0 && x < r && y>=0 && y < c &&map[x][y]=='.') return true;
return false;
}
void bfs(Node start){
memset(flag,false,sizeof(flag)); //初始所有點標記為false
flag[start.x][start.y] = true; //起點標記為true
queue<Node>f;
while(!f.empty()) f.pop(); //清空創建的隊列
Node m,n,tep;
int tx,ty,xx,yy;
int i,j,k,num;
f.push(start);
while(!f.empty()){ //如果隊列不為空
m = f.front(); //取出隊首元素
tx = m.x; ty = m.y; num = m.num;
if(num > maxt){ //如果該元素的長度大于maxt，更新maxt
maxt = num;
ans = m;
}
for(i = 0;i < 4; i++){ //以m為起點向4個方向BFS
xx = tx + move[i][0];
yy = ty + move[i][1];
if(!flag[xx][yy] && legal(xx,yy)){
flag[xx][yy] = true;
tep.x = xx;
tep.y = yy;
tep.num = num + 1;
f.push(tep);
if(num+1>maxt){ //如果有更大的則更新
maxt = num + 1;
ans = tep;
}
}
}
f.pop(); //彈出隊首元素
}
}
int main(){
int i,j,T;
Node start,end;
bool mark;
scanf("%d",&T);
while(T--){
scanf("%d%d",&c,&r);
mark = false; maxt = -1;
for(i = 0;i < r; i++)
scanf("%s",map[i]);
for(i = 0;i < r; i++){
for(j = 0;j < c; j++){
if(map[i][j]=='.'){ //任選一點BFS
start.x = i;
start.y = j;
start.num = 0;
bfs(start);
mark = true;
break;
}
}
if(mark) break;
}
maxt = -1;ans.num = 0; //此時ans一定是直徑的端點，將它設為起點
bfs(ans); //進行第二次BFS
printf("Maximum rope length is %d.\n",maxt);
}
}
TOJ3517(The longest athletic track): 題目給出了一棵生成樹，問這棵生成樹最長的路的長度是多少。
#include<iostream>
#include<queue>
#define INF 999999
#define M 2002
using namespace std;
int n;
int maxx;
int map[M][M],sum[M];
bool flag[M];
int bfs(int begin){
queue<int>f;
int i,m,k,key;
maxx=0;
memset(flag,false,sizeof(flag));
f.push(begin);
while(!f.empty()){
k=f.front();
for(i=1;i<=n;i++){
if(map[k][i]!=INF&&!flag[i]){
flag[i]=true;
f.push(i);
sum[i]=sum[k]+map[k][i];
if(sum[i]>maxx) { maxx=sum[i];key=i; }
}
}
f.pop();
}
return key;
}
int main()
{
int i,j,k,dis,key,cas;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
map[i][j]=map[j][i]=INF;
for(i=1;i<n;i++){
scanf("%d%d%d",&j,&k,&dis);
map[j][k]=map[k][j]=dis;
}
sum[1]=0;
key=bfs(1);
sum[key]=0;
key=bfs(key);
printf("%d\n",maxx);
}
//system("pause");
}
早就想學一下歸并排序求逆序對，在這之前只會用樹狀數組來做，有時候還需要離散化，而且效率還不如歸并排序高。 其實還是蠻簡單的，知道歸并排序的原理就很容易知道如何求逆序對了。設數組為A，關鍵是在合并的時候，用數組L 和 R 表示左右兩個子數組，因為逆序對的個數f(A) = f(L) + f(R) + s(L,R);其中f(L) 和 f(R) 分別表示L 內部 和R內部的逆序對個數，s(L.R)表示大數在L，小數在R的逆序對。因為L和R是已經排好序的，故其實只需求s(L,R).這個可以在合并L和R依次進行比較的時候算出。
for(k = p;k <= r;k ++){
if(L[i]<=R[j])
a[k] = L[i++];
else{ //如果L最上面的數大于R的，那么L[i]及后面的數可以和R[j]構成n1-i+1個逆序對
a[k] = R[j++];
count +=(n1 -i + 1); //累加
}
}
歸并排序的代碼：
void merge(int p,int q,int r){
int n1 = q-p+1,n2 = r-q;
int i,j,k;
for(i = 1;i <= n1; i++)
L[i] = a[p+i-1];
for(j = 1;j <= n2; j++)
R[j] = a[q+j];
L[n1+1] = INF;
R[n2+1] = INF;
i = 1;j = 1;
for(k = p;k <= r;k ++){
if(L[i]<=R[j])
a[k] = L[i++];
else{
a[k] = R[j++];
count +=(n1 -i + 1);
}
}
}
void merge_sort(int p,int r){
if(p<r){
int q = (p+r)/2;
merge_sort(p,q);
merge_sort(q+1,r);
merge(p,q,r);
}
}
2010年7月7日
今天看了下多重背包，理解的還不夠深入，不過因為是01背包過來的，所以接受起來很容易。 主要是運用了二進制的思想將一個數量為N很大的物品分為了logN個數量小的物品，而這logN個物品可以組成數量為0到N任意數量，所以這種策略是 成立的。 多重背包問題有TOJ1034，TOJ1670. TOJ1034 : 大意是有6種規格的石頭，編號從1到6，編號為 i 的石頭的價值為 i .現在給出各種石頭的數量，問有沒有可能得到總價值的一半。 做法: DP, 每種石頭價值為v[i],價值為 i ，數量為 num[i] ,通過多重背包看能不能恰好取得總價值的一半。 一個優化是總價值為奇數直接不用考慮，而在DP的時候設置一個標記來記錄是否已經取得總價值一半，如果取得則可以返回。 做法2：這種方法的前提是POJ discuss里的一種做法，即給每個石頭的數量mod 8。證明是用抽屜原理證的，很復雜，我沒有看。但是這樣以來，數量 一下子大大減少，極大的提高了效率。 我說的做法2事實上是我的最初做法，即DFS，搜索，在搜索過程中注意剪枝，再加上數量取模的優化，復雜度也不高。 Code for 1034(Dividing):
import java.util.Scanner;
import java.util.*;
import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
public class Main {
public static int f[] = new int[20001*6]; // f[i]表示容量為 i 的背包最多能裝的物品的價值
public static int v[] = new int[7];
public static int num[] = new int[7];
public static int total,flag,key; //total為 6 種大理石的總價值 ，flag為標記，一旦為1表示可以取得，可以返回了
public static void onezeropack(int cost,int weight) { // 01背包函數，注意循環是從total 到 cost，不要弄反
int i;
for(i = total;i >= cost; i--) {
f[i] = Math.max(f[i],f[i-cost]+weight);
if(f[i] == key) { // 如果可以取得總價值一半，flag=1，返回
flag = 1;
return ;
}
}
}
public static void finishpack(int cost,int weight) {
int i;
if(flag==1) return ;
for(i = cost;i <= total; i++) {
f[i] = Math.max(f[i], f[i-cost]+weight);
if(f[i] == key) {
flag = 1;
return ;
}
}
}
public static void multipack(int cost,int weight,int amount) {
if(cost*amount >= total) {
finishpack(cost, weight);
return ;
}
if(flag==1) return ;
int k = 1;
while(k < amount) { // 該過程即為將一件物品拆分為1，2，4...2^k 件物品進行01背包過程
onezeropack(k*cost, k*weight);
amount -= k;
k *= 2;
}
onezeropack(cost*amount, weight*amount);
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int i,j,cas = 1;
while(true) {
Arrays.fill(f,0);
total = 0; flag = 0;
for(i = 1;i <= 6; i++) {
num[i] = in.nextInt();
v[i] = i;
total += i*num[i];
}
if(num[1]==0&&num[2]==0&&num[3]==0&&num[4]==0&&num[5]==0&&num[6]==0)
break;
if(total%2==1) flag = 0;
else {
key = total/2;
for(i = 1;i <= 6; i++)
multipack(i, i, num[i]);
}
System.out.println("Collection #"+cas+":");
if(flag==0) System.out.println("Can't be divided.");
else System.out.println("Can be divided.");
System.out.println();
cas++;
}
}
}
TOJ 1670： 大意是一臺取款機有N中貨幣，每種貨幣面值為 V[i] ，數量為 num[i] , 給出一個價值，為在這個價值之內(包括這個價值)最大能取得多大。 分析：典型的多重背包，給出的價值即為背包容量，每種貨幣為一種物品，價值為v[i] , 數量為num[i]，求能得到的最大價值。 注釋就不加了，參考上面的程序 Code for 1670(Cash Mechine):
#include <cstdio>
#include <cstring>
int f[100002],v[12],num[12],cost[12];
int total,n;
int max(int a,int b){ return a>b?a:b;}
void OneZeroPack(int cost,int value){
int i,j;
for(i = total;i >= cost; i--)
f[i] = max(f[i],f[i-cost]+value);
}
void completePack(int cost,int weight){
int i;
for(i = cost;i <= total; i++)
f[i] = max(f[i],f[i-cost]+weight);
}
void multiPack(int cost,int weight,int amount){
if(cost*amount >= total){
completePack(cost,weight);
return ;
}
int k = 1;
while(k < amount){
OneZeroPack(k*cost,k*weight);
amount -= k;
k*=2;
}
OneZeroPack(cost*amount,amount*weight);
}
int main(){
int i,j,k;
while(scanf("%d%d",&total,&n)!= EOF){
memset(f,0,sizeof(f));
for(i = 1;i <= n; i++){
scanf("%d%d",&num[i],&cost[i]);
v[i] = cost[i];
}
for(i = 1;i <= n; i++)
multiPack(cost[i],v[i],num[i]);
printf("%d\n",f[total]);
}
}
2010年7月5日
題目大意是N個人互相有債a[i](正的表示別人欠錢，否則表示自己欠別人錢,a[i]的和保證為0),但是這N個人只有朋友間才能互相算帳，現在給出N個人的債，并且給出M個關系，即誰和誰是朋友，最后問有沒有可能所有人都把帳算清。
Sample Input 1: Sample Input 2:
5 3 4 2
100 15
-75 20
-25 -10
-42 -15
42 0 2
0 1 1 3
1 2
3 4
Sample Output 1: Sample Output 2:
POSSIBLE IMPOSSILBE
思路1：
每輸入一個關系，合并，最后從1到N，對于每一個人，找出它們的祖先，將他們的債debt加到祖先的debt
上。通俗的講，就是每個集合的成員都將自己的debt加到祖先上，自己歸0，最后看祖先的值是否為0；
最后在從1到N掃一遍如果有debt不為0的，輸出“IMPOSSIBLE”，否則“POSSIBLE”；
缺點：復雜度高，查詢復雜度*N，最后勉強過了，時間0.63s
思路2：
路徑壓縮，每輸入一個關系，合并。最后從1到N，如果 i 的debt不為0，從 i 到 i 的祖先的路徑不斷壓縮直到
祖先，這樣雖然仍然是N次操作，但由于在壓縮過程中大部分成員debt歸0，故實際上進行操作的次數遠小于N.
最后時間為0.11,比起上一種方法有了很大提高
Code 1:
#include <cstdio>
#include <cstring>
struct Node{
int father,v,num;
}a[10002];
int find(int n){
int tep,m = n;
while(n != a[n].father)
n = a[n].father;
while(m != n){
tep = a[n].father;
a[n].father = n;
m = tep;
}
return n;
}
void Union(int root1,int root2){
int t1,t2;
t1 = find(root1),t2 = find(root2);
if(t1 == t2) return ;
else{
if(a[t1].v > a[t2].v){
a[t1].v += a[t2].v;
a[t2].father = t1;
}
else{
a[t2].v += a[t1].v;
a[t1].father = t2;
}
}
}
int main()
{
int n,m,i,j;
bool flag = false;
scanf("%d%d",&n,&m);
for(i = 0;i < n; ++i){
a[i].father = i,a[i].v = 0;
scanf("%d",&a[i].num);
}
while(m--){
scanf("%d%d",&i,&j);
Union(i,j);
}
for(i = 0;i < n; ++i){
int tep = find(i);
int tt = a[i].num;
a[i].num -= tt;
a[tep].num += tt;
}
for(i = 0;i < n; i++)
if(a[i].num != 0){
flag = true;
break;
}
if(flag) printf("IMPOSSIBLE\n");
else printf("POSSIBLE\n");
}
Code 2:
#include <cstdio>
#include <cstring>
struct Node{
int father,v,num;
}a[10002];
int find(int n){
int m = n,tep;
while(n != a[n].father)
n = a[n].father;
while(m != n){
tep = a[m].father;
int tt = a[m].num;
a[m].num -= tt;
a[tep].num += tt;
a[m].father = n;
m = tep;
}
return n;
}
void Union(int root1,int root2){
int t1,t2;
t1 = find(root1),t2 = find(root2);
if(t1 == t2) return ;
else{
if(a[t1].v > a[t2].v){
a[t1].v += a[t2].v;
a[t2].father = t1;
}
else{
a[t2].v += a[t1].v;
a[t1].father = t2;
}
}
}
int main()
{
int n,m,i,j;
bool flag = false;
scanf("%d%d",&n,&m);
for(i = 0;i < n; ++i){
a[i].father = i,a[i].v = 0;
scanf("%d",&a[i].num);
}
while(m--){
scanf("%d%d",&i,&j);
Union(i,j);
}
for(i = 0;i < n; ++i)
if(a[i].num != 0) find(i);
for(i = 0;i < n; i++)
if(a[i].num != 0){
flag = true;
break;
}
if(flag) printf("IMPOSSIBLE\n");
else printf("POSSIBLE\n");
}
這道題題意很難懂，大意是有N個公司，每個公司有一個center，最初每個公司的center都在自己公司，然后有M次操作，每次操作 A , B (A保證是一個集合的center，B不一定) 表示將A所在的集合并到B所在的集合，且B的center成為了A的center。每次操作后兩個公司的線的距離增加abs(A-B)%1000; Sample Input: (E P表示查詢P距離自己center的線的長度，I P Q 表示合并 P ,Q);
1
4
E 3
I 3 1
E 3
I 1 2
E 3
I 2 4
E 3
O
Sample Output:
0
2
3
5
Code:
#include <cstdio>
#include <iostream>
#define M 20010
using namespace std;
struct Node{
int father,num;
}a[M];
void initial(int n){
int i;
for(i = 1;i <= n; i++){
a[i].father = i;
a[i].num = 0;
}
}
int find(int n){
int tep,m = n;
if(n == a[n].father) return n;
find(a[n].father); //遞歸查找n的祖先
a[n].num += a[a[n].father].num; //n的直需要更新(加上n的父親的值)
a[n].father = a[a[n].father].father;
}
int main()
{
int T,n,i,j,k;
char order[3];
scanf("%d",&T);
while(T--){
scanf("%d",&n);
initial(n);
while(scanf("%s",order)){
if(order[0]== 'O') break;
if(order[0] == 'E'){
scanf("%d",&k);
find(k);
printf("%d\n",a[k].num);
}
else{
scanf("%d%d",&j,&k);
int dis = abs(j-k)%1000;
a[j].num = dis; //該值dis為j的值
a[j].father = k; //k成為了j的父親
}
}
}
}
2010年6月23日
題目給定一個進制b，然后給兩個b進制下的大數 m 和 n ，要求求出m % n的結果，用b進制表示。
最近在學JAVA，發現做起高精度簡直太爽了~ 這個題有JAVA簡直就是個水題，知道一些函數就好了。
BigInteger a = in.nextBigInteger(base); //將一個大數按照base進制輸入
a.mod(b) ; //a%b,其中a和b都是大數且結果為10進制，不管a和b是什么進制
String str= a.toString(base); //將一個大數a轉換成b進制的字符串
這個題就用到這些東西，代碼就不貼了。~~
2010年6月12日
很簡單的題，給定N個矩陣，然后給出一系列運算式，用括號來限制運算，最后求一共進行了多少次乘法運算。 R(m,s) 和Q(s,n)相乘，要進行m*s*n次～ 處理運算先后的時候，用棧實現，即后進先出就可以了。 Sample Input:
9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))
Sample Outout:
0
0
0
error
10000
error
3500
15000
40500
47500
15125
Code:
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
using namespace std;
struct Matrx{
char id;
int x,y;
}a[30];
Matrx stack[100];
int main()
{
int i,j,k,n,ans;
bool flag;
map<char,int>mark;
scanf("%d",&n);
for(i = 1;i <= n; i++){
cin >> a[i].id;
scanf("%d%d",&a[i].x,&a[i].y);
mark[a[i].id] = i;
}
string str;
while(cin>>str){
ans = 0; flag = true;
int len = str.length();
int head,tail;
head = tail = 0;
for(i = 0;i <len; i++){
if(str[i] == '(')
continue;
else if(str[i] == ')'){ //pop
if(head == 1)
head --;
else if(head > 1){
int tx = stack[head-2].x;
int ty = stack[head-1].y;
if(stack[head-2].y != stack[head-1].x) flag = false;
ans += stack[head-2].x*stack[head-2].y*stack[head-1].y;
head -= 2;
stack[head].x = tx;
stack[head++].y = ty;
}
}
else{ // push
stack[head++] = a[mark[str[i]]];
}
}
if(!flag) printf("error\n");
else printf("%d\n",ans);
}
}
給定從1 到 N的 N 個數，問有多少種不同方案劃分這些數。比如N = 3，則有5種方案：
{{1},{2},{3}}
{{1,2},{3}}
{{1,3},{2}}
{{2,3},{1}}
{{1,2,3}}
最后的結果只保留后四位，即mod10000；
上網查了下，集合的劃分的個數叫做bell數，bell數可以遞歸求解：
bell[0] = 1;
bell [n + 1] = sigma(C(n,k))*(bell[k]); (0<=k<=n)
然而這個題卻不可以這樣做，因為N得范圍是2000，這樣做必定超時，于是想到了DP，如果用dp[i][j]表示i個數
劃分成j個集合，那么便有dp[i][j] = j * dp[i-1][j] + dp[i-1][j-1];( i > j )直觀理解就是，將i個數劃分成j個集合的個數，即為i-1個數劃分到j個集合的數，再將多的那個依次放到j個集合中，所以乘以j，或者是i-1個數放在j-1個集合中，第j個集合為空，則正好將多的這個數放到這個集合中，于是便有上邊的狀態轉移方程。
Code:
 #include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int map[2002][2002];
  void DP() {
 memset(map,0,sizeof(map));
int i,j,k;
  for(i = 0;i <= 2000; i++){
map[i][i] = 1;
map[i][1] = 1;
 }
for(i = 0;i <= 2000 ;i++)
for(j = 0; j < i; j++)
map[i][j] = (j * map[i-1][j] + map[i-1][j-1])%10000;
 }
int main()
{
int i,j,k,n;
DP();
while(scanf("%d",&n),n){
int ans = 0;
for(i = 0;i <= n; i++)
ans = (ans + map[n][i])%10000;
string str = "0000";
str[3] = ans%10+'0'; ans/=10;
str[2] = ans%10+'0'; ans/=10;
str[1] = ans%10+'0'; ans/=10;
str[0] = ans%10+'0'; ans/=10;
cout<<str<<endl;
}
}
2010年5月28日
偏序集的兩個定理：
定理1) 令（X,≤）是一個有限偏序集，并令r是其最大鏈的大小。則X可以被劃分成r個但不能再少的反鏈。
其對偶定理稱為Dilworth定理：
定理2) 令（X,≤）是一個有限偏序集，并令m是反鏈的最大的大小。則X可以被劃分成m個但不能再少的鏈。
即：鏈的最少劃分數=反鏈的最長長度
相關的題目有pku 1065，pku 3636，pku 1548
POJ 3636:
#include<iostream>
#include<algorithm>
#define M 20002
using namespace std;
struct Node{
int h,w;
}a[M];
int tail[M],n;
void LIS(int n){
int i,j,m,len,mid,low,high;
len=1;tail[1]=a[1].h;
for(i=2;i<=n;i++){
if(tail[len]<=a[i].h) {
len++;
tail[len]=a[i].h;
}
else{
low=1;high=len;
while(low<high){
mid=(low+high)/2;
if(a[i].h>=tail[mid]) low=mid+1;
else high=mid;
}
tail[low]=a[i].h;
}
}
printf("%d\n",len);
}
bool cmp(Node a,Node b){
if(a.w!=b.w)return a.w>b.w;
else return a.h<b.h;
}
int main()
{
int i,j,k,cas;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&a[i].w,&a[i].h);
sort(a+1,a+1+n,cmp);
LIS(n);
}
//system("pause");
return 0;
}
POJ 1548:
#include<iostream>
#include<algorithm>
using namespace std;
int k,a[700],tail[800],b[860];
void LIS(){
int i,j,m,n,len,mid,left,right;
n=1;
for(i=k-1;i>=1;i--) b[n++]=a[i];
n--;
len=1;tail[1]=b[1];
for(i=2;i<=n;++i){
if(b[i]>tail[len]){
len++;
tail[len]=b[i];
}
else{
left=1;right=len;
while(left<right){ //二分查找插入的位置
mid=(left+right)/2;
if(tail[mid]<b[i]) left=mid+1;
else right=mid;
}
tail[left]=b[i]; //插入
}
}
printf("%d\n",len);
}
int main()
{
int i,j,m,n;
while(1){
k=1;
scanf("%d%d",&i,&j);
if(i==-1&&j==-1) break;
a[k++]=j;
while(scanf("%d%d",&i,&j)){
if(i==0&&j==0 ){
LIS();
break;
}
a[k++]=j;
}
}
}
|