头像

trudbot

AC协会




在线 


最近来访(11)
用户头像
123_34
用户头像
NZX
用户头像
杨淇
用户头像
Tiebo
用户头像
J_C
用户头像
乒乒乓乓_4
用户头像
Azusamitsusa
用户头像
islandempty
用户头像
encoder
用户头像
白天数星星QAQ

活动打卡代码 AcWing 693. 行程排序

trudbot
11小时前
//
// Created by trudbot on 2022/6/26.
//

#include <bits/stdc++.h>

using namespace std;
unordered_map<string, string> nextCity;
unordered_map<string, bool> selected;

int main() {
    int T, N;
    cin >> T;
    string s1, s2;
    for(int i=1; i<=T; i++)
    {
        cin>> N;
        getchar();
        for(int j=0; j<N; j++)
        {
            getline(cin, s1);
            getline(cin, s2);
            nextCity[s1] = s2;
            selected[s2] = true;
        }

        string curr;
        for(auto &city : nextCity)
        {
            if(selected.count(city.first) == 0)
            {
                curr = city.first;
                break;
            }
        }

        printf("Case #%d:", i);
        while(nextCity.count(curr) != 0)
        {
            cout << " " << curr << "-" << nextCity[curr];
            curr = nextCity[curr];
        }
        printf("\n");
        nextCity.clear();
        selected.clear();
    }
    return 0;
}




trudbot
11小时前

用一个哈希表把每张机票的出发地和目的地都存起来, 就得到了类似于链表的一个东西, 这时候我们只需要找的整个行程最开始出发的地方, 遍历即可。

//
// Created by trudbot on 2022/6/26.
//

#include <bits/stdc++.h>

using namespace std;
unordered_map<string, string> nextCity;
unordered_map<string, bool> selected;

int main() {
    int T, N;
    cin >> T;
    string s1, s2;
    for(int i=1; i<=T; i++)
    {
        cin>> N;
        getchar();
        for(int j=0; j<N; j++)
        {
            getline(cin, s1);
            getline(cin, s2);
            nextCity[s1] = s2;
            selected[s2] = true;
        }

        string curr;
        for(auto &city : nextCity)
        {
            if(selected.count(city.first) == 0)
            {
                curr = city.first;
                break;
            }
        }

        printf("Case #%d:", i);
        while(nextCity.count(curr) != 0)
        {
            cout << " " << curr << "-" << nextCity[curr];
            curr = nextCity[curr];
        }
        printf("\n");
        nextCity.clear();
        selected.clear();
    }
    return 0;
}



活动打卡代码 AcWing 3311. 最长算术

trudbot
1天前
//
// Created by trudbot on 2022/6/25.
//

#include <bits/stdc++.h>
#define MaxN 200000
using namespace std;

int main() {
    int arr[MaxN];
    int T, N;
    int i, j;
    int max;
    cin >> T;
    int temp;
    for(i=1; i<=T; i++)
    {
        cin >> N;
        memset(arr, 0, N);
        for(j=0; j<N; j++)
            cin >> arr[j];

        for(j=N-1; j>=1; j--)
            arr[j] -= arr[j-1];

        max = 0;
        int r = 1, len;
        while(r < N)
        {
            len = 0;
            int curr = arr[r];
            for(r; r<N; r++)
            {
                if(arr[r] == curr)
                    len++;
                else
                    break;
            }
            if(len > max)
                max = len;
        }

        printf("Case #%d: %d\n", i, max+1);
    }
    return 0;
}




trudbot
3天前

方法一 暴力

将每辆巴士的服务范围存储起来, 再遍历得到服务某城市的巴士数量.
c++10ms, 时间限制以及测试数据都太宽松, 暴力完全没有问题
单次测试数据的时间复杂度为O(N*P)

//
// Created by trudbot on 2022/6/23.
//

#include <bits/stdc++.h>

using namespace std;

int main() {
    vector<pair<int, int>> bars;

    int T, N, P, C;
    int l, r;
    int i, j, k;
    int count;
    cin >> T;
    for(i=1; i<=T; i++)
    {
        cin >> N;
        for(j=0; j<N; j++)
        {
            cin >> l >> r;
            bars.emplace_back(l, r);
        }

        cin >> P;
        cout << "Case #" << i << ":";
        while(P--)
        {
            count = 0;
            cin>> C;
            for(auto p : bars)
            {
                if(C>=p.first && C<=p.second)
                    count++;
            }
            cout << " " << count;
        }

        bars.clear();
        cout << endl;
    }

    return 0;
}

更为巧妙的方法

我们是否能通过所有巴士的服务范围而直接得到任何一座城市的巴士数量呢
对一段序列{0, 0, 0, 0, 0}, 如果我们想让它第二到第四个元素都加个1, 我们可以让第二个元素+1, 第五个元素-1,
得到{0, 1, 0, 0, -1}, 再执行seq[i] = seq[i]+seq[i-1], 就可以得到{0, 1, 1, 1, 0}. 这种变化是线性传递的, 2处的变化和5处的变化相互抵消, 从而2的变化只影响了[2, 5)

如下代码c++6ms, 面对较大数据时表现较好

//
// Created by trudbot on 2022/6/23.
//

#include <bits/stdc++.h>

using namespace std;

int main() {
    int count[5010];
    int T, N, P, C;
    int i, j, k;
    int l, r;

    cin >> T;
    for(i=1; i<=T; i++)
    {
        for(j=1; j<5001; j++)
            count[j] = 0;
        cin >> N;
        for(j=0; j<N; j++)
        {
            cin>> l >> r;
            count[l]++;
            count[r+1]--;
        }

        for(j=2; j<=5001; j++)
            count[j] += count[j-1];

        cin >> P;
        cout << "Case #" << i << ":";
        while(P--)
        {
            cin >> C;
            cout << " " << count[C];
        }

        cout << endl;
    }

    return 0;
}




trudbot
3天前

很明显这是一个图遍历的问题, 每个人最大能到达的房间数量我们设为MaxSteps, 则这个值应该为 1 + (前后左右中满足号码要求的房间)的MaxStep之和.
与最短路径的思想是类似的.

//
// Created by trudbot on 2022/6/23.
//

#include <bits/stdc++.h>
using namespace std;
#define MaxN 1010

int rooms[MaxN][MaxN];//记录房间的编号以及位置
int visited[MaxN][MaxN];//用于记录该位置房间MaxStep是否已经确定
int MaxSteps[MaxN][MaxN];//记录最大可到达房间数
int s;
map<int, pair<int, int>> pos;//记录对应编号房间到其位置的映射, (不是必须)


void CountMaxSteps(int row, int col)
{
    if(visited[row][col])
        return;

    visited[row][col] = true;

    if(row > 1)//如果上边有房间
    {
        if(rooms[row-1][col] == rooms[row][col]+1)
        {
            CountMaxSteps(row-1, col);
            MaxSteps[row][col] += MaxSteps[row-1][col];
        }
    }

    if(col > 1)//如果左边有房间
    {
        if(rooms[row][col-1] == rooms[row][col]+1)
        {
            CountMaxSteps(row, col-1);
            MaxSteps[row][col] += MaxSteps[row][col-1];
        }
    }

    if(row < s)//如果下面有房间
    {
        if(rooms[row+1][col] == rooms[row][col]+1)
        {
            CountMaxSteps(row+1, col);
            MaxSteps[row][col] += MaxSteps[row+1][col];
        }
    }

    if(col < s)//如果右边有房间
    {
        if(rooms[row][col+1] == rooms[row][col]+1)
        {
            CountMaxSteps(row, col+1);
            MaxSteps[row][col] += MaxSteps[row][col+1];
        }
    }

}

int main() {

    int T;
    cin >> T;

    for(int i=1; i<=T; i++)
    {
        cin >> s;
        //一系列数据输入及初始化
        for(int j=1; j<=s; j++)
            for(int k=1; k<=s; k++)
            {
                cin >> rooms[j][k];
                pos[rooms[j][k]] = {j, k};
                visited[j][k] = false;
                MaxSteps[j][k] = 1;
            }

        //编号较小的房间更有可能到达尽可能多的房间, 当然这里也可以直接遍历, 就不需要用哈希表了
        for(int j=1; j<=s; j++)
            for(int k=1; k<=s; k++)
            {
                if(!visited[j][k])
                    CountMaxSteps(j, k);
            }

        //找出最大的房间
        int res = 1;
        for(int j=2; j<=s*s; j++)
        {
            if(MaxSteps[pos[j].first][pos[j].second] > MaxSteps[pos[res].first][pos[res].second])
                res = j;
        }

        cout << "Case #" << i << ": " << res << " " << MaxSteps[pos[res].first][pos[res].second] << endl;
    }


    return 0;
}



活动打卡代码 AcWing 691. 立方体IV

trudbot
3天前
//
// Created by trudbot on 2022/6/23.
//

#include <bits/stdc++.h>
using namespace std;
#define MaxN 1010

int rooms[MaxN][MaxN];
int visited[MaxN][MaxN];
int MaxSteps[MaxN][MaxN];
int s;
map<int, pair<int, int>> pos;

void CountMaxSteps(int row, int col)
{
    if(visited[row][col])
        return;

    visited[row][col] = true;

    if(row > 1)
    {
        if(rooms[row-1][col] == rooms[row][col]+1)
        {
            CountMaxSteps(row-1, col);
            MaxSteps[row][col] += MaxSteps[row-1][col];
        }
    }

    if(col > 1)
    {
        if(rooms[row][col-1] == rooms[row][col]+1)
        {
            CountMaxSteps(row, col-1);
            MaxSteps[row][col] += MaxSteps[row][col-1];
        }
    }

    if(row < s)
    {
        if(rooms[row+1][col] == rooms[row][col]+1)
        {
            CountMaxSteps(row+1, col);
            MaxSteps[row][col] += MaxSteps[row+1][col];
        }
    }

    if(col < s)
    {
        if(rooms[row][col+1] == rooms[row][col]+1)
        {
            CountMaxSteps(row, col+1);
            MaxSteps[row][col] += MaxSteps[row][col+1];
        }
    }

}

int main() {

    int T;
    cin >> T;

    for(int i=1; i<=T; i++)
    {
        cin >> s;
        for(int j=1; j<=s; j++)
            for(int k=1; k<=s; k++)
            {
                cin >> rooms[j][k];
                pos[rooms[j][k]] = {j, k};
                visited[j][k] = false;
                MaxSteps[j][k] = 1;
            }

        for(int j=1; j<=s*s; j++)
        {
            if(!visited[pos[j].first][pos[j].second])
            {
                CountMaxSteps(pos[j].first, pos[j].second);
            }
        }

        int res = 1;
        for(int j=2; j<=s*s; j++)
        {
            if(MaxSteps[pos[j].first][pos[j].second] > MaxSteps[pos[res].first][pos[res].second])
                res = j;
        }

        cout << "Case #" << i << ": " << res << " " << MaxSteps[pos[res].first][pos[res].second] << endl;
    }


    return 0;
}




trudbot
4天前

这道题的难点在于确定嫌疑人的的组别, 一开始理解错了, 以为一个诈骗团伙中任两个人都互相打过电话, 但其实是只要嫌疑人n跟诈骗团伙内的任意一个人互相打过电话, n就可以归为这个团伙内的人.

图的存储及嫌疑人判定
这部分较为简单, 直接上完整代码

//有向图矩阵, CallTime[a][b]表示a 给 b 打电话的总时长
int CallTime[MaxN][MaxN];

//判断n是否为嫌疑人
inline bool IsSuspect(int n){
    int outNum = 0, inNum = 0;
    for(int i=1; i<=N; i++){
        if(CallTime[n][i] && CallTime[n][i] <= 5){
            outNum++;
            if(CallTime[i][n])
                inNum++;
        }
    }
    if(outNum <= K || outNum < inNum*5)
        return false;
    return true;
}

嫌疑人归类
用一个数组来保存嫌疑人的组别.
team[n] = 0时代表n的组别未确定

int team[MaxN];

这里很显然是图的遍历问题, 我们定义一个计数器int teamNum = 1;.
首先我们在所有嫌疑人中找到一个未确定组别的嫌疑人n, 从n开始进行遍历, 这里我用的是BFS, 所有与n相互通话的嫌疑人都归为当前组别, 然后对这些嫌疑人进行遍历.BFS结束后, 计数器加一

最后所有的嫌疑人都确定了组别, 我们按teamNum从小到大依次输出各团伙即可

完整代码

//
// Created by trudbot on 2022/6/23.
//

#include <bits/stdc++.h>
#define MaxN 1001

using namespace std;
int N, K;

//有向图矩阵, CallTime[a][b]表示a 给 b 打电话的总时长
int CallTime[MaxN][MaxN];
int team[MaxN];
int teamNum = 1;
//判断n是否未嫌疑人
inline bool IsSuspect(int n){
    int outNum = 0, inNum = 0;
    for(int i=1; i<=N; i++){
        if(CallTime[n][i] && CallTime[n][i] <= 5){
            outNum++;
            if(CallTime[i][n])
                inNum++;
        }
    }
    if(outNum <= K || outNum < inNum*5)
        return false;
    return true;
}


int main() {
    int M;
    cin >> K >> N >> M;
    int a, b, time;

    while(M--){
        cin >> a >> b >> time;
        CallTime[a][b] += time;
    }
    vector<int> suspect;
    for(int i=1; i<=N; i++){
        if(IsSuspect(i)){
            suspect.push_back(i);
        }
    }
    if(suspect.empty()){
        cout << "None" << endl;
        return 0;
    }
    int temp;

    for(int i : suspect){
        if(team[i] == 0){//找一个为确定组别的顶点作为起点
            queue<int> q;
            q.push(i);
            while(!q.empty()){
                temp = q.front();
                q.pop();
                //这个判断的意义在于, 一个顶点可能被多个与它双向连通的顶点加入队列
                if(team[temp] != 0) continue;
                team[temp] = teamNum;
                for(int j : suspect){
                    if(team[j] == 0 && CallTime[temp][j] && CallTime[j][temp])
                        q.push(j);
                }
            }
            teamNum++;
        }
    }

    //输出
    for(int i=1; i<teamNum; i++){
        for(int j=1; j<=N; j++)
            if(team[j] == i)
                cout << j << " ";
        cout << endl;
    }

    return 0;
}

有些地方处理得比较粗暴, 存在优化空间
作者:trudbot 结果: Accepted 通过了 11/11个数据 运行时间: 484 ms 运行空间: 5084 KB




trudbot
4天前
//
// Created by trudbot on 2022/6/23.
//

#include <bits/stdc++.h>

using namespace std;
int arr[201];

int main() {
    int n, N;
    cin >> n >> N;
    for(int i=1; i<=n; i++){
        cin >> arr[i];
    }
    int sum = 0;
    int min = N;
    for(int i=n; i>=0; i--){
        if(arr[i] < min){
            sum += (min - arr[i]) * i;
            min = arr[i];
        }
    }
    cout << sum << endl;
    return 0;
}


活动打卡代码 AcWing 4279. 笛卡尔树

trudbot
4天前
//
// Created by trudbot on 2022/6/21.
//作者:trudbot 结果: Accepted 通过了 10/10个数据 运行时间:10 ms 运行空间: 212 KB

#include <bits/stdc++.h>
using namespace std;

typedef struct node{
    int val;
    struct node* left, *right;
}*Node;

//新建结点
inline Node NewNode(int val){
    Node n = new node;
    n->val = val;
    n->left = n->right = nullptr;
    return n;
}

//找到子序列中最小元素的下标
inline int FindMin(const int* seq, int first, int last){
    if(first == last){
        return first;
    }
    if(first > last){
        return -1;
    }
    int mini = first;
    while(++first <= last){
        if(seq[first] < seq[mini]){
            mini = first;
        }
    }
    return mini;
}

//树的建立
Node BuildTree(const int* seq, int first, int last){
    if(first == last){//序列只有一个元素, 就可以返回一个无孩子的结点, 当然这句判断可有可无, 这里是为了尽量减少递归层数
        return NewNode(seq[first]);
    }
    if(first > last){//序列为空, 返回NULL
        return nullptr;
    }
    int pos = FindMin(seq, first, last);
    Node root = NewNode(seq[pos]);
    root->left = BuildTree(seq, first, pos-1);
    root->right = BuildTree(seq, pos+1, last);
    return root;
}

//广度优先遍历
void BFS(Node root){
    queue<Node> q;
    Node temp;
    q.push(root);
    while(!q.empty()){
        temp = q.front();
        q.pop();
        cout << temp->val << " ";
        if(temp->left)
            q.push(temp->left);
        if(temp->right)
            q.push(temp->right);
    }
}


int main() {
    int N;
    cin>> N;
    int seq[N];
    for(int i=0; i<N; i++){
        cin >> seq[i];
    }
    Node tree = BuildTree(seq, 0, N-1);
    BFS(tree);
    return 0;
}




trudbot
5天前

解题思路
树的存储
树的每个结点的权各不相同, 且1 <= weight <=1000, 所以我们可以考虑用大数组构建哈希来存储, 数组的下标即是结点的权又是结点的位置, 这样我们就不用额外保存权了
另外为了后续的判断方便, 我们可以对每个结点的前驱进行保存

#define MaxNum 1001

int l[MaxNum], r[MaxNum], pre[MaxNum];//左孩子, 右孩子, 以及前驱(父母)
int Root;//用来保存根结点的位置

以及用两个数组来保存中序和后序序列

int inorder[31], postorder[31];

树的构建
后序是: 左 -> 右 -> 根
中序是: 左 -> 根 -> 右
所以一段后序序列的最后一个元素必然是根结点,
这时候我们可以在中序序列中查找到根的位置i, 这时左右子树的中序序列就确定了:在i左边的是左子树, i右边的是右子树

再通过左右子树的中序序列长度, 我们也可以获取到它们的后序序列.

这样左右子树的中、后序序列我们就都确定了, 进行递归即可

//参数分别为: 中序序列的两个边界, 后序序列的两个边界
int BuildTree(int li, int ri, int lp, int rp){
    if(li > ri){
        return 0;//0为无效位置
    }
    int root = postorder[rp];
    int i;
    for(i=li; i<=ri; i++){
        if(inorder[i] == root){
            break;
        }
    }
    //边界的确定有些麻烦,检验的一个方法是,两个序列的长度必须相等
    l[root] = BuildTree(li, i-1, lp, lp+i-li-1);
    if(l[root] != 0){
        pre[l[root]] = root;
    }
    r[root] = BuildTree(i+1, ri, rp+i-ri, rp-1);
    if(r[root] != 0){
        pre[r[root]] = root;
    }
    return root;
}

陈述正确性判断
我们先把陈述读入字符串内, 然后对字符串中查找关键字以确定陈述的类型, 用sscanf读入数据, 进行判断即可
在给出完整函数之前, 我们先来解决一些比较难判断的陈述

  • 结点的层次
    我们用一个数组来保存所有结点的层次信息, 再用一个函数完成层次信息的获取
int Level[MaxNum];
void getLevel(int root, int level){
    if(root == 0){
        return;
    }
    Level[root] = level;
    getLevel(l[root], level+1);
    getLevel(r[root], level+1);
}
  • 是否为满二叉树

满二叉树即除叶结点外所有的结点的度都为2
给出判断函数

bool IsFullTree(int root){
    if((r[root] == 0) && (l[root] == 0)){//叶子结点
        return true;
    }
    if((r[root] == 0) ^ (l[root] == 0)){//度为1的结点
        return false;
    }
    return IsFullTree(l[root]) && IsFullTree(r[root]);
}

最后给出完整的判断函数

bool Solution(const string& str){
    int A, B;
    if(str.find("root") < str.length()){
        sscanf(str.c_str(), "%d", &A);
        return A == Root;
    }
    else if(str.find("siblings") < str.length()){
        sscanf(str.c_str(), "%d and %d", &A, &B);
        if(A == B) return false;
        return pre[A] == pre[B];
    }
    else if(str.find("parent") < str.length()){
        sscanf(str.c_str(), "%d is the parent of %d", &A, &B);
        return l[A] == B || r[A] == B;
    }
    else if(str.find("left") < str.length()){
        sscanf(str.c_str(), "%d is the left child of %d", &A, &B);
        return l[B] == A;
    }
    else if(str.find("right") < str.length()){
        sscanf(str.c_str(), "%d is the right child of %d", &A, &B);
        return r[B] == A;
    }
    else if(str.find("same level") < str.length()){
        sscanf(str.c_str(), "%d and %d", &A, &B);
        return Level[A] == Level[B];
    }
    else if(str.find("full tree") < str.length()){
        return IsFullTree(Root);
    }
}

完整程序

//
// Created by trudbot on 2022/6/22.
//结果: Accepted 通过了 11/11个数据 运行时间: 22 ms 运行空间: 216 KB

#include <bits/stdc++.h>
#define MaxNum 1001
using namespace std;

int l[MaxNum], r[MaxNum], pre[MaxNum];

int Root;
int inorder[31], postorder[31];
int Level[MaxNum];

int BuildTree(int li, int ri, int lp, int rp){
    if(li > ri){
        return 0;
    }
    int root = postorder[rp];
    int i;
    for(i=li; i<=ri; i++){
        if(inorder[i] == root){
            break;
        }
    }
    l[root] = BuildTree(li, i-1, lp, lp+i-li-1);
    if(l[root] != 0){
        pre[l[root]] = root;
    }
    r[root] = BuildTree(i+1, ri, rp+i-ri, rp-1);
    if(r[root] != 0){
        pre[r[root]] = root;
    }
    return root;
}

void getLevel(int root, int level){
    if(root == 0){
        return;
    }
    Level[root] = level;
    getLevel(l[root], level+1);
    getLevel(r[root], level+1);
}

bool IsFullTree(int root){
    if((r[root] == 0) && (l[root] == 0)){//叶子结点
        return true;
    }
    if((r[root] == 0) ^ (l[root] == 0)){//度为1的结点
        return false;
    }
    return IsFullTree(l[root]) && IsFullTree(r[root]);
}

bool Solution(const string& str){
    int A, B;
    if(str.find("root") < str.length()){
        sscanf(str.c_str(), "%d", &A);
        return A == Root;
    }
    else if(str.find("siblings") < str.length()){
        sscanf(str.c_str(), "%d and %d", &A, &B);
        if(A == B) return false;
        return pre[A] == pre[B];
    }
    else if(str.find("parent") < str.length()){
        sscanf(str.c_str(), "%d is the parent of %d", &A, &B);
        return l[A] == B || r[A] == B;
    }
    else if(str.find("left") < str.length()){
        sscanf(str.c_str(), "%d is the left child of %d", &A, &B);
        return l[B] == A;
    }
    else if(str.find("right") < str.length()){
        sscanf(str.c_str(), "%d is the right child of %d", &A, &B);
        return r[B] == A;
    }
    else if(str.find("same level") < str.length()){
        sscanf(str.c_str(), "%d and %d", &A, &B);
        return Level[A] == Level[B];
    }
    else if(str.find("full tree") < str.length()){
        return IsFullTree(Root);
    }
}

int main() {
    int N;
    cin >> N;
    for(int i=0; i<N; i++)
        cin >> postorder[i];

    for(int i=0; i<N; i++)
        cin >> inorder[i];

    Root = BuildTree(0, N-1, 0, N-1);
    getLevel(Root, 1);

    int M;
    cin >> M;
    getchar();
    string str;
    while(M--){
        getline(cin, str);
        if(Solution(str)){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }

    return 0;
}