2018年全国多校算法寒假训练
题目描述
夫夫有一天对一个数有多少位数感兴趣，但是他又不想跟凡夫俗子一样，
所以他想知道给一个整数n，求n！的在8进制下的位数是多少位。
输入描述:
第一行是一个整数t(0<t<=1000000)(表示t组数据)<br />接下来t行，每一行有一个整数n(0<=n<=10000000)
输出描述:
输出n！在8进制下的位数。
示例1
输入
3 4 2 5
输出
2 1 3
思路: 斯特林公式。
斯特林公式（Stirling's approximation）是一条用来取n的阶乘的近似值的数学公式，求N！的位数：
lnN!=NlnN-N+0.5*ln(2*N*pi) ！要想求有多少位，将他换成以10为底便可。利用换底公式得 log10N!=lnN!/ln10=n*lg(n/E) +lg(sqrt(2*n*PI)).把式子取整形加1就是位数！
代码：
1 //#include "bits/stdc++.h"
2 #include "cstdio"
3 #include "map"
4 #include "set"
5 #include "cmath"
6 #include "queue"
7 #include "vector"
8 #include "string"
9 #include "cstring"
10 #include "time.h"
11 #include "iostream"
12 #include "stdlib.h"
13 #include "algorithm"
14 #define db double
15 #define ll long long
16 #define vec vector<ll>
17 #define Mt vector<vec>
18 #define ci(x) scanf("%d",&x)
19 #define cd(x) scanf("%lf",&x)
20 #define cl(x) scanf("%lld",&x)
21 #define pi(x) printf("%d\n",x)
22 #define pd(x) printf("%f\n",x)
23 #define pl(x) printf("%lld\n",x)
24 #define inf 0x3f3f3f3f
25 #define rep(i, x, y) for(int i=x;i<=y;i++)
26 const int N = 1e6 + 5;
27 const int mod = 1e9 + 7;
28 const int MOD = mod - 1;
29 const db eps = 1e-10;
30 const db PI = acos(-1.0);
31 using namespace std;
32 const db E=2.71828182845;
33 int main()
34 {
35 ll t,n;
36 cl(t);
37 while(t--)
38 {
39 ll ans=1;
40 cl(n);
41 if(n>3){
42 ans=(n*(log10((db)n/E))+log10(sqrt((db)2.0*n*PI)))/log10(8)+1;
43 }
44 pl(ans);
45 }
46 return 0;
47 }D 小牛vs小客
题目描述
小牛和小客玩石子游戏，他们用n个石子围成一圈，小牛和小客分别从其中取石子，谁先取完谁胜，每次可以从一圈中取一个或者相邻两个，每次都是小牛先取，请输出胜利者的名字（小牛获胜输出XiaoNiu，小客获胜输出XiaoKe）（1 2 3 4 取走 2 13 不算相邻）
输入描述:
输入包括多组测试数据<br />每组测试数据一个n（1≤n≤1e9）
输出描述:
每组用一行输出胜利者的名字（小牛获胜输出XiaoNiu，小客获胜输出XiaoKe）
示例1
输入
2 3
输出
XiaoNiu XiaoKe
思路：博弈题目，取石子（七）问题。
思路：假设石子数等于5，如果先者先取一个，那么后者拿走两个，将剩下的两个石子分成两堆，后者赢。如果先者先取二个，那么后者取一个使剩下的两个石子分成两堆，后者赢。
假设石子数等于6，如果先者先取一个，那么后者拿走一个，将剩下的石子分成两段，每段两个，如果先者再拿两个，那么后者赢，如果先者再拿一个，那么后者再取另一堆中的一个，这样剩下的两个石子被分成两堆， 后者赢。 如果先者先取两个，那么后者也取两个使剩下的两个石子分成两堆，后者赢。
所以当先者取走后，后者取走一个或者两个，将剩下的石子分成对称的两段，以此类推，那么如果石子数大于2后者一定赢。
代码：
1 #include <stdio.h>
2
3 int main (void)
4 {
5 int n;
6 while (scanf("%d", &n) != EOF)
7 {
8 if(n > 2)
9 printf("XiaoKe\n");
10 else
11 printf("XiaoNiu\n");
12 }
13 return 0;
14 }G：大水题
给出一个数n，求1到n中，有多少个数不是2 5 11 13的倍数。
输入描述:
本题有多组输入<br />每行一个数n，1<=n<=10^18.
输出描述:
每行输出输出不是2 5 11 13的倍数的数共有多少。
示例1
输入
15
输出
4
说明
1 3 7 9
思路：
容斥原理：要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。
代码：
1 #include<map>
2 #include<vector>
3 #include<queue>
4 #include<cstdio>
5 #include<cstdlib>
6 #include<cstring>
7 #include<iostream>
8 #include<algorithm>
9 #include<cmath>
10 #define maxn 100010
11 using namespace std;
12 typedef long long ll;
13 #define PI acos(-1.0)
14 int main()
15 {
16 ll n;
17 ios::sync_with_stdio(false);
18 while(scanf("%lld",&n)!=EOF)
19 {
20 ll cnt;
21 cnt=n-(n/2)-(n/5)-(n/11)-(n/13);
22 cnt=cnt+(n/10)+(n/22)+(n/26)+(n/55)+(n/65)+(n/143);
23 cnt=cnt-(n/110)-(n/130)-(n/715)-(n/286);
24 cnt=cnt+(n/1430);
25 cout<<cnt<<endl;
26 }
27 return 0;
28 }F：
题目描述
共有N堆石子，已知每堆中石子的数量，两个人轮流取石子，每次只能选择N堆石子中的一堆取一定数量的石子（最少取一个），取过子之后，还可以将该堆石子中剩余的石子随意选取几个放到其它的任意一堆或几堆上。等哪个人无法取子时就表示此人输掉了游戏。注意：一堆石子没有子之后，就不能再往此处放石子了。
假设每次都是小牛先取石子，并且游戏双方都绝对聪明，现在给你石子的堆数、每堆石子的数量，请判断出小牛能否获胜。
输入描述:
可能有多组测试数据(测试数据组数不超过1000)<br />每组测试数据的第一行是一个整数，表示N(1<=N<=10)<br />第二行是N个整数分别表示该堆石子中石子的数量。（每堆石子数目不超过100）<br />当输入的N为0时，表示输入结束
输出描述:
对于每组测试数据，输出Win表示小牛可以获胜，输出Lose表示小牛必然会败。
示例1
输入
3 2 1 3 2 1 1 0
输出
Win Lose<br /><br />
思路:如果只有一堆石子,则先手必胜.如果有两堆相同数目的石子,显然先手必败,因为对手只需对称操作即可.
同理可知,如果石子可分为两组,对应堆石子数相等,如{1,2,3,1,2,3},则先手同样必败,于是数目相同的两堆先可以暂不考虑.
如果有两堆数目不同的石子,则先手可以使之数目相同,先手必胜.
如果有三堆互不相同的石子,先手可以选择最大的一堆操作,移除一部分后,使剩下的石子正好补齐剩下两堆之间的差距,先手必胜.依次类推,先手必败当且仅当初始时石子数是{1,2,3,1,2,3}这种类型.
代码：
1 #include<stdio.h>
2 int stack[15],C[15];
3 int main()
4 {
5 int N;
6 while (scanf("%d",&N)!=EOF)
7 {
8 if (N==0) return 0;
9 for (int i=1;i<=N;i++) scanf("%d",&C[i]);
10 for (int i=1;i<=N-1;i++)
11 for (int j=i+1;j<=N;j++)
12 if (C[i]>C[j])
13 {
14 int tmp=C[i];
15 C[i]=C[j];
16 C[j]=tmp;
17 }
18 int T=0;
19 for (int i=1;i<=N;i++)
20 {
21 if (T==0) stack[++T]=C[i];
22 else
23 {
24 if (stack[T]==C[i]) T--;
25 else stack[++T]=C[i];
26 }
27 }
28 if (T==0) printf("0\n");
29 else printf("1\n");
30 }
31 return 0;
32 }