這兩天看拓?fù)渑判颍珹題很不順利，桑心啊，桑心啊~~
題意描述：
N個(gè)人參加比才，給出M組兩個(gè)隊(duì)員之間的勝負(fù)情況，要求輸出總體的比賽名次。如果有多種情況，輸出字典序最小的那組結(jié)果。
拓?fù)渑判騾㈤啠?a href="http://m.shnenglu.com/hoolee/archive/2012/08/16/187400.html">http://m.shnenglu.com/hoolee/archive/2012/08/16/187400.html
以下是本題代碼；
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 510
int N, M;
int mp[LEN][LEN];
int indgr[LEN];
int s[LEN];
int list[LEN];
int lstlen;
int findZeroIndgr()
{
int i;
for(i = 0; i < N; i++)
if(s[i] == 0 && indgr[i] == 0)
return i;
}
void Topological()
{
int i, j;
int zr;
for(i = 0; i < N; i++)
{
zr = findZeroIndgr();
s[zr] = 1;
list[lstlen++] = zr;
for(j = 0; j < N; j++)
if(mp[zr][j] == 1)
indgr[j]--;
}
}
int main()
{
int i, j;
int p1, p2;
while(scanf("%d%d", &N, &M) != EOF)
{
memset(mp, 0, sizeof(mp));
memset(indgr, 0, sizeof(indgr));
memset(s, 0, sizeof(s));
for(i = 0; i < M; i++)
{
scanf("%d%d", &p1, &p2);
p1--;
p2--;
if(mp[p1][p2] == 0)
{
mp[p1][p2] = 1;
indgr[p2]++;
}
}
lstlen = 0;
Topological();
int gard = 0;
for(i = 0; i < lstlen; i++)
if(gard++ != 0)
printf(" %d", list[i] + 1);
else
printf("%d", list[i] + 1);
putchar(10);
}
//system("pause");
}
posted @
2012-08-18 17:17 小鼠標(biāo) 閱讀(249) |
評(píng)論 (0) |
編輯 收藏
摘要: 下面我先說以下拓?fù)渑判颍?
嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)》上的定義是：由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱之為拓?fù)渑判颉?
直觀的說偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。
拓?fù)渑判虻木唧w做法是：
1.在有向圖中選擇一個(gè)沒有前驅(qū)（入度為0）的頂點(diǎn)，輸出
2.從圖中刪除該頂點(diǎn)和所有以它為尾的弧，并更新相關(guān)點(diǎn)的入度
3.重復(fù)1，2步，直到所有頂點(diǎn)都被輸出，或者發(fā)現(xiàn)圖中存在回路。
閱讀全文
posted @
2012-08-16 19:19 小鼠標(biāo) 閱讀(1829) |
評(píng)論 (0) |
編輯 收藏
題意描述：
有幾種面額固定的硬幣，每種面額的硬幣都有無數(shù)張。給你一定的金額，問總共有多少種找零方案。
完全背包問題，動(dòng)態(tài)方程為：f[j] += f[j - mny[i]];
myi[i]表示第i種硬幣的面值，f[j]表示數(shù)額為j的找零方案。
表示對(duì)完全背包的動(dòng)態(tài)方程不甚理解，希望大神不惜指點(diǎn)。。
以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 350
#define LENM 20
int main()
{
int i, j;
int f[LEN];
int mny[LENM];
int n;
for(i = 1; i <= 17; i++)
mny[i] = i * i;
while(scanf("%d", &n), n)
{
memset(f, 0, sizeof(f));
f[0] = 1;
for(i = 1; i <= 17; i++)
for(j = mny[i]; j <= n; j++)
f[j] += f[j - mny[i]];
printf("%d\n", f[n]);
}
//system("pause");
}
posted @
2012-08-15 14:12 小鼠標(biāo) 閱讀(306) |
評(píng)論 (0) |
編輯 收藏
題意描述：
給定一定數(shù)量的不同面值的鈔票，輸出由這些鈔票組成的不超過出款上限（題目中的cash）的最大金額。
01背包問題，請(qǐng)參閱：
http://m.shnenglu.com/hoolee/archive/2012/08/14/187179.html這里我想多說一句，本題中背包的容量是題中給的cash，每件物品的花費(fèi)就是該鈔票的面值，物品的價(jià)值也是該種鈔票的面值，這里的花費(fèi)和價(jià)值是一樣的。
以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LENND 20
#define LENF 100010
typedef struct
{
int v;
int amt;
}Cash;
Cash cs[100];
int f[LENF];
int Max(int a, int b)
{
if(a > b)
return a;
return b;
}
int main()
{
int i, j;
int cash, N;
int n[LENND], D[LENND];
while(scanf("%d", &cash) != EOF)
{
scanf("%d", &N);
for(i = 0; i < N; i++)
scanf("%d%d", &n[i], &D[i]);
int count = 1;
for(i = 0; i < N; i++)
{
int M = n[i];
int t = 1;
while(M - t > 0)
{
cs[count].v = D[i];
cs[count++].amt = t;
M -= t;
t *= 2;
}
if(M != 0)
{
cs[count].v = D[i];
cs[count++].amt = M;
}
}
memset(f, 0, sizeof(f));
for(i = 1; i < count; i++)
{
int allv = cs[i].amt * cs[i].v;
for(j = cash; j >= allv; j--)
f[j] = Max(f[j], f[j - allv] + allv);
}
printf("%d\n", f[cash]);
}
//system("pause");
}
posted @
2012-08-14 17:33 小鼠標(biāo) 閱讀(228) |
評(píng)論 (0) |
編輯 收藏
摘要: 01背包的狀態(tài)轉(zhuǎn)移方程為：
當(dāng)v
當(dāng)v>=Ci時(shí)f[i,v]=Max(f[i-1,v],f[i-1,v-Ci]+Wi);(2)//當(dāng)?shù)趇件物品能夠放下時(shí)，我們可以選擇放，或不放，取決于總價(jià)值的大小。
其中v為當(dāng)前背包的中容量，Ci表示第i件物品的體積，Wi表示第i件物品的價(jià)值，f[i,v]表示容量為v的背包在考慮前i件物品后的最大價(jià)值。 閱讀全文
posted @
2012-08-14 16:32 小鼠標(biāo) 閱讀(1575) |
評(píng)論 (0) |
編輯 收藏題意描述：有幾種不同的債券共購買，每種債券有相應(yīng)的年效益，這些債券每年可以兌現(xiàn)一次，并且沒有任何手續(xù)費(fèi)，兌現(xiàn)后可以選擇購買不同債券。給定初始金額和年限，求出最終的最大收益。
解題思路：每年按01背包問題計(jì)算一遍即可。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 100000
typedef struct
{
int w;
int i;
}Bonds;
int f[LEN];
Bonds bd[20];
int Max(int a, int b)
{
if(a > b)
return a;
return b;
}
int main()
{
int i, j, k;
int N;
int M, Y;
int d, a, b;
scanf("%d", &N);
while(N--)
{
scanf("%d%d", &M, &Y);
scanf("%d", &d);
for(i = 1; i <= d; i++)
{
scanf("%d%d", &bd[i].w, &bd[i].i);
bd[i].w /= 1000;//債券的面值都是1000的整數(shù)倍
}
int alli = 0;
for(j = 0; j < Y; j++)
{
M += alli;
int P = M / 1000;//債券的面值都是1000的整數(shù)倍
memset(f, 0, sizeof(f));
for(i = 1; i <= d; i++)
for(k = bd[i].w; k <= P; k++)
f[k] = Max(f[k], f[k - bd[i].w] + bd[i].i);
alli = f[P];
}
M += alli;
printf("%d\n", M);
}
//system("pause");
}
posted @
2012-08-14 11:45 小鼠標(biāo) 閱讀(231) |
評(píng)論 (0) |
編輯 收藏
01背包壓縮的動(dòng)態(tài)方程為f[v]=Max(f[v],f[v-Ci]+Wi)。
詳情參閱《背包九講》：http://wenku.baidu.com/view/519124da5022aaea998f0f22.html
以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 20000
#define LENN 4000
typedef struct
{
int w;
int d;
}Charm;
int Max(int a, int b)
{
if(a > b)
return a;
return b;
}
int main()
{
int i, j;
Charm cm[LENN];
int N, M;
int f[LEN];
while(scanf("%d%d", &N, &M) != EOF)
{
for(i = 1; i <= N; i++)
scanf("%d%d", &cm[i].w, &cm[i].d);
memset(f, 0, sizeof(f));
for(i = 1; i <= N; i++)
for(j = M; j >= cm[i].w; j--)
f[j] = Max(f[j], f[j - cm[i].w] + cm[i].d);
printf("%d\n", f[M]);
}
//system("pause");
}
posted @
2012-08-14 10:44 小鼠標(biāo) 閱讀(366) |
評(píng)論 (0) |
編輯 收藏由于跟另外一題基本一樣，這里不多解釋了，請(qǐng)參閱：
http://m.shnenglu.com/hoolee/archive/2012/08/13/187069.html以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN 10100
typedef struct
{
double l;
double r;
}Node;
typedef struct
{
int x0;
int y0;
int x1;
int y1;
}Line;
Line lin[LEN];
Node nd[LEN];
long long count;
int cmp(const void *a, const void *b)
{
Node *a0 = (Node*)a;
Node *b0 = (Node*)b;
if(fabs(a0 -> l - b0 -> l) > 0.000000001)
return a0 -> l > b0 -> l ? 1 : -1;
else
return a0 -> r > b0 -> r ? 1 : -1;
}
void Merge(Node *nd, int f, int m, int r)
{
int i, j, k;
Node *b = (Node*)malloc(sizeof(Node) * (r - f + 3));
i = f;
j = m + 1;
k = 0;
while(i <= m && j <= r)//merge
{
if(nd[i].r <= nd[j].r)
{
b[k++] = nd[i++];
if(k + f > i)
count += k + f - i;
}
else
b[k++] = nd[j++];
}
while(i <= m)
{
b[k++] = nd[i++];
if(k + f > i)
count += k + f - i;
}
while(j <= r)
b[k++] = nd[j++];
for(i = f; i <= r; i++)//copy
nd[i] = b[i - f];
free(b);
}
void MgSort(Node *nd, int f, int r)
{
if(f < r)
{
int m = (f + r) / 2;
MgSort(nd, f, m);
MgSort(nd, m + 1, r);
Merge(nd, f, m, r);
}
}
int main()
{
int i, j;
int n;
double x0, y0, x1, y1;
double k, t;
double l, r;
while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; i++)
{
scanf("%d%d%d%d", &lin[i].x0, &lin[i].y0, &lin[i].x1, &lin[i].y1);
}
scanf("%lf%lf", &l, &r);
for(i = 0; i < n; i++)
{
k = 1.0 * (lin[i].y1 - lin[i].y0) / (lin[i].x1 - lin[i].x0);
nd[i].l = k * (l - lin[i].x0) + lin[i].y0;
nd[i].r = k * (r - lin[i].x0) + lin[i].y0;
}
qsort(nd, n, sizeof(Node), cmp);
count = 0;
MgSort(nd, 0, n - 1);
printf("%lld\n", count);
}
//system("pause");
}
posted @
2012-08-13 15:12 小鼠標(biāo) 閱讀(256) |
評(píng)論 (0) |
編輯 收藏題意描述：
求若干條線段交叉點(diǎn)的個(gè)數(shù)。題目保證不會(huì)有兩條以上的線段交與一點(diǎn)。
乍一看還以為是計(jì)算幾何的東西，其實(shí)不然，題目的條件限制使得這一題很簡(jiǎn)單。我們把題目描述的地圖想象為笛卡爾坐標(biāo)系上的點(diǎn)，可以規(guī)定，兩邊岸上的點(diǎn)都有相同的x值（分別為x0，x1且x0<x1），這樣，如果x0，x1所夾范圍內(nèi)存在相交的兩條線段l1、l2的話，假設(shè)他們與x0，x1交點(diǎn)的y值分別為l1y0,l1y1和l2y0,l2y1，那么這兩條線段必須滿足以下簡(jiǎn)單條件：(l1y0-l2y0)*(l1y1-l2y1)<0。也就是說，在直線x0上和x1上，l1、l2的y值大小順序是相反的，這讓我們聯(lián)想到了逆序?qū)Α?br />具體做法是：
先將每條線段按x0對(duì)應(yīng)的y值排序（我稱之為第一次排序），然后根據(jù)x1對(duì)應(yīng)的y值求出逆序?qū)Φ膫€(gè)數(shù)，既是交叉點(diǎn)的個(gè)數(shù)。求逆序?qū)Φ姆椒ㄗ钪苯拥木褪窃诿芭菖判蚴怯涗浗粨Q的次數(shù)，不過這樣會(huì)超時(shí)，改進(jìn)的算法是利用歸并排序，在每次歸并的時(shí)候統(tǒng)計(jì)逆序?qū)€(gè)數(shù)（注意兩個(gè)數(shù)相等的情況，當(dāng)兩數(shù)相等時(shí)它們不是逆序?qū)?/strong>）。
注意：在第一次排序中，因?yàn)椴煌€段的y值可能是相等的，這種情況下我們要依據(jù)x1對(duì)應(yīng)的y值排序。忽略這種情況會(huì)導(dǎo)致計(jì)算的逆序?qū)€(gè)數(shù)增多。
逆序?qū)㈤啠?a href="http://m.shnenglu.com/hoolee/archive/2012/07/18/184090.html">http://m.shnenglu.com/hoolee/archive/2012/07/18/184090.html
做的好艱辛，感謝冰冰學(xué)長(zhǎng)。
以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#define LEN 1010000
typedef struct
{
int e;
int w;
}Road;
long long count;
Road rd[LEN];
int cmp(const void *a, const void *b)
{
Road *a0 = (Road*)a;
Road *b0 = (Road*)b;
if(a0 -> e != b0 -> e)
return a0 -> e > b0 -> e ? 1 : -1;
else
return a0 -> w > b0 -> w ? 1 : -1;
}
void Merge(Road *rd, int f, int m, int r)
{
int i, j;
Road *b = (Road*)malloc(sizeof(Road) * (r - f + 3));
i = f;
j = m + 1;
int k = 0;
while(i <= m && j <= r)
{
if(rd[i].w > rd[j].w)
b[k++] = rd[j++];
else
{
b[k++] = rd[i++];
if(k + f > i)
count += (k + f - i);
}
}
while(i <= m)
{
b[k++] = rd[i++];
if(k + f > i)
count += (k + f - i);
}
while(j <= r)
b[k++] = rd[j++];
for(i = f; i <= r; i++)
rd[i] = b[i - f];
free(b);
}
void MgSort(Road *rd, int f, int r)
{
if(f < r)
{
int m = (f + r) / 2;
MgSort(rd, f, m);
MgSort(rd, m + 1, r);
Merge(rd, f, m, r);
}
}
int main()
{
int i, j, k;
int N, M, K;
int T;
scanf("%d", &T);
for(k = 1; k <= T; k++)
{
scanf("%d%d%d", &N, &M, &K);
for(i = 0; i < K; i++)
scanf("%d%d", &rd[i].e, &rd[i].w);
qsort(rd, K, sizeof(Road), cmp);
count = 0;
MgSort(rd, 0, K - 1);
printf("Test case %d: %lld\n", k, count);
}
//system("pause");
return 0;
}
posted @
2012-08-13 15:04 小鼠標(biāo) 閱讀(1340) |
評(píng)論 (1) |
編輯 收藏大整數(shù)的乘法。假設(shè)求a*b，做法是將b的每一位與a相乘后再求和，注意b的不同位權(quán)值是不一樣的。
以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 100
void Out(char *s)
{
for(int i = 0; i < 10; i++)
printf("%d", s[i]);
putchar(10);
}
void Add(char *num1, char *num2)
{
int i, j;
for(i = 0; i < LEN; i++)
num1[i] += num2[i];
int t = 0;
int t2;
for(i = 0; i < LEN; i++)
{
t2 = num1[i] + t;
t = t2 / 10;
num1[i] = t2 % 10;
}
}
void Multi(char *num1, int n, int w)
{//num1與n相乘，n的權(quán)重為10^(w-1)
int i, j;
char c;
int len = LEN;
while(num1[--len] == 0 && len > 0);
for(i = len; i >= 0; i--)//move
num1[w - 1 + i] = num1[i];
for(i = 0; i < w - 1; i++)
num1[i] = 0;
for(i = 0; i < LEN; i++)//multiply
num1[i] *= n;
int t = 0;
int t2;
for(i = 0; i < LEN; i++)//carry bit
{
t2 = num1[i] + t;
t = t2 / 10;
num1[i] = t2 % 10;
}
}
void Reverse(char *s)
{
int len = strlen(s);
for(int i = 0; i < len / 2; i++)
{
char c = s[i];
s[i] = s[len - 1 - i];
s[len - 1 - i] = c;
}
}
void ToNum(char *s)
{
int len = strlen(s);
for(int i = 0; i < len; i++)
s[i] -= '0';
}
void Copy(char *t, char *f)
{
for(int i = 0; i < LEN; i++)
t[i] = f[i];
}
char A[LEN];//最終結(jié)果
char B[LEN];//乘數(shù)
char C[LEN];//乘數(shù)
char D[LEN];
/*
*獲取C[]的每一位與B[]相乘，結(jié)果存在D[]中，
*并不斷將D[]加到A[]上，最后A[]中存的就是結(jié)果
*/
int main()
{
int i, j;
gets(B);
gets(C);
int lenc = strlen(C);
Reverse(B);
Reverse(C);
ToNum(B);
ToNum(C);
int w = 1;
for(i = 0; i < lenc; i++)
{
Copy(D, B);
Multi(D, C[i], i + 1);
Add(A, D);
}
i = LEN;
while(A[--i] == 0 && i > 0);
for(; i >= 0; i--)
printf("%d", A[i]);
putchar(10);
//system("pause");
}
import java.math.*;
import java.util.*;
public class Main 
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s1 = sc.nextLine();
String s2 = sc.nextLine();
BigInteger b1 = new BigInteger(s1);
BigInteger b2 = new BigInteger(s2);
BigInteger b3 = b2.multiply(b1);
System.out.println(b3);
}
}
posted @
2012-08-12 11:16 小鼠標(biāo) 閱讀(537) |
評(píng)論 (0) |
編輯 收藏