|
|
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;
}
}
}
|