2018年全国多校算法寒假训练营练习比赛（第三场）

本文主要是介绍2018年全国多校算法寒假训练营练习比赛（第三场），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A 不凡的夫夫

题目描述 

第一行是一个整数t(0<t<=1000000)(表示t组数据)
接下来t行，每一行有一个整数n(0<=n<=10000000)

输出n！在8进制下的位数。

3
4
2
5

2
1
3

思路: 斯特林公式。

斯特林公式（Stirling's approximation）是一条用来取n的阶乘的近似值的数学公式。一般来说，当n很大的时候，n阶乘的计算量十分大，所以斯特林公式十分好用，而且，即使在n很小的时候，斯特林公式的取值已经十分准确。求N！的位数：
lnN!=NlnN-N+0.5*ln(2*N*pi)  ！要想求有多少位，将他换成以10为底便可。利用换底公式得  lnN!/ln10=log10N!把式子取整形加1就是位数！

代码：

#include<map>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define maxn 100010
using namespace std;
typedef long long ll;
#define E  2.71828182845  
#define PI 3.1415926  
int main(){ll n,t;scanf("%lld",&t);while(t--){ll ans=1;scanf("%lld",&n);if(n>3){ans=(log10(sqrt((long double)2.0 *PI*n))+(n*(log10((long double)n)-log10((long double)E))))/log10(8)+1;}printf("%lld\n",ans);}return 0;
}

B 一个小问题

题目描述 

第一行是正整数k(k<=100000)
接下来k行，每行有俩个正整数a，r(100000>a>r>=0)

在每个测试用例输出非负整数m，占一行。
如果有多个可能的值，输出最小的值。
如果没有可能的值，则输出-1。

2
8 7
11 9

31

思路：中国剩余定理。模板题

代码：

#include<map>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 100010
using namespace std;
typedef long long ll;
void gcd(ll a,ll b,ll &d,ll &x,ll &y)
{if(!b){d=a;x=1;y=0;}else{gcd(b,a%b,d,y,x);y-=x*(a/b);}
}ll c(ll n,ll a[],ll b[])
{ll m1=a[0];ll r1=b[0];ll flag=0;ll d;for(ll i=1;i<n;i++){ll m2=a[i];ll r2=b[i];if(flag)continue;ll x,y;gcd(m1,m2,d,x,y);ll c=r2-r1;if(c%d){flag=1;continue;}ll t=m2/d;x=(c/d*x%t+t)%t;r1=m1*x+r1;m1=m1*m2/d;}if(flag) return -1;if(n==1&&r1==0) return m1;return r1;
}
ll aa[550000],bb[550000];int main()
{ll k,i;cin>>k;for(i=0;i<k;i++)cin>>aa[i]>>bb[i];cout<<c(k,aa,bb)<<endl;
}

题目描述 

输入包括多组测试数据
每组测试数据一个n（1≤n≤1e9）

每组用一行输出胜利者的名字（小牛获胜输出XiaoNiu，小客获胜输出XiaoKe）

2
3

XiaoNiu
XiaoKe

思路：博弈题目，取石子（七）问题。

假设石子数等于5，如果先者先取一个，那么后者拿走两个，将剩下的两个石子分成两堆，后者赢。如果先者先取二个，那么后者取一个使剩下的两个石子分成两堆，后者赢。

假设石子数等于6，如果先者先取一个，那么后者拿走一个，将剩下的石子分成两段，每段两个，如果先者再拿两个，那么后者赢，如果先者再拿一个，那么后者再取另一堆中的一个，这样剩下的两个石子被分成两堆， 后者赢。         如果先者先取两个，那么后者也取两个使剩下的两个石子分成两堆，后者赢。

所以当先者取走后，后者取走一个或者两个，将剩下的石子分成对称的两段，以此类推，那么如果石子数大于2后者一定赢。

#include <stdio.h>  int main (void)  
{  int n;  while (scanf("%d", &n) != EOF)  {  if(n > 2)  printf("XiaoKe\n");  else  printf("XiaoNiu\n");  }  return 0;  
}  

E 进击吧！阶乘

题目描述 

多个测试数据，每个测试数据输入一个数N

每组用一行输出N的阶乘

1
2
3

1
2
6

思路：Java大数阶乘模板题

代码：

import java.math.BigInteger;
import java.util.Scanner;
public class Main{public static void main(String[] args) {     Scanner inputScanner=new Scanner(System.in);while(inputScanner.hasNext()){int n=inputScanner.nextInt();BigInteger m;m=BigInteger.valueOf(1);//将m定义成大数的1for(int i=1;i<=n;i++){m=m.multiply(BigInteger.valueOf(i));//大数乘法}System.out.println(m);}  }
}

题目描述 

可能有多组测试数据(测试数据组数不超过1000)
每组测试数据的第一行是一个整数，表示N(1<=N<=10)
第二行是N个整数分别表示该堆石子中石子的数量。（每堆石子数目不超过100）
当输入的N为0时，表示输入结束

对于每组测试数据，输出Win表示小牛可以获胜，输出Lose表示小牛必然会败。

3
2 1 3
2
1 1
0

Win
Lose

提示：
例如：如果最开始有4堆石子，石子个数分别为3 1 4 2，而小牛想决定要先拿走第三堆石子中的两个石子（石子堆状态变为3 1 2 2），然后他可以使石子堆达到的状态有以下几种：
3 1 2 2（不再移动石子）
4 1 1 2（移动到第一堆一个）
3 2 1 2（移动到第二堆一个）
3 1 1 3（移动到第四堆一个）
5 1 0 2（全部移动到第一堆）
3 3 0 2（全部移动到第二堆）
3 1 0 4（全部移动到最后）

思路：博弈问题。取石子问题（三）

代码：

#include<map>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define maxn 100010
using namespace std;
int n;
int s;
int main()
{int ans[110],i,num;while(scanf("%d",&n)&&n){memset(ans,0,sizeof(ans));for(i=0;i<n;++i){scanf("%d",&num);ans[num]++;}s=0;for(i=0;i<101;++i){if(ans[i]&1){s=1;break;}}if(s)printf("Win\n");elseprintf("Lose\n");}return 0;
} 

题目描述 

本题有多组输入
每行一个数n，1<=n<=10^18.

每行输出输出不是2 5 11 13的倍数的数共有多少。

15

4

1 3 7 9

思路：容斥原理：  要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。

    那么的面积就是集合A、B、C各自面积之和减去 , ,  的面积，再加上的面积。

         由此，我们也可以解决n个集合求并的问题。

代码：

#include<map>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define maxn 100010
using namespace std;
typedef long long ll;
#define PI acos(-1.0)
int main()
{ll n;ios::sync_with_stdio(false);while(scanf("%lld",&n)!=EOF){ll cnt;cnt=n-(n/2)-(n/5)-(n/11)-(n/13);cnt=cnt+(n/10)+(n/22)+(n/26)+(n/55)+(n/65)+(n/143);cnt=cnt-(n/110)-(n/130)-(n/715)-(n/286);cnt=cnt+(n/1430);cout<<cnt<<endl;}return 0;
}

这篇关于2018年全国多校算法寒假训练营练习比赛（第三场）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！