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

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;
}