寒鸽儿のBlog

这场人均AK罢，T2挂了(鬼晓得有负数哦，时间够还去剪枝就是作死)
Rnk12 300丢死人了

T1 解方程

取几个模数暴力就好了。听说自然溢出也能过？
复杂度$\mathcal{O(nr)}$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll m1 = 998244353, m2 = 19260817, m3 = 1000000007;
vector<ll> a, ans;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, l, r, cnt = 0;
	cin >> n >> l >> r;
	a.resize(n + 1);
	for(int i = 0; i <= n; ++i) cin >> a[i];
	for(int i = l; i <= r; ++i) {
		ll t1 = 1, t2 = 1, t3 = 1, a1 = 0, a2 = 0, a3 = 0;
		for(int j = 0; j <= n; ++j) {
			a1 = (a1 + (t1 * a[j]) % m1) % m1;
			a2 = (a2 + (t2 * a[j]) % m2) % m2;
			a3 = (a3 + (t3 * a[j]) % m3) % m3;
			t1 = t1 * i % m1;
			t2 = t2 * i % m2;
			t3 = t3 * i % m3;
		}
		if(a1 == 0 && a2 == 0 && a3 == 0) {
			ans.push_back(i);
			++cnt;
		}
	}
	cout << cnt << '\n';
	for(int i = 0; i < cnt; ++i) cout << ans[i] << '\n';
	return 0;
}

T2 求和问题

暴力dfs。
艹，竟然有负数，不要去用可行性剪枝。
复杂度$\mathcal{O(2^n)}$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<ll> x;
ll ans;
int n, k, q;

void dfs(int cur, ll sum, int cnt) {
	if(cur == n) {
		if(sum == q && k == cnt) ++ans;
		return;	
	}
	dfs(cur + 1, sum, cnt);
	if(cnt < k)
		dfs(cur + 1, sum + x[cur], cnt + 1);
}

bool cmp(ll a, ll b) {
	return a > b;	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k >> q;
	x.resize(n);
	for(int i = 0; i < n; ++i) {
		cin >> x[i];
	}
	sort(x.begin(), x.end(), cmp); 
	dfs(0, 0, 0);
	cout << ans << '\n';
	return 0;
}

T3 集合

先排序，枚举最小值，二分查最大值，中间的数都能选。
复杂度$\mathcal{O(nlogn + qlognlogn)}$(预处理2的幂表格应该是$\mathcal{O((n+q)logn)}$)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1000000007;

vector<ll> v;

int bsh(int l, int r, ll x) {
	while(l < r) {
		int mid = (l + r + 1) >> 1;
		if(v[mid] <= x) l = mid;
		else r = mid - 1;
	}
	return l;
}

ll qp(ll a, ll b) {
	ll res = 1 % mod;
	for(; b; b >>= 1) {
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll ans = 0;
	int n, k;
	cin >> n >> k;
	v.resize(n);
	for(int i = 0; i < n; ++i) cin >> v[i];
	sort(v.begin(), v.end());
	for(int i = 0; i < n; ++i) {
		int nxt = bsh(i, n - 1, v[i] + k);
		if(v[nxt] == v[i] + k) {
			ll len = nxt - i + 1 - 2;
			ans = (ans + qp(2, len)) % mod;
		}
	}
	cout << ans << '\n';
	return 0;
}

T4 求和

对于比较大的$k$采用暴力求,为$\mathcal{O(\frac{n}{k})}$。
比较小的$k$打个表预处理。
当$k$取到$\sqrt{n}$的时候从数学上讲对随机数据是理论最快的。
复杂度$\mathcal{O(q\sqrt{n})}$。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int bis = 315, maxn = 123456;
int a[maxn];
ll kd[bis + 10][bis + 10];

int main() {
	int n, q, k, b;
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; ++i)
		scanf("%d", a + i);
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= bis; ++j) {
			kd[j][i % j] += a[i];
		}
	}
	while(q--) {
		scanf("%d %d", &k, &b);
		if(k <= bis) {
			if(b > k) printf("0\n");
			else printf("%lld\n", kd[k][b]);
		} else {
			ll ans = 0;
			for(int i = 0; ((ll)i * k + b) <= n; ++i) {
				ans = ans + a[i * k + b];
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}