【清北学堂国庆刷题班】 Day3

T1 欢乐

【问题描述】

你是能看到第一题的friends呢。

——hja

众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。

给定N，求一个K，使得K!≥N!K!K!\ge \frac {N!} {K!}并且K尽量小。

【输入格式】

一行一个整数N。

【输出格式】

一行一个整数代表答案。

【样例输入】

10

【样例输出】

7

【数据规模与约定】

对于30%的数据，N≤10N\le 10

对于60%的数据，N≤100N\le 100

对于80%的数据，N≤1000N\le 1000

对于100%的数据，3≤N≤1063\le N \le 10^6

思路

取对数

看到这道题目，我第一感觉是来模拟！PS:模拟多爽啊。

结果发现，这大于多少以上的写不出来了，程序立刻就炸了，时间分分钟超过了，整个人都崩了！

所以就有了三十分的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath> 
using namespace std;
long long n;
unsigned long long a[100];
int main()
{
	cin>>n;
	if(n==20)
	{
		cout<<13<<endl;
		return 0;
	}
	if(n>=21&&n<=22)
	{
		cout<<14<<endl;
		return 0;
	}
	if(n>=23&&n<=24)
	{
		cout<<15<<endl;
		return 0;
	}
	if(n>=25)
	{
		cout<<13+ceil((n-19)/2)<<endl;
		return 0;
	}
	a[1]=1;
	for(int i=2;i<=n;i++)
	a[i]=a[i-1]*i;
	for(int i=1;i<=n;i++)
	if(a[i]*a[i]>=a[n])
	{
		cout<<i<<endl;
		return 0;
	}
	return 0;
}

这是一份非常模拟的代码，而且有一些是自己找的规律，我就想当然地写了上去，但是很不幸，还是只有这么一点分。我便陷入了沉思。

等到老师讲的时候，才发现。世界如此简单。

取一个对数不就可以了吗？为什么可以取对数呢？

（郑重其事的说）原因有三，首先这个阶乘有一个神奇的特点，就是越到后面，位数就越是不一样，这样我们就可以取一个对数，直接计算它的位数，然后对于这个位数直接进行计算，我们就可以取得正确答案了。其次，我们对于乘法，如果大于十位的话，实际上两个数相乘，总的位数**大概？**就是两个数的位数之和－１，所以我们就可以算对数来解决。最后一点原因就是，就是，我也不知道，应该也就两点原因吧。

然后这个除法怎么办了，难不成换成乘法吗，而且我们取得是10的对数，所以我们可以使用高中一年级就学过的对数换底公式：
∀a,c∈(0,1)∪(1,+∞),有log⁡ab=log⁡cblog⁡ca \forall a,c \in (0,1) \cup (1,+\infty),有 \log_a b=\frac {\log_c b}{\log_c a}
这样就可以把乘除法转化为加减法了，这样世界就非常简单了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
long double a[1000005];//保留一下精度，否则会出问题
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	a[i]=a[i-1]+log10(i);//递推每个数的阶乘的对数
	for(int i=1;i<=n;i++)
	{
		if(a[i]>=a[n]-a[i])//运用了对数换底公式
		{
			cout<<i<<endl;
			return 0;
		}
	}
}

T2 水题

【问题描述】

你是能看到第二题的friends呢。

——aoao

众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。

现在有若干个任务，每个任务需要一定的执行时间，以及要求其依赖的所有任务执行完成后才能够执行。你可以同时做多个任务，但是一个任务一旦开始就不能停下必须做完。如果当前有多个任务可以做，按照这些任务到来的时间作为第一关键字，任务的名字作为第二关键字选择最小的任务执行。问执行完所有任务所需要的时间是多少。

【输入格式】

一行一个字符串。

对于每个任务，其格式为“任务名字:[依赖任务1,依赖任务2,……,依赖任务k]:执行时间”。不同任务与不同任务之间用分号分割。在输入完所有任务之后，会用“/”隔开一个整数，该整数代表同一时间最多执行多少个任务。

【输出格式】

一行一个整数代表答案。

【样例输入】

b:[a]:2;c:[a]:3;a:[]:1/2

【样例输出】

4

【数据规模与约定】

对于30%的数据，任务数量≤10\le 10。

对于60%的数据，任务数量≤100\le 100。

对于100%的数据，任务数量≤1000\le 1000，任务的名字长度小于等于50，所需要的执行时间不超过100，总依赖数量不超过200000。

思路

模拟题， 先鸽一下，如果在2020.11.4之前还没有看见这个更改的话，请从我的QQ2844938982告诉我，谢谢大家了

代码(std)

1

T3 模拟

【问题描述】

你是能看到第三题的friends呢。

——laekov

众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。

给定N个长度不超过50的01字符串，你可以将其不断重复直到长度为50!。现在要求输出从1∼50!中有多少个位置，在这个位置上所有字符串1的个数加起来等于i。

【输入格式】

第一行一个整数N代表字符串个数。

接下来N行每行一个字符串。

【输出格式】

输出N+1行，其中第i行代表1的个数为i−1的位置的个数对109+710^9+7取模之后的结果。

【样例输入】

1

1

【样例输出】

0

318608048

【数据规模与约定】

对于20%的数据，N=1N=1。

对于40%的数据，$N\le 10 $。

对于另外20%的数据，所有字符串长度均为质数。

对于另外20%的数据，所有字符串长度小于等于10。

对于100%的数据，1≤N≤1001\le N \le 100，我觉得原来的第三题太简单了，所以临时换了这个题。

思路

这道题是一道典型的分类讨论， 我们可以在考试中根据不同的数据点来给答案，也不失是一种好办法

  • N=1N=1

    这样只有一个字符串，因此也就是说我们要统计0或1的个数，所以最终的答案就是第一个字符串的0的个数a，1的个数b，以及字符串的总长度x，是0的个数则为a∗50!xa*\frac {50!} {x},同理，是1的个数则为b∗50!xb*\frac {50!} {x},这样就可以得到20%的分数了

  • 字符串的长度小于等于10

    这种情况还是可以按照N=1N=1的思路来写的，因为我们可以求字符串长度的最小公倍数，然后各自拓展到这个最小公倍数长度的字符串，进行统计，接下来的就是和$N=1 $同理了

  • 字符串长度互质

    我们可以讨论得到，当两个字符串长度互质的时候，我们不关心这个字符串长什么样子，因为每一位一定对应每一位，而且我们只需要知道每个字符串有几个0和几个1，然后用类似于多项式乘法即可

  • 其他

    如果是其他情况的话，我们可以进行把不是互质的转化为互质的，如

    第一个字符串长为4为1001，第二个字符串长为6为010011。那我们就可以找到他们的最大公约数2，把这个分成长度为2的组合，如

    10 01 10 01 10 01

    01 00 11 01 00 11

    这样分完组之后我们可以发现对于一个长度的字符串

    10 01

    01 00 11

    可以将他们的首位取出，构成两个新的字符串

    10

    001

    对这个进行统计，再将他们的下一位取出，再构成两个新的字符串，顺理成章，我们就可以做出来其他的情况了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define inc(a,b) {a+=b;if (a>=mo) a-=mo;}
const int maxn=1010;
const int mo=1000000007;
const int maxb=32*27*25*49;
const int prime[]={0,11,13,17,19,23,29,31,37,41,43,47,0};//提前定义质数
int n,num[maxb+10],res[maxn][12],resx[maxn][12],ans[maxn],l[maxn];
char s[maxn][maxn];
int main()
{
	scanf("%d",&n);
	for (int a=1;a<=n;a++)
	{
		scanf("%s",s[a]+1);
		l[a]=strlen(s[a]+1);//读取每一个字符串的长度
	}
	for (int a=1;a<=n;a++)
		if (maxb%l[a]==0)
			for (int b=1,c=1;b<=maxb;b++,c++)
			{
				if (c>l[a]) c=1;
				if (s[a][c]=='1') num[b]++;
			}
	for (int a=1;a<=maxb;a++)
		inc(res[num[a]][a%12],1);
	for (int a=1;prime[a];a++)
	{
		int v=prime[a];
		memset(num,0,sizeof(num));
		for (int b=1;b<=n;b++)
			if (l[b]%v==0)
			{
				for (int c=1,d=1;c<=v*12;c++,d++)
				{
					if (d==l[b]+1) d=1;
					if (s[b][d]=='1') num[c]++; 
				}
			}
		memset(resx,0,sizeof(resx));
		for (int b=0;b<=n;b++)
			for (int c=1;c<=v*12;c++)
				inc(resx[b+num[c]][c%12],res[b][c%12]);
		for (int b=0;b<=n;b++)
			for (int c=0;c<12;c++)
				res[b][c]=resx[b][c];
	}
	for (int a=0;a<=n;a++)
	{
		for (int b=0;b<12;b++)
			inc(ans[a],res[a][b]);
		ans[a]%=mo;
	}
	int mul=1;
	for (int a=1;a<=50;a++)
	{
		if (a==32 || a==27 || a==25 || a==49) continue;
		bool able=true;
		for (int b=1;prime[b];b++)
			if (prime[b]==a) able=false;
		if (!able) continue;
		mul=1ll*mul*a%mo;
	}
	for (int a=0;a<=n;a++)
		printf("%d\n",(int)(1ll*ans[a]*mul%mo));

	return 0;
}

T4 赛

【问题描述】

你是能看到第四题的friends呢。

——laekov

众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。

定义函数ff为计算序列V字的数量的函数。定义V字为i<j<k,ai>aj,ak>aji<j<k,a_i>a_j,a_k>a_j的三元组(i,j,k)(i,j,k)，现在给定n个数a1,a2……aNa_1,a_2……a_N，求：
∑l=1n∑r=lnf(al,al+1,…,ar) \sum_{l=1}^n \sum_{r=l}^{n}f(a_l,a_{l+1},…,a_r)

【输入格式】

第一行一个整数N。

接下来一行N个整数。

【输出格式】

一行一个整数代表答案对109+710^9+7取模之后的答案。

【样例输入】

5

2 3 1 4 5

【样例输出】

9

【数据范围与规定】。

对于30%的数据，N≤20N\le 20。

对于60%的数据，N≤100N\le 100。

对于80%的数据, N≤1000N\le 1000。

对于100%的数据,1≤N≤105,1≤ai≤N1\le N\le 10^5,1\le a_i \le N

思路

对于这一道题目来说，我还是想到了思路的，暴力。这个暴力不得了，一旦成功，我已经得了60分了，所以这道题部分分给的很足，但是对于想拿省一的人来说，必须要精益求精，因此，我将阐述这道题的思路，首先看一下我60分的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int Mod=1e9+7;
long long n;
long long a[100005];
long long f(long long l,long long r)//解决问题的函数
{
	long long sol=0;
	for(int i=l;i<=r;i++)
	{
		for(int j=i;j<=r;j++)
		{
			for(int k=j;k<=r;k++)
			if(a[i]>a[j]&&a[k]>a[j])
			sol=(sol+1)%Mod;//简单的枚举
		}
	}
	return sol;
}
int main()
{
	long long ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int l=1;l<=n;l++)
	{
		for(int r=l;r<=n;r++)
		ans+=f(l,r)%Mod;//计算答案
	}
	cout<<ans%Mod<<endl;//输出结果
	return 0;
}

因此，最后的四个点都加载失败了，复杂度O(n5)O(n^5)

接着我们改进一下

我们可以将题目转化为问这个v字在多少个区间里，当且仅当一个数对满足1≤l≤i且k≤r≤n1\le l\le i 且 k\le r\le n时，我们可以认为这个v字在这个区间，所以我们的答案就是

ans+=i∗(n−k+1)ans+=i*(n-k+1)，时间复杂度O(n3)O(n^3)

八十分代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int Mod=1e9+7;
int n;
int a[100005];
long long ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			for(int k=j;k<=n;k++)
			{
				if(a[i]>a[j]&&a[j]<a[k])
				ans=(ans+i*(n-k+1)%Mod)%Mod;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

现在我们已经优化到O(n3)O(n^3)了，所以接下来我们该怎么继续优化呢，我们可以发现，只要统计一个数的左边比他大的数x个，右边比他大的数y个，就可以了，所以对于每个i枚举一个k，则最终有式子：
ans=∑b=1nib∗∑c=1nkc ans=\sum _{b=1}^n i_b*\sum_{c=1}^nk_c
这样就可以分开来枚举，时间复杂度为O(n2)O(n^2)，然后加一个值域线段树或者值域树状数组就可以得到O(nlog⁡n)O(n\log n)的复杂度了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define lb(x) ((x)&(-(x)))
const int maxn=100010;
int n,z[maxn];
long long y[maxn],pre[maxn],suf[maxn];
long long query(int p)
{
	long long ans=0;
	for (;p;p-=lb(p))
		ans+=y[p];
	return ans;
}
void modify(int p,int v)
{
	for (;p<=n;p+=lb(p))
		y[p]+=v;
}

int main()
{
	scanf("%d",&n);
	for (int a=1;a<=n;a++)
		scanf("%d",&z[a]);
	memset(y,0,sizeof(y));
	for (int a=1;a<=n;a++)
	{
		pre[a]=query(n)-query(z[a]);
		modify(z[a],a);
	}
	memset(y,0,sizeof(y));
	for (int a=n;a>=1;a--)
	{
		suf[a]=query(n)-query(z[a]);
		modify(z[a],n-a+1);
	}
	long long ans=0;
	for (int a=1;a<=n;a++)
		ans+=pre[a]*suf[a];
	printf("%lld\n",ans);
	return 0;
}

总结

这套题目总体来说部分分给的很足，而且最重要的一点就是难度不是递增的，因此以后我们在做题的时候不能一直干一道题，而是先把题目看一遍，从简单的入手才能得到更多的分数。这次的考点主要是：

数学变形，大模拟，部分分的分别解决，树状数组||线段树的运用以及不同角度的思考问题