比赛-OBlack学长的训练赛2 (26 Aug, 2018)

A. 函数##

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

#define SC(a, b) (static_cast<a>(b))

typedef long long ll;

double K;

struct data {
	int x, y;
	data(int x = 0, int y = 0):
		x(x), y(y) { }
	bool operator < (const data &tmp)
	const
	{
		return SC(double, x) * K + SC(double, y) > SC(double, tmp.x) * K + SC(double, tmp.y);
	}
};

int L, R, N, pos[102000];
priority_queue< double, vector<double>, greater<double> > Q;
priority_queue<data> F;

void fun1()
{
	K = sqrt(K);
	for (int i = L; i <= R; ++i)
		for (int j = 1; j <= N; ++j)
			Q.push(SC(double, i) * K + SC(double, j));
	for (int i = 1; i < N; ++i)
		Q.pop();
	printf("%.2lf
", Q.top());
	return;
}

void fun2()
{
	K = sqrt(K);
	int cnt = 0;
	F.push(data(L, 1)), pos[1] = L;
	while (cnt < N - 1) {
		data p = F.top();
		F.pop(), ++cnt;
		if (p.x + 1 <= R && (p.y == 1 || pos[p.y - 1] == p.x + 1))
			F.push(data(p.x + 1, p.y)), pos[p.y] = p.x + 1;
		if (p.x == L || pos[p.y + 1] == p.x - 1)
			F.push(data(p.x, p.y + 1)), pos[p.y + 1] = p.x;
	}
	data t = F.top();
	printf("%.2lf
", SC(double, t.x) * K + SC(double, t.y));
	return;
}

int main()
{
	
	scanf("%d%d%lf%d", &L, &R, &K, &N);
//	if (K == 0) {
//		printf("%.2lf
", SC(double, (N - 1) / (R - L + 1) + 1));
//		return 0;
//	}
//	if (R - L <= 10) {
//		fun1();
//		return 0;
//	}
	fun2();
	return 0;
}

B. 情侣##

#include <stdio.h>
#include <ctype.h>

using namespace std;

#define SC(a, b) (static_cast<a>(b))

typedef long long ll;

const int MOD = 998244353;

char *p1, *p2, buf[1 << 20], sss[50];

inline char gc()
{
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))?EOF:*p1++;
}

template<typename T>
void rd(T &num)
{
	char tt;
	while (!isdigit(tt = gc()));
	num = tt - '0';
	while (isdigit(tt = gc()))
		num = num * 10 + tt - '0';
	return;
}

template<typename T>
void pt(T num)
{
	int top = 0;
	do sss[++top] = num % 10 + '0';
	while (num /= 10);
	while (top)
		putchar(sss[top--]);
	putchar('
');
	return;
}


int f[5005][5005], J[10005], C[5005], inv2;

inline int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }

void init()
{
	f[1][1] = 1;
	for (int i = 2; i <= 5000; ++i) {
		for (int j = 0; j <= i; ++j) {
			f[i][j] = add(f[i][j], SC(int, SC(ll, f[i - 1][j]) * j % MOD));
			if (j)
				f[i][j] = add(f[i][j], SC(int, SC(ll, f[i - 1][j - 1]) * (2 * i - j) % MOD));
			f[i][j] = add(f[i][j], SC(ll, f[i - 1][j]) * (2 * i - 1 - j) % MOD * (2 * i - 2 - j) % MOD * inv2 % MOD);
			f[i][j] = add(f[i][j], SC(ll, f[i - 1][j + 1]) * (j + 1) % MOD * (2 * i - 2 - j) % MOD);
			f[i][j] = add(f[i][j], SC(ll, f[i - 1][j + 2]) * (j + 1) % MOD * (j + 2) % MOD * inv2 % MOD);
		}
	}
	return;
}

inline int mont(int a, int b)
{
	a %= MOD;
	int t = 1;
	while (b) {
		if (b & 1) t = SC(int, SC(ll, t) * a % MOD);
		b >>= 1, a = SC(int, SC(ll, a) * a % MOD);
	}
	return t;
}

int main()
{
	int T;
	rd(T);
	inv2 = mont(2, MOD - 2);
	init();
	J[0] = 1;
	for (int i = 1; i <= 10000; ++i)
		J[i] = SC(int, SC(ll, J[i - 1]) * i % MOD);
	C[0] = 1;
	for (int i = 1; i <= 5000; ++i)
		C[i] = SC(int, SC(ll, C[i - 1]) * 2 % MOD);
	J[10000] = mont(J[10000], MOD - 2);
	for (int i = 9999; i >= 0; --i)
		J[i] = SC(int, SC(ll, J[i + 1]) * (i + 1) % MOD);
	while (T--) {
		int n, d, ans = 0;
		rd(n), rd(d);
		for (int t = 1, i = 0; i <= n; ++i, t = SC(int, SC(ll, t) * d % MOD))
			ans = add(ans, SC(int, SC(ll, t) * f[n][i] % MOD));
		ans = SC(int, SC(ll, ans) * C[n] % MOD * J[2 * n] % MOD);
		pt(ans);
	}
	return 0;
}

C. 军训##