vector在算法竞赛中主要当作可变数组来用

询问学号

分析：直接建立一个数组按照顺序记录按顺序到达的同学的学号，之后在数组中查询即可

#include <cstdio>
#include <vector>
using namespace std;
int n,m,tmp;
int main(){
    vector<int> v;//定义一个变长数组
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d",&tmp);
        v.push_back(tmp);//按进入顺序存入vector
    }
    for(int i=0;i<m;i++){
        scanf("%d",&tmp);
        printf("%d\n",v[tmp-1]);
    }
    return 0;
}

寄包柜

分析：第一个想到的肯定是二维数组，但是看下数据范围：$4 \cdot 10^5 \cdot 10^5 \approx 40G$ ，显然超出内存限制。
但后面特别说明：已知超市里共计不会超过 $10^7$ 个柜子，$\log_{2}^{4*10^7} \approx 25.2535 $ 也就是说其实总的空间 $4 \cdot 10^7 \approx 2^{25.2535} < 64M $ 就可以满足需要，但由于每个柜子中的格子数是未知的，这种情况正是变长数组 vector 的用武之地啊。

#include <cstdio>
#include <vector>
using namespace std;
int n,q,opt,i,j,k;
int main(){
    scanf("%d%d",&n,&q);
    vector<vector<int> >locker(n+1);//编号从1到n，0号没用
    while(q--){//q次询问
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d%d",&i,&j,&k);
            if(locker[i].size()<j+1){//要有1号到j号共j+1个盒子(算上0号)
                locker[i].resize(j+1);//不够就扩展
            }
            locker[i][j]=k;//够的话就存入
        }
        else{
            scanf("%d%d",&i,&j);
            printf("%d\n",locker[i][j]);//查询直接输出
        }
    }
    return 0;
}