商河网站建设,关联词有哪些四年级,app拉新项目一手渠道商,做网站建设一年能赚多少gym103117J. Ants
题意#xff1a;
n个蚂蚁在长度为1e91的木棍上#xff0c;第i个蚂蚁在ai位置上#xff0c;朝向为0/1#xff08;0表示左#xff0c;1表示右#xff09;,如果蚂蚁相遇则彼此调转方向。木棍两侧分别有厚度为a和b的墙#xff0c;蚂蚁每撞一次墙#xf…gym103117J. Ants
题意
n个蚂蚁在长度为1e91的木棍上第i个蚂蚁在ai位置上朝向为0/10表示左1表示右,如果蚂蚁相遇则彼此调转方向。木棍两侧分别有厚度为a和b的墙蚂蚁每撞一次墙墙的厚度就会减1当墙撞没时蚂蚁就会直接掉下去问最后一个蚂蚁掉下去的时间
题解
模拟题 有几点注意
蚂蚁相遇调转方向可以相当于方向没变一个蚂蚁需要撞两次墙才能回到原先的位置(墙没撞开)相当于周期为2len每个周期每只蚂蚁会对两侧的墙各撞一次所以我们可以将前面整数个周期都算完最后就剩下一轮直接模拟完事
思路很简单但是最后一轮的模拟很麻烦我和队友调了4个小时才改出来但是发现网上有很多简易的方法 我们用两个队列分别存向左向右的蚂蚁每次取出两个队列首的元素比较两个元素谁离端点更近更近的会先撞墙然后掉头加入另一个队列中直到墙撞开
代码 const int N 2e6 5;int n, a, b, p[N], d[N], L 1e9 1;LL s, ans; LL q1[N], q2[N];
int hh 1, tt, h 1, t;void inline work1() {LL u q1[hh];if (a) {a--;q2[t] u L;}else {ansmax(ans,u); }
}void inline work2() {LL u q2[h];if (b){b--;q1[tt] u L;} else {ansmax(ans, u);}
}int main() {read(n), read(a), read(b);for (int i 1; i n; i) read(p[i]);for (int i 1; i n; i) read(d[i]);LL tmp min(a, b) / n;a - n * tmp, b - tmp * n;s tmp * L * 2;for (int i 1; i n; i)if (d[i] 0) q1[tt] p[i];//左 for (int i n; i; i--)if (d[i] 1) q2[t] L - p[i];//右 while (hh tt || h t) {if (h t || (hh tt q1[hh] q2[h])) work1();//左边先到 else work2();}printf(%lld\n, ans s);return 0;
}
我和队友的代码 就是纯模拟讨论四种情况
// Problem: Ants
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/17624/J
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC target(avx)
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize(Ofast)
// created by myq
#include algorithm
#include cctype
#include climits
#include cmath
#include cstdio
#include cstdlib
#include cstring
#include iostream
#include list
#include map
#include queue
#include set
#include sstream
#include stack
#include string
#include unordered_map
#include unordered_set
#include vector
using namespace std;
typedef long long ll;
#define x first
#define y second
typedef pairint, int pii;
const int N 1000010;
const int mod 998244353;
#define int long long
int a[N];
int d[N];
int n, l, r;
signed main()
{ios::sync_with_stdio(0);cin n l r;int len 1e9 1;int j 0;for (int i 1; i n; i) {cin a[i];}int lcnt 0;int rcnt 0;int res1 0;int res2 0;for (int i 1; i n; i) {cin d[i];if (!d[i])lcnt, res1 max(res1, a[i]);elsercnt, res2 max(res2, len - a[i]);}int tt min(l / n, r / n);int res 0;res 2 * len * tt;l- tt * n;r- tt * n;if (l lcnt r rcnt) {// if (n 11)// cout 1 endl;vectorint vv;vectorint vv2;for (int i 1; i n; i)if (d[i])vv2.push_back(len - a[i]);for (int i 1; i n; i)if (!d[i])vv.push_back(a[i]);int L (l 0 ? (vv.size() ? vv.back() : 0) : vv[l - 1] len);int R (r 0 ? (vv2.size() ? vv2[0] : 0) : vv2[(int)vv2.size() - r] len);res max(L, R);}else if (l lcnt r rcnt) {// if (n 11)// cout 2 endl;r- rcnt;vectorint vv;vectorint vv2;for (int i 1; i n; i)if (d[i])vv2.push_back(len - a[i]);for (int i 1; i n; i)if (!d[i])vv.push_back(a[i]);if (l) {int tmp vv[l - 1] len;int tmp2 0;int tmp3 0;if (rcnt) {tmp2 vv2[0] len;}if (r) {int tr min(r, l);tmp3 vv[tr - 1] 2 * len;}res max({tmp, tmp2, tmp3});}else {res max((vv2.size() ? vv2[0] len : 0ll), vv.back());}}else if (l lcnt r rcnt) {// if (n 11)// cout 3 endl;vectorint vv;vectorint vv2;l- lcnt;for (int i 1; i n; i)if (d[i])vv2.push_back(len - a[i]);for (int i 1; i n; i)if (!d[i])vv.push_back(a[i]);if (r) {int tmp 0;int tmp2 vv2[vv2.size() - r] len;int tmp3 0;if (lcnt) {tmp vv.back() len;}if (l) {int tr min(l, r);tmp3 2 * len vv2[vv2.size() - tr];}res max({tmp3, tmp, tmp2});}else {res max((vv.size() ? len vv.back() : 0ll), vv2[0]);}}else if (l lcnt r rcnt) {// if (n 11)// cout 4 endl;res len;l- lcnt;r- rcnt;lcnt 0;rcnt 0;// if(n87)// coutresendl;for (int i 1; i n; i) {a[i] len - a[i];d[i]^ 1;if (!d[i])lcnt;elsercnt;}if (l lcnt r rcnt) {// if (n 11) {// cout 41 endl;// cout l r endl;// cout lcnt rcnt endl;// }vectorint vv;vectorint vv2;for (int i 1; i n; i)if (d[i])vv2.push_back(len - a[i]);for (int i 1; i n; i)if (!d[i])vv.push_back(a[i]);reverse(vv.begin(), vv.end());reverse(vv2.begin(), vv2.end());// sort(vv.begin(), vv.end());// sort(vv2.begin(), vv2.end(), greaterint());// if(n87)// coutvv[l-1]len vv2[(int)vv2.size() - r] len vv.back() vv2[0]endl;int L (l 0 ? (vv.size() ? vv.back() : 0) : vv[l - 1] len);int R (r 0 ? (vv2.size() ? vv2[0] : 0) : vv2[(int)vv2.size() - r] len);res max(L, R);}else if (l lcnt r rcnt) {// if (n 11)// cout 42 endl;r- rcnt;vectorint vv;vectorint vv2;for (int i 1; i n; i)if (d[i])vv2.push_back(len - a[i]);for (int i 1; i n; i)if (!d[i])vv.push_back(a[i]);reverse(vv.begin(), vv.end());reverse(vv2.begin(), vv2.end());if (l) {// if(n59)// coutl r lcnt rcntendl;int tmp vv[l - 1] len;int tmp2 0;int tmp3 0;if (rcnt) {tmp2 vv2[0] len;}if (r) {int tr min(r, l);tmp3 vv[tr - 1] 2 * len;}res max({tmp, tmp2, tmp3});}else {res max((vv2.size() ? vv2[0] len : 0ll), vv.back());}}else if (l lcnt r rcnt) {if (n 11)cout 43 endl;vectorint vv;vectorint vv2;l- lcnt;for (int i 1; i n; i)if (d[i])vv2.push_back(len - a[i]);for (int i 1; i n; i)if (!d[i])vv.push_back(a[i]);reverse(vv.begin(), vv.end());reverse(vv2.begin(), vv2.end());if (r) {int tmp 0;int tmp2 vv2[vv2.size() - r] len;int tmp3 0;if (lcnt) {tmp vv.back() len;}if (l) {int tr min(l, r);tmp3 2 * len vv2[vv2.size() - tr];}res max({tmp3, tmp, tmp2});}else {res max((vv.size() ? len vv.back() : 0ll), vv2[0]);}}}cout res endl;return 0;
}
/**
* In every life we have some trouble
* When you worry you make it double
* Dont worry,be happy.
**/
