前几天的比赛,很久没做题了,加上前几题数学成分重,只过了一题,简单写下。
A. Exam
构造数列,满足相邻两个数之差大于1。比较容易得出的结论是,个数比较大的时候，是完全可以奇偶分开
e.g: 1 3 5 7 9 2 4 6 8 这样是没有问题的，需要考虑个数少的时候情况特殊，1~4分开列出答案。需要主要4个数是可以2 4 1 3 这样排的。
我没正确考虑4个数情况，WA了两次。
#include#include #include using namespace std;int n;int main(){#ifdef LOCAL freopen("534A.in", "r", stdin);#endif cin >> n; if (n >= 5) { cout << n << endl; for (int i = 1; i <= n; i+=2) cout << i << ' '; for (int i = 2; i <= n; i+=2) cout << i << ' '; cout << endl; } else { if (n == 1) cout << "1\n1\n"; else if (n == 2) cout << "1\n1\n"; else if (n == 3) cout << "2\n1 3\n"; else if (n == 4) cout << "4\n2 4 1 3\n"; } return 0;}
B. Covered Path
贪心，保证在尽量多的点上速度都是尽量大的？如果时间内能加速到vt，那么比较显然的最优方案是一开始就按最大加速度，而最后的时候最大加速度（减速）
模拟的方法来完成，随时计算vt+t(remain)×d确保剩下时间能减速到vt，没讲太明白，见代码吧
#include#include #include using namespace std;int v0, vt, vh, t, d, s;int main(){#ifdef LOCAL freopen("534B.in", "r", stdin);#endif cin >> v0 >> vt; cin >> t >> d; if (v0 > vt) swap(v0, vt); t -= 1; vh = v0; s = v0; while (vh <= vt+(t-1)*d && t) { vh += min(d, vt+(t-1)*d-vh);// cout << vh << endl; s += vh; t--; } while (vh > vt || t) { s += vt; vt += min(d, vh-vt);// cout << vh << endl; t--; } cout << s << endl; return 0;}
C. Polycarpus' Dice
数学题，比如第一个骰子可以取1,2 那么A的取值范围就是(1+剩下骰子取最小)~(2+剩下骰子取最大)
倒过来可以通过A的取值确定该骰子取值范围，我的做法是在计算第i个骰子范围时
把该骰子的每个取值，得到的A的范围看作一条线段，第一条就是(1+剩下骰子取最小)~(1+剩下骰子取最大)，这样该骰子每一个取值构成一条线段，
按左边坐标排列起来，然后就是看A这个值，存在于多少条线段中，比较端点值来确定。
#include#include #include using namespace std;const int MAXN = 400000+50;int n;int d[MAXN];long long A, smin, smax;int main(){#ifdef LOCAL freopen("534C.in", "r", stdin);#endif scanf("%d%lld", &n, &A); for (int i = 0; i < n; i++) { scanf("%d", d+i); smin += 1; smax += d[i]; } for (int i = 0; i < n; i++) { int can; long long fl, fr, ll, lr, vmax; vmax = (smax - d[i]) - (smin - 1) + 1; fl = smin; fr = 1 + smax - d[i]; ll = d[i] + smin - 1; lr = smax; if (ll <= A && A <= fr) can = d[i]; else if (fl <= A && A <= ll) can = min(A - fl + 1, vmax); else can = min(lr - A + 1, vmax); printf("%d ", d[i] - can); } printf("\n"); return 0;}
马马虎虎的题解。别人并不能看懂。