CCF-CSP真题《202309-4 阴阳龙》思路+python，c++满分题解

以你之姓@ 2024-02-19 08:31 41阅读 0赞

> 想查看其他题的真题及题解的同学可以前往查看：[CCF-CSP真题附题解大全][CCF-CSP]

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>202309-4</td> 
  </tr> 
  <tr> 
   <td>试题名称：</td> 
   <td>阴阳龙</td> 
  </tr> 
  <tr> 
   <td>时间限制：</td> 
   <td>2.0s</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>1.0GB</td> 
  </tr> 
  <tr> 
   <td>问题描述：</td> 
   <td> <h3>问题描述</h3> <p>西西艾弗岛的下方是一个庞大的遗迹群，神兽“阴阳龙”栖居在这个遗迹群中。</p> <p>为了得到这件宝物，西西艾弗遗迹探索有限公司（以下简称“公司”）派遣了&nbsp;p&nbsp;名员工前往遗迹群，这些员工依次编号为&nbsp;1&nbsp;到&nbsp;p。</p> <p>遗迹可以视为一个大小为&nbsp;n×m&nbsp;的网格，左下角坐标&nbsp;(1,1)，右上角坐标&nbsp;(n,m)。初始时，第&nbsp;i&nbsp;名员工所在的位置是&nbsp;(xi,yi)。<strong>保证所有员工初始所在的位置两两不同</strong>。</p> <p>作为神兽，阴阳龙有着特殊之处。当其在&nbsp;p=(u,v)&nbsp;位置以强度&nbsp;t∈[1,7]&nbsp;现身时，会导致遗迹群的环境发生阴和阳的变转，从而导致在遗迹中的人的位置发生变化。</p> <p>具体来说，阴阳龙首先观察右、右上、上、左上、左、左下、下和右下这八个方向，并在这八个方向找到和阴阳龙“距离”最近的员工（不包括&nbsp;p）的“距离”。<br> 其中，垂直和水平方向的“距离”是指员工和阴阳龙连线的长度；斜线方向的“距离”是指员工和阴阳龙连线在水平方向上投影的长度。设想从阴阳龙的位置同时出发，<br> 分别向这 8 个方向前进，每一单位时间运动 1 个“距离”。如果在某一时刻，在某一方向刚好遇到一位员工，则此时前进的距离即被记为&nbsp;k；否则，如果在某一时刻，<br> 在某一方向上刚好到达遗迹的边界，但是在此之前任何方向上都没有遇到员工，则令&nbsp;k=0。形式化描述上述确定&nbsp;k&nbsp;的方法是：</p> <p>记&nbsp;d0&nbsp;到&nbsp;d7&nbsp;依次为向量&nbsp;(1,0),(1,1),(0,1),(−1,1),(−1,0),(−1,−1),(0,−1),(1,−1)，令：<br> K1={k∈N+∣∃i∈[0,7],j∈[1,p],s.t.(xj,yj)=p+kdi}<br> K2={k∈N+∣∀i∈[0,7],(p+kdi)∈[1,n]×[1,m]}</p> <p>其中：</p> 
    <ul> 
     <li>(xi,yi)&nbsp;为第&nbsp;i&nbsp;名员工在此次阴阳龙现身前的位置（这个位置可能和其初始位置不同，但为了方便起见，我们使用同一个记号）；</li> 
     <li>K1&nbsp;为所有员工到阴阳龙距离组成的集合；</li> 
     <li>K2&nbsp;为从阴阳龙出发直至在某一方向抵达边界所包括全部的距离组成的集合。</li> 
    </ul><p>若&nbsp;K=K1⋂K2=∅，则令&nbsp;k=0；否则令&nbsp;k=minK&gt;0。</p> <p>例如，参考下图中的例子，其中左下角为&nbsp;(1,1)，右上角为&nbsp;(7,7)，共有&nbsp;8&nbsp;名员工，位置如图。</p> <p>若&nbsp;p=(4,4)，那么员工 1 刚好在阴阳龙所在位置，不计入；员工 3 不在阴阳龙的 8 个方向上，不计入；员工 2、4、5、6 与阴阳龙“距离”是 2；员工 7、8、9 与阴阳龙“距离”是 3，因此有&nbsp;K1=2,3。由于与阴阳龙“距离”为 3 就到达了遗迹的边界，所以有&nbsp;K2=1,2,3。因此&nbsp;k=2。</p> <p>若&nbsp;p=(2,2)，那么员工 2、3、7、8、9都不在阴阳龙的 8 个方向上，不计入；员工 1、6 与阴阳龙的“距离”是 2；员工 4、5 与阴阳龙的“距离”是 4，因此有&nbsp;K1=2,4。由于与阴阳龙“距离”为 1 时，就在向下、向左、向左下三个方向上到达了遗迹的边界，所以有&nbsp;K2=1。因此&nbsp;k=0。</p> <p><img alt="" height="850" src="https://img-blog.csdnimg.cn/103316c64a0a40479e5174bcf46efec3.png" width="853"><br> 变化前各员工位置</p> <p>如果&nbsp;k&gt;0，则将八个方向上的距离为&nbsp;k&nbsp;的位置上的员工以&nbsp;p&nbsp;为中心逆时针旋转&nbsp;t&nbsp;倍的八分之一个圆周的角度。形式化地：</p> 
    <ul> 
     <li> <p>若&nbsp;k=0，则什么也不会发生。</p> </li> 
     <li> <p>否则，∀i∈[0,7]，若&nbsp;p+kdi&nbsp;位置上有员工，那么其该员工会被移动到&nbsp;p+kd(i+t)mod8。</p> </li> 
    </ul><p>易知在所有员工移动结束后，每个位置上仍至多有一个员工。例如，在上图所示的例子中取&nbsp;p=(4,4),t=1，则变化后各员工所在位置如下图所示。</p> <p><img alt="" height="853" src="https://img-blog.csdnimg.cn/2767254bcba24d7b8354d34a2fe70713.png" width="855"><br> 变化后各员工位置</p> <p>在全部员工进入遗迹群后，西西艾弗遗迹探索有限公司总共探测到&nbsp;q&nbsp;次阴阳龙的现身。很不幸的是，由于来自东方神秘力量的干扰，这&nbsp;q&nbsp;次阴阳龙的现身后，西西艾弗遗迹探索有限公司失去了所有员工的位置信息，因此他希望你帮他计算出所有员工的位置。</p> <h3>输入格式</h3> <p>从标准输入读入数据。</p> <p>第一行四个正整数&nbsp;n,m,p,q；</p> <p>接下来&nbsp;p&nbsp;行，第&nbsp;i&nbsp;行两个正整数&nbsp;(xi,yi)&nbsp;表示第&nbsp;i&nbsp;名员工的初始位置。</p> <p><strong>保证所有员工初始所在的位置两两不同</strong>。</p> <p>接下来&nbsp;q&nbsp;行，第&nbsp;i&nbsp;行三个正整数&nbsp;ui,vi,ti&nbsp;表示西西艾弗遗迹探索有限公司探测到的第&nbsp;i&nbsp;次阴阳龙现身的位置和强度。</p> <h3>输出格式</h3> <p>输出到标准输出中。</p> <p>为了减少输出量，设&nbsp;q&nbsp;次阴阳龙的现身后所有员工的位置为&nbsp;(x1,y1),…,(xp,yp)，则你只需要输出：<br> ⨁i=1pi×xi+yi<br> 其中&nbsp;⨁&nbsp;表示按位异或，即&nbsp;<code>C/C++</code>&nbsp;中的&nbsp;<code>^</code>&nbsp;运算符。</p> <h3>样例输入</h3> 
    <blockquote> 
     <p>3 3 9 1<br> 1 1<br> 1 2<br> 1 3<br> 2 1<br> 2 2<br> 2 3<br> 3 1<br> 3 2<br> 3 3<br> 2 2 1</p> 
    </blockquote> <h3>样例输出</h3> 
    <blockquote> 
     <p>20</p> 
    </blockquote> <h3>样例说明</h3> <p>阴阳龙现身前，每个员工所在的位置如下：</p> 
    <blockquote> 
     <p>3 6 9<br> 2 5 8<br> 1 4 7</p> 
    </blockquote> <p>阴阳龙现身一次后，每个员工所在位置如下：</p> 
    <blockquote> 
     <p>6 9 8<br> 3 5 7<br> 2 1 4</p> 
    </blockquote> <h3>评测用例规模与约定</h3> 
    <table> 
     <thead> 
      <tr> 
       <th>子任务编号</th> 
       <th>n≤</th> 
       <th>m≤</th> 
       <th>p≤</th> 
       <th>q≤</th> 
       <th>子任务分值</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>1</td> 
       <td>1000</td> 
       <td>1000</td> 
       <td>105</td> 
       <td>105</td> 
       <td>40</td> 
      </tr> 
      <tr> 
       <td>2</td> 
       <td>109</td> 
       <td>109</td> 
       <td>1000</td> 
       <td>1000</td> 
       <td>15</td> 
      </tr> 
      <tr> 
       <td>3</td> 
       <td>105</td> 
       <td>105</td> 
       <td>105</td> 
       <td>105</td> 
       <td>25</td> 
      </tr> 
      <tr> 
       <td>4</td> 
       <td>109</td> 
       <td>109</td> 
       <td>105</td> 
       <td>105</td> 
       <td>20</td> 
      </tr> 
     </tbody> 
    </table><p>对于全部数据：</p> <p>1≤n,m≤10^9,1≤p,q≤1×10^5,1≤xi,u≤n,1≤yi,v≤m,1≤ti≤7。</p> <p><strong>保证所有员工初始所在的位置两两不同</strong>。</p> </td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[阴阳龙][Link 1]

> 感兴趣的同学可以如此编码进去进行练习提交

**c++满分题解：**

#include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
     
    const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
    const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
     
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n, m, p, q;
        cin >> n >> m >> p >> q;
        vector<array<int, 2>> pos(p);
        unordered_map<int, set<array<int, 2>>> row, col, ld, rd;
        auto insert = [&](int id){
            int x = pos[id][0], y = pos[id][1];
            row[x].insert({y, id});
            col[y].insert({x, id});
            ld[x + y].insert({y, id});
            rd[x - y].insert({y, id});
        };
        auto remove = [&](int id){
            int x = pos[id][0], y = pos[id][1];
            row[x].erase({y, id});
            col[y].erase({x, id});
            ld[x + y].erase({y, id});
            rd[x - y].erase({y, id});
        };
        for(int i = 0; i < p; ++ i){
            cin >> pos[i][0] >> pos[i][1];
            insert(i);
        }
        for(int i = 0; i < q; ++ i){
            int u, v, t;
            cin >> u >> v >> t;
            vector<array<int, 3>> candidate;
     
            auto search = [&](const set<array<int, 2>>& people, int d, int dirr, int dirl){
                auto pos = people.lower_bound(array<int, 2>{d, p});
                if (pos != people.end()){
                    candidate.push_back({(*pos)[0] - d, (*pos)[1], dirr});
                }
                if (pos != people.begin()){
                    pos = prev(pos);
                    if ((*pos)[0] == d && pos != people.begin())
                        pos = prev(pos);
     
                    if ((*pos)[0] != d){
                        candidate.push_back({d - (*pos)[0], (*pos)[1], dirl});
                    }
                }
            };
     
            search(row[u], v, 2, 6);
            search(col[v], u, 0, 4);
            search(ld[u + v], v, 3, 7);
            search(rd[u - v], v, 1, 5);
     
            if (candidate.empty())
                continue;
            sort(candidate.begin(), candidate.end(), [&](const array<int, 3>& a, const array<int, 3>& b){
                return a[0] < b[0];
            });
            int mindis = min({u - 1, n - u, v - 1, m - v});
            if (candidate[0][0] > mindis)
                continue;
            mindis = candidate[0][0];
            for(int i = 0; i < candidate.size(); ++ i){
                if (candidate[i][0] != mindis)
                    break;
                int dis = candidate[i][0];
                int id = candidate[i][1];
                remove(id);
                int dir = (candidate[i][2] + t) % 8;
                pos[id][0] = u + dis * dx[dir];
                pos[id][1] = v + dis * dy[dir];
                insert(id);
            }
        }
        LL ans = 0;
        for(int i = 0; i < p; ++ i){
            ans ^= (1ll * (i + 1) * pos[i][0] + pos[i][1]);
        }
        cout << ans << '\n';
        return 0;
    }

**运行结果：**

![2a1a6040f3d94313a0414fcbb4eaeba9.png][]

[CCF-CSP]: https://blog.csdn.net/weixin_53919192/article/details/124893395?spm=1001.2014.3001.5502
[Link 1]: http://118.190.20.162/view.page?gpid=T172
[2a1a6040f3d94313a0414fcbb4eaeba9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/2621042e47194120a2717724191c43aa.png