HG 模拟题 2018.11.1

2018-11-01 19:07:16


T1

题目大意

给出一个长度为n的序列,求两两相加所得的所有数的位数和。(比如:1 2 3,两两相加得到3 4 5,位数都为1,那么位数和为3)

输入样例

9

1 2 3 4 5 6 7 8 9

输出样例

56

数据范围

对于30%的测试数据,n≤1000。

对于另外30%的测试数据,存在x使得所有ai,满足$10^x≤ai≤5*10^x-1$

对于100%的测试数据,$2≤n≤1000000,1≤ai≤10^8$。

解法

很简单,排一遍序,然后对于一个数$a_i$,我们可以找到一个分解点k,$a_i+a_{1..k-1}$都不发生进位,k到i都发生进位,用lower_bound处理即可。一定要开longlong orz

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
inline int read()
{
    int x=0,w=0; char c=0;
    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return w?-x:x;
}
int n;
long long ans=0;
int a[1000100],b[10];
int get(int x)
{
    int cnt=0;
    while(x>0) {x/=10;cnt++;}
    return cnt;
}
int main()
{
    n=read();b[0]=1;
    for(int i=1;i<=9;i++)
        b[i]=b[i-1]*10;
    for(int i=1;i<=n;i++)
        a[i]=read();
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        int p=get(a[i]);
        int tmp=b[p]-a[i];
        int res=lower_bound(a+1,a+i,tmp)-a;
        ans+=(i-1)*p+(i-res);
    }
    printf("%lld",ans);
    return 0;
}

T2

那个。。无法总结题意。。。不知道怎么说好。。直接贴了吧

题目大意

小Z住的房子一共有n个人,他们每人有一个重要度。 房子的门上可以装若干把锁。 假设共有k把锁,命名为1到k。每把锁有一种对应的钥匙,也用1到k表示。 钥匙可以复制若干份并发给任意多个居民。每个人都可以持有若干钥匙,可以不持有钥匙。 如果几名居民钥匙的并集是全集,他们都在场时就能打开房门。 房东规定,一组居民都在场时能打开房门当且仅当他们的重要度加起来至少为m。 问至少需要给房间装多少把锁。即,求最小的k,使得可以适当地给居民们每人若干钥匙,使得任意一组重要度之和小于m的居民持有的钥匙不能打开所有房门,使得任意一组重要度之和大于等于m的居民持有的钥匙能打开所有房门。

输入数据

第一行两个整数n和m。 第二行n个整数表示居民们的重要度ai。

输出数据

一个整数表示最少需要多少把锁,即最小的k。

样例输入

4 3 1 1 1 1

样例输出

6

数据范围

对于前30%的测试数据,满足所有ai=1。 对于另外30%的测试数据,1≤n≤8。 对于100%的测试数据,1≤n≤20,1≤m≤109,任意居民重要度≤m。

解法

这道题我是真的不知道怎么讲好orz

答案是这样的居民子集个数x:重要度的和不足m,但加入任何一个新居民都将导致重要度的和大于等于m。 必要性:由于上面的集合重要度都不够,他们都至少缺一把锁。若不足x把锁,这些子集中必有两个x,y缺同一把锁l。把这两个子集x和y并起来,仍然缺l这把锁,无法开门,但现在子集的重要度已经达到n了,与题目要求矛盾。 充分性:一共x把锁,每把锁上面各写一个这种居民的子集(互不相同)。一个居民持有所有上面的子集不包括自己的锁的钥匙,这样满足要求。 注意到如果所有人加起来重要度都不够,则需要一把锁,无人有钥匙。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int n,m,res=1;
int a[30],ans=0;
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=0;i<(1<<n);i++)
    {
        int sum=0,tmp=0x7ffffff;
        for(int j=1;j<=n;j++)
        {
            if((i&(1<<(j-1)))!=0) sum+=a[j];
            else tmp=min(tmp,a[j]);
        }
        if(sum<m && sum+tmp>=m) ans++;
    }
    printf("%lld",max(ans,(int)1));
    return 0;
}

T3

题目大意

给出T组数据,每组数据一个n。1≤a,b≤n,求所有长为a,宽为b的长方形拼成正方形所需的最小块数的成绩。

输入数据

第一行一个整数t。 接下来t行每行一个整数n。

输出数据

t行,每行一个整数表示答案。

样例输入

3 1 2 3

样例输出

1 4 1296

解法

首先我们可以轻易的推出$f[n]=\sum_{i=1}^n{\sum_{j=1}^n{i*j/gcd(i,j)^2}}$

原题不如概括后简洁和清晰,但概括和抽象也是图论和数论所要强调的能力。这次考试犯了数论题的大忌:死盯着题目想结论,而不是概括出式子进行观察和思考

明显的离线算法,所以问题在于预处理的复杂度上,只能比线性多一点。 将式子展开可以得到$\frac{n!^{2n}}{\Pi^n_{i=1}\Pi^n_{j=1}gcd(i,j)}$ 对于分子可以O(n)预处理,关键在于gcd(i,j)的计算。首先考虑的是利用已有结果推得未知结果。

如果我已经知道了f(n-1)。$f(n)=f(n-1)+\frac{n!*n^n}{\Pi^n_{i=1}gcd(i,n)}$显然gcd(i,n)一定是n的约数,考虑到n的约数个数是log级的,所以我们枚举gcd的大小。当gcd大小为x时,显然有$gcd(\frac{i}{x},\frac{n}{x})==1$,所以gcd为x对答案贡献就是x乘上与$\frac{n}{x}$互质的数的个数。用公式书写就是$x*\varphi(\frac{n}{x})$。考虑到$\varphi(\frac{n}{x})$可以O(n)预处理,所以复杂度就是O(nlogn)。

还是过不了,怎么办?我们单独考虑每个素数对答案的贡献,对于一个素数x,它在k*x处会对答案有$x^{2k-1}$的贡献,求一遍前缀积即为答案。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma GCC optimize (2)
#define int long long
using namespace std;
const int mod=19260817;
inline int read()
{
    int x=0,w=0; char c=0;
    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return w?-x:x;
}
int n,t,cnt=0,ma=0;
int p[10000100],sum[10000100];
int a[1000100],f[10000100],mul[10000100];
int pow(int x,int k)
{
    if(k==0) return 1;
    int res=1,tmp=pow(x,k/2);
    if(k%2==1) res=x;
    res=(res*tmp%mod)*tmp%mod;
    return res;
}
void init()
{
    for(int i=0;i<=1e7;i++)
        sum[i]=1;
    for(int i=2;i<=1e7;i++)
    {
        if(!f[i])
        {
            for(int j=2;i*j<=1e7;j++)
                f[i*j]=1;
            int tmp=i;
            while(tmp<=1e7)
            {
                int p=i;
                for(int k=1;tmp*k<=1e7;k++)
                {
                    sum[tmp*k]=sum[tmp*k]*p%mod;
                    p=(p*i%mod)*i%mod;
                }
                tmp*=i;
            }
        }
    }
    for(int i=1;i<=1e7;i++)
        sum[i]=(sum[i-1]*sum[i])%mod*sum[i]%mod;
    mul[1]=1;
    for(int i=2;i<=1e7;i++)
        mul[i]=mul[i-1]*i%mod;
}
signed main()
{
    init();
    t=read();
    while(t--)
    {
        n=read();
        printf("%lld\n",pow(mul[n],2*n)*pow(sum[n],mod-2)%mod);
    }
    return 0;
}