菜单

bzoj3000 Big Number 数论,斯特林公式。jxnu acm新生选拔赛。

2018年9月19日 - betway体育

Description

为您少只整数N和K,要求你输出N!的K进制的位数。

极端小之累

Input

生差不多组输入数据,每组输入数据列一行,每行两只数——N,K

Problem Description

概念一栽正整数集合K,集合中来N个数,集合中元素Ki(1<=i<=N)是带有i个无同质因子的绝小的频繁。因为Ki可能会见特别可怜,所以用集聚中有Ki对10^9+7获得余。

Output

每行一个再三为出口结果

Input

主题只有唯一一组测试数据,第一执吃出N,q,表示K的个数与q次询问。1<=N<=1000,q<=10^5.
连通下去q行每行一个恰恰整数(64各项整数范围外),请判断该针对性10^9+7落余后,是否以集合K中。

Sample Input

2 5
2 10
10 10
100 200

Output

对于每次询问,根据题意输出Yes或No

Sample Output

1
1
7
69
对于100%的多少,有2≤N≤2^31, 2≤K≤200,数据组数T≤200。

Sample Input

3 3
2
6
33

题解

因而Stirling公式求近似值

位数=logk(n!)+1

≈ logk(sqrt(2πn)*(n/e)^n)+1

= logk( sqrt(2πn))+log[(n/e)^n]+1

=1/2*logk( 2πn)+nlog(n/e)+1

=0.5*logk ( 2πn)+nlog(n/e)+1

=0.5*logk ( 2πn)+nlog(n)-nlog(e)+1

PS:pi=acos(-1.0),e=exp(1)

PS2:eps的存在是以防备n=2,k=2这样刚好之情状出现,这个时段向上取整要多获得1位

 

斯特林公式是求解n!的近乎似解,对于比较生之n数值是老大准之。

图片 1

据此可以经数学方法解决。

 1 #include<cstring>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<cstdio>
 5 #include<algorithm>
 6 
 7 #define ll long long
 8 using namespace std;
 9 const double eps=0.00000000001;
10 const double pai=3.14159265359;
11 const double e=exp(1);
12 
13 int n,k;
14 
15 int main()
16 {
17     freopen("fzy.in","r",stdin);
18     freopen("fzy.out","w",stdout);
19     while(~scanf("%d%d",&n,&k))
20     {
21         if (n<=1000)
22         {
23             double ans=0;
24             for (int i=1;i<=n;i++)
25                 ans+=log(i);
26             ans/=log(k);
27             int res=ceil(ans+eps);
28             printf("%d\n",res);
29         }
30         else
31         {
32             double res=(log(sqrt(2*pai*n))+n*log(n/e))/log(k);
33             ll ans=ceil(res-eps);
34             printf("%lld\n",ans);
35         }
36     }
37 }

对了,c++小数处理的时刻会发精度损失的题目,所以需要适宜添加一个小数

 

Sample Output

Yes
Yes
No

直接用set保存下,查询就从set里查询就行。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 #include <set>
 6 #define ll long long
 7 using namespace std;
 8 const int MAX = 1e4+10;
 9 const int MOD = 1e9+7;
10 int vis[10010],b[MAX*10],k;
11 void init() {
12     for(int i = 2; i < 10000; i ++) {
13         if(!vis[i]){
14             b[++k] = i;
15             for(int j = i+i; j < 10000; j += i)
16                 vis[j] = 1;
17         }
18     }
19 }
20 int main() {
21     int n,q;
22     std::ios::sync_with_stdio(false);
23     init();
24     cin>>n>>q;
25     set<ll> st;
26     for(int i = 1; i <= n; i ++) {
27         ll ans = 1;
28         for(int j = 1; j <= i; j ++) {
29             ans = 1LL*b[j]*ans%MOD;
30         }
31         st.insert(ans);
32     }
33     ll num;
34     while(q--) {
35         cin>>num;
36         if(st.count(num)) printf("Yes\n");
37         else printf("No\n");
38     }
39     return 0;
40 }

 

非安全字符串

Problem Description

集训十分俗,于是boss发明了一个“益智”游戏——假设来同样段仅由U和L构成的字符串,我们定义当连续的U的个数大于等于三之时,这个字符串是免安全之。现喻你字符串的长度n,请您毕竟有会转移多少只非安全字符串。

Input

输入有差不多组,每组仅输入一个n,代表字符串的长,当n等于0的时光输入完毕。(4<=n<=30)

Output

出口可生成的不安全字符串的个数。

Sample Input

4
5
0

Sample Output

3
8

Hint:对于第一个样例,当n为4的时候,我们满足条件的有 UUUU LUUU UUUL 三种情况

思路:递推吧,因为每一个情况都是由前一个情况转变过来的,所以用一个dp数组去存每个情况相应的值,每一层的意思如下:(i为当前序列的长度)

dp[i][0]从来不老三单连续U的行最右边边也L
dp[i][1]无老三只连续U的队列最右侧边有一个U
dp[i][2]从未有过老三独连续U的班最右边发三三两两独连续的U
dp[i][3]发生三只连的U的排

组成每个情况可窥见

  1. dp[i][0]可以由dp[i-1][0]+dp[i-1][1]+dp[i-1][2]扭转过来,因为前一状态只要不是发出矣3单连续的U的队列,在太右侧边加一个L哪怕得形成
  2. dp[i][1]可以由dp[i –
    1][0]扭转过来,因为只能是当最为右侧没有U的行列加上个U形成
  3. dp[i][2]可以由dp[i –
    1][1]变动过来,因为只能是于极度右边边发一个U之行列加上个U形成
  4. dp[i][3]可以由dp[i – 1][3] * 2 + dp[i –
    1][2]变动过来,因为若原先就是起连续3只U的排最右侧边加上什么都是该情形,然后也可以在极其右面边有些许个U的队加上个U形成

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #define ll long long
 5 using namespace std;
 6 ll dp[33][4];
 7 int main() {
 8     dp[1][0] = dp[1][1] = 1;
 9     dp[1][2] = dp[1][3] = 0;
10     for(int i = 2; i < 33; i ++) {
11         dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2];
12         dp[i][1] = dp[i-1][0];
13         dp[i][2] = dp[i-1][1];
14         dp[i][3] = dp[i-1][3]*2 + dp[i-1][2];
15     }
16     int n;
17     while(scanf("%d",&n)&&n) {
18         cout << dp[n][3] << endl;
19     }
20     return 0;
21 }

 

 

壮壮的数组

Problem Description

A,B,C为老三单要素个数为n的多次组,A={a1,a2,a3…an},B={b1,b2,b3…bn},C={c1,c2,c3…cn};
已经知A、B数组,而且出ci等于ai或bi(1<=i<=n),毫无疑问,C数组有那个多种重组。
然而zz不期待C数组全由A数组或者B数组组成,每一样栽组成都出一个K值,K=c1*c2*c3*…*cn。
今欲你请来各一样栽组成对应的K值,并拿其加起的结果。这个结果可能会见格外十分,请用答案对1e9+7取模。
例如A={1,2,3} B={2,2,4}。
C数组可能吧{a1,b2,b3} {b1,a2,b3} {b1,b2,a3} {a1,a2,b3} {a1,b2,a3}
{b1,a2,a3}
K值分别吗8,16,12,8,6,12,所以若当出口62。

大量输入,建议下scanf

Input

输入数据包含多单测试实例,每个测试实例的率先执行仅发一个整数n(1<=n<=100000),表示A,B,C数组元素个数,第二行有n个数据表示a1
a2 a3…an,第三推行有n个数据表示b1 b2
b3…bn,(1<=ai,bi<=1e9)。处理到文件之毕。

Output

对于每个测试实例,输出一行数据表示问题之答案,请将答案对1e9+7取模。

Sample Input

3
1 2 3
2 2 4
1
3
4

Sample Output

62
0


其实就是求(a1+b1)*(a2+b2)*....*(an+bn)-a1*a2...*an-b1*b2*...*bn。答案取摸就行。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #define ll long long
 5 using namespace std;
 6 const int MAX = 100010;
 7 const int mod = 1e9+7;
 8 ll a[MAX], b[MAX];
 9 int main() {
10     int n;
11     std::ios::sync_with_stdio(false);
12     while(cin>>n) {
13         ll ans = 1;
14         for(int i = 1; i <= n; i ++) {
15             cin >> a[i];
16             ans *= a[i];
17             ans %= mod;
18         }
19         ll cnt = 1;
20         for(int i = 1; i <= n; i ++) {
21             cin >> b[i];
22             cnt *= b[i];
23             cnt %= mod;
24         }
25         ll sum = 1;
26         for(int i = 1; i <= n; i ++) {
27             sum *= (a[i]+b[i]);
28             sum %= mod;
29         }
30         cout << (sum+mod-ans+mod-cnt)%mod << endl;
31     }
32     return 0;
33 }

 

 

 

涛涛的Party

Problem Description

涛神因为极度强,并且专门美,所以具有不少花的联系方式,每个美女都发出温馨之食量以及魅力值,大家还知,物以类聚,人以群分,朋友之爱侣即使是友善之情侣,所以红颜一般都是有投机之美女朋友围,而且这些花特别团结,如果它们底情人发生没来让请之它们纵然不见面应邀请。涛涛想惩罚一个party,但是他单纯准备了w
kg的食品,他惦记获取最好要命之仙人魅力值,不明白怎么邀请美女,于是他去问问你,你可知告他,他会取得的绝色魅力数是有些吧

Input

数量有差不多组,第一尽输入n,m和w(1≤n≤1000,0≤m≤min(n*(n-1)/2,10^5),1≤w≤1000);第二行输入n个整型变量w1,w2,…,wn(1≤wi≤1000)代表美女i的饭量;第三实践输入n个整型变量b1,b2,…,bn(1≤bi≤106)代表美女i的魅力值;接下去的m行输入两单数x和y(1≤xi,yi≤n,xi≠yi),代表x和y是恋人

Output

出口涛涛能博得的极酷魅力值

Sample Input

3 1 5
3 2 5
2 4 2
1 2
4 2 11
2 4 6 6
6 4 2 1
1 2
2 3

Sample Output

6
1

并查集和01背包的采用,同一个集聚下之人口方可算一个口。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 #include <set>
 6 using namespace std;
 7 int n,m,W;
 8 int w[1010], b[1010],fa[1010], dp[1010];
 9 struct Nod{
10     int w, b;
11     Nod(){
12         w = b = 0;
13     }
14 }nod[1010];
15 int find(int x) {
16     return fa[x] = (x==fa[x])?x:find(fa[x]);
17 }
18 void unite(int x, int y) {
19     x = find(x);
20     y = find(y);
21     if(x < y) fa[y] = x;
22     else fa[x] = y;
23 }
24 int main() {
25     std::ios::sync_with_stdio(false);
26     while(cin>>n>>m>>W) {
27         for(int i = 1; i <= n; i ++) cin>>w[i],fa[i] = i;
28         for(int i = 1; i <= n; i ++) cin>>b[i];
29         for(int i = 1; i <= m; i ++) {
30             int x, y;
31             cin>>x>>y;
32             unite(x,y);
33         }
34         for(int i = 1; i <= n; i ++) {
35             int x = find(i);
36             nod[x].w += w[i];
37             nod[x].b += b[i];
38         }
39         for(int i = 1; i <= n; i ++) {
40             if(nod[i].b != 0 && nod[i].w != 0) {
41                 for(int j = W; j >= nod[i].w; j --) {
42                     dp[j] = max(dp[j],dp[j-nod[i].w]+nod[i].b);
43                 }
44             }
45         }
46         printf("%d\n",dp[W]);
47         for(int i = 1; i <= n; i ++){
48             nod[i].b = nod[i].w = 0;
49         }
50         memset(dp,0,sizeof(dp));
51     }
52     return 0;
53 }

手机信号

Problem Description

现今在商海上传了千篇一律缓效果极简的手机,在大哥大上就此一个 7×7
的显示屏来展示手机信号,每个区块能显一个字符。满信号的时光显得如下:

+—–+
|- 4G|
|– |
|— |
|—- |
|—–|
+—–+
(杭电描述区块对字宽的设定不联合,正确显示请看输出样例)
每一样约束信号(第i(1≤i≤5) 格信号有 i独-)代表 20%
的信号强度,不足一约束信号的一些未出示。同时会于右手上斗显示当前的网传输模式。在信号强度不低于
90% 的时显得4G;当信号低于 90%、不小于 60% 的时候显得3G;否则显示E。
对于给定的眼前信号强度 d%,输出信号的 7×7 像从的图腾。

Input

输入一个平头 d(0≤d≤100),表示信号强度。

Output

遵问题要求输出,每行末尾不要输出多余的空白字符。

Sample Input

0
65

Sample Output

+-----+
|    E|
|     |
|     |
|     |
|     |
+-----+
+-----+
|-  3G|
|--   |
|---  |
|     |
|     |
+-----+

直接判断下就行了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     int d;
 5     while(cin>>d){
 6         if(d < 20){
 7             cout << "+-----+\n|    E|\n|     |\n|     |\n|     |\n|     |\n+-----+\n";
 8         }else if(d < 40){
 9             cout << "+-----+\n|-   E|\n|     |\n|     |\n|     |\n|     |\n+-----+\n";
10         }else if(d < 60){
11             cout << "+-----+\n|-   E|\n|--   |\n|     |\n|     |\n|     |\n+-----+\n";
12         }else if(d < 80){
13             cout << "+-----+\n|-  3G|\n|--   |\n|---  |\n|     |\n|     |\n+-----+\n";
14         }else if(d < 90){
15             cout << "+-----+\n|-  3G|\n|--   |\n|---  |\n|---- |\n|     |\n+-----+\n";
16         }else if(d < 100){
17             cout << "+-----+\n|-  4G|\n|--   |\n|---  |\n|---- |\n|     |\n+-----+\n";
18         }else if(d == 100){
19             cout << "+-----+\n|-  4G|\n|--   |\n|---  |\n|---- |\n|-----|\n+-----+\n";
20         }
21     }
22     return 0;
23 }

 

涛神的城建

Problem Description

涛神有一个城建被游人参观,涛神特别的健壮,涛神的强壮值是strong,每个旅游者为生好之强壮值,涛神为了挣钱,他会晤择多单区间去抢夺别人,所以要比较涛神弱的,他即如收到他们之强壮值的差值,但是还是发生较涛涛强壮的,所以涛涛打劫那个人之话语,涛涛要给大人他们的强壮值的差值,所以涛涛可以择于不从劫那个区间的食指,(人是可重新打劫的,区间不行)涛涛最多能净赚多少钱也?

Input

先是推行吃你三只整型变量n,m,strong(1≤n,m≤10000,1≤strong≤200),
仲行给你n个人的强壮值a1,a2,…,an(1≤ai≤200).
对接下m行给你少只整型变量l,r(1≤li≤ri≤n),代表区间里连了第l只游客到第r个游客,涛涛可以选取由不打劫这个区间

Output

出口涛涛可以抢到之极端多的钱

Sample Input

5 4 10
9 12 9 7 14
1 2
4 5
3 4
1 4

Sample Output

7
这题有毒,题目说区间不行,但必须按可以取重复的区间才能AC。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #define ll long long
 5 using namespace std;
 6 const int MAX = 10010;
 7 ll sum[MAX], str;
 8 int main() {
 9     std::ios::sync_with_stdio(false);
10     int n, m;
11     while(cin>>n>>m>>str) {
12         ll x;
13         for(int i = 1; i <= n; i ++) {
14             cin >> x;
15             sum[i] = sum[i-1] + str - x;
16         }
17         ll ans = 0;
18         while(m--) {
19             int l, r;
20             cin >> l >> r;
21             ll y = sum[r] - sum[l-1];
22             if(y > 0) ans += y;
23         }
24         cout << ans << endl;
25         memset(sum,0,sizeof(sum));
26     }
27 }

 

dada的GCD

Problem Description

C语言都学了了怎么计算两只数的最大公约数,而同一段子距离[L,R]的GCD即这段距离所有数的最大公约数。现在给你平失误长为n的行,如果对序列的任意子区间[L,R],都有应声段距离的gcd>=2,那么这段序列就称为dada的GCD序列。
n<=10^4
班的每个数仅次于10^9

Input

率先尽有一个平头t,代表t组数据
每组输入有一个刚好整数n,
紧接着一行n个正整数。

大气输入,使用cin的同室请关闭stdio同步

Output

假使是dada的GCD序列,就输出Yes,反的输出No

Sample Input

2
3
2 6 4
3
4 6 9

Sample Output

Yes
No
语文水平有待提高了,竟然没看懂题意,写了几次都是靠猜的,赛后猜知道要全部的最大公约数大于等于2就行。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 #define ll long long
 6 using namespace std;
 7 const int MAX = 1e5;
 8 ll a[MAX];
 9 ll gcd(ll a, ll b){
10     return b?gcd(b,a%b):a;
11 }
12 int main() {
13     std::ios::sync_with_stdio(false);
14     int t, n;
15     cin>>t;
16     while(t--) {
17         cin>>n;
18         for(int i = 1; i <= n; i ++) {
19             cin >> a[i];
20         }
21         if(n == 1){
22             if(a[0] >= 2) puts("Yes");
23             else puts("No");
24         }else {
25             ll ans = gcd(a[0],a[1]);
26             for(int i = 2; i <= n; i ++) ans = gcd(ans,a[i]);
27             if(ans >= 2)puts("Yes");
28             else puts("No");
29         }
30     }
31     return 0;
32 }

 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图