# HHUOJ 1114

## 1114: 屁屁上的巴掌

[提交][状态][讨论版][命题人:外部导入]

```1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
```

## 样例输出

```0
1
2
2

DFS，一开始想，写个函数判断周围有没有其他污点就行了，写着写着发现要用递归，然后才知道要用深搜（迟钝。。想通之后就简单了

```
``` 1 #include <iostream>
2 #include <stdio.h>
3 #include <cstring>
4 #include <algorithm>
5
6 using namespace std;
7
8 const int maxn = 105;
9 char board[maxn][maxn];
10 int dx[] = { -1,-1,-1,0,1,1,1,0 };
11 int dy[] = { -1,0,1,1,1,0,-1,-1 };
12 int n, m;
13 void dfs(int x, int y)
14 {
15     for (int i = 0; i < 8; i++)
16     {
17         int tempx = x + dx[i];
18         int tempy = y + dy[i];
19         if (board[tempx][tempy] == ‘@‘)
20         {
21             board[tempx][tempy] = ‘*‘;
22             dfs(tempx, tempy);
23         }
24     }
25 }
26 int main(void)
27 {
28     int n, m;
29     while (scanf_s("%d%d", &m, &n) != EOF && m != 0)
30     {
31         memset(board, ‘*‘, sizeof(board));
32         int i, j;
33         int count;
34         for (i = 1; i <= m; ++i)
35         {
36             for (j = 1; j <= n; ++j)
37             {
38                 cin >> board[i][j];
39             }
40         }
41         for (i = 0; i <= m + 1; ++i)
42         {
43             board[i][0] = ‘#‘;
44             board[i][n + 1] = ‘#‘;
45         }
46         for (j = 0; j <= n + 1; ++j)
47         {
48             board[0][j] = ‘#‘;
49             board[m + 1][j] = ‘#‘;
50         }
51         count = 0;
52         for (i = 1; i <= m; ++i)
53         {
54             for (j = 1; j <= n; ++j)
55             {
56                 if (board[i][j] == ‘@‘)
57                 {
58                     dfs(i, j);
59                     count++;
60                 }
61             }
62         }
63         cout << count << endl;
64     }
65     return 0;
66 }```

` `

## Ural 1114 Boxes

Boxes Time Limit: 600ms Memory Limit: 16384KB This problem will be judged on Ural. Original ID: 111464-bit integer IO format: %lld      Java class name: (Any) N boxes are lined up in a sequence (1 ≤ N ≤ 20). You have A red balls and B blue balls (0 ≤

## HDU 1114 Piggy-Bank 猪仔储钱罐（AC代码）完全背包（容量需满，价值最小）

1 #include <iostream> 2 #define MAX 0xfffffff 3 using namespace std; 4 //要求:1.刚好装满 2.总价值最小 5 int value[501]; 6 int weight[501]; 7 int dp[10010]; 8 int min(int a,int b) 9 { 10 return a<b?a:b; 11 } 12 int cal(int v,int n) //空间.种类 13 { 14 int i,j; 1

## csuoj 1114: 平方根大搜索

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1114 1114: 平方根大搜索 Time Limit: 5 Sec  Memory Limit: 128 MBSubmit: 118  Solved: 60[Submit][Status][Web Board] Description 在二进制中,2的算术平方根,即sqrt(2),是一个无限小数1.0110101000001001111... 给定一个整数n和一个01串S,你的任务是在sqrt(

## Acdream 1114 Number theory 莫比乌斯反演

http://acdream.info/problem?pid=1114 题目大意,给你一个序列a,求出这个序列中互质数的有多少对.其中所有的整数的都小于等于222222. f(d) 为 gcd 恰好为 d 的数的对数, F(d) 为 gcd 为 d 的倍数的对数, μ(d) 表示莫比乌斯函数 F(d) = ∑ f(n) 其中( n % d == 0 ) 莫比乌斯反演一下就可以得到, f(d) = ∑ μ(n / d) * F(n) 其中( n % d == 0) 所以我们最后所要的答案就是 f