HG 模拟题 2018.11.1
hicc0305
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;
}
```