萌新袜子刚学 OI,求助 40pts
查看原帖
萌新袜子刚学 OI,求助 40pts
350270
CatFromMars楼主2025/6/2 22:09

如题,已经很努力的调试了,但是调不出来,有没有大佬可以帮忙看看呐 QAQ

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf = 1e8;
const int N = 100;
const int M = 100;
struct node {
	int u, last, step;
};
unordered_map <int, int> F;
unordered_map <int, unordered_map <int, int> > vis;
int limit;
int updt(int x, int y) {
	if(!x) return x;
	else return min(x, y);
}
vector <int> vec[N + 10];
int tot = 0;
void bfs() {
	queue <node> que;
	que.push((node){1, 0, 1});
	vis[1][0] = 1;
	while(!que.empty()) {
		const node fr = que.front(); que.pop();
        if(fr.step == limit) continue;
		const int u = fr.u;

		que.push((node){fr.u, fr.last + 1, fr.step + 1});
		
		if(fr.last <= 1) continue;
		ll v = 1ll * fr.u * 1ll * fr.last;
		if(v > inf) continue;
		if(!vis[v][fr.step + 1])
			tot++,
			vec[fr.step + 1].push_back(v), 
			vis[v][fr.step + 1] = 1, 
			// cout << v << ' ' << fr.step + 1 << endl, 
			que.push((node){(int)v, fr.last, fr.step + 1});
	}
}

int n, m;
int a[N + 10], w[N + 10], mc;
int f[N + 10][N * 2 + 10];
void updmin(int &x, int y) {
	x = min(x, y);
}
int qry(int x) {
	if(x <= limit) return 1;
	else {
		for(int i = 1; i <= limit; i++) {
			for(int k = 0; k < vec[i].size(); k++) {
				int w = vec[i][k];
				if(w > x) continue;

				if(x - w + i <= limit) return 1;

				for(int j = i; j + i <= limit; j++) {
					int l = 0, r = vec[j].size() - 1, pos = -1;
					while(l <= r) {
						int mid = (l + r) >> 1;
						if(vec[j][mid] + w <= limit) l = mid + 1, pos = mid;
						else r = mid - 1;
					}

					if(pos > 0) {
						int rest = w + vec[j][pos];
						if(x - rest + i + j <= limit) return 1;
					}
				}
			}
		}
	}
	return 0;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> mc;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= n; i++)
		cin >> w[i];

	memset(f, 0x3f, sizeof(f));
	f[0][mc] = 0;
	int rest = mc;
	for(int i = 0; i < n; i++) {
		for(int j = a[i + 1]; j <= mc; j++) {
			updmin(f[i + 1][j - a[i + 1]], f[i][j]);
			updmin(f[i + 1][min(j - a[i + 1] + w[i + 1], mc)], f[i][j] + 1);
		}
	}

	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= mc; j++)
			limit = max(limit, i - f[i][j]);
	bfs();
	for(int i = 1; i <= limit; i++)
		sort(vec[i].begin(), vec[i].end());

	while(m--) {
		int x;
		cin >> x;
		cout << qry(x) << '\n';
	}
}
2025/6/2 22:09
加载中...