Znzryb's Blog
0%

Posted on Edited on

题目大意

"
Pahom 从黎明开始，到日落结束，使用铲子做标记，走动的区域尽可能大。由标记点组成的多边形代表Pahom所宣称的土地。

Pahom 每秒走一米，每个标记点需要 mm 秒制作，从黎明到日落总共有 tt 秒可用时间。找出Pahom可以宣称的最大区域。

Pahom必须在结束时返回起点。
"

思路讲解

这个函数可以三分啊。对，就是可以三分嗯。

image

P的这个单调性和 tan 的单调性是相反的。

image

从图像上，可以看出其上升速度是比较缓慢的，和 x 同阶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
auto fx=[&](ll n) -> DB {
    ll perimeter=total_tim-n*mark_time;
    DB res=0.5*perimeter*perimeter/(2.0*n);
    res/=tan(pi/n);
    return res;
};
while (r-l>9) {
    ll mid1=l+(r-l)/3,mid2=r-(r-l)/3;
    if (fx(mid1)>fx(mid2)) {
        r=mid2;
    }else {
        l=mid1;
    }
}

AC代码

AC
https://qoj.ac/submission/2010802

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

我们试图设计一个墙壁，将其作为2D矩形砖块形状的镶嵌，所有砖块都具有完全的整数坐标和完全的整数大小。

给定这个2D墙壁上砖块的描述，确定墙壁是否确实是一个墙壁——覆盖一个完美的矩形，没有砖块重叠，砖块之间也没有空白空间。这意味着区域内的每个非整数坐标都应该被一个砖块完全覆盖。

image

分别说明样本1、2和3的砖块图示。

输入

  • 一行，包含砖块数量 nn (1≤n≤1 000 0001 \le n \le 1\,000\,000)。

  • nn 行，每行描述一个砖块，包括四个整数 x y w hx \ y\ w\ h 分别表示 xy 坐标、宽度、高度 (0≤x,y≤1080 \le x, y \le 10^8; 1≤w,h≤1081 \le w, h \le 10^8)。

说白了就是这个砖块的位置，还有长宽都告诉你了。呃，但是呢这个砖块的的这个长宽，还有数量比较大。需要你判断一下这些砖块之间有没有重叠。

思路讲解

一言以蔽之，我们这道题目所采用的策略就是维护一个在当前激活的 X 区间上的不相交的 Y 区间集合。也就是说，我们的这个 activates 集合，它里面存储的是 y 区间。然后 activates 的进出是使用的 event 去控制，去顺序遍历 event 以控制 activates 里面的y 区间集合的进出。

其实扫描线思想的精髓呢，其实就是把二维的问题看成是一维的问题，通过消除偏序关系，维护激活集合。**维护激活的矩形集合。**等方式。

如果说我们维护一个集合，这个集合当中只有当前还生效的矩形，我们是不是会轻松很多？

呃，我们先使用event类来模拟这个矩形的进入和删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Event {
    ll x,y_st,y_ed,op;
    bool operator<(const Event & o) const {
        if (x!=o.x) return x<o.x;
        return op<o.op;

    }
    // auto operator<=>(const Event &)const =default;
};
    multiset<Event> event_st;
    for (int i=0;i<N;++i) {
        ll x,y,w,h;
        cin>>x>>y>>w>>h;
        mnx=min(mnx,x);
        mny=min(mny,y);
        mxx=max(mxx,x+w);
        mxy=max(mxy,y+h);
        acc_area+=w*h;
        // rect_ls[i]={x,y,w,h};
        event_st.insert({x,y,y+h,1});
        event_st.insert({x+w,y,y+h,0});
    }

然后我们去读取 event 类去模拟这个进入和删除的过程，保持 activates 这个Pair set里面只有这个，已经激活的矩形，那么已经激活的矩形其实就相当于一段线段了（在Y方向上的线段）。我们使用check函数去检查一下，就是我们插入的这个东西，它会不会呃和activs里面本来就有的这个线段重叠（不过，因为activates里面的这个所有的线段都是互不重叠的，所以说判断起来会非常容易，只需要检查前驱和后继即可。）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 如果假设 activates 是这个互不重叠的，那么肯定没问题
set<pair<ll,ll>> activates;
for (auto &event:event_st) {
    auto [x,y_st,y_ed,op]=event;
    if (op==1) {
        if (!check({y_st,y_ed})) {
            cout<<"no\n";
            return;
        }
        activates.insert({y_st,y_ed});
    }else {
        activates.erase({y_st,y_ed});
    }
}
cout<<"yes\n";
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
auto check=[&](pair<ll,ll> y_pair) -> bool {
    if (activates.empty()) {
        return true;
    }
    auto it=activates.upper_bound(y_pair);
    if (it!=activates.end()) {
        if (y_pair.first>=it->second || y_pair.second<=it->first) {

        }else {
            return false;
        }
    }
    if (it!=activates.begin()) {
        it=prev(it);
        if (y_pair.first>=it->second || y_pair.second<=it->first) {

        }else {
            return false;
        }
    }
    return true;
};

AC代码

AC
https://qoj.ac/submission/2011619

AC
https://codeforces.com/gym/106157/submission/361754040

https://qoj.ac/submission/2011657

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目总结：Colourful Captcha

本题要求构造一个符合特定条件的 ASCII 艺术矩形（验证码），以区分“简化模型（模拟机器人）”和“人类”的读取结果。

1. 核心约束

  • 尺寸限制：行数 ≤10\le 10，每行长度 ≤100\le 100 且长度相等。

  • 字符构成：仅限大写英文字母和点 .。

  • 人类读取 (C1C_1)：

    • 人类通过“大字母”的孔洞数量来识别颜色。
    • 孔洞规则：B 有 2 个孔；A, D, O, P, Q, R 有 1 个孔；其余字母 0 个孔。
    • 识别单位：由四连通字母组成的区域视为一个“大字母”。
    • 识别顺序：从左到右，且大字母的水平边界框（Bounding Box）不得相交或接触。

  • 机器人读取 (C2C_2)：

    • 机器人直接扫描文本中的子串。
    • 包含要求：图中必须包含子串 C2C_2，且其两端不能紧邻其他字母（如 C2=REDC_2=\text{RED}，允许 .RED.，禁止 REDHAT）。
    • 排除要求：图中严禁出现除 C2C_2 以外的其他彩虹颜色名子串。

2. 彩虹颜色与孔洞对应表

颜色名 孔洞序列
RED 1, 0, 1
ORANGE 1, 1, 0, 1, 0, 0
YELLOW 0, 0, 0, 0, 1, 0
GREEN 0, 1, 0, 0, 0
BLUE 2, 0, 0, 0
VIOLET 0, 0, 1, 0, 0, 0

3. 样例解释

输入：C1=BLUEC_1 = \text{BLUE}, C2=REDC_2 = \text{RED}

输出分析：

art
1
2
3
4
5
6
7
BB..L...U.U.EEE  <-- 第一部分：人类识别为 BLUE
B.B.L...U.U.E..      B(2孔), L(0孔), U(0孔), E(0孔)
BBB.L...U.U.EEE      四个大字母水平不接触，识别结果：BLUE
B.B.L...U.U.E..
RED.RED.RED.RED  <-- 第二部分：机器人识别为 RED
                     包含子串 RED，且两端由点号或边界隔离
                     未包含 ORANGE, YELLOW 等其他子串

思路讲解

这道题目给出的构造条件非常的宽松，你甚至可以就是直接就是嗯每一列它都是用 s_ai 组成就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string s_human,s_ai;
cin>>s_human>>s_ai;
vector<string> ans_ls(12);
for (int i=1;i<=10;++i) {
    for (int j=0;j<s_human.size();++j) {
        ans_ls[i]+=s_ai;
        ans_ls[i]+=".";
    }
}
for (int i=0,idx=1;i<s_human.size();++i,idx+=SZ(s_ai)+1) {
    char ch=s_human[i];
    if (ch=='B') {
        ans_ls[2][idx]='.';
        ans_ls[9][idx]='.';
    }else if (one_hole.contains(ch)) {
        ans_ls[2][idx]='.';
    }
}
for (int i=1;i<=10;++i) {
    cout<<ans_ls[i]<<"\n";
}

那么你会看到叔叔就长成这样，直接使用 s_ai 的 red 啊去组成这样子一个列。violt的话只有O的部分是有一个呃空缺的，我们只要点一个点一个点就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
_______________[ Testcase #1 INPUT ]_______________
VIOLET
RED

_______________[ Testcase #1 OUTPUT]_______________
RED.RED.RED.RED.RED.RED.
RED.RED.R.D.RED.RED.RED.
RED.RED.RED.RED.RED.RED.
RED.RED.RED.RED.RED.RED.
RED.RED.RED.RED.RED.RED.
RED.RED.RED.RED.RED.RED.
RED.RED.RED.RED.RED.RED.
RED.RED.RED.RED.RED.RED.
RED.RED.RED.RED.RED.RED.
RED.RED.RED.RED.RED.RED.

AC代码

AC
https://qoj.ac/submission/2013731

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

"
F. 徒步旅行

每个测试的时间限制：3.5秒

每个测试的内存限制：1024兆字节

输入：标准输入

输出：标准输出
"

您正在为一位来自荷兰的朋友创建一次峰区山丘之旅。这次旅行将从当地著名的观景点“山1”到世界著名的观景点“山2”。

为了让这位朋友感到宾至如归，您希望尽量减少步行路线中最高和最低山丘之间的高度差。

给定一个地方点和它们之间路径的图，找到这样一个最优平坦路线。

输入

  • 一行，包含山的数量nn（2≤n≤5,0002 \le n \le 5,000）和连接它们的路径数量mm（1≤m≤25,0001 \le m \le 25,000）。

  • 一行，包含nn个整数h1…hnh_1 \ldots h_n（0≤h≤1060 \le h \le 10^6），表示从第11到第nn座山的高度（单位：米）。

  • mm行，每行包含两个整数aa和bb（1≤a,b≤n1 \le a, b \le n），表示山aa和山bb之间存在双向路径。

保证山11和山22之间存在路径（直接或间接）。

思路讲解

  1. 离散化高度：
    将地图中所有出现过的山丘高度提取出来，从小到大排序，并去重。得到一个有序序列 H={y1,y2,…,yk}H = \{y_1, y_2, \dots, y_k\}。

  2. 双指针（滑动窗口）：
    设置两个指针 left 和 right，对应高度序列中的索引。

  • 固定 left****，移动 right：尝试寻找满足连通性的最小 right。
  • 一旦 Hill 1 和 Hill 2 连通，记录当前差值 H[right]−H[left]H[right] - H[left]，然后尝试增大 left（收缩窗口）看是否依然连通。
  • 连通性检查：可以使用 BFS、DFS 或者 并查集 (DSU)。
  1. 复杂度分析：
  • 高度去重后最多有 NN 个。
  • 外层双指针移动 O(N)O(N) 次。
  • 每次移动进行一次图遍历 O(N+M)O(N + M)。
  • 总复杂度约为 O(N×(N+M))O(N \times (N + M))。
  • 题目给出了 3.5 秒 的宽裕时限，对于 N=5000,M=25000N=5000, M=25000 来说，这个复杂度在 C++ 中是可以跑过的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 下面就是双指针
for (int i=0;i<N;++i) {
    bool isb=false;
    for (int j=bp;j<N;++j) {
      // 判断是否联通
        if (bfs(height_idx_ls[i].first,height_idx_ls[j].first)) {
          // 一旦联通，就 break 
            bp=j;
            ans=min(ans,abs(height_idx_ls[i].first-height_idx_ls[j].first));
            isb=true;
            break;
        }
    }
    // 已经无可救药了
    if (!isb) {
        bp=N+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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<pair<ll,ll>> height_idx_ls(N);
    vector<ll> H(N+2);
    for (int i=1;i<=N;++i) {
        cin>>height_idx_ls[i-1].first;
        height_idx_ls[i-1].second=i;
        H[i]=height_idx_ls[i-1].first;
    }
    sort(all(height_idx_ls));
    vector<vector<ll>> g(N+2);
    for (int i=1;i<=M;++i) {
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> vis(N+2);
    int tim=0;
    auto bfs=[&](ll low,ll high) {
        if (low>H[1] || H[1]>high) {
            return false;
        }
        if (low>H[2] || H[2]>high) {
            return false;
        }
        queue<ll> q;
        q.push(1);
        ++tim;
        vis[1]=tim;
        while (!q.empty()) {
            ll u=q.front();
            q.pop();
            for (auto v:g[u]) {
                if (vis[v]>=tim) continue;
                if (low>H[v] || H[v]>high) {
                    continue;
                }
                q.push(v);
                vis[v]=tim;
            }
        }
        if (vis[2]>=tim) {
            return true;
        }
        return false;
    };

    ll ans=INF;
    ll bp=0;
    // 下面就是双指针
    for (int i=0;i<N;++i) {
        bool isb=false;
        for (int j=bp;j<N;++j) {
		        // 判断是否联通
            if (bfs(height_idx_ls[i].first,height_idx_ls[j].first)) {
                bp=j;
                ans=min(ans,abs(height_idx_ls[i].first-height_idx_ls[j].first));
                isb=true;
                break;
            }
        }
        // 已经无可救药了
        if (!isb) {
            bp=N+1;
        }
    }
    cout<<ans<<"\n";
}

AC代码

AC
https://qoj.ac/submission/2010554

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目总结：G. Get Good

基本参数

  • nn: 总天数。

  • aa: 处于“精力充沛”状态下每日获得的技能点。

  • bb: 处于“疲劳”状态下每日获得的技能点（a≥ba \ge b）。

  • xx: 连续工作 xx 天后，状态从“精力充沛”转为“疲劳”。

  • yy: 连续休息 yy 天后，状态重置为“精力充沛”。

规则说明

  1. 初始状态：第 1 天开始时处于“精力充沛”状态。

  2. 工作机制：

  • 前 xx 天工作，每天得 aa 分。
  • 从第 x+1x+1 天起如果不休息继续工作，每天得 bb 分。

  1. 休息机制：随时可以开始连续休息 yy 天。休息期间得 0 分，休息结束后重新变为“精力充沛”状态（即又能享受 xx 天的高收益 aa）。

  2. 目标：在 nn 天内通过合理安排工作与休息的时间，求最大化技能点总和。

样例解释

  • 样例 2 (n=4,a=4,b=2,x=3,y=3n=4, a=4, b=2, x=3, y=3)

    • 方案 A：连续工作 4 天。前 3 天得 3×4=123 \times 4 = 12，第 4 天疲劳得 2，总分 12+2=1412+2=14。
    • 方案 B：工作 1 天后休息 3 天。总分 4。
    • 最大值：14。

  • 样例 3 (n=5,a=3,b=2,x=3,y=1n=5, a=3, b=2, x=3, y=1)

    • 方案 A：工作 5 天。前 3 天得 3×3=93 \times 3 = 9，后 2 天疲劳得 2×2=42 \times 2 = 4，总分 13。
    • 方案 B：工作 3 天（得 9），休息 1 天，第 5 天重新精力充沛工作（得 3），总分 9+0+3=129+0+3=12。
    • 最大值：13。

  • 样例 4 (n=5,a=4,b=1,x=3,y=1n=5, a=4, b=1, x=3, y=1)

    • 由于疲劳收益 b=1b=1 太低，休息 1 天比疲劳工作更划算。
    • 方案：工作 3 天（得 3×4=123 \times 4 = 12），休息 1 天（得 0），第 5 天重新开始工作（得 4），总分 12+0+4=1612+0+4=16。
    • 最大值：16。

思路讲解

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
ll N,a_fresh,b_tired,x_do,y_rest;
cin >> N>>a_fresh>>b_tired>>x_do>>y_rest;
// if (a_fresh==b_tired) {
//     cout<<N*a_fresh<<"\n";
//     return;
// }
ll l=N*b_tired,r=N*a_fresh;
ll ans=0;
do {
    ll num_a=min(x_do,N),num_b=N-num_a;
    ll lans=num_a*a_fresh+num_b*b_tired;
    ans=max(lans,ans);
}while (false);
do {
    ll num_a=N/(x_do+y_rest),rem=N-num_a*(x_do+y_rest);
    ll lans=num_a*x_do*a_fresh+min(rem,x_do)*a_fresh+
        (rem-min(rem,x_do))*b_tired;
    ans=max(lans,ans);
}while (false);
// 最后一段加上的原因见下：
do {
    ll num_a=N/(x_do+y_rest);
    ll rem=0;
    if (num_a>=1) {
        rem=N-num_a*(x_do+y_rest);
        rem+=y_rest;
    }else {
        rem=N-num_a*(x_do+y_rest);
    }
    ll lans=num_a*x_do*a_fresh+rem*b_tired;
    ans=max(lans,ans);
}while (false);
cout<<ans<<"\n";

b 和 a，x 的不同关系已经在前两种情况中包含了，但是 b 和 x+a+x 的关系还没有包含。

image

AC代码

心路历程（WA，TLE，MLE……）