欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

2020ICPC·小米 网络选拔赛热身赛

程序员文章站 2022-03-06 20:22:30
A-ABBAB-Beauty Values题目链接.解题思路:按贡献度的思想。例如有数组a:下标 0 1 2 3数组 1 2 1 3a[0]在区间[0,1],[0,2],[0,3],[0,4]中,贡献度为4 * 1;同理a[1]的贡献度为3 * 2;由于a[2]和a[0]重复了,所以a[2]在[2,2],[2,3],[1,2],[1,3],贡献度为4;所以用a[2]的贡献度减去a[0]的贡献度,2 * 3 - 2 * 1;a[3]的贡献度为1 * 4;设一个数组vis...

A-ABBA

题目链接

解题思路:

运用dp的思想:
dp[i][j] 表示放i个A,j个B的方案数。
dp[i][j] 可以由 dp[i - 1][j] 和 dp[i][j - 1] 来表示
当i <= n时,A可以随意放,当j <= m时,B可以随意放。
当 i > n,如果放A,AB的数量要小于等于n,i - j 是至少有多少个AB ,i - j <=n;
当 j > m,如果放B,BA的数量要小于等于m,j - i 是至少有多少个BA ,j - i <=n;

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+100;
const int mod = 1e9+7;
int n,m;
int d[N][N];
int main(){
    while(cin >> n >> m){
        for(int i = 0;i <= n+m; i++)
            for(int j = 0;j <= n+m;j++)
                d[i][j] = 0;
        d[0][0]=1;
        for(int i = 0;i <= n+m; i++){
            for(int j = 0;j <= n+m; j++){
                if(i-j <= n && i > 0) d[i][j] = (d[i][j] + d[i-1][j]) % mod;
                if(j-i <= m && j > 0) d[i][j] = (d[i][j] + d[i][j-1]) % mod;
            }
        }
        cout << d[n+m][n+m] << "\n";
    }
    
    return 0;
}

B-Beauty Values

题目链接

解题思路:

按贡献度的思想。例如有数组a:
下标 0 1 2 3
数组 1 2 1 3
a[0]在区间[0,1],[0,2],[0,3],[0,4]中,贡献度为4 * 1;
同理a[1]的贡献度为3 * 2;
由于a[2]和a[0]重复了,所以a[2]在[2,2],[2,3],[1,2],[1,3],贡献度为4;
所以用a[2]的贡献度减去a[0]的贡献度,2 * 3 - 2 * 1;
a[3]的贡献度为1 * 4;
设一个数组vis用来记录前面数字的下标;
综上所述,贡献度的公式可以看为:
vis[a[i]] == -1 ? ans += (ll)(n - i) * (i + 1) : ans += (ll)(n - i) * (i - vis[a[i]]);

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
ll a[N];
int vis[N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    memset(vis, -1, sizeof(vis));
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (vis[a[i]] != -1) {
            ans += (ll)(n - i) * (i - vis[a[i]]);
        } else {
            ans += (ll)(n - i) * (i + 1);
        }
        vis[a[i]] = i;
    }
    printf("%lld\n", ans);
    return 0;
}

F-Fraction Comparision

题目链接

解题思路:

由于数据量非常大,先比较分数的整数部分,然后剩下的分数进行通分比较。

#include<bits/stdc++.h>

using namespace std;

int main()
{
    long long int x,a,y,b,flag1,flag2;
    while(scanf("%lld%lld%lld%lld",&x,&a,&y,&b)!=EOF)
    {
        if (x/a<y/b)
            printf("<\n");
        else if (x/a==y/b)
        {
            flag1=x%a;
            flag2=y%b;
            flag1=flag1*b;
            flag2=flag2*a;
            if(flag1<flag2)
                printf("<\n");
            else if(flag1==flag2)
                printf("=\n");
            else
                printf(">\n");
        }
        else
            printf(">\n");
    }
    return 0;
}

G-Gemstones

方法一:用栈进行模拟,跑一边for循环即可;
方法二:string的erase库函数,暴力找;

#include <bits/stdc++.h>

using namespace std;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    string a;
    cin>>a;
    int i,sum=0,flag;
    while(1)
    {
        flag=0;
        for(i=0; i<a.length()-2; i++)
            if(a[i]==a[i+1]&&a[i+1]==a[i+2])
            {
                sum++;
                a.erase(i,3);
                flag=1;
                break;
            }
        if(flag==0)
            break;
    }
    printf("%d\n",sum);
    return 0;
}

本文地址:https://blog.csdn.net/qq_47783181/article/details/109264551