# 小技巧

  1. 递归,从后向前
  2. 预处理
  3. 划分子结构
  4. 单调队列、滑动窗口
  5. 能剪的枝一定要减!能剪的枝一定要减!能剪的枝一定要减!
  6. 但是剪枝别剪挂了……

# 手动扩栈

编译时指定参数

-Wl,--stack=size

size 是栈的大小,单位为字节。


# P5686 [CSP-SJX2019] 和积和

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 500005, P = 1e9+7;
int n;
ll a[N], b[N], sa[N], sb[N], s[N], ssa[N], ssb[N];
int main() {
	
	scanf("%d", &n);
	for(int i=1; i<=n; ++i) scanf("%lld", a+i);
	for(int i=1; i<=n; ++i) scanf("%lld", b+i);
	
	ll ans = 0, s = 0, sa = 0, sb = 0;
	for(int i=n; i>=1; --i) {
		sa += a[i]*(n+1-i)%P; sa%=P; sb += b[i]*(n+1-i)%P; sb%=P;
		ll del = ((a[i]*sb%P + b[i]*sa%P)%P + P - a[i]*b[i]%P*(n-i+1)%P)%P;
		s += del; s %= P;
		ans += s; ans %= P;
	}
	printf("%lld\n", ans);
	
	return 0;
}

# U129453 「EZEC-4.5」占座位

题解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll, ll> f;
ll n, k;
ll dfs(ll n) {
	if(f[n]) return f[n];
	if(n < 2*k+2) return f[n] = 1;
	return f[n] = dfs(n/2) + dfs(n-n/2);
}
int main() {
	scanf("%lld%lld", &n, &k);
	if(k == 0) printf("%lld\n", n); else printf("%lld\n", dfs(n));
	return 0;
}

# P1182 数列分段 Section II

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m; ll a[N];
bool check(ll v) {
	ll sum = 0, pt = 0;
	int i=1;
	while(i<=n) {
		while(i<=n && sum + a[i] <= v) {
			sum += a[i];
			++i;
		}
		++pt; if(pt > m) return false; sum = 0;
	}
	return true;
}
int main() {
	//freopen("p1182_1.in","r",stdin);
	scanf("%d%d", &n, &m);
	
	ll l=1, r=1e9;
	for(int i=1; i<=n; ++i) {
		scanf("%lld", a+i);
		l = max(l, a[i]);
	}
	
	while(l < r-1) {
		ll mid = l+(r-l)/2;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	if(check(l)) printf("%lld\n", l); else printf("%lld\n", r);
	
	return 0;
}

# P2822 组合数问题

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N = 2200, INF = 0x3f3f3f3f;
int c[N][N], sum[N][N];
int T, k;
int main() {
	
	scanf("%d%d", &T, &k);
	c[0][0] = 1;
	for(int i=1; i<=2000; ++i) {
		c[i][0] = 1;
		for(int j=1; j<=i; ++j) {
			c[i][j] = c[i-1][j-1] + c[i-1][j];
			c[i][j] %= k;
		}
	}
	for(int i=0; i<=2000; ++i) {
		for(int j=0; j<=i; ++j) {
			sum[i][j] = (c[i][j] == 0);
		}
	}
	for(int i=0; i<=2000; ++i) {
		for(int j=1; j<=2000; ++j) {
			sum[i][j] += sum[i][j-1];
		}
	}
	for(int j=0; j<=2000; ++j) {
		for(int i=1; i<=2000; ++i) {
			sum[i][j] += sum[i-1][j];
		}
	}
	while(T--) {
		int n, m;
		scanf("%d%d", &n, &m);
		printf("%d\n", sum[n][min(n,m)]);	
	}
	return 0;
}

# P1007 独木桥

求最大时间时,把碰面想象成交换身份即可

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int l, n, p[5005];
int main() {
	
	scanf("%d%d", &l, &n);
	for(int i=1; i<=n; ++i) scanf("%d", p+i);
	
	int ans1 = 0;
	for(int i=1; i<=n; ++i) {
		ans1 = max(ans1, min(p[i], l+1-p[i]));
	}
	int ans2 = 0;
	for(int i=1; i<=n; ++i) {
		ans2 = max(ans2, max(p[i], l+1-p[i]));
	}
	printf("%d %d\n", ans1, ans2);
	return 0;
}
更新于