历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing《PAT甲级辅导课》第11章模拟

作者：

姜萍Jumping , 2022-09-18 12:32:03 , 所有人可见 , 阅读 287

第11章模拟

1008. Elevator

笔记

直接模拟即可，注意无论是完成一次上升、或下降、或不动时，都要强制停留5s

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int last = 0, cur, sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> cur;

        if (last <= cur) sum += (cur - last) * 6;
        else sum += (last - cur) * 4;
        sum += 5;           // 完成操作后停留5s

        last = cur;
    }

    cout << sum << endl;

    return 0;
}

1011. World Cup Betting

笔记

贪心：每场比赛取最大赔率即可

#include <iostream>
using namespace std;
const int N = 3;
double a[N][N];

int get_max_index(double a[]) {
    int max_i = 0;
    if (a[1] > a[max_i]) max_i = 1;
    if (a[2] > a[max_i]) max_i = 2;
    return max_i;
}

int main() {
    string name = "WTL";

    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) 
            cin >> a[i][j];

    double res = 1;
    for (int i = 0; i < 3; i++) {
        int index =get_max_index(a[i]);
        cout << name[index] << ' ';
        res *= a[i][index];
    }

    printf("%.2lf\n", (res * 0.65 - 1) * 2);

    return 0;    
}

1014. Waiting in Line

笔记

用$n$个queue模拟窗口，一个数组$n$维数组end_time记录每个窗口最后一名人员的结束服务时间，即最早可提供服务的时间
模拟易错细节
- 区分人满和人不满的情况
- 当一个人的开始服务时间<17:00时，才保存其结束服务时间

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 22, K = 1010;
queue<int> windows[N];
int t[K], window_end_time[N], person_end_time[K];


int main() {
    int n, m, k, q;
    cin >> n >> m >> k >> q;

    for (int i = 1; i <= k; i++) cin >> t[i];

    memset(person_end_time, -1, sizeof person_end_time);

    for (int i = 1; i <= k; i++) {

        int w = 1;      // 假设选第1个窗口
        for (int j = 2; j <= n; j++)
            if (i <= m * n) {
                // 没排满
                if (windows[j].size() < windows[w].size()) 
                    w = j;       // 人更少
            } else {
                if (windows[j].front() < windows[w].front()) 
                    w = j;   // 选择最早能提供服务的窗口
            }

        // 选择第w个窗口服务
        window_end_time[w] += t[i];

        if (i > m * n) windows[w].pop();
        windows[w].push(window_end_time[w]);

        if (window_end_time[w] - t[i] < 6 * 90) 
            person_end_time[i] = window_end_time[w];    // 合法情况才添加
    }

    int id;
    while(q--) {
        cin >> id;
        int p = person_end_time[id];
        if (p != -1) 
            printf("%02d:%02d\n", p / 60 + 8, p % 60);
        else 
            puts("Sorry");
    }

    return 0;
}

1031. Hello World for U

推导过程

列方程
$$ \begin{cases} n_1=n_3\\ n_1+n_2+n_3-2=N\\ n_1 = \max(n_2)\\ \end{cases} $$
把①和②代入③可得
$$ n_1 = \max(N+2-2n_1) =N+2-2\max(n_1) $$
变形得
$$ \max(n_1) = \frac{N+2-n_1}{2} \geqslant n_1 $$
解得
$$ n_1\leqslant \frac{N+2}{3} $$
取$n_1=n_3=\lfloor \frac{N+2}{3} \rfloor $，则$n_2 = N+2-2n_1$

笔记

数学推导如上
得到$n_1$、$n_2$和$n_3$后，再把字符填充到二维字符输出
由于二维字符数组默认值是\0，因此需要逐个判断其内容是否是有效字符，如果不是则输出空格

#include <iostream>
using namespace std;
const int N = 85;
char g[N][N];

int main() {
    string s;
    cin >> s;

    int n = s.size();
    int n1 = (n + 2) / 3;
    int n2 = n + 2 - 2 * n1;

    int k = 0;
    for (int i = 0; i < n1; i++)
        g[i][0] = s[k++];               // 左边

    for (int j = 1; j < n2 - 1; j++)
        g[n1 - 1][j] = s[k++];          // 下边

    for (int i = n1 - 1; i >= 0; i--) {
        g[i][n2 - 1] = s[k++];          // 上边
    }

    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < n2; j++)
            if (g[i][j]) cout << g[i][j];
            else cout << ' ';
        cout << endl;
    }

    return 0;
}

1041. Be Unique

笔记

哈希表统计每个数出现的次数，再重新遍历一次，首次出现次数为1的就是开奖号码

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], cnt[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cnt[a[i]]++;        // 统计次数
    }

    int res = -1;
    for (int i = 0; i < n; i++)
        if (cnt[a[i]] == 1) {
            res = a[i];
            break;
        }

    if (res != -1) printf("%d\n", res);
    else puts("None");

    return 0;
}

1042. Shuffling Machine

笔记

模拟置换过程。用一个数组备份原始顺序，模拟即可
可以先用数模拟，然后再输出对应的含义

#include <iostream>
#include <cstring>
using namespace std;
const int N = 55;
int a[N], b[N], h[N];
int n, k;

string print(int x) {
    if (x <= 13) return 'S' + to_string(x);
    else if (x <= 26) return 'H' + to_string(x - 13);
    else if (x <= 39) return 'C' + to_string(x - 26);
    else if (x <= 52) return 'D' + to_string(x - 39);
    else return 'J' + to_string(x - 52);
 }

int main() {
    cin >> k;

    n = 54;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];        // 置换向量
        a[i] = i;
    }

    while(k--) {
        for (int i = 1; i <= n; i++)
            b[h[i]] = a[i];
        memcpy(a, b, sizeof a);     // 把b复制到a中
    }

    string res;
    for (int i = 1; i <= n; i++)
        res += print(a[i]) + ' ';
    res.pop_back();

    cout << res << endl;

    return 0;
}

1047. Student List for Course

笔记

用vector保存每门课选课的学生，排序后再输出
这题用ios::sync_with_stdio(false);和cin.tie(0);依旧会超时，需要改成printf和scanf

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 2505;
vector<string> lesson[N];

int main() {

    int n, k;
    scanf("%d%d", &n, &k);

    int m, l_id;
    char name[5];
    while(n--) {
        scanf("%s%d", name, &m);
        while(m--) {
            scanf("%d", &l_id);
            lesson[l_id].push_back(name);
        }
    }

    for (int i = 1; i <= k; i++) {
        printf("%d %d\n", i, lesson[i].size());
        sort(lesson[i].begin(), lesson[i].end());
        for (string student : lesson[i])
            printf("%s\n", student.c_str());
    }

    return 0;
}

1054. The Dominant Color

笔记

用哈希表统计次数，输出超过总数一半次数的元素即可

#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int, int> h;

int main() {
    int m, n, x;
    cin >> m >> n;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            cin >> x;
            h[x]++;
        }

    for (auto item : h)
        if (item.second > (m * n / 2)) {
            cout << item.first << endl;
            break;
        }

    return 0;
}

1056. Mice and Rice

笔记

模拟分组淘汰赛，计算次数为$n+\lceil \frac{n}{m} \rceil + \lceil \frac{n}{m^2} \rceil + \cdots$，最坏情况是$m=2$时，$n+\lceil \frac{n}{2} \rceil + \lceil \frac{n}{2^2} \rceil + \cdots \lt 2n$，故时间复杂度为$O(n)$
用数组int w[N]保存每只老鼠的最终重量，vector<int> cur保存参赛选手的序号，int rank[N]表示最终排名
当cur元素个数超过$1$时，模拟分组比赛。在组内线性查找最终重量最大的老鼠，并保存到vector<int> next中，被淘汰的排名为当轮淘汰后剩余人数+1，可根据$\lceil \frac{cur.size()}{m} \rceil + 1$计算得到，而上取整可通过下取整实现：$\lceil \frac{n}{m} \rceil = \lfloor \frac{n + m - 1}{m} \rfloor$。当轮结束后，更新cur = next，继续下一轮
依次输出rank数组即可

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
const int N = 1010;
int n, m, w[N], ranks[N];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        scanf("%d", &w[i]);     // 读入最终重量

    int x;
    vector<int> cur;
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);             // 读入参赛次序   
        cur.push_back(x);          
    }

    while(cur.size() > 1) {
        vector<int> next;
        int remain = ((int)cur.size() + m - 1) / m;      // 本轮剩余个数

        int left = 0;
        while(left < (int)cur.size()) {
            int right = min(left + m - 1, (int)cur.size() - 1);
            int t = left;      // 这组获胜者
            for (int i = left + 1; i <= right; i++)
                if (w[cur[t]] < w[cur[i]])
                    t = i;
            next.push_back(cur[t]);
            for (int i = left; i <= right; i++)
                if (i != t)
                    ranks[cur[i]] = remain + 1;  // 更新落选排名
            left = right + 1;
        }
        cur = next;
    }

    ranks[cur[0]] = 1;       // 更新冠军排名

    cout << ranks[0];
    for (int i = 1; i < n; i++)
        cout << ' ' << ranks[i];
    cout << endl;

    return 0;
}

1062. Talent and Virtue

笔记

排序，根据题意自定义比较函数

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, L, H;

struct Person {
    int id, level, virtue, talent, total;

    bool operator< (const Person& t) const{
        if (level != t.level) return level < t.level;
        else if (total != t.total) return total > t.total;
        else if (virtue != t.virtue) return virtue > t.virtue;
        else return id < t.id;
    }

} p[N];

int getLevel(int virtue, int talent) {
    if (virtue >= H && talent >= H) return 1;
    else if (virtue >= H && talent < H) return 2;
    else if (virtue >= talent) return 3;
    else return 4;
}

int main() {
    scanf("%d%d%d", &n, &L, &H);

    int id, level, virtue, talent, total;
    int m = 0;      // 实际人数
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &id, &virtue, &talent);
        if (virtue < L || talent < L) continue;

        level = getLevel(virtue, talent);
        total = virtue + talent;
        p[m++] = {id, level, virtue, talent, total};
    }

    sort(p, p + m);

    printf("%d\n", m);
    for (int i = 0; i < m; i++)
        printf("%08d %d %d\n", p[i].id, p[i].virtue, p[i].talent);

    return 0;
}

1065. A+B and C (64bit)

笔记

由于long long至多保存64bit，因此计算可能会溢出，可能的情况如下
- $A$和$B$都为非负数（含$0$，符号位都为$0$），但$A+B$为负数（不含$0$，符号位为$1$），溢出，则一定比$C$大
- $A$和$B$都为负数（不含$0$，符号位都为$1$），但$A+B$为非负数（含$0$，符号位为$0$），溢出，则一定比$C$小
不溢出时正常比较

#include <iostream>
using namespace std;
typedef long long LL;

bool check(LL a, LL b, LL c) {
    LL d = a + b;
    if(a >= 0 && b >= 0 && d < 0) return true;    // 正溢出，一定最大
    else if (a < 0 && b < 0 && d >= 0) return false; // 负溢出，一定最小
    else return d > c;      // 不溢出，正常比较
}

int main() {
    int n;
    cin >> n;

    LL a, b, c;
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld%lld", &a, &b, &c);
        if(check(a, b, c)) printf("Case #%d: true\n", i);
        else printf("Case #%d: false\n", i);
    }

    return 0;
}

1069. The Black Hole of Numbers

笔记

按位拆分数字到数组，然后排序，正向构造得减数，反向构造得被减数，当差不等于$0$且不等于$6174$时继续循环
由于一定会执行一次，因此可用do while()循环

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int a, b, c;
    cin >> c;

    int bits[4];
    do {
        // 分离数字
        for(int i = 0; i < 4; i++) {
            bits[i] = c % 10;
            c /= 10;
        }

        sort(bits, bits + 4);   // 排序

        // 构建数字
        a = 0;
        b = 0;
        for(int i = 0; i < 4; i++) {
            a = a * 10 + bits[3 - i];
            b = b * 10 + bits[i];
        }

        c = a - b;
        printf("%04d - %04d = %04d\n", a, b, c);
    } while(c && c != 6174);

    return 0;
}

1080. Graduate Admission

笔记

自定义排序函数，排序后模拟录取
首先找到相同排名的学生，然后对排名相同的学生执行拟录取：
- 依次遍历相同排名的学生，顺序查找志愿中录取未满的学校
  - 如果存在，标记拟录取该学校（未修改录取情况，不影响已录取人数）
  - 如果都录取满，则标记$-1$
- 再次遍历排名相同的学生，根据标记录取学生，此时修改录取情况，影响已录取人数
难点在于如何录取排名并列的情况，引入“拟录取”即可解决

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 40010, M = 110, K = 7;
int max_wish[M];    // 各学校最大录取人数
vector<int> college[M];     // 各学校录取情况
int st[N];      // 各学生录取情况，-1表示未录取

struct Student {
    int id, entrance, interview, final;
    int wish[K];

    bool operator< (const Student& t) const {
        if (final != t.final) return final > t.final;
        else return entrance > t.entrance;
    }

    bool operator== (const Student& t) const {
        return final == t.final && entrance == t.entrance;
    }
} students[N];

int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < m; i++)
        scanf("%d", &max_wish[i]);
    int entrance, interview;
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &entrance, &interview);
        students[i].id = i;
        students[i].entrance = entrance;
        students[i].interview = interview;
        students[i].final = entrance + interview;   // 不用除以2出现浮点数
        for (int j = 0; j < k; j++)
            scanf("%d", &students[i].wish[j]);
    }

    sort(students, students + n);


    // 录取
    memset(st, -1, sizeof st);
    for (int i = 0; i < n; ) {
        int j = i + 1;      // 查找排名一样的学生
        while(j < n && students[j] == students[i]) j++;

        // 同一排名的人
        for(int t = i; t < j; t++) {
            for (int u = 0; u < k; u++) {
                int school = students[t].wish[u];
                if (college[school].size() < max_wish[school]) {
                    st[t] = school;         // 拟录取
                    break;
                }
            }
        }

        for(int t = i; t < j; t++)
            if (st[t] != -1)
                college[st[t]].push_back(students[t].id);  // 正式录取

        i = j;
    }

    // 输出
    for (int i = 0; i < m; i++) {
        if (college[i].size()) {
            sort(college[i].begin(), college[i].end());
            printf("%d", college[i][0]);
            for (int j = 1; j < college[i].size(); j++)
                printf(" %d", college[i][j]);
        }
        printf("\n");
    }

    return 0;
}

1083. List Grades

笔记

自定义排序

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;

struct Student {
    string name, id;
    int grade;

    bool operator< (const Student& t) const {
        return grade > t.grade;
    }
} stu[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> stu[i].name >> stu[i].id >> stu[i].grade;

    sort(stu, stu + n);

    int left, right;
    scanf("%d%d", &left, &right);

    bool success = false;
    for (int i = 0; i < n; i++) {
        if (stu[i].grade >= left && stu[i].grade <= right) {
            success = true;
            cout << stu[i].name << ' ' << stu[i].id << endl;
        }
    }
    if (!success) puts("NONE");

    return 0;
}

1092. To Buy or Not to Buy

笔记

用哈希表unordered_map<char, int>记录珠子的情况
- 买到的珠子串：每个珠子，对应字符个数$+1$
- 想要的珠子串：每个珠子，对应字符个数$-1$
遍历哈希表，分别统计正数之和与负数之和。
- 如果负数之和不为$0$，则输出No 负数之和
- 否则输出Yes 正数之和

#include <unordered_map>
#include <iostream>
using namespace std;
unordered_map<char, int> h;

int main() {
    string a, b;
    cin >> a >> b;

    for (auto c : a) h[c]++;
    for (auto c : b) h[c]--;

    int negetive = 0, positive = 0;
    for (auto item : h) {
        int num = item.second;
        if (num > 0) positive += num;
        else negetive -= num;
    }

    if (negetive) printf("No %d\n", negetive);
    else printf("Yes %d\n", positive);

    return 0;
}

1095. Cars on Campus

笔记

由于查询某时刻的停车数，不需要知道是哪辆车，因此可用Event类描述每辆车的记录，它包括时刻（秒）和状态（$0$表示in，$1$表示out），而不必记录车号。
为了统计停留最长时间的车，可用哈希表unorder_map<string, vector<Event>> car保存每辆车的记录。由于记录存在非法情况，因此需要筛选，满足以下条件
- 第一个事件一定是in
- 之后一定有一个out与之配对
- 最后一个一定是out，不能是in
用erase删除vector里的非法Event事件，把所有合法事件保存到vector<Event> events中，然后按时间升序排序
在events查询某一个时刻的停车数；通过car统计最长停留时间的车
时间复杂度为$O(n \log n + k)$

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 1e4 + 10;

struct Event {
    int tm, status;

    bool operator< (const Event& t) const {
        return tm < t.tm;
    }
};

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    char id[8], status[4];
    int hour, minute, second, tm, st;
    unordered_map<string, vector<Event>> cars;
    for (int i = 0; i < n; i++) {
        scanf("%s %d:%d:%d %s", id, &hour, &minute, &second, status);
        tm = hour * 3600 + minute * 60 + second;
        st = status[0] == 'o';      // in为0，out为1
        cars[id].push_back({tm, st});
    }

    // 剔除非法情况，保存合法事件流
    vector<Event> events;
    for (auto& car : cars) {
        auto& car_events = car.second;
        sort(car_events.begin(), car_events.end());
        int k = 0;
        for (int i = 0; i < car_events.size(); i++)
            if (car_events[i].status == 0 && i + 1 < car_events.size() 
                    && car_events[i + 1].status == 1) {
                        // 第i个为in，第i+1个为out，合法
                        car_events[k++] = car_events[i];
                        car_events[k++] = car_events[i + 1];
                        i++;
                    }
        car_events.erase(car_events.begin() + k, car_events.end()); // 删除非法记录
        for (auto& event : car_events)
            events.push_back(event);        // 保存合法事件到事件流中
    }

    sort(events.begin(), events.end());

    // 处理查询
    int t = 0, cnt = 0;
    while(m--) {
        scanf("%d:%d:%d", &hour, &minute, &second);
        tm = hour * 3600 + minute * 60 + second;
        while(t < events.size() && events[t].tm <= tm) {
            if (events[t].status == 0) cnt++;
            else cnt--;
            t++;
        }
        printf("%d\n", cnt);
    }

    // 找最大停留时间
    int max_time = -1;
    unordered_map<string, int> max_times;
    for (auto& car : cars) {
        auto& car_events = car.second;
        int t = 0, i = 0;
        while(i + 1 < car_events.size()) {
            t += car_events[i + 1].tm - car_events[i].tm;
            i += 2;
        }
        max_times[car.first] = t;
        max_time = max(max_time, t);
    }

    vector<string> res;
    for (auto& item : max_times)
        if (item.second == max_time)
            res.push_back(item.first);
    sort(res.begin(), res.end());

    hour = max_time / 3600;
    minute = (max_time % 3600) / 60;
    second = max_time % 60;
    for (int i = 0; i < res.size(); i++)
        printf("%s ", res[i].c_str());
    printf("%02d:%02d:%02d\n", hour, minute, second);

    return 0;
}

1105. Spiral Matrix

笔记

行数可从$\lceil \sqrt{N} \rceil$开始查找，如果能够整除$n$，则为最小的行数，列数可通过总数除以行数获得。
用vector<vector<int>> res(r, vector<int>(c))保存结果，其中r是行数，c是列数
用方向int dx[] = {0, 1, 0, -1}和int dy[] = {1, 0, -1, 0}实现螺旋顺序，每次撞墙就换方向

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N = 1e4 + 10;
int n, a[N];

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    sort(a, a + n, greater<int>());

    int r = ceil(sqrt(n));
    while (n % r != 0) r++;
    int c = n / r;

    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
    vector<vector<int>> res(r, vector<int>(c));
    for (int i = 0, x = 0, y = 0, k = 0; i < n; i++) {
        res[x][y] = a[i];
        int x_new = x + dx[k], y_new = y + dy[k];
        if (x_new < 0 || x_new >= r || y_new < 0 || y_new >= c || res[x_new][y_new]) {
            k = (k + 1) % 4;        // 换向
            x_new = x + dx[k];
            y_new = y + dy[k];
        }
        x = x_new;
        y = y_new;
    }

    for (int i = 0; i < r; i++) {
        printf("%d", res[i][0]);
        for (int j = 1; j < c; j++)
            printf(" %d", res[i][j]);
        printf("\n");
    }

    return 0;
}

1109. Group Photo

笔记

自定义排序，模拟
注意特判最后一排的人数，它与前几排人数可能不一致，假设总行数为$m$，则最后一行的人数为$\lfloor \frac{n}{m} \rfloor + n \bmod m$
可用根据距离中心点的位置模拟下标变化规律${0, -1, 1, -2, 2, \cdots}$

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e4 + 10, K = 12;
int dx[N];
string res[N];

struct Person{
    string name;
    int height;

    bool operator< (const Person& t) const {
        if (height != t.height) return height >t.height;
        else return name < t.name;
    }
} persons[N];

void init(int n) {
    dx[0] = 0;
    for (int i = 1, k = 1; k < n; i++) {
        dx[k++] = -i;
        if (k < n) dx[k++] = i;
    }
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    char name[10];
    int height;
    for (int i = 0; i < n; i++) {
        scanf("%s %d", name, &height);
        persons[i] = {name, height};
    }

    sort(persons, persons + n);


    init(n);
    int row_n = n / k;      // 每行人数
    int left, current_row_n;    // 左边界，当前行实际人数
    for (int left = 0; left < n; left += current_row_n) {
        current_row_n = row_n;
        if (!left) current_row_n += n % row_n;      // 特判最后一排
        int mid = current_row_n / 2;        // 中间位置
        for (int j = 0, u = 0; j < current_row_n; j++) {
            int x = mid + dx[u++];      // 计算下一个安排的位置
            if (x < 0 || x >= current_row_n)
                x = mid + dx[u++];
            res[x] = persons[left + j].name;
        }

        // 输出
        printf("%s", res[0].c_str());
        for (int i = 1; i < current_row_n; i++)
            printf(" %s", res[i].c_str());
        printf("\n");
    }

    return 0;
}

1121. Damn Single

笔记

本题主要涉及查找，因此需要考虑用哈希表加快查找
① 若把已知夫妻放入哈希表中，再从客人中查找落单情况，计算次数约为$M^2=(10^4)^2=10^8$；② 若把客人放入哈希表中，再依次从已知夫妻中查找落单情况，计算次数约为$2N=10^5$，效率远高于方法①

#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 50010;
int n, m, couple[N][2];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &couple[i][0], &couple[i][1]);

    scanf("%d", &m);
    unordered_set<int> person;
    int x;
    while(m--) {
        scanf("%d", &x);
        person.insert(x);
    }

    for (int i = 0; i < n; i++) {
        int a = couple[i][0], b = couple[i][1];
        if (person.count(a) && person.count(b)) {
            person.erase(a);
            person.erase(b);
        }
    }

    vector<int> res;
    for (auto elem : person)
        res.push_back(elem);

    sort(res.begin(), res.end());

    printf("%d\n", res.size());
    if (res.size()) {
        printf("%05d", res[0]);
        for (int i = 1; i < res.size(); i++)
            printf(" %05d", res[i]);
        printf("\n");
    }

    return 0;
}

1128. N Queens Puzzle

笔记

已知列一定合法，那么只可能在行、主对角线和次对角线出问题。可用bool数组描述棋盘的行、主对角线、次对角线的占用情况。
假设原点在左下角，x为行位置，y为列位置，row[i] == true表示第i行已经被占用，不能再放棋子；dg[x + y] == true表示格子(x, y)所在的主对角线已被占用；udg[y - x + n] == true表示格子(x, y)所在的次对角线已被占用，之所以+ n是因为y - x可能为负数，而y - x + n避免了该情况，同时不影响其含义。
因此每读入棋子在某一列的位置后，先判断该位置相关的行、主对角线、次对角线是否已被占用。如果已被占用，则一定不合法；否则更新放下棋子后，对相关的行、主对角线、次对角线的影响

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
bool row[N], dg[2 * N], udg[2 * N];

int main() {
    int t;
    scanf("%d", &t);

    int n, x;
    while(t--) {
        memset(row, 0, sizeof row);
        memset(dg, 0, sizeof dg);
        memset(udg, 0, sizeof udg);

        scanf("%d", &n);
        bool success = true;
        for (int y = 1; y <= n; y++) {
            scanf("%d", &x);
            if (row[x] || dg[x + y] || udg[y - x + n]) success = false;
            row[x] = dg[x + y] = udg[y - x + n] = true;
        }

        if (success) puts("YES");
        else puts("NO");
    }

    return 0;
}

1129. Recommendation System

笔记

首先用一个int数组记录每个商品访问的次数，然后用一个长度为$11$（因为至多$10$个，加上刚刚访问的一共$11$个）的数组res保存访问次数位于前$k$的商品id。
每次用户访问一个商品时，先输出res数组的前$k$个商品，然后更新访问次数，检查被更新的商品是否位于res中。
- 如果不在里头，则插入到res末尾
- 如果在里头，则什么也不做
之后对res排序，但只输出前k个。由于开始访问的商品个数不到k，因此实际输出的元素个数是数组元素个数与k的较小者。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50010;
int n, k, cnt[N], res[11];

int main() {
    scanf("%d%d", &n, &k);
    int id, m = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &id);
        if (i) {
            // 推荐商品
            printf("%d:", id);
            for (int j = 0; j < m; j++)
                printf(" %d", res[j]);
            printf("\n");
        }

        cnt[id]++;
        bool exist = false;
        for (int j = 0; j < m; j++)
            if (res[j] == id) {
                exist = true;
                break;
            }
        if (!exist) res[m++] = id;      // 插入末尾
        sort(res, res + m, [](int a, int b) {
            if (cnt[a] != cnt[b]) return cnt[a] > cnt[b];
            else return a < b;
        });
        m = min(m, k);      // 更新为实际长度和k的较小者
    }


    return 0;
}

1132. Cut Integer

笔记

$Z$至多$30$位，平分后每个$15$位，都可用int存储。为了快速切分，可先以字符串形式读入，然后用stoi转成int型。
本题需注意一个隐藏条件，$a \times b$不能为$0$，因为$0$不能做除数

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;

int main() {
    int n;
    string s;
    cin >> n;
    while(n--) {
        cin >> s;

        int len = s.size();
        int n = stoi(s);
        int a = stoi(s.substr(0, len / 2));
        int b = stoi(s.substr(len / 2, len));
        if (a * b && n % (a * b) == 0) puts("Yes");
        else puts("No");
    }

    return 0;
}

1140. Look-and-say Sequence

笔记

用第一类双指针算法找到重复段，然后计算长度，构造下一个串

#include <iostream>
using namespace std;

int main() {
    int d, n;
    cin >> d >> n;

    string a = to_string(d);
    for (int i = 1; i < n; i++) {
        string b;
        int j = 0, k = 1;
        while (j < a.size()) {
            k = j + 1;
            while(k < a.size() && a[k] == a[j]) k++;    // 找重复部分
            int len = k - j;
            b += a[j] + to_string(len);
            j = k;
        }
        a = b;
    }
    cout << a << endl;

    return 0;
}

1147. Heaps

笔记

读入完全二叉树，从下标1开始存放元素
根据大根堆和小根堆的定义，分别检查前一半的结点是否满足父节点大于（小于）子结点的关系即可：如果都不满足，说明不是堆
用dfs实现后序遍历

#include <iostream>
using namespace std;
const int N = 1010;
int t, n, a[N];

void dfs(int u) {
    int p = 2 * u, q = 2 * u + 1;
    if (p <= n) dfs(p);
    if (q <= n) dfs(q);

    printf("%d", a[u]);
    if (u != 1) printf(" ");        // 根节点最后输出
}

int main() {
    scanf("%d%d", &t, &n);
    while(t--) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);

        bool max_heap = true, min_heap = true;
        // 判断是否是大根堆
        for (int i = 1; i <= (n + 1) / 2 && max_heap; i++) {
            int p = 2 * i, q = 2 * i + 1;
            if (p <= n && a[i] < a[p]) max_heap = false;
            if (q <= n && a[i] < a[q]) max_heap = false;
        }

        if (!max_heap) {
            // 判断是否是小根堆
            for (int i = 1; i <= (n + 1) / 2 && min_heap; i++) {
                int p = 2 * i, q = 2 * i + 1;
                if (p <= n && a[i] > a[p]) min_heap = false;
                if (q <= n && a[i] > a[q]) min_heap = false;
            }
        }

        if (max_heap) puts("Max Heap");
        else if (min_heap) puts("Min Heap");
        else puts("Not Heap");

        dfs(1);     // 后序遍历
        printf("\n");
    }

    return 0;
}

0 评论

App 内打开

AcWing《PAT甲级辅导课》 第11章 模拟

第11章 模拟