2020牛客多校第九场AFI题解

A. Groundhog and 2-Power Representation

题意

求二进制表达式的值，形如2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

解题

对于python，只需要一行

print(eval(input().replace("(","**(")))

或者也可以像队友一样正常写，就是速度有点慢。

st = [0]*20005
cnt = 0
mat = [0]*20005
def solve(l,r): # 计算[l, r]的表达式的值
    i = l
    ans=0
    while(i<=r):
        if(S[i]=='2'):
            if(mat[i+1]!=0):
                ans+=solve(i+2,mat[i+1]-1)
                i = mat[i+1]+1
            else:
                ans+=2
                i+=1
        else:
            i+=1

    return 2**ans


S = input()
n = len(S)
for i in range(len(S)): # st左括号的位置，mat对应的右括号的位置
    if(S[i]=='('):
        st[cnt+1] = i
        cnt+=1
    if(S[i]==')'):
        p = st[cnt]
        mat[p] = i 
        cnt-=1
A = 0
i = 0
while(i<=n-1): # 遍历整个式子开始计算
    if(S[i]=='2'):
        if(mat[i+1]!=0):
            A+=solve(i+2,int(mat[i+1])-1)
            i=mat[i+1]+1
        else:
            A+=2
            i+=1
    else:
        i+=1

print(A)

F. Groundhog Looking Dowdy

题意

n天，每天可以从ki件衣服里选一件衣服穿，并得到收益，一共进行m天，求最小的最大收益和最小收益差值。

解题

按照收益值排序后，用滑动窗口维护一下最小值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=2e6+6;

int n, m, t, len, cnt, ans=0x3f3f3f3f;

struct node {
    int d, v;
}a[maxn]; 
int vis[maxn];

int cmp(node aa, node bb) {
    return aa.v<bb.v;
}

int main() {
    scanf("%d%d",&n,&m);
    cnt=1;
    for(int i=1;i<=n;i++) {
        scanf("%d",&t);
        for(int j=1;j<=t;j++) {
            scanf("%d",&a[cnt].v);
            a[cnt++].d = i;
        }
    }
    sort(a+1,a+cnt,cmp);

    int i=0;
    while(len<m) {
        i++;
        if(!vis[a[i].d]) {
            vis[a[i].d]++;
            len++;
        }
    }

    cnt--;
    int l=1;
    while(i<=cnt) {
        ans = min(ans, a[i].v-a[l].v);
        len--; vis[a[l].d]--; l++;
        if(!vis[a[l].d]) vis[a[l].d]++,len++;
        while(len<m && i<=cnt) {
            i++;
            if(!vis[a[i].d]) vis[a[i].d]++,len++;
        }
    }
    printf("%d\n",ans);
}

I. The Crime-solving Plan of Groundhog

题意

给定n个数要求组成乘积最小的两个不含前导零的数字。

解题

排序后第一个不为0的数位单独提取出来作为第一个数，第二个数则是剩下数位组成的最小的数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int t,n,pos,x,te,flag;
vector<int> a;

int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        a.clear();
        pos=flag=0;
        for(int i=1;i<=n;i++) scanf("%d",&x),a.push_back(x);
        sort(a.begin(),a.end());
        for(pos=0;pos<n;pos++) {
            if(a[pos]) {flag=(pos!=0);break;}
        }
//        for(int i=0;i<a.size();i++) printf("%d ",a[i]);printf("\n");
        if(flag)swap(a[0],a[pos+1]);
//        for(int i=0;i<a.size();i++) printf("%d ",a[i]);printf("\n");
        te=a[pos];
        a.erase(a.begin()+pos);
//        for(int i=0;i<a.size();i++) printf("%d ",a[i]);printf("\n");
        for(int i=0;i<a.size();i++) {
            a[i]*=te;
        }
        for(int i=a.size();i>0;i--) {
            if(a[i]>=10&&i!=0) a[i-1]+=a[i]/10,a[i]%=10;
        }
        for(int i=0;i<a.size();i++) {
            printf("%d",a[i]);
        }
        printf("\n");

    }
}