【 경 기 】 【 교 내 테스트 】 2020 - 7 - 19 교 내 테스트

2020 - 7 - 19 교 내 테스트 총화 + 문제 풀이.
경기 링크
클릭 하여 링크 열기
경기 경력
A 문 제 를 열 어 보 니 심 슨 포인트 인 데 심 슨 포 인 트 를 배우 지 못 해서 뛰 었 습 니 다.
B 문 제 를 열 어 보 니 조합 계수 인 데 뛰 었 다.
C 문 제 를 풀 어 보 니 욕심 문제 인 것 같다.
C 를 계속 보 니 인터넷 욕심 같은 느낌 이 든다.하지만 생각 할 수록 이상 하 다. 그리고 sb dp 문제 라 는 것 을 알 게 되 었 다.야드 를 재 어 보 니 냈 다.
B 문 제 를 보 니 조합 수 를 사용 해 직접 푸 시 하 는 방법 을 고려 할 수 있어 60 점 을 받 았 다.이어서 생각해 보 니 아무것도 생각 나 지 않 았 다.볼 륨 형식 인 것 같 지만 소 용 없어 요.그래서 무슨 생각 을 해 야 할 지 모 르 겠 어 요.왠 지 10 시 30 분 이 야.
A 문 제 를 다시 보면 두 부분 으로 나 눌 수 있다.그리고 B 문 제 를 보고 시 계 를 치 는 규칙 을 찾 으 려 고 했 지만 시간 이 부족 했다.
예상 득점: 20 + 60 + 100. 실제 득점 과 편차 가 없다.
실 수 는 두 번 째 문제 인 '그래서 무슨 생각 을 해 야 할 지 모 르 겠 어' 에 있다 고 느 꼈 다. 무슨 생각 을 해 야 할 지 전혀 모 르 는 것 은 아 닐 것 이다. 식 이 귀 찮 고 쓰기 가 귀 찮 기 때문이다.예 를 들 어 예 를 들 었 을 뿐 식 의 형식 을 쓰 지 않 았 지만 더 이상 식 을 미 룰 수 없 었 다.다음 부 터 는 번 거 로 움 을 두려워 하지 마 세 요!
시험 이 끝 난 후 1 인당 시 계 를 쳐 서 규칙 을 찾 아 T2 를 자 르 는 것 을 발견 하 였 다.
(1) - 작은 Q 의 플라스마 장
문제 풀이
자가 적응 심 슨 포 인 트 를 사용 하면 됩 니 다.
코드

#include 
#include 
#include 
using namespace std;
typedef double db;
const int MAXN = 205, MAXR = 1e4 + 5;
const db inf = 1e8, lim = 1e4, eps = 1e-8;
int n, tot;
db x[MAXN], y[MAXN], r[MAXN], R[MAXN];
struct Region {
	db ps;
	int tag;
	Region() {}
	Region(db _p, int t) : ps(_p), tag(t) {}
} store[MAXN * 4];
bool cmp(Region x, Region y) { return x.ps < y.ps; }
pair cross(db x, db y, db r, db ps) {
	if (ps < x - r || ps > x + r)
		return make_pair(inf, inf);
	db a = abs(ps - x), len = sqrt(r * r - a * a);
	return make_pair(y - len, y + len);
}
db f(db p) {
	tot = 0;
	for (int i = 1; i <= n; ++i) {
		pair tmp1 = cross(x[i], y[i], R[i], p), tmp2 = cross(x[i], y[i], r[i], p);
		if (tmp1.first <= lim && tmp2.first <= lim) {
			store[++tot] = Region(tmp1.first, 1);
			store[++tot] = Region(tmp2.first, -1);
			store[++tot] = Region(tmp2.second, 1);
			store[++tot] = Region(tmp1.second, -1);
		} else if (tmp1.first <= lim && tmp2.first > lim) {
			store[++tot] = Region(tmp1.first, 1);
			store[++tot] = Region(tmp1.second, -1);
		}
		//   
	}
	sort(store + 1, store + tot + 1, cmp);
	db ret = 0;
	int sum = 0;
	for (int i = 1; i < tot; ++i) {
		db len = store[i + 1].ps - store[i].ps;
		sum += store[i].tag;
		if (sum)
			ret += len;
	}
	return ret;
}
db simpson(db a, db b) {
	db mid = (a + b) * 0.5;
	return (b - a) * (f(a) + f(b) + 4.0 * f(mid)) / 6.0;
}
db cal(db x, db y, db ans) {
	db mid = (x + y) * 0.5;
	db lv = simpson(x, mid), rv = simpson(mid, y);
	if (fabs(lv + rv - ans) < 15.0 * eps)
		return lv + rv + (lv + rv - ans) / 15.0;
	else
		return cal(x, mid, lv) + cal(mid, y, rv);
}
int main() {
	scanf("%d", &n);
	double lp = inf, rp = -inf;
	for (int i = 1; i <= n; ++i) {
		scanf("%lf%lf%lf%lf", &x[i], &y[i], &R[i], &r[i]);
		lp = min(lp, x[i] - R[i]);
		rp = max(rp, x[i] + R[i]);
	}
	printf("%.3lf
", cal(lp, rp, simpson(lp, rp)));
	return 0;
}

(2) - 작은 Z 의 도시 여행
문제 풀이
위 - 아래, 왼쪽 - 오른쪽 소득 의 결과 가 고정 되면 최종 적 으로 도착 하 는 점 이 고정 되 어 있 음 을 발견 할 수 있다.최종 x 좌 표를 통 해 최종 y 좌 표를 통 해 총 걸음 수 는 3 개의 4 원 방정식 을 열거 할 수 있 고 한 개의 숫자 가 확실 하지 않 으 면 그 수 를 매 거 한 후에 계산 하면 된다.
그러나 이런 복잡 도 는 \ (\ mathcal O (Tn) \) 의 것 으로 분명히 지나 갈 수 없다.우 리 는 식 의 형식 이 이와 유사 하 다 는 것 을 발견 했다.
\[\sum_k \binom{r}{m+k} \binom{s}{n-k} \]
이것 이 판 드 먼 드 볼 륨 이라는 것 을 발견 했다.그 러 니 양식 을 사용 하면 된다.
\[\sum_k \binom{r}{m+k} \binom{s}{n-k}=\binom{r+s}{m+n} \]
어떻게 증명 합 니까? 이것 은 볼 륨 의 형식 임 을 발견 합 니 다.생 성 함수 사용 을 고려 합 니 다: \ (\ binom {r} {k} \) 의 생 성 함 수 는 \ (f (x) = (1 + x) ^ r \), \ (g (x) = (1 + x) ^ s \) 입 니 다. 그러면 등식 왼쪽 은 \ ([x ^ {m + n} f (x) \ cdot g (x) \) 에 해당 합 니 다.바로 \ ([x ^ {m + n}] (1 + x) ^ {r + s} = \ binom {r + s} {n + m} \) 입 니 다.
총결산
4. 567917. 판 드 먼 드 볼 륨..
코드

#include 
using namespace std;
typedef long long ll;
const int CN = 2e5 + 5, Mod = 998244353, N = 2e5;
int ml(int x, int y) { return (ll) x * y % Mod; }
int ad(int x, int y) { return (x + y > Mod) ? (x + y - Mod) : (x + y); }
int ksm(int x, int y) {
	int ret = 1;
	for (; y; y >>= 1, x = ml(x, x))
		if (y & 1) ret = ml(ret, x);
	return ret;
}
int T, r, fac[CN << 1], ifac[CN << 1];
ll x, y;
void Init() {
	fac[0] = ifac[0] = 1;
	for (int i = 1; i <= 2 * N; ++i) fac[i] = ml(fac[i - 1], i);
	for (int i = 1; i <= 2 * N; ++i) ifac[i] = ksm(fac[i], Mod - 2);
}
int binom(int x, int y) {
	if (x < 0 || y < 0 || x < y) return 0;
	return ml(fac[x], ml(ifac[y], ifac[x - y]));
}
int main() {
	scanf("%d", &T);
	Init();
	while (T--) {
		scanf("%lld%lld%d", &x, &y, &r);
		if (x > r || y > r || ((x + y + r) % 2 == 1)) {
			printf("0
");
			continue ;
		}
		printf("%d
", ml(binom(r, (r - x - y) / 2), binom(r, (r - x - y) / 2 + x)));
	}
	return 0;
}

(3) - 작은 H 의 동전 게임
문제 풀이
모드 \ (k \) 의 나머지 가 다른 위치 와 관계 가 없 음 을 쉽게 발견 할 수 있 으 므 로 모드 \ (k \) 의 나머지 에 따라 분류 한 다음 dp 를 사용 하면 됩 니 다 (최대 독립 집합 과 같은 dp).
코드

#include 
#include 
using namespace std;
typedef long long ll;
const int CN = 1e5 + 5, inf = 1e9;
int N, K, a[CN];
ll ans, f[CN][2];
int main() {
	scanf("%d%d", &N, &K);
	for (int i = 1; i <= N; ++i)
		scanf("%d", &a[i]);
	for (int i = 1; i <= K; ++i) {
		int cnt = 0;
		f[0][0] = 0;
		f[0][1] = -inf;
		for (int j = i; j <= N - K; j += K) {
			++cnt;
			f[cnt][0] = f[cnt][1] = -inf;
			f[cnt][0] = max(f[cnt - 1][0], f[cnt - 1][1]);
			f[cnt][1] = f[cnt - 1][0] + a[j] + a[j + K];
		}
		ans += max(f[cnt][0], f[cnt][1]);
	}
	printf("%lld
", ans);
	return 0;
}