洛谷题单——数据结构0x1

P3156 询问学号

#include <iostream>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

using  namespace std;

const int N = 1e7 + 10;
int a[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    while (m--)
    {
        int x;
        cin >> x;
        cout << a[x] << endl;
    }
}

P3613 【深基15.例2】寄包柜

这题需要两次映射，看了题解，发现还可以通过嵌套map实现！

#include <iostream>
#include <map>
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

using  namespace std;

map<int, map<int, int >> mp;

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

    while (m--) {
        int op;
        cin >> op;
        if(op == 1)
        {
            int x, y ,z;
            cin >> x >> y >> z;
            mp[x][y] = z;
        }
        else
        {
            int x ,y;
            cin >> x >> y;
            cout << mp[x][y] << endl;
        }
    }
}

P1449 后缀表达式

简化版表达式求值，使用栈来存储计算值

#include <iostream>
#include <stack>
#include <string>
#include <cctype>

using namespace std;

using i64 = long long;

stack<i64> st;

int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < s.size()  - 1; i++)
    {
        if (isdigit(s[i]))
        {
            i64 res = 0;
            while (i < s.size() && isdigit(s[i]))
            {
                res = res * 10 + (s[i] - '0');
                i++;
            }
            st.push(res);
  
        }
        else if (s[i] == '.')
        {
            continue;
        }
       
        else
        {
            i64 a, b;
            a = st.top();
            st.pop();
            b = st.top();
            st.pop();
            if (s[i] == '+')
                st.push(b + a);
            if (s[i] == '-')
                st.push(b - a);
            if (s[i] == '*')
                st.push(b * a);
            if (s[i] == '/')
                st.push(b / a);
        }
    }
    cout << st.top() << endl;
    return 0;
}

P1996 约瑟夫问题

这题其实最好用队列做，当遍历到该元素时，直接出列即可。这里我是用数组模拟。

#include <iostream>

using namespace std;
const int N = 105;
int arr[N];

int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    arr[i - 1] = i;
  }
  int pos = 0;
  for (int i = 1; i <= n; i++) {
    int cnt = 0;
    while (1) {

      if (arr[pos]) {		//未出队
        cnt++;
      }
      if (cnt == m) {		//指定元素输出，并出队（置0）
        cout << arr[pos] << " ";
        arr[pos] = 0;
        break;
      }
      pos = (pos + 1) % n;	//下一元素
    }
  }
}

P1160 队列安排

这里没能做出来，一直在调bug，这里直接复制题解上的std::list来解决。

这题其实还能用树来完成：题解 P1160 【队列安排】 - 洛谷专栏 (luogu.com.cn)

// #include <iostream>

// using namespace std;

// const int N = 1e5 + 5;

// int head, e[N], ne[N], idx;

// void init() {
//   head = -1;
//   idx = 0;
// }

// void add_to_head(int x) {
//   e[idx] = x;
//   ne[idx] = head;
//   head = idx;
//   idx++;
// }

// void insert(int x, int pos) {
//     if(pos == 0)            //当pos为0时，直接插入到头部，insert只适用于非头节点插入
//     {
//         add_to_head(x);
//         return;
//     }
//   e[idx] = x;
//   ne[idx] = ne[pos];
//   ne[pos] = idx;
//   idx++;
// }

// int find(int x)
// {
//     int pos = 0;
//     for(int i = head; i != -1; i = ne[i])
//     {

//         if(e[i] == x) return pos;
//     }
//     return -1;
// }

// void remove(int pos) { ne[pos] = ne[ne[pos]]; }

// int main() {
//   int n, m;
//   int x, y;
//   cin >> n;
//   init();
//   int cnt = 1;
//   add_to_head(cnt++);
//     for(int i = 1; i <  n; i ++)
//     {

//     cin >> x >> y;
//     if (y == 1) {
    
//       insert(cnt++, find(x));
//     } else {
//       insert(cnt++, find(x) -1);
//     }
//   }

 
//     cin >> m;
//     for(int i =  0; i < m; i ++ )
//     {
//         cin >> x;
//         if(find( x) - 1)
//         remove( find(x) - -1);
//     }


// }


#include <iostream>
#include <list>

using namespace std;



using Iter = list<int>::iterator; // 定义迭代器类型别名
const int maxN = 1e5 + 10; 
Iter pos[maxN]; // 记录每个同学在链表中的位置
list<int> queList; // 双向链表
bool erased[maxN]; // 记录同学是否被移除
int N; 


void buildQueue() {
    queList.push_front(1); // 将1号同学加入队列头
    pos[1] = queList.begin(); // 记录1号同学的位置
    
    for (int i = 2; i <= N; i++) {
        int k, p;
        scanf("%d%d", &k, &p); // 输入插入指令
        if (p == 0) {
            pos[i] = queList.insert(pos[k], i); // 插入到k号同学左边
        } else {
            auto nextIter = next(pos[k]);
            pos[i] = queList.insert(nextIter, i); // 插入到k号同学右边
        }
    }
    
    int M;
    scanf("%d", &M); // 输入要移除的同学数量
    for (int x, i = 1; i <= M; i++) {
        scanf("%d", &x); // 输入要移除的同学编号
        if (!erased[x]) {
            queList.erase(pos[x]); // 移除指定同学
        }
        erased[x] = true; // 标记同学已被移除
    }
}


int main()
{
  scanf("%d", &N);
  buildQueue();
  bool first = true;
  for (int x: queList)
  {
      if (!first)
          putchar(' ');
      first = false;
      printf("%d", x);
  }
  putchar('\n');
  return 0;
}

P1540 [NOIP2010 提高组] 机器翻译

使用队列来模拟内存，然后定义一个辅助数组记录哪些值被加载到内存上

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

typedef long long LL;                            


bool a[1005];
queue<int> que;
int main()
{
    int m ,n;
    cin >> m >> n;
    int cnt = 0;
    while(n--)
    {
        int tmp;
        cin >> tmp;
        if(a[tmp])
            continue;
        a[tmp] = true;
        cnt++;
        que.push(tmp);
        if(que.size() > m)
            {
                a[que.front()] = false;
                que.pop();
            }
    }
    cout << cnt << endl;
}

P2058 [NOIP2016 普及组] 海港

我们可以记录每个人而不是每艘船来解决问题

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

struct {
    int tm;
    int where;
}ship_man[300005];

int addr[100005];
int uid;
int pre_uid;

int main()
{
    int n;
    cin >> n;
    int res = 0;
    while(n--)
    {
        int t, man, where;
        cin >> t >> man;
        while(man--)
        {
            cin >> where;
            ship_man[uid].where = where;
            ship_man[uid].tm = t;
            if(addr[where] == 0)    //新物种
                res++;
            addr[where]++;
            uid++;
        } 
        while(ship_man[uid - 1].tm - ship_man[pre_uid].tm >= 86400)
        {
            addr[ship_man[pre_uid].where]--;
            if(addr[ship_man[pre_uid].where] == 0)  //物种灭绝
                res--;
            pre_uid++;
        }
        cout << res << endl;
    }
}