[Offer收割]编程练习赛11(部分) - dblank

[Offer收割]编程练习赛11(部分)

[[Offer收割]编程练习赛11](http://hihocoder.com/contest/offers11)

A.hiho字符串

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

如果一个字符串恰好包含2个'h'、1个'i'和1个'o',我们就称这个字符串是hiho字符串。

例如"oihateher"、"hugeinputhugeoutput"都是hiho字符串。

现在给定一个只包含小写字母的字符串S,小Hi想知道S的所有子串中,最短的hiho字符串是哪个。

输入

字符串S

对于80%的数据,S的长度不超过1000

对于100%的数据,S的长度不超过100000

输出

找到S的所有子串中,最短的hiho字符串是哪个,输出该子串的长度。如果S的子串中没有hiho字符串,输出-1。

样例输入

happyhahaiohell

样例输出

5

解题思路:

  • 双指针法。
  • r移动到区间满足条件(这个地方要h、i、o的个数都大于所需的)。
  • l每次都移动一位,让对应的str[l]个数减去。
  • 在这个过程中,对满足条件的(r - l)更新ans。

AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 100000 + 10, inf = 0x3f3f3f3f;
typedef long long ll;
char s[N];
int main()
{
    scanf("%s", s);
    int h = 0, i = 0, o = 0;
    int l = 0, r = 0, len = strlen(s);
    int ans = inf, flag = 0;
    while(l<len)
    {
        while(r<len && !flag)
        {
            if(s[r] == 'h')
                h++;
            if(s[r] == 'i')
                i++;
            if(s[r] == 'o')
                o++;
            r++;
            if(h >= 2 && i >= 1 && o >= 1)
            {
                flag = 1;
                break;
            }
        }
        if(h==2&&i==1&&o==1)
            ans = min(r - l, ans);
        if(s[l] == 'h') h--;
        if(s[l] == 'i') i--;
        if(s[l] == 'o') o--;
        if(!(h >= 2 && i >= 1 && o >= 1))
            flag = 0;
        l++;
    }
    if(ans == inf) ans=-1;
        cout<<ans<<endl;
    return 0;
}

B. 物品价值

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi现在有n个物品,每个物品都有一个价值。并且这n个物品总共有m个不同的属性,每个物品都具有其中若干属性。

小Ho要从中选出若干物品,满足每个属性都正好有奇数个物品拥有,且被选出的物品价值总和最大。你能帮助小Ho完成任务么?

输入

第一行一个数T(<=10),表示数据组数。对于每一组数据:

第一行两个数n,m(1<=n<=1000,m<=10)

接下来每两行描述一件物品。对于每一件物品:

第一行两个数v和s,表示其价值和所含属性数量(v<=100000,s<=m)

第二行s个数,表示该物品拥有的属性编号(1<=编号<=m)

输出

物品价值总和的最大值。

样例输入

`
1
3 2
2 1
1
2 1
2
5 2
1 2
`

样例输出

5

解题思路:

  • 是一个01背包问题,它背包容量是每个属性的奇偶状态。
  • 对于奇偶状态,因为m最多为10,我们使用二进制状态压缩表示。
  • dpi表示选择到第i个物品时,属性奇偶状态为j的最大价值和。

注意初始话这个dp状态数组

AC代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1000 + 10;
int dp[N][1<<11], bag[N];
int v[N], m;
int getStatus(int *vis)
{
    int res = 0;
    for(int i = 1; i<=m; i++)
        res = res*2 + vis[i];
    return res;
}
int main()
{
    int t, vis[12];
    scanf("%d", &t);
    while(t--)
    {
        int n, s, tp;
        scanf("%d%d", &n, &m);
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i<=n; i++)
        {
            scanf("%d%d", &v[i], &s);
            memset(vis, 0, sizeof(vis));
            for(int j = 1; j<=s; j++)
            {
                scanf("%d", &tp);
                vis[tp] = 1;
            }
            bag[i] = getStatus(vis);
            dp[i][bag[i]] = v[i];          //初始化dp数组
        }
        for(int i = 2; i<=n; i++)
        {
            for(int j =(1<<m)-1; j>=0; j--)
            {
                dp[i][j] = max(dp[i-1][j], dp[i][j]);   //不选取该物品
                if(dp[i-1][j^bag[i]])
                    dp[i][j] = max(dp[i][j], dp[i-1][j^bag[i]] + v[i]);  //选取该物品
            }
        }
        printf("%d\n", dp[n][(1<<m)-1]);
    }
    return 0;
}

C.岛屿3

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

H国正在进行一项持续N周的填海造岛工程。整片工程海域可以被看作是1000x1000的网格。

每周都有一块1x1的单位方格海域被填成陆地。如果我们将连成一片的陆地(一块单位方格与它上下左右4个单位方格是相连的)视为岛屿,H国想监测每周末整片海域中一共存在有多少个岛屿,以及这些岛屿的总面积和总周长各是多少。

假设工程持续三周,第一周被填的海域坐标是(0,0),那么第一周结束后有1座岛屿、总面积是1、总周长是4:

第二周被填的海域坐标是(1, 1),那么第二周结束后有2座岛屿、总面积是2、总周长是8:

#..
.#.
...

第三周被填的海域坐标是(1, 0),那么第三周结束后有1座岛屿、总面积是3、总周长是8:

#..
##.
...

你能完成这项任务么?

输入

第一行包含一个整数N,表示工程持续的周数。(1 <= N <= 100000)

以下N行每行包含两个整数x和y,表示当周被填的海域坐标。(0 <= x, y < 1000)

输出

输出N行,每行包含3个整数,依次是当周末岛屿的数量、总面积和总周长。

样例输入

3 
0 0   
1 1   
1 0

样例输出

1 1 4  
2 2 8  
1 3 8 

解题思路

  • 用并查集来表示集合的状态
  • 对于集合的个数,每次添加一个一个岛屿便试图将其与上下左右添加至集合里面。
  • 如果添加成功则集合个数和边长都会改变.
  • 集合个数为__总岛屿个数 - 合并成功个数_ , __4 - 上下左右岛屿个数×2__.

AC 代码

#include<bits/stdc++.h>

typedef long long ll;
using namespace std;
const int N = 1000000 + 10000, inf = 0x3f3f3f3f;
int root[N], run[][2] = {1, 0, 0, 1, -1, 0, 0, -1};
int vis[1010][1010];
int Find(int x)
{
    return x == root[x] ? x : root[x] = Find(root[x]);
}
int join(int x, int y)
{
    int a = Find(x), b = Find(y);
    if(a != b)
    {
        root[a] = b;
        return 1;
    }
    return 0;
}
int main()
{
    int n;
    scanf("%d", &n);
    memset(vis, 0, sizeof(vis));
    for(int i = 0; i<N-1; i ++)
        root[i] = i;
    int l = 0,cnt = 0,res, x, y, mark;
    for(int i = 1; i<=n; i++)
    {
        scanf("%d%d", &x, &y);
        vis[x][y] = 1;
        res = 0;
        for(int j = 0; j<4; j++)
        {
            int n_x = x + run[j][0], n_y = y + run[j][1];
            if(n_x>=0 && n_y>=0 && vis[n_x][n_y])
            {
                if(join(x*1005+y, n_x*1005+n_y))
                    cnt++;
                res++;
            }
        }

        l += 4-2*res;
        printf("%d %d %d\n", i - cnt, i, l);
    }
    return 0;
}

相关文章

发表新评论