posted @
2013-03-15 22:24 小鼠標 閱讀(218) |
評論 (0) |
編輯 收藏
摘要: 安裝ubuntu11.10后無線網絡無法啟動，就算在網絡里面啟動，也會自動關閉……
閱讀全文
posted @
2012-10-02 21:12 小鼠標 閱讀(944) |
評論 (1) |
編輯 收藏
摘要: 水水更健康吧，好幾天木有A題了。
字符串處理、四舍五入。
閱讀全文
posted @
2012-09-17 20:08 小鼠標 閱讀(151) |
評論 (0) |
編輯 收藏今年天津賽區網選第一題，開始2min就有人秒掉，有人說以前做過原題。
八進制數與十進制數的轉換，的確挺水的。
代碼如下：
#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 小鼠標 閱讀(283) |
評論 (0) |
編輯 收藏
摘要: 網絡流算法描述如下：
1.利用殘留網絡尋找增廣路
2.將這一條增廣路在圖中去除，并修改殘留網絡
3.重復1、2步，直到找不到殘留網絡
閱讀全文
posted @
2012-09-07 22:13 小鼠標 閱讀(313) |
評論 (0) |
編輯 收藏
摘要: 最赤裸的網絡流，不斷找出增廣路增廣即可。找增廣路時，這里用的深度優先搜索。
閱讀全文
posted @
2012-09-07 21:29 小鼠標 閱讀(292) |
評論 (1) |
編輯 收藏題意描述：有n個緊鎖的房間和這n個房間門上的n把鑰匙，每個房間中隨機鎖了一把鑰匙。你可以破壞一扇門，取出其中的鑰匙，嘗試用鑰匙打開另外的門（然后取出鑰匙去打開另外的門，或者接著破壞另外的門）。最多可以破壞k（<=n）扇門，但是第一扇門只能用鑰匙打開。求所有門能被打開（被破壞，或是被鑰匙打開）的概率。
傳說中的第一類斯特林數。
如果用s[n][k]表示n個門中有k個環的情況數，則有：
s[n][k] = s[n - 1][k - 1] + (n - 1) * s[n - 1][k], 1 <= k <= n - 1
上面的公式可以這樣理解：當前n - 1個門組成k - 1個環的時候，再加入第n個門形成一個單環即可；當n - 1個門組成k個環時，要加入第n個門，為了不增加環的個數，只需要將n插在前n - 1個門的任意一個門之后即可。
初始化情況為：
s[i][0] = 0;
s[i][i] = 1, i >= 1
因為第一個門不能在環中，只需將第一個門在環中的情況減去，即是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 小鼠標 閱讀(1175) |
評論 (0) |
編輯 收藏二分圖的性質：一個圖十二分圖，當且僅當圖中不存在奇數環。
把點分成兩個集合，把每個集合中相連的邊刪除即可。枚舉所有集合，找出刪除邊最小的那個。
#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 小鼠標 閱讀(224) |
評論 (0) |
編輯 收藏二維完全背包。
看過背包九講，意識到本題是背包，但開始時沒有把動態方程沒有搞清楚。
f[i][j]表示長i寬j的布能得到的最大價值。
#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 小鼠標 閱讀(196) |
評論 (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 小鼠標 閱讀(130) |
評論 (0) |
編輯 收藏