风向晚。maplefan

　　体育老师小明要将自己班上的学生按顺序排队。他首先让学生按学号从小到大的顺序排成一排，学号小的排在前面，然后进行多次调整。一次调整小明可能让一位同学出队，向前或者向后移动一段距离后再插入队列。
例如，下面给出了一组移动的例子，例子中学生的人数为8人。
0）初始队列中学生的学号依次为1, 2, 3, 4, 5, 6, 7, 8；
1）第一次调整，命令为“3号同学向后移动2”，表示3号同学出队，向后移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 3, 6, 7, 8；
2）第二次调整，命令为“8号同学向前移动3”，表示8号同学出队，向前移动3名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 8, 3, 6, 7；
3）第三次调整，命令为“3号同学向前移动2”，表示3号同学出队，向前移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 3, 5, 8, 6, 7。
小明记录了所有调整的过程，请问，最终从前向后所有学生的学号依次是多少？
请特别注意，上述移动过程中所涉及的号码指的是学号，而不是在队伍中的位置。在向后移动时，移动的距离不超过对应同学后面的人数，如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。在向前移动时，移动的距离不超过对应同学前面的人数，如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。

　　输入的第一行包含一个整数n，表示学生的数量，学生的学号由1到n编号。
第二行包含一个整数m，表示调整的次数。
接下来m行，每行两个整数p, q，如果q为正，表示学号为p的同学向后移动q，如果q为负，表示学号为p的同学向前移动-q。

　　输出一行，包含n个整数，相邻两个整数之间由一个空格分隔，表示最终从前向后所有学生的学号。

　　对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ m ≤ 1000，所有移动均合法。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int n,m;
    vector<int> a;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    a.push_back(i);
    for(int cas=0;cas<m;cas++)
    {
        int x,y;
        cin>>x>>y;
        vector<int>::iterator it;
        for(it=a.begin();it!=a.end();it++)
            if(*it==x)
            break;
        a.erase(it);
        a.insert(it+y,x);

    }
    for(int i=0;i<a.size();i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;

}

 

　　请实现一个铁路购票系统的简单座位分配算法，来处理一节车厢的座位分配。
假设一节车厢有20排、每一排5个座位。为方便起见，我们用1到100来给所有的座位编号，第一排是1到5号，第二排是6到10号，依次类推，第20排是96到100号。
购票时，一个人可能购一张或多张票，最多不超过5张。如果这几张票可以安排在同一排编号相邻的座位，则应该安排在编号最小的相邻座位。否则应该安排在编号最小的几个空座位中（不考虑是否相邻）。
假设初始时车票全部未被购买，现在给了一些购票指令，请你处理这些指令。

　　输入的第一行包含一个整数n，表示购票指令的数量。
第二行包含n个整数，每个整数p在1到5之间，表示要购入的票数，相邻的两个数之间使用一个空格分隔。

　　输出n行，每行对应一条指令的处理结果。
对于购票指令p，输出p张车票的编号，按从小到大排序。

　　1) 购2张票，得到座位1、2。
2) 购5张票，得到座位6至10。
3) 购4张票，得到座位11至14。
4) 购2张票，得到座位3、4。

　　对于所有评测用例，1 ≤ n ≤ 100，所有购票数量之和不超过100。

#include <iostream>
#include<list>
#include<math.h>
using namespace std;
  int main(){
  int n,m,temp,Count;
  int a[200];
  int b[30];

  for(int i=0;i<20;i++){
    b[i]=5;
  }
  for(int i=0;i<100;i++){
    a[i]=1;
  }

  cin>>n;
  while(n--){
    cin>>m;
    Count =m;
    for(int i=0;i<20;i++)
  {
      temp = i;
     if(b[i]>=m){
        break;
     }
     else temp++;
  }
   if(temp==20){
    for(int i=0;i<100;i++)
    if((a[i]==1)&&(Count!=0)){
        cout<<i+1<<" ";
        Count--;
        a[i]=0;
    }



   }
   else{
    for(int j=temp*5;j<temp*5+5;j++){
        if((a[j]==1)&&(Count!=0)){
            a[j]=0;
            cout<<j+1<<" ";
            Count--;
        }
    }
      b[temp] = b[temp] - m;
    cout<<endl;
   }
  }
  }

 

　　有一个学校的老师共用N个教室，按照规定，所有的钥匙都必须放在公共钥匙盒里，老师不能带钥匙回家。每次老师上课前，都从公共钥匙盒里找到自己上课的教室的钥匙去开门，上完课后，再将钥匙放回到钥匙盒中。
钥匙盒一共有N个挂钩，从左到右排成一排，用来挂N个教室的钥匙。一串钥匙没有固定的悬挂位置，但钥匙上有标识，所以老师们不会弄混钥匙。
每次取钥匙的时候，老师们都会找到自己所需要的钥匙将其取走，而不会移动其他钥匙。每次还钥匙的时候，还钥匙的老师会找到最左边的空的挂钩，将钥匙挂在这个挂钩上。如果有多位老师还钥匙，则他们按钥匙编号从小到大的顺序还。如果同一时刻既有老师还钥匙又有老师取钥匙，则老师们会先将钥匙全还回去再取出。
今天开始的时候钥匙是按编号从小到大的顺序放在钥匙盒里的。有K位老师要上课，给出每位老师所需要的钥匙、开始上课的时间和上课的时长，假设下课时间就是还钥匙时间，请问最终钥匙盒里面钥匙的顺序是怎样的？

　　输入的第一行包含两个整数N, K。
接下来K行，每行三个整数w, s, c，分别表示一位老师要使用的钥匙编号、开始上课的时间和上课的时长。可能有多位老师使用同一把钥匙，但是老师使用钥匙的时间不会重叠。
保证输入数据满足输入格式，你不用检查数据合法性。

　　输出一行，包含N个整数，相邻整数间用一个空格分隔，依次表示每个挂钩上挂的钥匙编号。

　　第一位老师从时刻3开始使用4号教室的钥匙，使用3单位时间，所以在时刻6还钥匙。第二位老师从时刻2开始使用钥匙，使用7单位时间，所以在时刻9还钥匙。
每个关键时刻后的钥匙状态如下（X表示空）：
时刻2后为1X345；
时刻3后为1X3X5；
时刻6后为143X5；
时刻9后为14325。

　　对于30%的评测用例，1 ≤ N, K ≤ 10, 1 ≤ w ≤ N, 1 ≤ s, c ≤ 30；
对于60%的评测用例，1 ≤ N, K ≤ 50，1 ≤ w ≤ N，1 ≤ s ≤ 300，1 ≤ c ≤ 50；
对于所有评测用例，1 ≤ N, K ≤ 1000，1 ≤ w ≤ N，1 ≤ s ≤ 10000，1 ≤ c ≤ 100。

AC代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, k, w, s, c, key[1001];


struct Teacher//定义教师结构体
{
    int key;//钥匙编号
    int time;//使用钥匙时间
    int flag;//设置标识符
};

bool cmp(Teacher t1,Teacher t2){
    if(t1.time !=t2.time){
        return t1.time<t2.time;
    }
    else if(t1.flag !=t2.flag){
        return t1.flag >t2.flag;
    }
    else{
        return t1.key < t2.key;
    }
}
int main(){
std::ios::sync_with_stdio(false);
 vector<Teacher> v;//定义结构体向量
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        key[i] = i;
    }
    for(int i=0;i<k;i++)
    {
        cin>>w>>s>>c;
        Teacher t;
        t.key = w;
        t.time = s;
        t.flag = 0;//借
        v.push_back(t);
        t.key = w;
        t.time = s+c;
        t.flag = 1;//归还
        v.push_back(t);
    }
   sort(v.begin(),v.end(),cmp);

   for(int i=0;i<v.size();i++){
    Teacher t = v[i];
    if(t.flag==0)//借钥匙
    {
       for(int j = 1;j<=n;j++){
        if(key[j]==t.key){
            key[j]=0;
            break;
        }
       }

    }
   else {//还钥匙
      for(int j=1;j<=n;j++){
        if(key[j]==0){
            key[j]=t.key;
            break;
        }
      }
   }
   }
   for (int i=1;i<=n;i++){
    cout<<key[i]<<" ";
   }
   cout<<endl;
   return 0;
}

 

　　在图像编码的算法中，需要将一个给定的方形矩阵进行Z字形扫描(Zigzag Scan)。给定一个n×n的矩阵，Z字形扫描的过程如下图所示：

对于下面的4×4的矩阵，
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3
对其进行Z字形扫描后得到长度为16的序列：
1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3
请实现一个Z字形扫描的程序，给定一个n×n的矩阵，输出对这个矩阵进行Z字形扫描的结果。

　　输入的第一行包含一个整数n，表示矩阵的大小。
输入的第二行到第n+1行每行包含n个正整数，由空格分隔，表示给定的矩阵。

　　输出一行，包含n×n个整数，由空格分隔，表示输入的矩阵经过Z字形扫描后的结果。

　　1≤n≤500，矩阵元素为不超过1000的正整数。

#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int a[600][600];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }

int m=n*2-1;
int i=0,j=0;//iÊÇÐУ¬jÊÇÁÐ
        int sum = 0;
     while(m--){
        if(sum%2==0){
                cout<<a[i][j]<<" ";
            while((j+1)<n&&(i-1)>=0){
                cout<<a[i-1][j+1]<<" ";
        j++;
        i--;
            }
            sum++;
            if(sum<n)
            {j++;
            }
            else {
                i++;
            }

        }
        else if(sum%2==1){
        cout<<a[i][j]<<" ";
            while((i+1)<n&&(j-1)>=0){
                 cout<<a[i+1][j-1]<<" ";
               // cout<<i+1<<":"<<j-1<<endl;
        i++;
        j--;

        }
           sum++;
           if(sum<n)
            {i++;
            }
            else {
                j++;
            }

     }
}
  return 0;
}

 

　　JSON (JavaScript Object Notation) 是一种轻量级的数据交换格式，可以用来描述半结构化的数据。JSON 格式中的基本单元是值 (value)，出于简化的目的本题只涉及 2 种类型的值：
* 字符串 (string)：字符串是由双引号 ” 括起来的一组字符（可以为空）。如果字符串的内容中出现双引号 “，在双引号前面加反斜杠，也就是用 \” 表示；如果出现反斜杠 \，则用两个反斜杠 \\ 表示。反斜杠后面不能出现 ” 和 \ 以外的字符。例如：””、”hello”、”\”\\”。
* 对象 (object)：对象是一组键值对的无序集合（可以为空）。键值对表示对象的属性，键是属性名，值是属性的内容。对象以左花括号 { 开始，右花括号 } 结束，键值对之间以逗号 , 分隔。一个键值对的键和值之间以冒号 : 分隔。键必须是字符串，同一个对象所有键值对的键必须两两都不相同；值可以是字符串，也可以是另一个对象。例如：{}、{“foo”: “bar”}、{“Mon”: “weekday”, “Tue”: “weekday”, “Sun”: “weekend”}。
除了字符串内部的位置，其他位置都可以插入一个或多个空格使得 JSON 的呈现更加美观，也可以在一些地方换行，不会影响所表示的数据内容。例如，上面举例的最后一个 JSON 数据也可以写成如下形式。
{
“Mon”: “weekday”,
“Tue”: “weekday”,
“Sun”: “weekend”
}
给出一个 JSON 格式描述的数据，以及若干查询，编程返回这些查询的结果。

　　第一行是两个正整数 n 和 m，分别表示 JSON 数据的行数和查询的个数。
接下来 n 行，描述一个 JSON 数据，保证输入是一个合法的 JSON 对象。
接下来 m 行，每行描述一个查询。给出要查询的属性名，要求返回对应属性的内容。需要支持多层查询，各层的属性名之间用小数点 . 连接。保证查询的格式都是合法的。

　　对于输入的每一个查询，按顺序输出查询结果，每个结果占一行。
如果查询结果是一个字符串，则输出 STRING <string>，其中 <string> 是字符串的值，中间用一个空格分隔。
如果查询结果是一个对象，则输出 OBJECT，不需要输出对象的内容。
如果查询结果不存在，则输出 NOTEXIST。

n ≤ 100，每行不超过 80 个字符。
m ≤ 100，每个查询的长度不超过 80 个字符。
字符串中的字符均为 ASCII 码 33-126 的可打印字符，不会出现空格。所有字符串都不是空串。
所有作为键的字符串不会包含小数点 .。查询时键的大小写敏感。
50%的评测用例输入的对象只有 1 层结构，80%的评测用例输入的对象结构层数不超过 2 层。举例来说，{“a”: “b”} 是一层结构的对象，{“a”: {“b”: “c”}} 是二层结构的对象，以此类推。

#include <iostream>
#include <string>
#include <map>
#include <cstdio>
using namespace std;

int n, m;
string s, str;
bool key;
map<string, string> json;

string handle(string str, string s)
{
    if (s.empty())
    {
        return str;
    }
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == ' ')
        {
            continue;
        }
        else if (s[i] == '{')
        {
            json[str] = "OBJECT";
            key = true;
        }
        else if (s[i] == '}')
        {
            int i;
            for (i = str.size() - 1; i >= 0; i--)
            {
                if (str[i] == '.')
                {
                    break;
                }
            }
            if (i < 0)
            {
                str = "";
            }
            else
            {
                str = str.substr(0, i);
            }
        }
        else if (s[i] == ':')
        {
            key = false;
        }
        else if (s[i] == ',')
        {
            key = true;
        }
        else if (s[i] == '"')
        {
            string temp;
            for (i = i + 1; i < s.size(); i++)
            {
                if (s[i] == '\\')
                {
                    i++;
                    temp += s[i];
                }
                else if (s[i] == '"')
                {
                    break;
                }
                else
                {
                    temp += s[i];
                }
            }
            if (key)
            {
                if (str == "")
                {
                    str = temp;
                }
                else
                {
                    str += '.' + temp;
                }
            }
            else
            {
                json[str] = "STRING " + temp;
                int i;
                for (i = str.size() - 1; i >= 0; i--)
                {
                    if (str[i] == '.')
                    {
                        break;
                    }
                }
                if (i < 0)
                {
                    str = "";
                }
                else
                {
                    str = str.substr(0, i);
                }
            }
        }
    }
    return str;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> m;
    cin.get();

    while (n--)
    {
        getline(cin, s);
        str = handle(str, s);
    }
    while (m--)
    {
        cin >> s;
        cout << (json[s] == "" ? "NOTEXIST" : json[s]) << endl;
    }
    return 0;
}