Press "Enter" to skip to content

杭电2020暑期多校第五场

发表于 2020年8月9日 作者 EricXia

A.Groundhog and 2-Power Representation

题意

解题思路

我估计正常的解题思路应该是双栈，但是赛后被同学提醒，Python可以一行搞定（?

参考代码

先上一下Java

import java.math.BigInteger;
import java.util.Scanner;
import java.util.Stack;
 
public class Main {
 
    public static void main(String[] args) {
        Stack<BigInteger> s=new Stack<>();
        Stack<Character> index=new Stack<>();
        Scanner scanner=new Scanner(System.in);
        String buf=scanner.nextLine();
        for (int i = 0; i < buf.length(); i++) {
            if(buf.charAt(i)=='0')
            {
                s.push(BigInteger.ZERO);
            }else if (buf.charAt(i)==')')
            {
                Character op=index.pop();
                BigInteger a=s.pop();
                BigInteger b=s.pop();
                while (op=='+')
                {
                    a=a.add(b);
                    b=s.pop();
                    op=index.pop();
                }
                b=b.pow(a.intValue());
                s.push(b);
            }else if (buf.charAt(i)=='(')
            {
                index.push('^');
            }else if (buf.charAt(i)=='+')
            {
                index.push('+');
            }else{
                s.push(BigInteger.valueOf(2));
            }
        }
        while (s.size()>1)
        {
            BigInteger a=s.pop();
            BigInteger b=s.pop();
            s.push(a.add(b));
        }
        System.out.println(s.peek());
    }
}

一行的Python

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

I.The Crime-solving Plan of Groundhog

题意

给你n个数字，你需要将其分成两个不前导零的数字，将其相乘，求积的最小值是多少。

解题思路

选择一个非零的数字乘以一个一个剩下的以非零开端的字典序最小的数就好了

参考代码

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
typedef long long ll;
using namespace std;
const int MAXN=(int)1e5+5;
int a[MAXN];
int main()
{
    int T,n;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        rep(i,0,n)scanf("%d",&a[i]);
        sort(a,a+n);
        if(a[0]==0)
        {
            int t=0;
            while(t<n&&!a[t])t++;
            swap(a[0],a[t]);
            if(t!=1)swap(a[1],a[t+1]);
            else swap(a[1],a[2]);
        }
        int x=0;
        per(i,1,n)
        {
            a[i]=x+a[i]*a[0];
            x=a[i]/10;
            a[i]%=10;
        }
        if(x)printf("%d",x);
        rep(i,1,n)printf("%d",a[i]);
        puts("");
    }
    return 0;
}

F.Groundhog Looking Dowdy

题意

在n天中选择m天，第i天有$k_i$件衣服，每件衣服有一个权值，每天只能穿一件衣服，求权值最大最小相差的最小值是多少。

解题思路

我的思路和标称差不多，只不过标称枚举的是左端点，而我枚举的是右端点

枚举右端点，移动左端点，使得区间中的不同的元素个数恰好为$m$，且长度最短。

加入右端点后只需要判断左端点是否与右端点相同或者区间中的不同元素的数量大于$m$，这时候就要移动左端点。

时间复杂度$O(\sum k_i\log \sum k_i)$

时间复杂度是排序的，枚举求值只需要$O(\sum k_i)$，这题时间卡的比较紧，所以如果枚举求值的时间复杂度为$O(\sum k_i \log \sum k_i)$极有可能会被T。

相传可以使用基数排序把整体时间复杂度降到$O(\sum k_i)$但是我信邪后尝试了一波发现跑的更慢了。

后面发现是自己基数选的不对，基数排序的时间复杂度为

$T(n, m, p) = \lceil\log_pm\rceil * (n + p)$

当我基数取1024是大概达到最小值（实际上是1000，但是1024比较好听而且还可以加速运算的功效，逃
然后时间复杂度就降到$O(\sum k_i)$了（时间421ms，套上速读的板子后就降为148ms，看来还是读写最耗时?

还有这题数据特别水，我看有些人只要每组要取都会取最小的就可以了。

参考代码

560ms

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
typedef long long ll;
using namespace std;
const int MAXN=(int)2e6+5;
pair<int,int>a[MAXN];
int mp[MAXN];
int main()
{
    int n,m,k,b;
    scanf("%d%d",&n,&m);
    int cur=0;
    rep(i,0,n)
    {
        scanf("%d",&k);
        rep(j,0,k){scanf("%d",&b);a[cur++]=make_pair(b,i);}
    }
    sort(a,a+cur);
    int r = 0,l=0, t=0;
    for ( r = 0; r < cur&&t<m; r++)
    {
        if(!mp[a[r].second])t++;
        mp[a[r].second]++;
    }
    int ans=a[r-1].first-a[l].first;
    for (; r < cur; r++)
    {
        if(!mp[a[r].second])t++;
        mp[a[r].second]++;
        while(a[r].second==a[l].second||t!=m)
        {
            if(mp[a[l].second]==1)t--;
            mp[a[l].second]--;
            l++;
        }
        ans=min(ans,a[r].first-a[l].first);
    }
    printf("%d\n",ans);
    return 0;
}

421ms

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
typedef long long ll;
using namespace std;
const int MAXN=(int)2e6+5;
pair<int,int>a[MAXN];
pair<int,int> tmp[MAXN];
int mp[MAXN];
inline int maxbit(int n)
{
    int d = 1;
    int p = 1024;
    for(int i = 0; i < n; ++i)
    {
        while(a[i].first >= p)
        {
            p *= 1024;
            ++d;
        }
    }
    return d;
}
void radixsort(int n)
{
    int d = maxbit(n);
    int count[1024] = {0};
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++)
    {
        memset(count,0,sizeof(count));
        for(j = 0; j < n; j++)
        {
            k = (a[j].first / radix) % 1024;
            count[k]++;
        }
        for(j = 1; j < 1024; j++)count[j] = count[j - 1] + count[j];
        for(j = n - 1; j >= 0; j--)
        {
            k = (a[j].first / radix) % 1024;
            tmp[count[k] - 1] = a[j];
            count[k]--;
        }
        memcpy(a,tmp,sizeof(pair<int,int>)*n);
        radix = radix * 1024;
    }
}
int main()
{
    int n,m,k,b;
    scanf("%d%d",&n,&m);
    int cur=0;
    rep(i,0,n)
    {
        scanf("%d",&k);
        rep(j,0,k){scanf("%d",&b);a[cur++]=make_pair(b,i);}
    }
    radixsort(cur);
    int r = 0,l=0, t=0;
    for ( r = 0; r < cur&&t<m; r++)
    {
        if(!mp[a[r].second])t++;
        mp[a[r].second]++;
    }
    int ans=a[r-1].first-a[l].first;
    for (; r < cur; r++)
    {
        if(!mp[a[r].second])t++;
        mp[a[r].second]++;
        while(a[r].second==a[l].second||t!=m)
        {
            if(mp[a[l].second]==1)t--;
            mp[a[l].second]--;
            l++;
        }
        ans=min(ans,a[r].first-a[l].first);
    }
    printf("%d\n",ans);
    return 0;
}

J.The Escape Plan of Groundhog

题意

统计四周为1内部0和1数量相差小于1的子矩阵的数量

解题思路

枚举列的范围，然后枚举行，统计与之前符合条件的行的前缀和相差小于1的数量。

本来统计相差1的数量我用的是unordered_map但是常数太大被T了一发。

然后考虑使用桶，但是桶的大小为$500\times 500\times 2=5\times 10^5$每次清空会使得时间复杂度爆掉

虽然清空耗时，但是最多只有500个不同的数值，所以我们可以开一个数组来记录之前都存了什么数字，然后要清空的时候就把这些值对应桶的位置清空就好，因为每个值最多访问两次所以时间复杂度是比较小的。

参考代码

84ms

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
typedef long long ll;
using namespace std;
const int MAXN=500+5;
int mp[550][550];
int s[550][550];
int k[MAXN*MAXN*2];
int v[MAXN];
int offset=MAXN*MAXN;

void clear(int tot)
{
    rep(i,0,tot)k[v[i]]--;
}
int main()
{
    int n,m,tot=0;
    ll ans=0;
    scanf("%d%d",&n,&m);
    rep(i,1,n+1)rep(j,1,m+1){scanf("%d",&mp[i][j]);if(!mp[i][j])mp[i][j]=-1;}
    rep(i,1,n+1)rep(j,1,m+1)s[i][j]+=(s[i][j-1]+mp[i][j]);
    for (int l = 1; l <=m-1 ; l++)
    {
        for (int r = l+1; r <=m; r++)
        {
            int sum=0;
            for (int i = 1; i <= n; i++)
            {
                if(mp[i][l]==-1||mp[i][r]==-1)
                {
                    sum=0;
                    clear(tot);
                    tot=0;
                    continue;
                }
                if(s[i][r]-s[i][l-1]==r-l+1)
                {
                    ans+=k[sum-(r-l-1)+offset]+k[sum-(r-l-1)-1+offset]+k[sum-(r-l-1)+1+offset];
                    k[sum+offset]++;
                    v[tot++]=sum+offset;
                }
                sum+=s[i][r]-s[i][l-1]-2;
            }
            clear(tot);
            tot=0;
        }
        
    }
    printf("%lld",ans);
    return 0;
}

发表于 2020杭电暑期多校

Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments
0
喜欢聆听每一种不同的观点，欢迎评论。x
()
x