头像

trudbot

AC协会




离线:9分钟前


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

活动打卡代码 AcWing 3428. 放苹果

trudbot
36分钟前
  • 递归的结束条件:苹果的数量为1或为0、盒子的数量为1, 这三种情况只有一种放法
  • 当苹果的数量小于盒子的数量时, 多余的盒子可以去掉
  • 当苹果的数量大于或等于盒子的数量时, 分为两部分
    • 所有的盒子都用到了的情况下, 每个盒子先放一个苹果, 得到了(n-m, m)的子问题
    • 至少存在一个盒子没用到的情况下, 抛弃一个盒子, 变成了(n, m-1)的子问题
//
// Created by trudbot on 2022/6/27.
//

#include <bits/stdc++.h>

using namespace std;

int dfs(int n, int m)
{
    if(n <= 1 || m == 1)
        return 1;
    if(n >= m)
        return dfs(n-m, m) + dfs(n, m-1);
    if(n < m)
        return dfs(n, n);
}

int main() {
    int n, m;
    while(cin >> n >> m)
        cout << dfs(n, m) << endl;
    return 0;
}




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

trudbot
12小时前
//
// 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
12小时前

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

//
// 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
4天前
//
// 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;
}