本文主要是介绍2018年全国多校算法寒假训练营练习比赛（第三场），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A 不凡的夫夫
题目描述
所以他想知道给一个整数n，求n！的在8进制下的位数是多少位。
输入描述:
第一行是一个整数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对a和r是否存在一个正整数x使每队a和r都满足：x mod a=r，求最小正解x或无解。
输入描述:
第一行是正整数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;
}
D 小牛vs小客
题目描述
输入描述:
输入包括多组测试数据
每组测试数据一个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);} }
}题目描述
共有N堆石子，已知每堆中石子的数量，两个人轮流取石子，每次只能选择N堆石子中的一堆取一定数量的石子（最少取一个），取过子之后，还可以将该堆石子中剩余的石子随意选取几个放到其它的任意一堆或几堆上。等哪个人无法取子时就表示此人输掉了游戏。注意：一堆石子没有子之后，就不能再往此处放石子了。
假设每次都是小牛先取石子，并且游戏双方都绝对聪明，现在给你石子的堆数、每堆石子的数量，请判断出小牛能否获胜。
输入描述:
可能有多组测试数据(测试数据组数不超过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年全国多校算法寒假训练营练习比赛（第三场）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
