2020牛客寒假算法基础集训营1

Posted by

题目链接:https://ac.nowcoder.com/acm/contest/3002#question

深夜水一篇题解,今天(应该是昨天了)打了一场,575/2780,如果早点起床估计rank还会再高些…出题人应该是老ll粉了.

A

应该算是一道计算几何题,之前没有写过这种题型,是我最后ac的一道题目.大致上就是分类讨论,计算每一类三角形出现个数,大致分为3类:

  1. 底边为2高为1,在最外侧.
  2. 底边为2高为1,在中间,也就是除了最边上的那些列/行.
  3. 底为1高为2,注意区分与1,2类重复的那些三角形.

还有要注意的地方就是计算底的值对应的高的个数对应组数的时候,如果出现小于等于零的数据,就要置零了.

代码:

#include <bits/stdc++.h>
using namespace std;
const int MOD =  1e9 + 7;

long long int n, m;

int main()
{
    scanf("%lld %lld", &n, &m);
    long long int part = 0;
    long long int left = n - 2;
    if ( left > 0 )
    {
        part += (left * n * 2 ) % MOD;
        if ( m - 2 > 0 ) part += ( ( left * 2 * n  % MOD) * (m - 2) ) % MOD;
    }
    long long int up = m - 2;
    if ( up > 0 ) 
    {
        part += ( up * m * 2 ) % MOD;
        if ( n - 2 > 0 ) part += ( ( up * 2 * m  % MOD) * ( n - 2) ) % MOD;
    }
    if ( m - 1 > 0 && n - 2 > 0 && m - 2 > 0 ) part += ( ( m - 1 ) * ( n - 2 ) % MOD) * ( m - 2 ) * 2 % MOD;
    if ( n - 1 > 0 && m - 2 > 0 && n - 2 > 0 ) part += ( ( n - 1 ) * ( m - 2 ) % MOD) * ( n - 2 ) * 2 % MOD;
    printf("%lld\n",part % MOD);
    return 0;
}

B

很水的一道题…直接上代码

#include <bits/stdc++.h>

using namespace std;

int n, x, a,b;

int main()
{
    scanf("%d %d %d %d",&n, &x, &a, &b);
    int perfect = n * a;
    int great = n * b;
    double per1 = x, per2 = 100 - x;
    double ans;
    ans = per1 * 0.01 * perfect + per2 * 0.01 * great;
    printf("%.2lf", ans);

    return 0;
}

D

也是一道水题,数组记录一下然后找没出现的数据就好了.

代码:

#include <bits/stdc++.h>

using namespace std;

int n;
map< int, int > m;
int cnt[100010];

int main()
{
    scanf("%d",&n);
    int num, i;
    for (  i = 1; i <= n - 1; i ++ )
    {
        scanf("%d",&num);
        cnt[num] = 1;
    }
    for (  i = 1; i <= n; i ++ )
    {
        if ( cnt[i] == 0 )
        {
            printf("%d\n",i);
            break;
        }
    }

    return 0;
}

E

一道数论题,计算数据的因子个数,然后进行迭代,注意优化一下计算因子个数的算法,第一次直接暴力求素数超时了,以及数据较大要开long long.

计算因子个数的算法: https://scheng52123.com/index.php/2020/02/05/countfactors/

代码:

#include <bits/stdc++.h>

using namespace std;

long long int n;

long long int _num( long long int n)
{ 
    long long int count = 2;
    for(long long int i = 2; i <= sqrt(n); i++)
    {
        if( n % i == 0 )
        {
            if( i == sqrt(n) && n/i==i)
            { 
                count++;   
            }
            else count += 2;
        }
    }
    return count;
}

int main()
{
    scanf("%lld", &n);
    long long int cnt = 0;
    long long int num = _num(n);
    cnt ++;
    while ( num != 2 )
    {
        num = _num(num);
        cnt ++;
    }
    printf("%lld\n",cnt);
    return 0;
}

G

稍微卡了一下,用了双向队列和滑动窗口思想.(看了学长的代码后发现直接O(n^2)暴力也可以…,然后队列应用还有更加巧妙的方法,后续更新).

将数据放到一个滑动窗口里,用一个数组的双向队列记录每种字母的每一个出现的位置.当单个字母的数量达到k时,记录一下答案的值,然后对应字母的队列弹出最前元素,对应字母的记录值自减一次,相当于滑动窗口前端弹出一个值.时间复杂度为O(n).

代码:

#include <bits/stdc++.h>

using namespace std;

map< char, int > m;
int n, k;

string ss;

struct dequeue
{
    deque<int> q;

} que[30];

int main()
{
    scanf("%d %d",&n, &k);
    cin >> ss;
    int len, ans;
    ans = 200010;
    for ( int i = 0; i < n; i ++  )
    {
        m[ss[i]] ++;
        (que[ss[i]-97].q).push_back(i);
        if ( m[ss[i]] == k )
        {
            len = i - ( que[ss[i]-97].q ).front() + 1;
            ans = min( ans, len );
            m[ss[i]] --;
            ( que[ss[i]-97].q ).pop_front();
        }
    }
    if ( ans == 200010 ) printf("-1\n");
    else printf("%d\n",ans);
    return 0;
}

比赛之后重新写了一个,实际上是可以不用双向队列的,可能是太久没用过队列,导致一些操作忘记了,思路是一样的,代码精简了些.

#include <bits/stdc++.h>

using namespace std;

int n, k;
string ss;

queue<int> q[30];
int cnt[30];

int main()
{
    scanf("%d %d",&n, &k);
    cin >> ss;
    int len, ans;
    ans = 200010;
    for ( int i = 0; i < n; i ++  )
    {
        cnt[ss[i]-97] ++;
        q[ss[i]-97].push(i);
        if ( cnt[ss[i]-97] == k )
        {
            len = i - q[ss[i]-97].front() + 1;
            ans = min( ans, len );
            cnt[ss[i]-97] --;
            q[ss[i]-97].pop();
        }
    }
    if ( ans == 200010 ) printf("-1\n");
    else printf("%d\n",ans);
    return 0;
}

H

这题给我的感觉就像是codeforce上的那种思维题,也是类似G题用一个滑动窗口的思想.

记录当前窗口长度,0的个数和1的个数.当cnt0和cnt1只要有一个大于k了就说明窗口前端需要弹出一个元素了.整个过程中满足要求的窗口的最大长度就是答案.

代码:

#include <bits/stdc++.h>

using namespace std;

int n, k;
string ss;

int main()
{
    scanf("%d %d", &n, &k);
    cin >> ss;
    int left, right;
    int cnt0, cnt1, sum;
    left = right = 0;
    cnt0 = cnt1 = sum = 0;
    int ans = 1, len;
    while ( right <= n - 1 )
    {
        if ( ss[right] == '0' ) cnt0 ++;
        else cnt1 ++;
        sum ++;
        if ( cnt0 <= k || cnt1 <= k )
        {
            len = sum;
            ans = max(len, ans);
        }
        else
        {
            if ( ss[left] == '0' ) cnt0 --;
            else cnt1 --;
            left ++;
            sum --;
            len = sum;
            ans = max(len, ans);
        }
        right ++;
    }
    printf("%d\n", ans);
    return 0;
}

I

当时被题目全是niconi的题面整懵了,比赛的时候考虑过dp写法,但是因为太久没练dp导致我不敢写.看了题解之后发现是一个很裸的dp

代码:

#include <bits/stdc++.h>

using namespace std;

//string str.substr(nStart)                 
//默认 从str字符串nStart位置开始截取到str结束为止

//string str.substr(nStart, nLength)  
// 从str字符串nStart位置开始截取nLength个字符!
//如果nLength>剩余的字符则截取到str结束为止

long long int dp[330000];
long long int n, a, b, c;
string ss;

int main()
{
    scanf("%lld %lld %lld %lld", &n, &a, &b, &c);
    cin >> ss;
    //long long int ans = 0;
    for ( int i = 3; i < n; i ++ )
    {
        dp[i] = dp[i - 1];
        long long int temp;
        if ( ss.substr(i - 3, 4) == "nico" )
        {
            if ( i == 3 ) temp = dp[i - 3];
            else temp = dp[i - 4];
            dp[i] = max( dp[i], temp + a);
        }
        if ( i >= 5 && ss.substr( i - 5, 6 ) == "niconi"  )
        {
            if ( i == 5 ) temp = dp[i - 5];
            else temp = dp[i - 6];
            dp[i] = max( dp[i], temp + b );
        }
        if ( i >= 9 && ss.substr( i - 9, 10 ) == "niconiconi" )
        {
            if ( i == 9 ) temp = dp[i - 9];
            else temp = dp[i - 10];
            dp[i] = max( dp[i], temp + c );
        }
    }
    printf("%lld\n",dp[n - 1]);

    return 0;
}

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注