NC练习赛

NC练习赛

A：牛能和宝石
题目：
牛能有 n 件装备和 n 颗宝石，第 i 件装备的重量为 ai ，第 i 颗宝石的重量为 bi?，牛能要给每一件装备都嵌上一颗宝石，当牛能给第 i 件装备嵌上第 j 颗宝石后，装备的重量会变为 ai+bi? ，牛能对装备的厌恶度为所有装备中重量的最大值。你作为牛能的好朋友，决定帮助牛能给装备嵌上宝石，使得牛能对装备的厌恶度尽可能的小。
输入描述:
第一行一个整数 n
第二行 n 个整数 a1a2...an
第三行 n 个整数 b1b2...bn
?

输出描述:
输出一个整数表示嵌上宝石后小灰灰对装备的厌恶度。
示例1
输入
5
1 2 3 4 5
5 4 3 2 1

输出
6

备注:
?1≤n，ai，bi ≤100000

思路：结论题，a正序数组和b逆序数组一一对应相加即可.（第一眼还以为背包问题，刚开始做题太紧张，wa了两次）

Code:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+7;
const int maxm = 2e5+7;
const long long mod = 1e9+7;
const long long INF =0x3f3f3f3f;
LL n,a[maxn],b[maxn],sum[maxn];
bool cmp(LL a,LL b)
{
    return a > b;
}
 
int main()
{
    scanf("%lld",&n);
    for(int i = 1; i <= n; i++)
        scanf("%lld",&a[i]);
    for(int i = 1; i <= n; i++)
        scanf("%lld",&b[i]);
    sort(a+1,a+n+1);
    sort(b+1,b+n+1,cmp);
    for(int i = 1; i <= n; i++)
        sum[i] = a[i] + b[i];
    sort(sum+1,sum+n+1,cmp);
    printf("%lld",sum[1]);
    return 0;
}

B：牛妹和01串
题目:
牛妹有一个{01}01串，串中只包含{0}0和{1}1，牛妹要把这个串划分成连续的m段，使得每一段至少包含一个0和一个1。
牛妹想最大化m，m最大是多少呢？
输入描述:
输入包含一行一个01串S。保证中至少包含一个0和一个1。
输出描述:
输出一行一个整数表示答案。
示例1

输入
10101111000010101111010101

输出
9

备注:
2≤∣S∣≤1e5
∣S∣表示字符串{S}S的长度。

思路：贪心策略，出现01/10就计数+1，接着跳到下一对字符串，假如没有出现01对就往下一个字符寻找.
Code:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+7;
const int maxm = 2e5+7;
const long long mod = 1e9+7;
const long long INF =0x3f3f3f3f;
char str[maxn];
int flag = 0;
 
int main()
{
    scanf("%s",str);
    int len = strlen(str);
    for(int i = 0; i < len-1;)
    {
        if(str[i] == '0' && str[i+1] == '1')
        {
            flag++;
            i = i + 2; 
        }
        else if(str[i] == '1' && str[i+1] == '0')
        {
            flag++;
            i = i + 2;
        }
        else
            i++;
    }
    printf("%d",flag);
    return 0;
}

C：矩阵消除游戏
题目：
牛妹在玩一个名为矩阵消除的游戏，矩阵的大小是n行m列，第i行第j列的单元格的权值为a(i,j)，牛妹可以进行k个回合的游戏，在每个回合，牛妹可以选择一行或者选择一列，然后将这一行或者这一列的所有单元格中的权值变为0，同时牛妹的分数会加上这一行或者这一列中的所有单元格的权值的和。

牛妹想最大化她的得分，球球你帮帮她吧！

输入描述:
第一行三个整数n,m,k
接下来n行每行m个整数表示矩阵中各个单元格的权值。
输出描述:
输出一个整数表示牛妹能获得的最大分数。
示例1

输入
3 3 2
101 1 102
1 202 1
100 8 100

输出
414

备注:
1≤n,m≤15
1≤a(i,j)≤1e6
1≤k≤n?m

思路：贪心策略，选取矩阵中最大的行权值和与最大的列权值和进行比较，然后删掉该行/该列的元素，但是要注意，还需要比较只选行或者只选列的情况（wa了一早上，到中午才发现），还有要注意排序后的坐标变化.

其实比赛的时候用dfs做的，样例过了，但其实可以hack掉，主要是不懂怎么回溯去接着搜下一种情况，翻了好多题解，几乎都是直接贪心写法吧，可能dfs会TLE？我也不确定，反正今早找巨佬帮忙找Bug，我都草稿纸上画满了方格，xswl，画了一早上，可以约一波五子棋了.

Code:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 7;
const int maxm = 2e5 + 7;
const int num = 16;
const long long INF = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
LL a[num][num],ans = 0,sum = 0,hh[num],ll[num],sum1,sum2;
int n,m,k;
struct node
{
    LL s,e; // s:第s行/列总和, e:第e行/列. 
}h[num],l[num];

bool cmp(node a,node b)
{
    return a.s > b.s;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1; i <= n; i++)
    {   
        for(int j = 1; j <= m; j++)
        {
            scanf("%lld",&a[i][j]);
            sum += a[i][j];
            h[i].s += a[i][j];
            hh[i] += a[i][j];
            h[i].e = i;
            l[j].s += a[i][j];
            ll[j] += a[i][j];
            l[j].e = j;
        }
    }
    if(k >= n || k >= m) //k=n∣∣k=m将所有行或所有列全部选择是最优策略
    {
        printf("%lld",sum);
        return 0;
    }
    for(int t = 1; t <= k; t++) //行列之中选最大 
    {
        sort(h+1,h+n+1,cmp);
        sort(l+1,l+m+1,cmp);
        if(h[1].s >= l[1].s)
        {
            ans += h[1].s;
            for(int y = 1; y <= m; y++)
            {
                l[y].s -= a[h[1].e][l[y].e];
                a[h[1].e][l[y].e] = 0;
                /*错误写法 
                    l[y].s -= a[h[1].e][y];
                    a[h[1].e][y] = 0;
                */ 
            }
            h[1].s = 0;
        }
        else
        {
            ans += l[1].s;
            for(int x = 1; x <= n; x++)
            {
                h[x].s -= a[h[x].e][l[1].e];
                a[h[x].e][l[1].e] = 0;
                /*错误写法 
                    h[x].s -= a[x][l[1].e];
                    a[x][l[1].e] = 0;
                */
            }
            l[1].s = 0;
        }
    }
    
    for(int i = 1; i <= k; i++) //单独只选行
    {
        sort(hh+1,hh+n+1);
        sum1 += hh[n];
        hh[n] = 0;
    } 
    ans = max(ans,sum1);
    
    for(int i = 1; i <= k; i++) //单独只选列 
    {
        sort(ll+1,ll+m+1);
        sum2 += ll[n];
        ll[m] = 0;
    } 
    ans = max(ans,sum2);
    printf("%lld",ans);
    return 0;
}


/*
3 3 2
101 1 102
1 202 1
100 8 100

414

3 4 2
6 6 3 4
2 5 6 7
1 10 3 4

39

3 3 2
5 20 10
10 20 20
5 10 10

90
 
3 3 2
5 10 5
20 20 10
10 20 10

90

*/

赛后总结： 肯定还是有题目超出自己能力的，尽管看了题解也一脸懵那种直接放弃了，自己有思路的就继续肝下去吧，虽然好像没了一早上，不过解出来了还是蛮开心的，比赛一定一定不要紧张，放平心态，一直看榜只会一直WA，还不如专心想题。一早上让我又熟练了一波调试...

NC练习赛

原文：https://www.cnblogs.com/K2MnO4/p/12382764.html