posted @
2013-03-15 22:24 小鼠標(biāo) 閱讀(221) |
評(píng)論 (0) |
編輯 收藏
摘要: 安裝ubuntu11.10后無(wú)線網(wǎng)絡(luò)無(wú)法啟動(dòng)，就算在網(wǎng)絡(luò)里面啟動(dòng)，也會(huì)自動(dòng)關(guān)閉……
閱讀全文
posted @
2012-10-02 21:12 小鼠標(biāo) 閱讀(947) |
評(píng)論 (1) |
編輯 收藏
摘要: 水水更健康吧，好幾天木有A題了。
字符串處理、四舍五入。
閱讀全文
posted @
2012-09-17 20:08 小鼠標(biāo) 閱讀(156) |
評(píng)論 (0) |
編輯 收藏今年天津賽區(qū)網(wǎng)選第一題，開(kāi)始2min就有人秒掉，有人說(shuō)以前做過(guò)原題。
八進(jìn)制數(shù)與十進(jìn)制數(shù)的轉(zhuǎn)換，的確挺水的。
代碼如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define LEN 100
char str[LEN];
int main()
{
int i, j;
int sum = 0;
scanf("%s", str);
while(str[0] != '0')
{
//printf("str = %s\n", str);
int len = strlen(str);
char str2[LEN];
strcpy(str2, str);
for(i = 0; i < len; i++)
{
switch(str[i])
{
case '0':
str[i] = 0;
break;
case '1':
str[i] = 1;
break;
case '2':
str[i] = 2;
break;
case '4':
str[i] = 3;
break;
case '5':
str[i] = 4;
break;
case '6':
str[i] = 5;
break;
case '7':
str[i] = 6;
break;
case '9':
str[i] = 7;
break;
}
}
sum = 0;
for(i = 0; i < len; i++)
sum += str[i] * (int)(pow(8, len - i - 1) + 0.5);
printf("%s: %d\n", str2, sum);
scanf("%s", str);
}
//system("pause");
return 0;
}
posted @
2012-09-10 20:26 小鼠標(biāo) 閱讀(286) |
評(píng)論 (0) |
編輯 收藏
摘要: 網(wǎng)絡(luò)流算法描述如下：
1.利用殘留網(wǎng)絡(luò)尋找增廣路
2.將這一條增廣路在圖中去除，并修改殘留網(wǎng)絡(luò)
3.重復(fù)1、2步，直到找不到殘留網(wǎng)絡(luò)
閱讀全文
posted @
2012-09-07 22:13 小鼠標(biāo) 閱讀(315) |
評(píng)論 (0) |
編輯 收藏
摘要: 最赤裸的網(wǎng)絡(luò)流，不斷找出增廣路增廣即可。找增廣路時(shí)，這里用的深度優(yōu)先搜索。
閱讀全文
posted @
2012-09-07 21:29 小鼠標(biāo) 閱讀(294) |
評(píng)論 (1) |
編輯 收藏題意描述：有n個(gè)緊鎖的房間和這n個(gè)房間門(mén)上的n把鑰匙，每個(gè)房間中隨機(jī)鎖了一把鑰匙。你可以破壞一扇門(mén)，取出其中的鑰匙，嘗試用鑰匙打開(kāi)另外的門(mén)（然后取出鑰匙去打開(kāi)另外的門(mén)，或者接著破壞另外的門(mén)）。最多可以破壞k（<=n）扇門(mén)，但是第一扇門(mén)只能用鑰匙打開(kāi)。求所有門(mén)能被打開(kāi)（被破壞，或是被鑰匙打開(kāi)）的概率。
傳說(shuō)中的第一類(lèi)斯特林?jǐn)?shù)。
如果用s[n][k]表示n個(gè)門(mén)中有k個(gè)環(huán)的情況數(shù)，則有：
s[n][k] = s[n - 1][k - 1] + (n - 1) * s[n - 1][k], 1 <= k <= n - 1
上面的公式可以這樣理解：當(dāng)前n - 1個(gè)門(mén)組成k - 1個(gè)環(huán)的時(shí)候，再加入第n個(gè)門(mén)形成一個(gè)單環(huán)即可；當(dāng)n - 1個(gè)門(mén)組成k個(gè)環(huán)時(shí)，要加入第n個(gè)門(mén)，為了不增加環(huán)的個(gè)數(shù)，只需要將n插在前n - 1個(gè)門(mén)的任意一個(gè)門(mén)之后即可。
初始化情況為：
s[i][0] = 0;
s[i][i] = 1, i >= 1
因?yàn)榈谝粋€(gè)門(mén)不能在環(huán)中，只需將第一個(gè)門(mén)在環(huán)中的情況減去，即是s[i][j] - s[i - 1][j - 1]才是合法的情況。
以下是代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 30
long long s[LEN][LEN];
int main()
{
int i, j;
int T;
int N, K;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &N, &K);
memset(s, 0, sizeof(s));
for(i = 0; i <= N; i++)// init
s[i][i] = 1;
for(i = 1; i <= N; i++)
for(j = 1; j <= i; j++)
s[i][j] = (i - 1) * s[i - 1][j] + s[i - 1][j - 1];
long long sum = 0;
long long base = 0;
for(i = 0; i <= K; i++)
sum += s[N][i] - s[N - 1][i - 1];
for(i = 0; i <= N; i++)
base += s[N][i];
double rs = 1.0 * sum / base;
printf("%.4lf\n", rs);
}
//system("pause");
return 0;
}
posted @
2012-09-06 20:39 小鼠標(biāo) 閱讀(1179) |
評(píng)論 (0) |
編輯 收藏二分圖的性質(zhì)：一個(gè)圖十二分圖，當(dāng)且僅當(dāng)圖中不存在奇數(shù)環(huán)。
把點(diǎn)分成兩個(gè)集合，把每個(gè)集合中相連的邊刪除即可。枚舉所有集合，找出刪除邊最小的那個(gè)。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 20
#define MAX 0xfffffff
int mp[LEN][LEN];
int N, M;
int rs;
int tt;
int gd[LEN];
void DFS(int n)
{
if(n >= N)
{
int i, j;
tt = 0;
for(i = 0; i < n; i++)
for(j = i + 1; j < n; j++)
{
if(gd[i] == gd[j])
tt += mp[i][j];
}
if(tt < rs)
rs = tt;
}
else
{
gd[n] = 1;
DFS(n + 1);
gd[n] = 0;
DFS(n + 1);
}
}
int main()
{
int i, j;
int T;
int x, y;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &N, &M);
memset(mp, 0, sizeof(mp));
for(i = 0; i < M; i++)
{
scanf("%d%d", &x, &y);
mp[x][y]++;
mp[y][x]++;
}
memset(gd, 0, sizeof(gd));
rs = MAX;
DFS(0);
printf("%d\n", rs);
}
//system("pause");
return 0;
}
posted @
2012-09-04 22:39 小鼠標(biāo) 閱讀(226) |
評(píng)論 (0) |
編輯 收藏二維完全背包。
看過(guò)背包九講，意識(shí)到本題是背包，但開(kāi)始時(shí)沒(méi)有把動(dòng)態(tài)方程沒(méi)有搞清楚。
f[i][j]表示長(zhǎng)i寬j的布能得到的最大價(jià)值。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 15
#define LENF 1010
typedef struct
{
int x;
int y;
int c;
}Cut;
Cut ct[LEN];
int f[LENF][LENF];
int N, X, Y;
int Max2(int a, int b)
{
if(a < b)
a = b;
return a;
}
int main()
{
int i, j, k;
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &N, &X, &Y);
for(i = 0; i < N; i++)
scanf("%d%d%d", &ct[i].x, &ct[i].y, &ct[i].c);
memset(f, 0, sizeof(f));
for(i = 1; i <= X; i++)
for(j = 1; j <= Y; j++)
for(k = 0; k < N; k++)
{
int x1 = ct[k].x;
int y1 = ct[k].y;
int c = ct[k].c;
if(i >= x1 && j >= y1)
{
f[i][j] = Max2(f[i][j], f[i - x1][j] + f[x1][j - y1] + c);
f[i][j] = Max2(f[i][j], f[i - x1][y1] + f[i][j - y1] + c);
}
x1 = ct[k].y;
y1 = ct[k].x;
if(i >= x1 && j >= y1)
{
f[i][j] = Max2(f[i][j], f[i - x1][j] + f[x1][j - y1] + c);
f[i][j] = Max2(f[i][j], f[i - x1][y1] + f[i][j - y1] + c);
}
}
printf("%d\n", f[X][Y]);
}
//system("pause");
return 0;
}
posted @
2012-09-04 21:34 小鼠標(biāo) 閱讀(199) |
評(píng)論 (0) |
編輯 收藏字符串處理的水題~~
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 100
char str[LEN];
int len;
int isURL()
{
int i;
for(i = 0; i < len; i++)
{
if(str[i] == ':')
break;
}
if((str[i + 1] == '/' || str[i + 1] == '\\') && (str[i + 2] == '/' || str[i + 2] == '\\'))
return 1;
return 0;
}
int isUnix()
{
if(str[0] == '/' || str[0] == '\\')
return 1;
return 0;
}
int isW()
{
int i;
for(i = 0; i < len; i++)
{
if(str[i] == ':')
break;
}
if(str[i + 1] == '/' || str[i + 1] == '\\')
{
if(str[i + 2] == '/' || str[i + 2] == '\\')
return 0;
return 1;
}
return 0;
}
int main()
{
int i, j;
int T;
scanf("%d", &T);
getchar();
while(T--)
{
gets(str);
len = strlen(str);
if(isURL())
{
printf("It's a URL!\n");
for(i = 0; i < len; i++)
{
if(str[i] == '\\')
putchar('/');
else
putchar(str[i]);
}
}
else if(isUnix())
{
printf("It's a path in Unix-like systems!\n");
for(i = 0; i < len; i++)
if(str[i] == '\\')
putchar('/');
else
putchar(str[i]);
}
else if(isW())
{
printf("It's a path in Windows system!\n");
for(i = 0; i < len; i++)
if(str[i] == '/')
putchar('\\');
else
putchar(str[i]);
}
putchar(10);
//printf("\n");
}
//system("pause");
return 0;
}
posted @
2012-09-04 19:57 小鼠標(biāo) 閱讀(133) |
評(píng)論 (0) |
編輯 收藏