E001 数的划分

Problem Description

将整数n分成k份，且每份不能为空，任意两种分法不能相同（不考虑顺序）。
例如：n=7，k=3，下面三种分法被认为是相同的。
1,1,5；1,5,1；5,1,1；
问有多少种不同的分法。

Input

每组数据由一行上的2个整数n，k构成（6 < n ≤ 200,2 ≤ k ≤ 6）。

Output

对每组测试数据，输出不同的分法整数。

Sample Input

7 3

Sample Output

4

实现思路

DFS查找，每次找的时候按参数为上层拆分数，目前的和，目前的层数

实现细节

注意剪枝，否则会t

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
int ans,n,k;
void dfs(int la,int sum,int le)
{
    if (le == k)
    {
        if (sum==n)
            ans++;
        return;
    }
    for (int i=la;sum+i*(k-le)<=n;i++)
        dfs(i,sum+i,le+1);
}
int main()
{
    while (cin >> n >> k)
    {
        ans=0;
        dfs(1,0,0);
        cout << ans << endl;
    }
}

E002 闪避湖泊

Problem Description

农夫约翰的农场在最近的一场暴风雨中被水淹没。但保险公司仅根据他得农场中最大的“湖泊”的大小赔偿一个数额。
农场可表示为N行M列的长方形网格，（1 ≤ N ≤ 100,1 ≤ M ≤ 100）。网格中的每个单元或是干的或是被淹没的，且恰有K个单元被水淹没，（1 ≤ K ≤ N*M）。正如人们所希望的，湖泊是一个中间单元，它与其他的单元共享一条长边（不是角落）。任何与中间单元共享一条长边或者与连通单元共享一条长边的单元是一个连通单元，是湖泊的一部分。

Input

有多组数据。每组的第1行有3个整数N，M和K。第2行到第K+1行，是整数R和C，表示被淹没的位置。

Output

对每组测试数据，输出有最大湖泊的单元的数目

Sample Input

3 4 5
3 2
2 2
3 1
2 3
1 1
3 5 4
2 3
3 2
2 4
1 2

Sample Output

4

2

实现思路

dfs查找

实现细节

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
bool mp[105][105];
int n,m,k;
int bfs(int x,int y)
{
   if (!mp[x][y])
       return 0;
    mp[x][y] = false;
    return bfs(x-1, y)+bfs(x+1, y)+bfs(x, y-1)+bfs(x, y+1)+1;
}
int main()
{
    int ret;
    while (cin >> n >> m >> k)
    {
        int x,y;
        ret = -INF;
        memset(mp, false, sizeof(mp));
        for (int i=1;i<=k;i++)
        {
            scanf("%d%d",&x,&y);
            mp[x][y] = true;
        }
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                ret = max(ret,bfs(i,j));
        cout << ret << endl;
    }
}