牛客NOIP暑期七天营-提高组2 Solution

T1 ACGT

大水题啊
在线处理,map一下当前扫到的单词序列,再把当前扫到的序列转ACGT一下,再看看有没有匹配的
看代码挺好理解的

#include <algorithm>
#include <map>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
 
std::map <std::string, int> mp;
 
int n, ans;
std::string str, acgt;
 
int main() {
    scanf ("%d", &n);
    for (int i = 1; i <= n; ++i) {
        std::cin >> str;
        ++mp[str];
        acgt.clear();
        for (int j = 0; j < str.size(); ++j)
            if (str[j] == 'A') acgt.push_back('T');
            else if (str[j] == 'T') acgt.push_back('A');
            else if (str[j] == 'C') acgt.push_back('G');
            else acgt.push_back('C');
        if (mp[acgt] > 0) {--mp[acgt]; --mp[str]; ++ans; }
    } printf ("%d\n", ans);
    return 0;
}

T2

解法一

其实也是比较容易的一道题。

很多做法都可以过,贪心,数位dp。这里介绍二分答案。

首先,用dfs遍历出2至18位的所有47数。由于这个数的神奇特性,dfs的复杂度其实相当低,小于2^18。

然后看题,提取题意“满足条件最小数”,很自然二分答案。而且是最low的那种二分答案。

注意如果所求数大于18位,直接输出"44444444447777777777"。

关于lower_bound和upper_bound--marTxx

其实我觉得直接用这个stl好一点,没有Illusions的码力,就只能打打stl了
这个函数返回的是一个指针,所以有两种写法

  • 不用指针
int p = upper_bound(a + 1, a + n + 1, x) - a;
  • 指针
int *p = upper_bound(a + 1, a + n + 1, x);

#include <bits/stdc++.h>
using namespace std;
int n;
long long l,r;
long long a[4194304];
int tot=0;
void dfs(long long x,int n7,int n4,int sum){
    if (n7>sum/2 || n4>sum/2) return ;
    if (n7==n4 && n7==sum/2) {
        a[++tot]=x;
        return ;
    }
    for (int i=1;i<=2;i++){
        if (i==1) dfs(x*10+4,n7,n4+1,sum);
        else dfs(x*10+7,n7+1,n4,sum);
    }
}
void work(long long x){
    int l=1;int r=tot,mid=10;
    while (l<r) {
        if (mid-l<=1 && r-mid<=1){
            if (a[l]>=x) cout<<a[l]<<endl;
            else if (a[mid]>=x) cout<<a[mid]<<endl;
            else cout<<a[r]<<endl;
            return;
        }
        mid=(l+r)/2;
        if (a[mid]<=x) l=mid;
        else r=mid;
    }
    cout<<a[mid]<<endl;
}
int main(){
    cin>>n;
    for (int i=2;i<=18;i+=2){
        dfs(0,0,0,i);
    }
    for (int i=1;i<=n;i++){
        long long k;
        cin>>k;
        if (k>a[tot]){
            cout<<"44444444447777777777"<<endl;
            continue;
        }
        work(k);
    }
    return 0;
}

解法二

贪心大法吼!!
有19位,可以long long
但是对于贪心一位一位地来,还是用char[]好一点
对于奇数位的数,我们直接输出数位+1的44..44477...77(保证最小)
A[]为原数组我们新建一个Ans数组来表示填的4和7的序列

  • 对于当前位A[i], 如果我们在这里填一个4

那么一定A[i] < 4A[i] == 4
A[i] < 4时,当前位大于了原数组,那么无论后面填的是啥,当前序列一定大于原数组,所以我们进行Cover操作,然后return(即尽可能地把4在高位填完,再填7,这样保证最小)
A[i] == 4时,当前位等于原数组,没有办法分出大小,所以我们继续看下一位,如果return回来了这里填4无解,那么我们就在这里填7

  • 对于当前位填7

(忽略前面4讲过的情况),那么一定有4 <A[i] < 7A[i] == 7
4<A[i]<7,同4的情况,直接Cover
A[i] == 7,直接看下一位

  • 现在还剩下一种扫到当前位,A[i] > 7的情况

这种情况直接return,并输出一下当前位数+2的444...444777...777(当前数位的数已经没有办法比原数组大了)
代码:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
 
int T, L, Flag, Four, Seven;
char A[20], Ans[20];
 
 
inline void NotFound() {
    for (int j = 1; j <= L / 2 + 1; ++j) printf ("4");
    for (int j = 1; j <= L / 2 + 1; ++j) printf ("7");
    printf ("\n");
}
 
inline void Print() {
    Flag = 1;
    for (int j = 0; j < L; ++j) printf ("%c", Ans[j]);
    printf ("\n");
}
 
inline void Cover(int now) {
    for (int i = now + 1; i < L; ++i)
        if (Four > 0) {--Four; Ans[i] = '4'; }
        else if (Seven > 0){--Seven; Ans[i] = '7'; }
    Print();
}
 
inline void _minnum(int Now) {
    if (Now == L) Print();
    if (A[Now] < '4') {
        if (Four > 0) {
            --Four; Ans[Now] = '4';
            Cover(Now);
            return ;
        }if (Seven > 0) {
            --Seven; Ans[Now] = '7';
            Cover(Now);
            return ;
        }
    }else if (A[Now] == '4') {
        if (Four > 0) {
            --Four; Ans[Now] = '4';
            _minnum(Now + 1);
            ++Four; if (Flag == 1) return ;
        }if (Seven > 0) {
            --Seven; Ans[Now] = '7';
            Cover(Now);
            return ;
        }
    }else if (A[Now] < '7') {
        if (Seven > 0) {
            --Seven; Ans[Now] = '7';
            Cover(Now);
            return ;
        }
    }else if (A[Now] == '7') {
        if (Seven > 0) {
            --Seven; Ans[Now] = '7';
            _minnum(Now + 1);
            ++Seven; if (Flag == 1) return ;
        }
    }
}
 
int main() {
    scanf ("%d", &T);
    for (int i = 1; i <= T; ++i) {
        scanf ("%s", A);
        Flag = 0; L = strlen(A);
        Four = L / 2; Seven = L / 2;
        if (L % 2 == 1) {NotFound(); continue; }
        _minnum(0);
        if (Flag == 0) NotFound();
    }
    return 0;
}
Last modification:August 21st, 2019 at 02:03 pm

One comment

  1. Illusions

    能这么打贪心的人还说我码力打,fake→_→

Leave a Comment