经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
洛谷模拟NOIP考试反思
来源:cnblogs  作者:Pleiades_Antares  时间:2018/10/8 8:55:51  对本文有异议

洛谷模拟NOIP考试反思

想法

考了这么简单的试qwq然而依然emmmmmm成绩不好
虽然本次难度应该是大于正常PJ难度的但还是很不理想,离预估分数差很多qwq
于是就有了本反思嘤嘤嘤

比赛链接

原比赛链接(已结束但仍然可提交)

题目解析反思

第一题

超简单(虽然仍然没做对)

第二题



代码扔上来qwq(虽然还是不会)

第三题



代码

第四题


毒瘤极了wodema
据说原来数据是50%那里的,但是出题人z某灵机一动加到了1000orz
于是很多人自然而然地想到了状压DP
普及组是到不了这个难度的,主要是z某他太坏了
50分做法(状压)

正解的100分正法并非毒瘤状压qwq

(有人说爆搜能骗40分?!)

讲评者

XD
---

TG

还是放一道TG第三题压压惊好了

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6. typedef long long int LL;
  7. const int Max_N(100050);
  8. const int Max_M(100050);
  9. const int Max_Q(100050);
  10.  
  11. template<typename Type>
  12. void gi(Type &Ret)
  13. {
  14.     Ret = 0;
  15.     char ch;
  16.     while (ch = getchar(), ch > '9' || ch < '0')
  17.         ;
  18.     do
  19.     {
  20.         (Ret *= 10) += ch - '0';
  21.     }
  22.     while (ch = getchar(), ch >= '0' && ch <= '9');
  23. }
  24.  
  25. inline int Abs(const int &x)
  26. {
  27.     return x >= 0 ? x : -x;
  28. }
  29.  
  30. int N, M, Q, X1[Max_N + Max_Q], Y1[Max_N + Max_Q], X2[Max_N + Max_Q], Y2[Max_N + Max_Q];
  31. int L[Max_N + Max_Q], R[Max_N + Max_Q], D[Max_N + Max_Q], U[Max_N + Max_Q], Anc[60][Max_N];
  32. LL T[Max_N + Max_Q], Sum[60][Max_N];
  33.  
  34. #define LEFT  (segt[cur].l)
  35. #define RIGHT (segt[cur].r)
  36. #define MID   (segt[cur].mid)
  37. #define COV   (segt[cur].Cov)
  38. #define TAG   (segt[cur].Tag)
  39. #define LCH   (cur << 1)
  40. #define RCH   ((cur << 1) | 1)
  41.  
  42. struct node
  43. {
  44.     int l, r, mid, Cov, Tag;
  45. };
  46. node segt[Max_M << 2];
  47. int C[Max_M];
  48.  
  49. void build_tree(const int &cur, const int &l, const int &r)
  50. {
  51.     LEFT = l, RIGHT = r, MID = l + ((- l) >> 1), COV = TAG = 0;
  52.     if (== r)
  53.         return;
  54.     build_tree(LCH, l, MID), build_tree(RCH, MID + 1, r);
  55. }
  56.  
  57. inline void cover(const int &cur, const int &v)
  58. {
  59.     COV = TAG = v;
  60. }
  61.  
  62. inline void pushdown(const int &cur)
  63. {
  64.     if (TAG)
  65.         cover(LCH, TAG), cover(RCH, TAG), TAG = 0;
  66. }
  67.  
  68. void cover(const int &cur, const int &l, const int &r, const int &v)
  69. {
  70.     if (LEFT == l && RIGHT == r)
  71.     {
  72.         cover(cur, v);
  73.         return;
  74.     }
  75.     pushdown(cur);
  76.     if (<= MID)
  77.         cover(LCH, l, r, v);
  78.     else
  79.         if (> MID)
  80.             cover(RCH, l, r, v);
  81.         else
  82.             cover(LCH, l, MID, v), cover(RCH, MID + 1, r, v);
  83. }
  84.  
  85. int query(const int &cur, const int &pos)
  86. {
  87.     if (LEFT == RIGHT)
  88.         return COV;
  89.     pushdown(cur);
  90.     if (pos <= MID)
  91.         return query(LCH, pos);
  92.     else
  93.         return query(RCH, pos);
  94. }
  95.  
  96. inline bool compL(const int &a, const int &b)
  97. {
  98.     return min(X1[a], X2[a]) < min(X1[b], X2[b]);
  99. }
  100.  
  101. void goL()
  102. {
  103.     build_tree(1, 0, M), memset(C, 0, sizeof(C));
  104.     sort(+ 1, L + 1 + L[0], compL);
  105.     sort(+ 1, R + 1 + R[0], compL);
  106.     sort(+ 1, D + 1 + D[0], compL);
  107.     sort(+ 1, U + 1 + U[0], compL);
  108.     for (int l = 1, r = 1, d = 1, u = 1, a, b, p;<= L[0];++l)
  109.     {
  110.         p = L[l];
  111.         while (<= R[0] && X1[R[r]] <= X2[p])
  112.         {
  113.             if (R[r] <= N)
  114.                 C[Y2[R[r]]] = R[r];
  115.             ++r;
  116.         }
  117.         while ((<= D[0] && X2[D[d]] <= X2[p]) || (<= U[0] && X2[U[u]] <= X2[p]))
  118.             if ((<= D[0]) && (> U[0] || X2[D[d]] <= X2[U[u]]))
  119.             {
  120.                 if (D[d] <= N)
  121.                     cover(1, Y2[D[d]], Y1[D[d]], D[d]);
  122.                 ++d;
  123.             }
  124.             else
  125.             {
  126.                 if (U[u] <= N)
  127.                     cover(1, Y1[U[u]], Y2[U[u]], U[u]);
  128.                 ++u;
  129.             }
  130.         a = query(1, Y2[p]), b = C[Y2[p]];
  131.         if (<= N)
  132.         {
  133.             if (== 0 && b == 0)
  134.                 Anc[0][p] = -1;
  135.             else
  136.                 if (&& (== 0 || X2[p] - X2[a] < X2[p] - X2[b]))
  137.                     Anc[0][p] = a, Sum[0][p] = (X2[p] - X2[a]) + Abs(Y2[p] - Y2[a]);
  138.                 else
  139.                     Anc[0][p] = b, Sum[0][p] = X2[p] - X2[b];
  140.         }
  141.         else
  142.         {
  143.             if (== 0 && b == 0)
  144.                 X2[p] = max(0LL, X2[p] - T[p]), T[p] = 0LL;
  145.             else
  146.                 if (&& (== 0 || X2[p] - X2[a] < X2[p] - X2[b]))
  147.                     if (T[p] <= X2[p] - X2[a])
  148.                         X2[p] -= T[p], T[p] = 0LL;
  149.                     else
  150.                     {
  151.                         T[p] -= X2[p] - X2[a], X2[p] = X2[a];
  152.                         if (T[p] <= Abs(Y2[p] - Y2[a]))
  153.                         {
  154.                             if (Y2[a] <= Y2[p])
  155.                                 Y2[p] -= T[p];
  156.                             else
  157.                                 Y2[p] += T[p];
  158.                             T[p] = 0LL;
  159.                         }
  160.                         else
  161.                             T[p] -= Abs(Y2[p] - Y2[a]), X2[p] = a;
  162.                     }
  163.                 else
  164.                     if (T[p] <= Abs(X2[p] - X2[b]))
  165.                     {
  166.                         if (X2[b] <= X2[p])
  167.                             X2[p] -= T[p];
  168.                         else
  169.                             X2[p] += T[p];
  170.                         T[p] = 0LL;
  171.                     }
  172.                     else
  173.                         T[p] -= Abs(X2[p] - X2[b]), X2[p] = b;
  174.         }
  175.     }
  176. }
  177.  
  178. inline int getR(const int &x)
  179. {
  180.     return max(X1[x], X2[x]);
  181. }
  182.  
  183. inline bool compR(const int &a, const int &b)
  184. {
  185.     return getR(a) > getR(b);
  186. }
  187.  
  188. void goR()
  189. {
  190.     build_tree(1, 0, M), memset(C, 0, sizeof(C));
  191.     sort(+ 1, L + 1 + L[0], compR);
  192.     sort(+ 1, R + 1 + R[0], compR);
  193.     sort(+ 1, D + 1 + D[0], compR);
  194.     sort(+ 1, U + 1 + U[0], compR);
  195.     for (int l = 1, r = 1, d = 1, u = 1, a, b, p;<= R[0];++r)
  196.     {
  197.         p = R[r];
  198.         while (<= L[0] && getR(L[l]) >= getR(p))
  199.         {
  200.             if (L[l] <= N)
  201.                 C[Y2[L[l]]] = L[l];
  202.             ++l;
  203.         }
  204.         while ((<= D[0] && getR(D[d]) >= getR(p)) || (<= U[0] && getR(U[u]) >= getR(p)))
  205.             if ((<= D[0]) && (> U[0] || getR(D[d]) >= getR(U[u])))
  206.             {
  207.                 if (D[d] <= N)
  208.                     cover(1, Y2[D[d]], Y1[D[d]], D[d]);
  209.                 ++d;
  210.             }
  211.             else
  212.             {
  213.                 if (U[u] <= N)
  214.                     cover(1, Y1[U[u]], Y2[U[u]], U[u]);
  215.                 ++u;
  216.             }
  217.         a = query(1, Y2[p]), b = C[Y2[p]];
  218.         if (<= N)
  219.         {
  220.             if (== 0 && b == 0)
  221.                 Anc[0][p] = -1;
  222.             else
  223.                 if (&& (== 0 || X2[a] - X2[p] < X2[b] - X2[p]))
  224.                     Anc[0][p] = a, Sum[0][p] = (X2[a] - X2[p]) + Abs(Y2[p] - Y2[a]);
  225.                 else
  226.                     Anc[0][p] = b, Sum[0][p] = X2[b] - X2[p];
  227.         }
  228.         else
  229.         {
  230.             if (== 0 && b == 0)
  231.                 X2[p] = min(* 1LL, X2[p] + T[p]), T[p] = 0LL;
  232.             else
  233.                 if (&& (== 0 || X2[a] - X2[p] < X2[b] - X2[p]))
  234.                     if (T[p] <= X2[a] - X2[p])
  235.                         X2[p] += T[p], T[p] = 0LL;
  236.                     else
  237.                     {
  238.                         T[p] -= X2[a] - X2[p], X2[p] = X2[a];
  239.                         if (T[p] <= Abs(Y2[p] - Y2[a]))
  240.                         {
  241.                             if (Y2[a] <= Y2[p])
  242.                                 Y2[p] -= T[p];
  243.                             else
  244.                                 Y2[p] += T[p];
  245.                             T[p] = 0LL;
  246.                         }
  247.                         else
  248.                             T[p] -= Abs(Y2[p] - Y2[a]), X2[p] = a;
  249.                     }
  250.                 else
  251.                     if (T[p] <= Abs(X2[b] - X2[p]))
  252.                     {
  253.                         if (X2[b] <= X2[p])
  254.                             X2[p] -= T[p];
  255.                         else
  256.                             X2[p] += T[p];
  257.                         T[p] = 0LL;
  258.                     }
  259.                     else
  260.                         T[p] -= Abs(X2[b] - X2[p]), X2[p] = b;
  261.         }
  262.     }
  263. }
  264.  
  265. inline int getD(const int &x)
  266. {
  267.     return min(Y1[x], Y2[x]);
  268. }
  269.  
  270. inline bool compD(const int &a, const int &b)
  271. {
  272.     return getD(a) < getD(b);
  273. }
  274.  
  275. void goD()
  276. {
  277.     build_tree(1, 0, M), memset(C, 0, sizeof(C));
  278.     sort(+ 1, L + 1 + L[0], compD);
  279.     sort(+ 1, R + 1 + R[0], compD);
  280.     sort(+ 1, D + 1 + D[0], compD);
  281.     sort(+ 1, U + 1 + U[0], compD);
  282.     for (int l = 1, r = 1, d = 1, u = 1, a, b, p;<= D[0];++d)
  283.     {
  284.         p = D[d];
  285.         while (<= U[0] && getD(U[u]) <= getD(p))
  286.         {
  287.             if (U[u] <= N)
  288.                 C[X2[U[u]]] = U[u];
  289.             ++u;
  290.         }
  291.         while ((<= L[0] && getD(L[l]) <= getD(p)) || (<= R[0] && getD(R[r]) <= getD(p)))
  292.             if ((<= L[0]) && (> R[0] || getD(L[l]) <= getD(R[r])))
  293.             {
  294.                 if (L[l] <= N)
  295.                     cover(1, X2[L[l]], X1[L[l]], L[l]);
  296.                 ++l;
  297.             }
  298.             else
  299.             {
  300.                 if (R[r] <= N)
  301.                     cover(1, X1[R[r]], X2[R[r]], R[r]);
  302.                 ++r;
  303.             }
  304.         a = query(1, X2[p]), b = C[X2[p]];
  305.         if (<= N)
  306.         {
  307.             if (== 0 && b == 0)
  308.                 Anc[0][p] = -1;
  309.             else
  310.                 if (&& (== 0 || Y2[p] - Y2[a] < Y2[p] - Y2[b]))
  311.                     Anc[0][p] = a, Sum[0][p] = (Y2[p] - Y2[a]) + Abs(X2[p] - X2[a]);
  312.                 else
  313.                     Anc[0][p] = b, Sum[0][p] = Y2[p] - Y2[b];
  314.         }
  315.         else
  316.         {
  317.             if (== 0 && b == 0)
  318.                 Y2[p] = max(0LL, Y2[p] - T[p]), T[p] = 0LL;
  319.             else
  320.                 if (&& (== 0 || Y2[p] - Y2[a] < Y2[p] - Y2[b]))
  321.                     if (T[p] <= Y2[p] - Y2[a])
  322.                         Y2[p] -= T[p], T[p] = 0LL;
  323.                     else
  324.                     {
  325.                         T[p] -= Y2[p] - Y2[a], Y2[p] = Y2[a];
  326.                         if (T[p] <= Abs(X2[p] - X2[a]))
  327.                         {
  328.                             if (X2[a] <= X2[p])
  329.                                 X2[p] -= T[p];
  330.                             else
  331.                                 X2[p] += T[p];
  332.                             T[p] = 0LL;
  333.                         }
  334.                         else
  335.                             T[p] -= Abs(X2[p] - X2[a]), X2[p] = a;
  336.                     }
  337.                 else
  338.                     if (T[p] <= Abs(Y2[p] - Y2[b]))
  339.                     {
  340.                         if (Y2[b] <= Y2[p])
  341.                             Y2[p] -= T[p];
  342.                         else
  343.                             Y2[p] += T[p];
  344.                         T[p] = 0LL;
  345.                     }
  346.                     else
  347.                         T[p] -= Abs(Y2[p] - Y2[b]), X2[p] = b;
  348.         }
  349.     }
  350. }
  351.  
  352. inline int getU(const int &x)
  353. {
  354.     return max(Y1[x], Y2[x]);
  355. }
  356.  
  357. inline bool compU(const int &a, const int &b)
  358. {
  359.     return getU(a) > getU(b);
  360. }
  361.  
  362. void goU()
  363. {
  364.     build_tree(1, 0, M), memset(C, 0, sizeof(C));
  365.     sort(+ 1, L + 1 + L[0], compU);
  366.     sort(+ 1, R + 1 + R[0], compU);
  367.     sort(+ 1, D + 1 + D[0], compU);
  368.     sort(+ 1, U + 1 + U[0], compU);
  369.     for (int l = 1, r = 1, d = 1, u = 1, a, b, p;<= U[0];++u)
  370.     {
  371.         p = U[u];
  372.         while (<= D[0] && getU(D[d]) >= getU(p))
  373.         {
  374.             if (D[d] <= N)
  375.                 C[X2[D[d]]] = D[d];
  376.             ++d;
  377.         }
  378.         while ((<= L[0] && getU(L[l]) >= getU(p)) || (<= R[0] && getU(R[r]) >= getU(p)))
  379.             if ((<= L[0]) && (> R[0] || getU(L[l]) >= getU(R[r])))
  380.             {
  381.                 if (L[l] <= N)
  382.                     cover(1, X2[L[l]], X1[L[l]], L[l]);
  383.                 ++l;
  384.             }
  385.             else
  386.             {
  387.                 if (R[r] <= N)
  388.                     cover(1, X1[R[r]], X2[R[r]], R[r]);
  389.                 ++r;
  390.             }
  391.         a = query(1, X2[p]), b = C[X2[p]];
  392.         if (<= N)
  393.         {
  394.             if (== 0 && b == 0)
  395.                 Anc[0][p] = -1;
  396.             else
  397.                 if (&& (== 0 || Y2[a] - Y2[p] < Y2[b] - Y2[p]))
  398.                     Anc[0][p] = a, Sum[0][p] = (Y2[a] - Y2[p]) + Abs(X2[p] - X2[a]);
  399.                 else
  400.                     Anc[0][p] = b, Sum[0][p] = Y2[b] - Y2[p];
  401.         }
  402.         else
  403.         {
  404.             if (== 0 && b == 0)
  405.                 Y2[p] = min(* 1LL, Y2[p] + T[p]), T[p] = 0LL;
  406.             else
  407.                 if (&& (== 0 || Y2[a] - Y2[p] < Y2[b] - Y2[p]))
  408.                     if (T[p] <= Y2[a] - Y2[p])
  409.                         Y2[p] += T[p], T[p] = 0LL;
  410.                     else
  411.                     {
  412.                         T[p] -= Y2[a] - Y2[p], Y2[p] = Y2[a];
  413.                         if (T[p] <= Abs(X2[p] - X2[a]))
  414.                         {
  415.                             if (X2[a] <= X2[p])
  416.                                 X2[p] -= T[p];
  417.                             else
  418.                                 X2[p] += T[p];
  419.                             T[p] = 0LL;
  420.                         }
  421.                         else
  422.                             T[p] -= Abs(X2[p] - X2[a]), X2[p] = a;
  423.                     }
  424.                 else
  425.                     if (T[p] <= Abs(Y2[b] - Y2[p]))
  426.                     {
  427.                         if (Y2[b] <= Y2[p])
  428.                             Y2[p] -= T[p];
  429.                         else
  430.                             Y2[p] += T[p];
  431.                         T[p] = 0LL;
  432.                     }
  433.                     else
  434.                         T[p] -= Abs(Y2[b] - Y2[p]), X2[p] = b;
  435.         }
  436.     }
  437. }
  438.  
  439. void get(const int &i, const int &u)
  440. {
  441.     if (X2[u] < X1[u])
  442.         X2[i] = max(0LL, X2[i] - T[i]);
  443.     if (X2[u] > X1[u])
  444.         X2[i] = min(* 1LL, X2[i] + T[i]);
  445.     if (Y2[u] < Y1[u])
  446.         Y2[i] = max(0LL, Y2[i] - T[i]);
  447.     if (Y2[u] > Y1[u])
  448.         Y2[i] = min(* 1LL, Y2[i] + T[i]);
  449. }
  450.  
  451. int main()
  452. {
  453.  
  454.     gi(N), gi(M);
  455.     for (int i = 1;<= N;++i)
  456.     {
  457.         gi(X1[i]), gi(Y1[i]), gi(X2[i]), gi(Y2[i]);
  458.         if (X2[i] < X1[i])
  459.             L[++L[0]] = i;
  460.         if (X2[i] > X1[i])
  461.             R[++R[0]] = i;
  462.         if (Y2[i] < Y1[i])
  463.             D[++D[0]] = i;
  464.         if (Y2[i] > Y1[i])
  465.             U[++U[0]] = i;
  466.     }
  467.     gi(Q);
  468.     for (int i = 1;<= Q;++i)
  469.     {
  470.         gi(X2[+ i]), gi(Y2[+ i]), X1[+ i] = X2[+ i], Y1[+ i] = Y2[+ i];
  471.         char op[5];
  472.         scanf("%s", op);
  473.         if (*op == 'L')
  474.             L[++L[0]] = N + i;
  475.         if (*op == 'R')
  476.             R[++R[0]] = N + i;
  477.         if (*op == 'D')
  478.             D[++D[0]] = N + i;
  479.         if (*op == 'U')
  480.             U[++U[0]] = N + i;
  481.         gi(T[+ i]);
  482.     }
  483.     goL(), goR(), goD(), goU();
  484.     for (int j = 1;<= 59;++j)
  485.         for (int i = 1;<= N;++i)
  486.             if (Anc[- 1][i] == -1)
  487.                 Anc[j][i] = -1;
  488.             else
  489.             {
  490.                 Anc[j][i] = Anc[- 1][Anc[- 1][i]];
  491.                 Sum[j][i] = Sum[- 1][i] + Sum[- 1][Anc[- 1][i]];
  492.                 Sum[j][i] = min(Sum[j][i], 1000000000000000LL + 1LL);
  493.             }
  494.     for (int i = N + 1, u;<= N + Q;++i)
  495.     {
  496.         if (T[i])
  497.         {
  498.             u = X2[i];
  499.             for (int j = 59;>= 0;--j)
  500.                 if (Anc[j][u] != -1 && Sum[j][u] <= T[i])
  501.                     T[i] -= Sum[j][u], u = Anc[j][u];
  502.             X2[i] = X2[u], Y2[i] = Y2[u];
  503.             if (Anc[0][u] == -1)
  504.                 get(i, u);
  505.             else
  506.             {
  507.                 if (X2[u] < X1[u])
  508.                     if (T[i] <= X2[i] - X2[Anc[0][u]])
  509.                         get(i, u);
  510.                     else
  511.                         T[i] -= X2[i] - X2[Anc[0][u]], X2[i] = X2[Anc[0][u]], get(i, Anc[0][u]);
  512.                 if (X2[u] > X1[u])
  513.                     if (T[i] <= X2[Anc[0][u]] - X2[i])
  514.                         get(i, u);
  515.                     else
  516.                         T[i] -= X2[Anc[0][u]] - X2[i], X2[i] = X2[Anc[0][u]], get(i, Anc[0][u]);
  517.                 if (Y2[u] < Y1[u])
  518.                     if (T[i] <= Y2[i] - Y2[Anc[0][u]])
  519.                         get(i, u);
  520.                     else
  521.                         T[i] -= Y2[i] - Y2[Anc[0][u]], Y2[i] = Y2[Anc[0][u]], get(i, Anc[0][u]);
  522.                 if (Y2[u] > Y1[u])
  523.                     if (T[i] <= Y2[Anc[0][u]] - Y2[i])
  524.                         get(i, u);
  525.                     else
  526.                         T[i] -= Y2[Anc[0][u]] - Y2[i], Y2[i] = Y2[Anc[0][u]], get(i, Anc[0][u]);
  527.             }
  528.         }
  529.         printf("%d %d\n", X2[i], Y2[i]);
  530.     }
  531.     return 0;

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号