社区讨论

MnZn有一个问题

cchrisgr_pretty_girl
P1912[NOI2009] 诗人小G参与者 1已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mhj0usme
此快照首次捕获于
2025/11/03 18:53
4 个月前
此快照最后确认于
2025/11/03 18:53
4 个月前
查看原帖
为什么存字符串长度前缀和的数组用 int 过不了(wa on test 2, 8 9, 10)，用 long double 就能过，句子的总长不应该小于等于 30×nmax30 \times n_{max} 也就是小于 int 的范围吗？
code（只有第四五行定义数组的地方有区别）
AC代码
CPP
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n, l, p, lst[N];
long double f[N], len[N];
string s[N];
struct node { int x, l, r; };
inline long double pow(long double x, int y) {
	long double ret = 1;
	while(y) {
		if(y & 1) ret *= x;
		x *= x, y >>= 1;
	}
	return ret;
}
inline void print(int x) {
	if(!x) return;
	print(lst[x]);
	for(int i = lst[x] + 1; i < x; ++i) cout << s[i] << ' ';
	cout << s[x] << endl;
	//putchar('\n');
}
int main() {
	//freopen("1.txt", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) {
		cin >> n >> l >> p;
		for(int i = 1; i <= n; ++i) {
			cin >> s[i];
			len[i] = len[i - 1] + s[i].size();
		}
		deque<node> q;
		q.push_back({0, 1, n});
		for(int i = 1; i <= n; ++i) {
			node aa = q.front();
			q.pop_front();
			if(aa.l + 1 <= aa.r) 
				q.push_front({aa.x, aa.l + 1, aa.r});
            //cout << i << "  " << aa.x << endl;
			lst[i] = aa.x, f[i] = f[aa.x] + pow(abs(len[i] - len[aa.x] + i - aa.x - 1 - l), p);
			while(!q.empty()) {
				aa = q.back();
				if(f[aa.x] + pow(abs(len[aa.l]-len[aa.x]+aa.l-aa.x-1-l),p) > f[i]+pow(abs(len[aa.l]-len[i]+aa.l-i-1-l), p)) 
					q.pop_back();
				else if(f[aa.x] + pow(abs(len[aa.r]-len[aa.x]+aa.r-aa.x-1-l),p) <= f[i]+pow(abs(len[aa.r]-len[i]+aa.r-i-1-l), p)) {
					if(aa.r<n) q.push_back({i, aa.r+1, n});
					break;
				} else {
					int ll = aa.l, rr = aa.r;
					while(ll <= rr) {
						int mid = ll + rr >> 1;
						if(f[aa.x]+pow(abs(len[mid]-len[aa.x]+mid-aa.x-1-l),p) > f[i]+pow(abs(len[mid]-len[i]+mid-i-1-l), p)) rr = mid - 1;
						else ll = mid + 1;
					}
					q.pop_back();
                    //if(i == 12) cout << rr << endl;
					q.push_back({aa.x, aa.l, rr}), q.push_back({i, rr + 1, n});
					break;
				}
			} if(q.empty()) q.push_back({i, i + 1, n});
		}
		if(f[n] > 1e18) cout << "Too hard to arrange" << endl;
		else {
            cout << (long long)f[n] << endl;
			//for(int i = 1; i <= n; ++i) cout << i << "  " << lst[i] << "  " << f[i] << "  " << s[i] << endl;
			print(n);
		}
		cout << "--------------------" << endl;
	}
	return 0;
}
WA代码
CPP
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n, l, p, len[N], lst[N];
long double f[N];
string s[N];
struct node { int x, l, r; };
inline long double pow(long double x, int y) {
	long double ret = 1;
	while(y) {
		if(y & 1) ret *= x;
		x *= x, y >>= 1;
	}
	return ret;
}
inline void print(int x) {
	if(!x) return;
	print(lst[x]);
	for(int i = lst[x] + 1; i < x; ++i) cout << s[i] << ' ';
	cout << s[x] << endl;
	//putchar('\n');
}
int main() {
	//freopen("1.txt", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) {
		cin >> n >> l >> p;
		for(int i = 1; i <= n; ++i) {
			cin >> s[i];
			len[i] = len[i - 1] + s[i].size();
		}
		deque<node> q;
		q.push_back({0, 1, n});
		for(int i = 1; i <= n; ++i) {
			node aa = q.front();
			q.pop_front();
			if(aa.l + 1 <= aa.r) 
				q.push_front({aa.x, aa.l + 1, aa.r});
            //cout << i << "  " << aa.x << endl;
			lst[i] = aa.x, f[i] = f[aa.x] + pow(abs(len[i] - len[aa.x] + i - aa.x - 1 - l), p);
			while(!q.empty()) {
				aa = q.back();
				if(f[aa.x] + pow(abs(len[aa.l]-len[aa.x]+aa.l-aa.x-1-l),p) > f[i]+pow(abs(len[aa.l]-len[i]+aa.l-i-1-l), p)) 
					q.pop_back();
				else if(f[aa.x] + pow(abs(len[aa.r]-len[aa.x]+aa.r-aa.x-1-l),p) <= f[i]+pow(abs(len[aa.r]-len[i]+aa.r-i-1-l), p)) {
					if(aa.r<n) q.push_back({i, aa.r+1, n});
					break;
				} else {
					int ll = aa.l, rr = aa.r;
					while(ll <= rr) {
						int mid = ll + rr >> 1;
						if(f[aa.x]+pow(abs(len[mid]-len[aa.x]+mid-aa.x-1-l),p) > f[i]+pow(abs(len[mid]-len[i]+mid-i-1-l), p)) rr = mid - 1;
						else ll = mid + 1;
					}
					q.pop_back();
                    //if(i == 12) cout << rr << endl;
					q.push_back({aa.x, aa.l, rr}), q.push_back({i, rr + 1, n});
					break;
				}
			} if(q.empty()) q.push_back({i, i + 1, n});
		}
		if(f[n] > 1e18) cout << "Too hard to arrange" << endl;
		else {
            cout << (long long)f[n] << endl;
			//for(int i = 1; i <= n; ++i) cout << i << "  " << lst[i] << "  " << f[i] << "  " << s[i] << endl;
			print(n);
		}
		cout << "--------------------" << endl;
	}
	return 0;
}

回复

共 2 条回复，欢迎继续交流。

正在加载回复...