模拟

算法

本文收录模拟题

你的牌太多了

B3767语言月赛202305 你的牌太多了2

题意简介

  • 双方：扶苏(FS) 和 小F(FR)，每人初始n张牌
  • 牌属性：每张牌有花色(f)和点数(p)
  • 目标：谁先打完所有牌谁获胜（s为1则扶苏先手，2为小F先手）

一轮游戏的流程

1. 首牌规则

  • 当前轮先手玩家出点数最小的牌
  • 如有多张点数最小，出花色最小的那张

2. 压制规则

  • 对方必须出同花色且点数更大的牌来压制
  • 压制成功则交换出牌权，继续压制
  • 压制失败则本轮结束

3. 轮次交接

  • 压制失败后，最后成功出牌者获得下轮先手权
  • 游戏持续直到一方牌打完

读题

注意（题意已经有一轮的定义，下文提到的一回合是指一个人出牌另一个选牌（不一定能选到出出去）。所以一轮可能有很多回合。）

如果你有充足的模拟经验，你就知道首先确定什么时候结束是一个好习惯。就像写dfs也会先写好什么时候退出搜索。那么很显然，只要一个人牌数为0就提出。我用num1和num2分别记录牌数。每次出一张牌就num–。我们把模拟过程写到函数里面，用返回值1代表扶苏先出完，2代表f先出完。框架如下

1
2
3
4
5
6
7
8
9
10
11
12
13
int play(card a[],card b[],int n){
    int num1=n,num2=n;
    while(num1>0 && num2>0){
        //待补充内容
    if(num1==0){
        return 1;
    }
    if(num2==0){
        return 2;
    }
}
}

每张牌有花色和点数之分，又因为点数和花色还有优先性，自然想到结构体以及结构体排序

1
2
3
4
5
6
7
8
9
10
11
struct card{
    int num;//点数
    int flo;//花色
}a[105],b[105];//两个人的手牌

bool cmp(card a,card b){
    if(a.num != b.num) return a.num < b.num;//优先点数最小
    else return a.flo < b.flo;//如有多张点数最小，出花色最小的那张
}
 //sort(a, a + n, cmp);，排序是必要的，但是放在main里面
 //sort(b, b + n, cmp);

由于s不同有先后手之分，但是不难想象到这是对称的，也就是说，只要你把一个人先手的情况写好，就可以用cv大法（复制粘贴），然后略微改动就好。框架如下

1
2
3
4
5
6
if(s==1){
    
}
else{
    
}

这里我们只分析s==1的情况。当扶苏先手，该怎样完成这个模拟。

因为扶苏先手，所以我需要在a数组中先选一张牌，选点数最小的那张。当然这时候有一个问题，既然我已经排序好了，是不是意味着我直接每次粗暴的选下一个就行，第一次选a[1],第二次a[2]……显然不对，因为有的牌不一定符合规则，如果到后面牌权交换，你要压制对方的话，可能你现下的牌不满足需求，就会跳。所以我们用一个vis[]数组标记双方的牌有没有出过。

1
bool vis1[105],vis2[105];

所以后面选牌时我们加上一个vis判断即可。

当扶苏选出了自己的第一张牌，那么小F就要压制他了。压制的规则是，花色相同且点数大于对方。很好实现。那么我只要比较扶苏和f出的牌就好了。但是问题来了，我该怎么记录扶苏出的牌。这么写是对的吗？

1
2
3
4
5
6
7
8
9
10
for(int i=0;i<n;i++){
     if(vis1[i]==1) continue;
    for(int j=0;j<n;j++){
        if(vis2[i]==1)continue;
        if(a[i].flo==b[j].flo && a[i].num<b[j].num){
              a[i].num = 0;
              b[j].num = 0;         
        }
    }
}

这样写是不满足题意的回合制的。你要知道，牌权并不是你出完到我。而是，一轮游戏（除第一轮先手确定）的先手是上一轮出牌的最后一个人。也就是说要是小F无法压制，那本轮结束，下一轮还是扶苏先手。如果可以压制，那扶苏需要看能不能有牌压制小F用来压制的牌，然后一直进行，直到有一方无法出牌。这里你要敏锐的感知到，每轮游戏的回合是不固定的，而且每一回合的出牌人也不固定。所以需要一个while(1)循环，直到不满足条件退出循环。

回到刚刚的问题，如何记录扶苏出的牌，来确保回合制可以进行。其实我只要把选牌这个阶段单独拎出来，**然后再用一个结构体数组tmp记录当下选的是什么牌，**把对方的压制写到后面就好。同时确保这个牌没被用过。（不要忘记每次出牌num都–）

1
2
3
4
5
6
7
8
for(int i = 0; i < n; i++){
    if(vis1[i] == 0){
           tmp = a[i];
           num1--;
            vis1[i] = 1;
             break;
                }
            }

现在扶苏选出来他先手要出的牌，要轮到f来选牌压制了。那么我们用循环来找，如果找到了符合条件的，就说明压制成功了。没用找到的话，压制失败本轮结束，由扶苏继续出牌。

也就是说，轮到小f出牌的回合会有两个结果，（压制成功和压制失败）。**那么我们用一个变量bool found=false来判断。**如果找到了，found=true,否则就本轮结束。

代码写到这步，你就要意识到这是你改写while(1)的时候了。因为你的轮数开始不确定了。

而因为一轮的各个回合中，不一定谁能最终压制成功，所以有两个点是不确定的。

  • 谁是下一轮的先手 用next表示
  • 当前轮次谁下一个出牌（谁要进行压制） 用now表示

每一次出牌，我设置变量next，表示本轮结束后下一轮先手。仍然next==1表示扶苏，2表示f。

用now变量表示下一个是谁出牌。now==1是表示扶苏，2表示f。

这个now好说，假设轮到f进行压制时，如果压制成功，本轮继续，就轮到扶苏出牌。now从2变1。如果压制失败，found=false，进入下一轮。这时now不变，还是2。因为上一轮最后出牌的是f。综上来说，只要轮到谁时谁成功压制，now就轮到对方，否则保持。

而next呢，谁是下一回合的先手，是不是由这一轮是谁最后出牌来表示。谁压制成功，谁就可能是这一轮最后的最后一个。也就是说，如果now==2，就说明现在f要进行压制，如果压制成功，next也应该等于2。

好的，不知道多少回合后，假设一轮已经结束，扶苏没能压制成功对方，那新的一轮中，是不是小f就要选牌了。那现在就是相当于小f先手。如何模拟这个控制呢？

我们前面已经提到用next表示谁是下一轮的先手。所以只要每次一轮过后，压制成功时，让first等于next。first为1时选扶苏的牌，否则f。

现在我们来汇总前面代码框架。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
while(num1>0 && num2>0){
    if(first==1){//本轮从扶苏开始
        //扶苏开始选牌
        //开始本轮循环
    }
    else{//本轮从f开始
        //f开始选牌
        //开始本轮循环
    }
    if(num1==0){
        return 1;
    }
    if(num2==0){
        return 2;
    }
    
}

现在我们补充好first==1时的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
if(first==1){
    card tmp;//记录当前出的牌
    int next=1;//next初始化，下一轮出牌人
    
    //扶苏选牌
    for(int i=0;i<n;i++){
        if(vis[i]==0){
            tmp==a[i];
            num1--;
            vis1[i]=1;
            break;
        }
    }
    
    int now=2;//当前轮下一个出牌的人，初始化
    
    //开始互相压制的多个回合
    while(1){
      bool found=false;//标记是否成功压制
        
        //轮到f压制
      if(now==2){
          for(int i=0;i<n;i++){
              if(vis[i]==0 && b[i].flo==tmp.flo && b[i].num >tmp.num){
                  found=true;//已经找到符合要求的牌，压制成功
                  tmp=b[i];//当前牌变为f用来压制的牌
                  num2--;//打出一张
                  vis2[i]=1;//这张牌已经用过了
                  now=1;//压制成功后轮到扶苏出牌了
                  next=2;//如果扶苏没能压制成功更改next变量，下一轮就是f出牌
                  break;//找到牌打出，结束f这次出牌
              }
          }
      }
        
       //轮到扶苏压制
      else{
          for(int i=0;i<n;i++){
     		if(vis1[i] == 0 && a[i].flo == tmp.flo && a[i].num > tmp.num){
                found=true;
                tmp=a[i];
                num1--;
                vis1[i]=1;
                now=2;
                next=1;
                break;
            }
          }
      }
        if(!found) break;//没压制成功的话，本轮直接结束进入下一回合
        
    }
    first=next;//压制成功了，这一轮出牌的最后一个人，变成下一轮的先手，要先选牌
}

终于吃完了这坨史，附上ac代码美美下班。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>
using namespace std;

struct card{
    int num;
    int flo;
}a[105],b[105];

bool vis1[105],vis2[105];

bool cmp(card a,card b){
    if(a.num != b.num) return a.num < b.num;
    else return a.flo < b.flo;
}

int play(card a[],card b[],int n){
    memset(vis1, 0, sizeof(vis1));
    memset(vis2, 0, sizeof(vis2));
    int num1 = n, num2 = n;
    int first = 1;
    
    while(num1 > 0 && num2 > 0){
        if(first == 1){
            card tmp;
            int next = 1;
            for(int i = 0; i < n; i++){
                if(vis1[i] == 0){
                    tmp = a[i];
                    num1--;
                    vis1[i] = 1;
                    break;
                }
            }
            int now = 2;
            while(1){
                bool found = false;
                if(now == 2){
                    for(int i = 0; i < n; i++){
                        if(vis2[i] == 0 && b[i].flo == tmp.flo && b[i].num > tmp.num){
                            found = true;
                            tmp = b[i];
                            num2--;
                            vis2[i] = 1;
                            now = 1;
                            next = 2;
                            break;
                        }
                    }
                }
                else{
                    for(int i = 0; i < n; i++){
                        if(vis1[i] == 0 && a[i].flo == tmp.flo && a[i].num > tmp.num){
                            found = true;
                            tmp = a[i];
                            num1--;
                            vis1[i] = 1;
                            now = 2;
                            next = 1;
                            break;
                        }
                    }
                }
                if(!found) break;
            }
            first = next;
        }
        else{
            card tmp;
            int next = 2;
            for(int i = 0; i < n; i++){
                if(vis2[i] == 0){
                    tmp = b[i];
                    num2--;
                    vis2[i] = 1;
                    break;
                }
            }
            int now = 1;
            while(1){
                bool found = false;
                if(now == 1){
                    for(int i = 0; i < n; i++){
                        if(vis1[i] == 0 && a[i].flo == tmp.flo && a[i].num > tmp.num){
                            found = true;
                            tmp = a[i];
                            num1--;
                            vis1[i] = 1;
                            now = 2;
                            next = 1;
                            break;
                        }
                    }
                }
                else{
                    for(int i = 0; i < n; i++){
                        if(vis2[i] == 0 && b[i].flo == tmp.flo && b[i].num > tmp.num){
                            found = true;
                            tmp = b[i];
                            num2--;
                            vis2[i] = 1;
                            now = 1;
                            next = 2;
                            break;
                        }
                    }
                }
                if(!found) break;
            }
            first = next;
        }
    }
    
    if(num1 == 0) return 1;
    else return 2;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        int n, m, r, s;
        cin >> n >> m >> r >> s;
        
        for(int i = 0; i < n; i++) cin >> a[i].flo;
        for(int i = 0; i < n; i++) cin >> a[i].num;
        for(int i = 0; i < n; i++) cin >> b[i].flo;
        for(int i = 0; i < n; i++) cin >> b[i].num;
        
        sort(a, a + n, cmp);
        sort(b, b + n, cmp);
        
        if(s == 1){
            int result = play(a, b, n);
            if(result == 1){
                cout << "FS wins!" << endl;
            } else {
                cout << "FR wins!" << endl;
            }
        } else {
            int result = play(b, a, n);
            if(result == 1){
                cout << "FR wins!" << endl;
            } else {
                cout << "FS wins!" << endl;
            }
        }
    }
    return 0;
}

精灵宝可梦对战

2023ccpc女赛G.精灵宝可梦对战

基本规则

  • 小A和小B各有若干宝可梦，每个宝可梦有7种属性
  • 双方轮流攻击，小A先手
  • 每轮包括两次攻击：小A攻击 → 小B攻击
  • 攻击方选择造成伤害最高的技能
  • 宝可梦轮换机制：攻击后排到队尾，下一只上场

胜负条件

  • 小A胜利：小B的所有宝可梦HP ≤ 0
  • 小B胜利：小A的所有宝可梦HP ≤ 0
  • 平局：进行K轮后仍未分出胜负

代码所述备矣，后面有心情再补充一点题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

// 小A的宝可梦属性数组
int h1[N]; // 血量
int a1[N]; // 物理攻击
int b1[N]; // 魔法攻击
int c1[N]; // 物理防御
int d1[N]; // 魔法防御
int e1[N]; // 终极技能所需能量
int w1[N]; // 终极技能伤害
int ea[N]; // 当前能量值

// 小B的宝可梦属性数组（同上）
int h2[N], a2[N], b2[N], c2[N], d2[N], e2[N], w2[N], eb[N];

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, k;
    cin >> n >> m >> k;
    
    // 使用队列管理存活的宝可梦
    queue<int> A, B;
    
    // 读取小A的宝可梦数据
    for(int i = 1; i <= n; i++) {
        cin >> h1[i] >> a1[i] >> b1[i] >> c1[i] >> d1[i] >> e1[i] >> w1[i];
        ea[i] = 0; // 初始化能量为0
        A.push(i); // 将宝可梦加入队列
    }
    
    // 读取小B的宝可梦数据
    for(int i = 1; i <= m; i++) {
        cin >> h2[i] >> a2[i] >> b2[i] >> c2[i] >> d2[i] >> e2[i] >> w2[i];
        eb[i] = 0; // 初始化能量为0
        B.push(i); // 将宝可梦加入队列
    }
    
    int cnt = 0; // 记录当前轮数
    int nowa, nowb; // 当前对战的宝可梦索引
    
    // 战斗主循环
    while(!A.empty() && !B.empty() && cnt < k) {
        // 获取当前对战的宝可梦
        nowa = A.front();
        nowb = B.front();
        A.pop();
        B.pop();
        
        // 小A的宝可梦攻击小B的宝可梦
        
        // 计算三种攻击方式的伤害
        int p = max(0, a1[nowa] - c2[nowb]); // 物理攻击伤害
        int ma = max(0, b1[nowa] - d2[nowb]); // 魔法攻击伤害
        int ww = 0; // 终极技能伤害初始为0
        
        // 检查是否可以释放终极技能
        if(ea[nowa] >= e1[nowa])
            ww = w1[nowa]; // 满足条件则设置终极技能伤害
            
        // 选择伤害最大的攻击方式
        int hurt = max({p, ma, ww});
        
        // 应用伤害并更新能量
        if(p == hurt) { // 选择物理攻击
            ea[nowa]++; // 物理攻击增加能量
            h2[nowb] -= p; // 造成伤害
        }
        else if(ma == hurt) { // 选择魔法攻击
            ea[nowa]++; // 魔法攻击增加能量
            h2[nowb] -= ma; // 造成伤害
        }
        else { // 选择终极技能
            ea[nowa] -= e1[nowa]; // 消耗能量
            h2[nowb] -= ww; // 造成伤害
        }
        
        // 将攻击方宝可梦放回队列末尾（轮换）
        A.push(nowa);
        nowa = A.front(); // 获取下一个准备上场的宝可梦
        
        // 检查防御方宝可梦是否阵亡
        if(h2[nowb] <= 0) {
            if(!B.empty()) {
                nowb = B.front(); // 更换下一个宝可梦
                B.pop();
            }
            else break; // 没有宝可梦可换了，结束战斗
        }
        
        // 小B的宝可梦攻击小A的宝可梦（同上逻辑）
        p = max(0, a2[nowb] - c1[nowa]); // 物理攻击伤害
        ma = max(0, b2[nowb] - d1[nowa]); // 魔法攻击伤害
        ww = 0; // 终极技能伤害初始为0
        
        if(eb[nowb] >= e2[nowb])
            ww = w2[nowb]; // 满足条件则设置终极技能伤害
            
        hurt = max({p, ma, ww}); // 选择最大伤害
        
        if(p == hurt) { // 物理攻击
            eb[nowb]++;
            h1[nowa] -= p;
        }
        else if(ma == hurt) { // 魔法攻击
            eb[nowb]++;
            h1[nowa] -= ma;
        }
        else { // 终极技能
            eb[nowb] -= e2[nowb];
            h1[nowa] -= ww;
        }
        
        // 将攻击方宝可梦放回队列末尾（轮换）
        B.push(nowb);
        
        // 检查防御方宝可梦是否阵亡
        if(h1[nowa] <= 0) 
            A.pop(); // 阵亡则从队列中移除
        
        cnt++; // 增加轮数
    }
    
    // 输出战斗结果
    if(!A.empty() && !B.empty()) 
        cout << "Draw" << '\n'; // 双方都有宝可梦存活
    else if(!A.empty())
        cout << "Alice" << '\n'; // 小A获胜
    else
        cout << "Bob" << '\n'; // 小B获胜
    
    return 0;
}

疾羽的救赎

2023ccpc女赛A.疾羽的救赎

🧩 核心规则

游戏元素：三种颜色棋子（紫/绿/黄）放置在编号2-9的棋盘格上，初始位置分别为格子2、3、4。棋子按栈结构叠放，移动时整体迁移——移动一个棋子会同时移动其上方所有棋子。

输入格式：12张行动卡片，每张包含颜色编号和移动步数。如输入1 3表示移动紫色棋子3步。

移动机制：从当前格子now移动到now + b号格子，棋子放置在目标格子栈顶。

🎮 胜负条件

成功标准：所有棋子最终都到达9号格子。程序输出"Y"表示成功，"N"表示失败。

仍然先把代码和注释扔上来。具体的后面补

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    // v[10] 存储每个格子上的棋子栈
    // v[i] 表示第i个格子上叠放的棋子（从下到上的顺序）
    vector<int> v[10];  
    
    // qi[4] 存储每个颜色棋子当前所在的格子编号
    // qi[1] = 紫色棋子位置, qi[2] = 绿色棋子位置, qi[3] = 黄色棋子位置
    vector<int> qi(4);  
    
    // 初始化棋盘状态：
    // 2号格子放紫色棋子(编号1)，3号格子放绿色棋子(编号2)，4号格子放黄色棋子(编号3)
    v[2].push_back(1);
    v[3].push_back(2);
    v[4].push_back(3);
    
    // 初始化每个颜色棋子的位置跟踪
    qi[1] = 2;  // 紫色棋子在2号格子
    qi[2] = 3;  // 绿色棋子在3号格子  
    qi[3] = 4;  // 黄色棋子在4号格子
    
    // 处理12张行动卡片
    for (int i = 1; i <= 12; i++) {
        int a, b, pos = -1;
        cin >> a >> b;  // 输入卡片颜色和步数
        
        // 获取当前颜色棋子所在的格子编号
        int now = qi[a];
        // 计算移动后的目标格子编号
        int nex = now + b;

        // 在当前格子的棋子栈中查找该颜色棋子的位置
        // 因为棋子可能被其他棋子压住，需要找到它在栈中的索引
        for (int j = 0; j < v[now].size(); j++) {
            if (v[now][j] == a) {
                pos = j;  // 记录该棋子及其上方所有棋子的起始位置
                break;  
            }
        }
        
        // 将该棋子及其上方的所有棋子移动到新格子
        // 从pos位置开始到栈顶的所有棋子都要移动
        for (int j = pos; j < v[now].size(); j++) {
            // 更新被移动棋子的位置信息
            qi[v[now][j]] = nex;
            // 将棋子添加到新格子的栈顶
            v[nex].push_back(v[now][j]);
        }
        
        // 从原格子中移除被移动的棋子
        // 注意：需要先保存原长度，因为pop_back()会改变size()
        int len = v[now].size();
        for (int j = pos; j < len; j++) {
            v[now].pop_back();
        }
    }
    
    // 检查所有棋子是否都在9号格子上
    // 如果9号格子上有3个棋子，说明全部移动成功
    cout << (v[9].size() == 3 ? "Y" : "N") << '\n';
}

signed main() {
    // 优化输入输出速度
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int t = 1;
    cin >> t;  // 读取测试用例数量
    
    // 处理每个测试用例
    while (t--) {
        solve();
    }
    return 0;
}

Painter

2023沈阳

一道有一点点技术的模拟题目。

大致题意是，有三种操作，第一种操作给出你圆心和半径以及符号。圆内的点都变这个符号。第二种操作给你矩形，在矩形内的变为这个符号。第三种给你四个数，y1-y1行的x2-x1列，打印出来这个范围对应的符号。

由于整个图太大，首先排除存下整个图暴力的可能性。那是不是就没用办法了呢？注意它每次只需要输出给出范围的图的符号。所以我们只需要判断这个范围的点有没有被渲染过。

由于有多次渲染，一次次覆盖显然有些浪费时间。但我们既然都说了是覆盖，那说明一个点，只要被最后一次操作渲染了，前面的就都不用管了。以此类推。所以我们可以一个点一个点的遍历，对于每个点，我们从预先存好的操作数组里面从后向前遍历（看后面的渲染，而不看会被覆盖的）。如果这个点在某次操作成功被渲染，那后面就不用看了，直接break。

理解完题意和模拟思路，你就要知道代码该怎么实现了。

为了后面遍历操作数组，我需要开一个结构体，然后这个结构体需要有一个string来判断是圆形渲染还是矩形。同时要有它们对应的数值（如圆心）。当然还有有符号char，存储满足条件后的渲染结果

1
2
3
4
5
6
struct Operation {
    string type;
    long long x, y, r; 
    long long x1, y1, x2, y2; 
    char col;
};

然后就是没技术含量的存数组输入环节

1
2
3
4
5
6
if (op == "Circle") {
            Operation oper;
            oper.type = "Circle";
            ss >> oper.x >> oper.y >> oper.r >> oper.col;
            operations.push_back(oper);
        }

大概这样，矩形同理。重点是当op==render需要输出时

为了遍历每个点，我们需要两个for循环，每个点初始为’.’

1
2
3
4
5
6
7
8
for (long long v = y2; v >= y1; v--) {
               for (long long u = x1; u <= x2; u++) {
                   char pixel = '.';
                   //pass
                   cout<<pixel;
           }
    cout <<endl;
}

循环里面就是这个题目的思维核心，覆盖于是倒着遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for (int i = operations.size() - 1; i >= 0; i--) {
                        Operation& oper = operations[i]; 
                        if (oper.type == "Circle") {
                            long long dx = u - oper.x;
                            long long dy = v - oper.y;
                           
                            if (dx * dx + dy * dy <= oper.r * oper.r) {
                                pixel = oper.col;
                                break;
                            }
                        }
                        else if (oper.type == "Rectangle") {
                            if (u >= oper.x1 && u <= oper.x2 && v >= oper.y1 && v <= oper.y2) {
                                pixel = oper.col;
                                break;
                            }
                        }
                    }

附上AC代码下班，注意要开longlong，否则wa 8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;

struct Operation {
    string type;
    long long x, y, r; 
    long long x1, y1, x2, y2; 
    char col;
};

void solve() {
    int n;
    cin >> n;
    cin.ignore(); 
    
    vector<Operation> operations;
    
    for (int i = 0; i < n; i++) {
        string line;
        getline(cin, line);
        stringstream ss(line);
        string op;
        ss >> op;
        
        if (op == "Circle") {
            Operation oper;
            oper.type = "Circle";
            ss >> oper.x >> oper.y >> oper.r >> oper.col;
            operations.push_back(oper);
        }
        else if (op == "Rectangle") {
            Operation oper;
            oper.type = "Rectangle";
            ss >> oper.x1 >> oper.y1 >> oper.x2 >> oper.y2 >> oper.col;
            operations.push_back(oper);
        }
        else if (op == "Render") {
            long long x1, y1, x2, y2;
            ss >> x1 >> y1 >> x2 >> y2;
            
            for (long long v = y2; v >= y1; v--) {
                for (long long u = x1; u <= x2; u++) {
                    char pixel = '.';
               
                    for (int i = operations.size() - 1; i >= 0; i--) {
                        auto& oper = operations[i];
                        if (oper.type == "Circle") {
                            long long dx = u - oper.x;
                            long long dy = v - oper.y;
                           
                            if (dx * dx + dy * dy <= oper.r * oper.r) {
                                pixel = oper.col;
                                break;
                            }
                        }
                        else if (oper.type == "Rectangle") {
                            if (u >= oper.x1 && u <= oper.x2 && v >= oper.y1 && v <= oper.y2) {
                                pixel = oper.col;
                                break;
                            }
                        }
                    }
                    cout << pixel;
                }
                cout << endl;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}