2021牛客寒假算法基础集训营3

C 重力坠击 || 暴力 || dfs状压

看数据范围暴力
(I)直接暴力枚举敌人位置(15*15),根据k次攻击进行k+1重循环
k再大一点,这种方法就不适用了,可以用dfs状压代替(见法二)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 3;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
struct node
{
    int x, y, r;
    bool f;
}pro[12];
struct node2
{
    int x, y;
}pro2[230];
bool jud(int x, int y, int r, int x1, int y1, int r1)
{
    if(sqrt((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y)) <= r + r1) return true;
    return false;
}
int main()
{
    int n, m, R, ans = 0, cnt = 0, cnt2 = 0;
    cin >> n >> m >> R;
    for(int i = 1; i <= n; ++i) scanf("%d %d %d", &pro[i].x, &pro[i].y, &pro[i].r), pro[i].f = 0;
    for(int i = -7; i <= 7; ++i)
        for(int j = -7; j <= 7; ++j)
            pro2[++cnt2].x = i, pro2[cnt2].y = j;
    if(m == 1)
    {
        for(int i = 1; i <= 225; ++i)
        {
            cnt = 0;
            for(int j = 1; j <= n; ++j)
            {
                if(jud(pro2[i].x, pro2[i].y, R, pro[j].x, pro[j].y, pro[j].r)) ++cnt;
            }
            ans = max(ans, cnt);
        }
    }
    else if(m ==2)
    {
        for(int i = 1; i <= 225; ++i)
        {
            for (int j = i + 1; j <= 225; ++j)
            {
                cnt = 0;
                for(int k = 1; k <= n; ++k)
                {
                    if(jud(pro2[i].x, pro2[i].y, R, pro[k].x, pro[k].y, pro[k].r) && !pro[k].f) {
                        ++cnt;
                        pro[k].f = 1;
                    }
                    if(pro[k].f) continue;
                    if(jud(pro2[j].x, pro2[j].y, R, pro[k].x, pro[k].y, pro[k].r) && !pro[k].f) {
                        ++cnt;
                        pro[k].f = 1;
                    }
                }
                ans = max(ans, cnt);
                for(int k = 1; k <= n; ++k) pro[k].f = 0;
            }
        }
    }
    else if(m == 3)
    {
        for(int i = 1; i <= 225; ++i)
        {
            for(int j = i + 1; j <= 225; ++j)
            {
                for(int k = j + 1; k <= 225; ++k)
                {
                    cnt = 0;
                    for(int t = 1; t <= n; ++t)
                    {
                        if(jud(pro2[i].x, pro2[i].y, R, pro[t].x, pro[t].y, pro[t].r) && !pro[t].f) {
                            ++cnt;
                            pro[t].f = 1;
                        }
                        if(pro[t].f) continue;
                        if(jud(pro2[j].x, pro2[j].y, R, pro[t].x, pro[t].y, pro[t].r) && !pro[t].f) {
                            ++cnt;
                            pro[t].f = 1;
                        }
                        if(pro[t].f) continue;
                        if(jud(pro2[k].x, pro2[k].y, R, pro[t].x, pro[t].y, pro[t].r) && !pro[t].f) {
                            ++cnt;
                            pro[t].f = 1;
                        }
                    }
                    ans = max(ans, cnt);
                    for(int k = 1; k <= n; ++k) pro[k].f = 0;
                }
            }
        }
    }
    cout << ans << endl;
}

(II)dfs状压

D 签到

F 匹配串

由于每个模式串至少有一个‘#’,所以只需要保证所有模式串前缀(第一个‘#’前)和后缀(最后一个‘#’后)不互相矛盾即可
注意:并不是要求所有前缀都一样,后缀都一样,而是保证不矛盾就可以,比如a#和ab#可以共存
wa点:反向看后缀时b数组要正着存!!因为模式串长度不一定相同,倒着存可能导致b的下标不同

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 3;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
char a[maxn], b[maxn];
int main()
{
    int n, ans = -1;
    cin >> n;
    string s;
    for(int i = 1; i <= n; ++i)
    {
        cin >> s;
        for(int j = 0; ; ++j)
        {
            if(s[j] == '#') break;
            if(a[j] == 0) a[j] = s[j];
            else if(a[j] != s[j]) ans = 0;
        }
        for(int j = s.size() - 1; ; --j)
        {
            if(s[j] == '#') break;
            if(b[j-s.size()+1] == 0) b[j-s.size()+1] = s[j];
            else if(b[j-s.size()+1] != s[j]) ans = 0;
        }
    }
    cout << ans << endl;
}

G 糖果 || 并查集

每一个朋友圈的每个小朋友都要给所在朋友圈中糖果数的最大值,并查集维护朋友圈
如何处理找到最大值:首先建圈时先不处理,建好圈后,遍历n个小朋友,对每个小朋友都find其父亲,并将父亲的糖果数置为他与他父亲糖果数的最大值,这样遍历一次后的效果是,每个小朋友都直接连着父亲(由于路径压缩),而且每个父亲的糖果数都是所在朋友圈的最大值。然后再遍历n个小朋友,每个小朋友得到的糖果数就等于其父亲的,累加即可

H 数字串

注意:字母串不仅可以变长,还可以变短!比如,aaa可以变成ka
满足这种情况的只能接到a或b之后,然后在符合条件的情况下,将a或b与后一个字母的第一位组合成新的,后一个字母的第二位(如果有的话)单独成为一个即可(10,20不行,由于0没有字母匹配)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 3;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
vector<char> v;
int main()
{
    string s;
    int x, y, tmp, tmp2;
    bool flag = 0;
    cin >> s;
    for(int i = 0; i < s.size(); ++i)
    {
        tmp = s[i] - 'a' + 1;
        if(flag) v.push_back(s[i]);
        else if(tmp <= 10 || tmp % 10 == 0)
        {
            if(tmp > 2) {v.push_back(s[i]); continue;}
            tmp2 = s[i+1] - 'a' + 1;
            if(tmp2 > 10 && tmp2 % 10 != 0)
            {
                x = tmp2 % 10;
                tmp2 /= 10;
                y = tmp2 % 10;
                tmp = tmp * 10 + y;
                v.push_back(tmp + 'a' - 1);
                v.push_back(x + 'a' - 1);
                flag = 1;
                ++i;
            }
            else if(tmp2 < 10)
            {
                x = tmp2 % 10;
                tmp = tmp * 10 + x;
                v.push_back(tmp + 'a' - 1);
                flag = 1;
                ++i;
            }
        }
        else
        {
            x = tmp % 10;
            tmp /= 10;
            y = tmp % 10;
            v.push_back(y + 'a' - 1);
            v.push_back(x + 'a' - 1);
            flag = 1;
        }
    }
    if(!flag) cout << -1 << endl;
    else{
        for(int i = 0; i <v.size(); ++i) printf("%c", v[i]);
    }
}

I 序列的美观度 || dp

(I)将有可能与后面数配成一对的数存在set里,若找到一对匹配,那么set中的元素无用了,就清空set,并存入当前最后一个数
此题满足这种“贪心”的想法,找到一对匹配,就算入答案,前面未匹配的一段元素就废掉

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 3;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
int a[maxn], ans;
set<int> s;
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        if(a[i] == a[i-1]) {
            ++ans;
            s.clear();
            s.insert(a[i]);
        }
        else {
            if(s.count(a[i])) {++ans; s.clear();}
            s.insert(a[i]);
        }
        
    }
    cout << ans << endl;
}

(II)dp

J 加法和乘法

n张牌,最后剩一张,则经过n-1轮。若n为奇数,则最后一轮是牛妹,因为无论何种情况的两张牌(奇奇、偶偶、奇偶),都可以变为偶数,所以牛妹一定赢。若n为偶数,则最后一轮是牛牛,此时如果至少有一个奇数,牛牛就能赢;若两张全为偶,牛牛就输。所以整个过程中,牛牛试图保留奇数,消灭偶数。而奇+偶=奇,奇*奇=奇只有这两种生成奇数的方式,牛牛一定选第一种,因为第一种不消耗奇数,还能消耗一个偶数。所以牛牛每次操作都是消耗一个偶数,奇数个数不变。牛妹试图消灭奇数,奇+奇=偶,所以牛妹每次操作都是消耗两个奇数,增加一个偶数。牛牛共有(n-1-1)/2+1=n/2次操作,牛妹共有n/2-1次操作,若牌数够,牛妹可以消耗n-2张奇数,而牛牛不产生奇数,所以若原有n-1张或n张奇数,牛妹消耗不掉,那么牛牛就赢。
注意:!!开始将n分奇偶前,要特判只有一张牌的情况。因为只有一张牌时,若为奇数,虽然此时牌数为奇数,但是牛牛赢

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 3;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
vector<char> v;
int a[maxn];
int main()
{
    int n, cnt = 0;
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        if(a[i] % 2 == 0) ++cnt;
    }
    if(n == 1){
        if(a[1] % 2)cout << "NiuNiu" << endl;
        else cout << "NiuMei" << endl;
        return 0;
    }
    if(n % 2 == 1) {cout << "NiuMei" << endl; return 0;}
    if(cnt <= 1) cout << "NiuNiu" << endl;
    else cout << "NiuMei" << endl;
}

官方题解

原文地址:https://www.cnblogs.com/Maxx-el/p/14380502.html