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

由于在比赛期间发现了很多是原题，所以直接抄了原题代码，稍后准备重写。

A - 不凡的夫夫

答案为$leftlfloor {sumlimits_{i = 1}^n {{{log }_8}i} } ight floor + 1$，由于数据范围的问题，可以将询问离线，然后$1$到$10^7$跑一遍答案都在了

听说有$O(1)$公式，表示并不会推...

#include <bits/stdc++.h>
using namespace std;

int ans[1000010];
struct Q {
  int n;
  int id;
  int ans;
}s[1000010];

double work(int x) {
  return log10(1.0 * x) / log10(8.0);
}

bool cmp(Q & a, Q & b) {
  return a.n < b.n;
}

int main() {
  int n;
  int T;
  cin >> T;
  for(int cas = 1; cas <= T; cas ++) {
    scanf("%d", &s[cas].n);
    s[cas].id = cas;
  }
  sort(s + 1, s + 1 + T, cmp);
  int now = 0;
  double A = 0.0;
  for(int i = 1; i <= T; i ++) {
    while(now < s[i].n) {
      now ++;
      A += work(now);
    }
    ans[s[i].id] = (int)A + 1;
  }
  for(int i = 1; i <= T; i ++) {
    printf("%d
", ans[i]);
  }
  return 0;
}

B - 一个小问题

该题存在一些问题。如果$a$全是素数，$r$全是$0$，由于要求$x$是正整数，那么答案是所有不同素数的乘积，答案会很大。

C - 守护白起

这题和POJ 2409一样，只是数据范围扩大了一下，注意取模。

代码稍后。

D - 小牛vs小客

只有$1$和$2$小牛会赢，其余都是小客赢。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  while(cin >> n) {
    if(n > 2) printf("XiaoKe
");
    else printf("XiaoNiu
");
  }
  return 0;
}

E - 进击吧！阶乘

大数运算，直接上了Java。

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class Main {
	static Scanner cin = new Scanner(System.in);
	
	public static void main(String[] args) {
		while(cin.hasNext()) {
			int n = cin.nextInt();
			BigInteger ans = BigInteger.ONE;
			for(int i = 1; i <= n; i ++) {
				ans = ans.multiply(BigInteger.valueOf(i));
			}
			System.out.println(ans);
		}
	}
}

F - 小牛再战

这题我是看样例猜的，除去1的数字全部异或起来，看是否为$0$。原因还要深入研究一下。

#include <bits/stdc++.h>
using namespace std;

int a[1000];
int n;

int main() {
  while(~scanf("%d", &n)) {
    if(n == 0) break;
    int ok = 0;
    for(int i = 1; i <= n; i ++) {
      scanf("%d", &a[i]);
      if(a[i] != 1) ok ^= a[i];
    }
    if(ok) printf("Win
");
    else printf("Lose
");
    
  }
  return 0;
}

G - 大水题

$状压dp$。

$dp[i]$表示能被$i$状态的数字整除的数字有几个，倒着减下来能算出能只能被被状态$i$整除的数字有几个，$dp[0]$就是答案。看一下代码就能明白了。

#include <bits/stdc++.h>
using namespace std;

long long x[10];
long long st[1000];
long long dp[1000];

void init() {
  x[0] = 2;
  x[1] = 5;
  x[2] = 11;
  x[3] = 13;
  for(int j = 0; j < (1 << 4); j ++) {
    st[j] = 1;
    for(int p = 0; p < 4; p ++) {
      if(j & (1 <<p)) st[j] *= x[p];
    }
   // cout << j << " " << st[j] << endl;
  }
}

int main() {
  init();
  long long n;
  while(~scanf("%lld", &n)) {
    long long ans = 0;
    for(int i = 0; i <= 20; i ++) {
      dp[i] = 0;
    }
    for(int i = 0; i < 16; i ++) {
      dp[i] = n / st[i];
    }
    for(int i = 15; i >= 0; i --) {
      for(int j = i + 1; j <= 15; j ++) {
        if((i | j) == j) {
          dp[i] -= dp[j];
        }
      }
    }
    printf("%lld
", dp[0]);
  }
  return 0;
}

H - 向左走

这题和POJ 1696一样，每次极角度排序找第一个即可。

代码稍后。

I - 三角形

皮克定理，这题和HDU 1705一样。

#include <bits/stdc++.h>
using namespace std;

struct point {
  long long x, y;
}p[5];

long long gcd(long long a, long long b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

long long work(point &a, point &b) {
  long long len1 = abs(a.x - b.x);
  long long len2 = abs(a.y - b.y);
  return gcd(len1, len2) - 1;
}

long long area(point &a, point &b, point &c) {
  return abs(a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y);
  //(x1y2+x2y3+x3y1-x1y3-x2y1-x3y2)
}

int main() {
  while(~scanf("%lld", &p[0].x)) {
    if(p[0].x == -1) break;
    scanf("%lld", &p[0].y);
    scanf("%lld%lld", &p[1].x, &p[1].y);
    scanf("%lld%lld", &p[2].x, &p[2].y);
    long long A = work(p[0], p[1]);
    long long B = work(p[1], p[2]);
    long long C = work(p[2], p[0]);
    long long s = area(p[0], p[1], p[2]);
    long long edge = A + B + C + 3;
    long long nei = (s - edge + 2) / 2;
    printf("%.1f %lld %lld %lld %lld
", 1.0 * s / 2.0, nei, A, B, C);
  }
  return 0;
}