posted @
2013-03-15 22:24 小鼠标 阅读(211) |
评论 (0) |
编辑 收藏
摘要: 安装ubuntu11.10后无线网络无法启动，就算在网络里面启动，也会自动关闭……
阅读全文
posted @
2012-10-02 21:12 小鼠标 阅读(927) |
评论 (1) |
编辑 收藏
摘要: 水水更健康吧，好几天木有A题了。
字符串处理、四舍五入。
阅读全文
posted @
2012-09-17 20:08 小鼠标 阅读(142) |
评论 (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 小鼠标 阅读(275) |
评论 (0) |
编辑 收藏
摘要: 网络流算法描述如下：
1.利用残留网络寻找增广路
2.将这一条增广路在图中去除，并修改残留网络
3.重复1、2步，直到找不到残留网络
阅读全文
posted @
2012-09-07 22:13 小鼠标 阅读(307) |
评论 (0) |
编辑 收藏
摘要: 最赤裸的网络流，不断找出增广路增广即可。找增广路时，这里用的深度优先搜索。
阅读全文
posted @
2012-09-07 21:29 小鼠标 阅读(281) |
评论 (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 小鼠标 阅读(1162) |
评论 (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 小鼠标 阅读(215) |
评论 (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 小鼠标 阅读(187) |
评论 (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 小鼠标 阅读(117) |
评论 (0) |
编辑 收藏