2023年

202309-2 坐标变换（其二）

这个题目前80分不难拿，数据量也比较小，后面二十分的数据会比较多。

我最开始就只是用暴力就写了，用俩数组存操作和数据，然后每轮遍历操作，分情况计算结果即可。但是这样过不了另外的20%，之后想到了或许能用前缀和，一串相同操作的数据就给编写到前缀和里，我一开始以为操作的先后顺序会影响到结果，所以以为必须要知道前缀和的长度是从哪到哪，所以也没写出来，但是之后发现虽然计算的顺序确实不一样了，但是逻辑上讲结果是一样的，因此还是可以使用前缀和的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include<string.h>
#include<math.h>
using namespace std;

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int op;
    double k[100010],tangle[100010],data;
    memset(k,1,sizeof(k));
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %lf",&op,&data);
        if(op==2)
        {
            tangle[i]=tangle[i-1]+data;
            k[i]=k[i-1];
        }
        else
        {
            k[i]=k[i-1]*data;
            tangle[i]=tangle[i-1];
        }
    }
    int i,j;
    double x,y;
    for(int b = 0; b < m; b++)
    {
        scanf("%d %d %lf %lf",&i,&j,&x,&y);
        double k_m=k[j]/k[i-1];
        double tangle_m=tangle[j]-tangle[i-1];
        double xx=(x*cos(tangle_m)-y*sin(tangle_m))*k_m;
        double yy=(x*sin(tangle_m)+y*cos(tangle_m))*k_m;
        printf("%.3f %.3f\n",xx,yy);
    }

    return 0;
}

202305-2 矩阵运算

这道题需要了解矩阵的几个基本运算分别怎么计算的，以及矩阵的转置是什么。

首先说矩阵的转置，其实就是把一个nxm的矩阵转换成mxn的矩阵举个例子

左边原本是2x3的矩阵，转置后成了右边3x2的矩阵

(123456)⊺=(142536)\begin{array}{cc} \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ \end{pmatrix}^\intercal = \begin{pmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{pmatrix} \end{array}

因此矩阵转置实际上就是调换一下n和m。那么矩阵的点乘又是什么呢？

首先矩阵的点乘需要矩阵的行列相等，其次运算时就是对应项相乘例如

A⊙B=(a11a12a13a21a22a23)⊙(b11b12b13b21b22b23)=(a11⋅b11a12⋅b12a13⋅b13a21⋅b21a22⋅b22a23⋅b23)A \odot B = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ \end{pmatrix} \odot \begin{pmatrix} b_{11} & b_{12} & b_{13} \\ b_{21} & b_{22} & b_{23} \\ \end{pmatrix} = \begin{pmatrix} a_{11} \cdot b_{11} & a_{12} \cdot b_{12} & a_{13} \cdot b_{13} \\ a_{21} \cdot b_{21} & a_{22} \cdot b_{22} & a_{23} \cdot b_{23} \\ \end{pmatrix}

但是这道题比较简单的是W是个一维向量。也就是根据题目所说将矩阵中的第ii行中的每个元素都和W(i)W^{(i)}相乘，所以这部分就变简单了。

矩阵的叉乘就比较复杂了，我们还是举个例子

A×B=(a11a12a13a21a22a23)×(b11b12b21b22b31b32)=(a11b11+a12b21+a13b31a11b12+a12b22+a13b32a21b11+a22b21+a23b31a21b12+a22b22+a23b32)A \times B = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ \end{pmatrix} \times \begin{pmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \\ b_{31} & b_{32} \\ \end{pmatrix} = \begin{pmatrix} a_{11}b_{11} + a_{12}b_{21} + a_{13}b_{31} & a_{11}b_{12} + a_{12}b_{22} + a_{13}b_{32} \\ a_{21}b_{11} + a_{22}b_{21} + a_{23}b_{31} & a_{21}b_{12} + a_{22}b_{22} + a_{23}b_{32} \\ \end{pmatrix}

可以看到，最终得到的矩阵的第一行第一列数据是A中的第一行和B中的第一列相乘相加，同样，第一行第二列的数据就是A的第一行和B中的第二列相乘并相加。

所以不难得到这道题的答案，但是想要拿满分这还不够。有30%的数据是比较大的，而n又远大于d，所以应该尽量让最后的运算中所含n的矩阵的运算减少，也就是说只需要修改运算顺序为

(W⋅(Q×KT))×V=W⋅(Q×(KT×V))(W \cdot (Q \times K^T))\times V=W \cdot (Q \times (K^T\times V))

即可。还要注意一个坑就是需要开long long，不开容易爆。

1

202303-2 垦田计划

这道题目有70%的分是很好拿的，暴力就能写。暴力思路很简单，就是每次都找耗时最长的区域，把耗时最长的区域投入额外资源，也就是每次耗时减一，随后资源总数减去所需资源数，直到资源总数等于0或耗时最长的区域已经无法再继续减了（也就是耗时最长的区域的时间都比k小），这时候进行输出。

不出意外的话肯定会出意外，这样想只能拿70的分，因为还有30%的测试集数据量太大了，也就是说m每次减少的太少了，需要多减一点。于是可以想到区间合并。既然减的太少，而且必须把所有同一值全部减一，最后的耗时才会减一，那我直接把所有同一值的区间合并，把他们的资源消耗数量也合并，这样不就好了吗。理论没问题，开始实践：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include<string.h>
#include<math.h>
#include <algorithm>
const int N = 1e5+10;
using namespace std;

int main()
{
    int n,k;
    long long m;
    cin >> n >> m >> k;
    int max_t=0;
    int t,c;
    int field[N];
    memset(field,0,sizeof(field));
    for(int i = 0; i < n; i++)
    {
        cin >> t >> c;
        field[t]+=c;
        max_t=max(t,max_t);//记录一下此时的最大值，方便第一次的查找
    }
    while(m>0)
    {
        if(max_t>k&&m>field[max_t])
        {
            m-=field[max_t];
            max_t--;
            field[max_t]+=field[max_t+1];//每次最大值减一之后，max-1的消耗需要加上之前max的消耗
        }
        else
        break;
    }
    cout << max_t << endl;


    return 0;
}
// 5 50 1
// 9 1
// 8 1
// 6 1
// 3 1
// 1 1
// 7
// 9 8 6 3 1

2022年

202212-2 训练计划

这道题也是拿前70%很简单，但是后30%就需要仔细思考了。

仔细想想，这道题求最晚开始时间比较难想通。首先如果这个节点是没有被依赖的节点，那它的最晚开始时间其实就是n-自己的时间+1。如果节点x1是被x2依赖的节点，那么它的最晚开始时间其实是x2的最晚开始时间-x1的时间，如果节点x1被多个节点依赖，那它的最晚开始时间其实是min(当前被依赖节点的最晚开始时间-x1的时间,上一个被依赖节点的最晚开始时间-x1的时间)。

所以就能得到递推公式xm[p].follow_day=min(xm[i].follow_day-xm[p].t,xm[p].follow_day);

梳理好思路，接下来就简单很多了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include<string.h>
#include<math.h>
#include <algorithm>
const int N = 110;
using namespace std;

struct exprise
{
    int pre;
    int pre_day=0;
    int follow_day=1e9;
    int follow=0;
    int t;
} xm[N];

int main()
{
    int n,sum=0,m,p,t;
    scanf("%d %d",&n,&m);
    xm[0].t=0;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d",&p);
        xm[i].pre=p;
        xm[p].follow=1;
    }
    for(int i = 1; i <= m; i++)
    {
        scanf("%d",&t);

        if(sum<t)//更新最大
        sum=t;

        p=xm[i].pre;
        xm[i].t=t;

        if(p) //更新依赖的天数
        xm[i].pre_day+=xm[p].pre_day+xm[p].t;
    }
    for(int i = 1; i <= m; i++)
    {
        if(xm[i].pre==0)
        {
            printf("%d ",1);
        }
        else
        {
            printf("%d ",xm[i].pre_day+1);
        }
    }
    bool flag=true;
    for(int i = m; i >= 1; i--)
    {
        p=xm[i].pre;
        if(p!=0&&xm[i].follow==0)//有前驱无后继
        {
            xm[i].follow_day=n-xm[i].t+1;
            xm[p].follow_day=min(xm[i].follow_day-xm[p].t,xm[p].follow_day);
        }
        else if(p!=0&&xm[i].follow==1)//有前驱有后继，更新前驱(自己的被后继更新过了)
        {
            xm[p].follow_day=min(xm[i].follow_day-xm[p].t,xm[p].follow_day);
        }
        else if(xm[i].follow==0&&p==0)//无前驱后继
        {
            xm[i].follow_day=n-xm[i].t+1;
        }
        if(xm[p].follow_day<0)
        {
            flag=false;
            break;
        }
    }
    if(!flag)
    return 0;
    else
    {
        puts("");
        for(int i = 1; i <= m; i++)
        {
            printf("%d ",xm[i].follow_day);
        }
    }

    return 0;
}

202209-2 何以包邮

这道题就是背包问题，一开始忘了背包咋写的了，近几年真的是越来越难了。之后上网搜索之后发现背包问题其实比较套路，但是状态转移方程真的很不好想。这道题稍微做了一点变形，就不是很做的出来了。

首先需要明确的是这道题和背包问题有什么异同？可以看到这道题中每本书只能选择一次，并且所有选择的书的价值必须大于x，这和背包问题中的选择价值最大的物品非常像。但是这道题又有点不同，它需要在商品的价值满足大于x的同时又是最小值。

那我们该怎么定义这个问题，让它和背包问题看起来差不多呢？主要在于对于题目中给定条件的转换，其实大于x也就是选定商品总价值减x是大于0的，这个情况下选取最小的数

202206-2 寻宝！大冒险！

这道题不知道咋用算法，但是有一些优化的思路，虽然最后还是写成屎山，但是总算是满分了。

70%那部分数据就不说了，纯构建两个二维数组遍历即可。说一说另外30%的数据，这部分我的优化思路就是对于每个在绿化图中的树，都拿寻宝图的B(0,0)去尝试碰一碰。

首先是对于绿化图中的树，只用一个一维数组进行存储，自定义一个带x和y的结构体即可，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include<string.h>
#include<math.h>
#include <algorithm>
#include<stdio.h>
using namespace std;

struct zuobiao
{
    int x;
    int y;
};

bool cmp(zuobiao a, zuobiao b)
{
    if(a.x==b.x)
    return a.y<b.y;
    else
    return a.x<b.x;
}

int main()
{
    int n,L,S;
    cin >> n >> L >> S;
    zuobiao trees[1010];
    for(int i = 0; i < n; i++)
    {
        cin >> trees[i].x >> trees[i].y;
    }
    int t_map[51][51];
    for(int i = S; i >= 0; i--)
    {
        for(int j = 0; j <= S; j++)
        {
            cin >> t_map[i][j];
        }
    }
    sort(trees,trees+n,cmp);
    int cnt=0;
    for(int ea = 0; ea < n; ea++)
    {
        bool flag=true;

        //即A(x,y)与B(0,0)对应
        int x=trees[ea].x;
        int y = trees[ea].y;

        //从下一个树（起点的数已经做过比较了）开始遍历B的每一个1，查看位置是否跟下一个A中的1对应，也就是A(x+i,y+j)=B(i,j)
        int ex=ea+1;

        if(x+S>L||y+S>L)
        flag=false;

        for(int i = 0; i <= S; i++)
        {
            for(int j = 0; j <= S; j++)
            {
                if(i==0&&j==0)
                continue;
                if(ex<n&&trees[ex].x==i+x&&trees[ex].y==j+y)
                {
                    if(t_map[i][j]==1)
                    ex++;
                    else
                    {
                        flag=false;
                        break;
                    }
                }
                else
                {
                    if(t_map[i][j]==1)
                    {
                        flag=false;
                        break;
                    }
                }
                while(ex<n)
                {
                    if(trees[ex].y>y+S||trees[ex].y<y)
                    ex++;
                    else
                    break;
                }
            }
            if(!flag)
            break;
        }

        if(flag)
        {
            cnt++;
        }
    }
    cout << cnt << endl;

    return 0;
}

2021年

202112-2 序列查询新解

暴力+剪枝（80分）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include<string.h>
#include<math.h>
#include <algorithm>
#include<stdio.h>
using namespace std;

#define ll long long

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int n,N;
    cin >> n >> N;
    int ans=0,x;
    ll error=0;
    int g[205];//存g的数值
    int i = 0;//存下标
    int r=N/(n+1);
    bool flag=true;
    int nn;//简化计算
    for(i; i < n; i++)
    {
        cin >> x;//输入下一个数
        nn=i*r;
        if((x-ans)%r==0)//x-ans是需要被赋值的数的数量
        {
            for(int j = ans; j < x; j+=r)
            {
                error+=abs(j-nn);
            }
        }
        else
        {
            int j = ans;
            int xx=(x-ans)/r;//有多少轮可以简化计算
            for(j; xx>0; xx--,j+=r)
            {
                error+=abs(j-nn);
            }
            //剩余轮常规运算
            for(j; j<x; j++)
            {
                g[i]=j/r;
                error+=abs(g[i]-i);
            }
        }
        ans=x;//下一轮
    }
    nn=i*r;
    if((N-ans)%r==0)//x-ans是需要被赋值的数的数量
    {
        for(int j = ans; j < N; j+=r)
        {
            error+=abs(j-nn);
        }
    }
    else
    {
        int j = ans;
        int xx=(N-ans)/r;//有多少轮可以简化计算
        for(j; xx>0; xx--,j+=r)
        {
            error+=abs(j-nn);
        }
        //剩余轮常规运算
        for(j; j<N; j++)
        {
            g[i]=j/r;
            error+=abs(g[i]-i);
        }
    }
    cout << error << endl;
    return 0;
}

202104-2 领域均值

二维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include<string.h>
#include<math.h>
#include <algorithm>
#include<stdio.h>
using namespace std;

#define ll long long

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int n,L,r,t;
    cin >> n >> L >> r >> t;
    int arr[610][610],x;
    memset(arr,0,sizeof(arr));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> x;
            arr[i][j] = arr[i][j - 1] + arr[i - 1][j] - arr[i - 1][j - 1] + x;
        }
    }
    
    int cnt=0,x_max,x_min,y_min,y_max,sum;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            double ans;
            x_min=max(0,i-r);
            x_max=min(r+i,n-1);
            y_min=max(0,j-r);
            y_max=min(r+j,n-1);
            ans=arr[x_max+1][y_max+1] - arr[x_max+1][y_min] - arr[x_min][y_max+1] + arr[x_min][y_min];

            sum=(x_max-x_min+1)*(y_max-y_min+1);
            
            sum=ceil(ans/sum);
            if(sum<=t)
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

2018年

201812-2 小明放学

这个题目看起来并不难，只需要每次输入红绿灯时间时进行判断目前前行了的时间是否超过红绿灯时间，之后再将时间模一轮红绿灯时间，再进行判断到了哪个红绿灯即可。

坑点在于需要给总时间开longlong，一开始没注意，直接答案错误，给我懵了好久，之后才发现的。难点在于模除之后的判断，判断应该是 红->绿->黄->红 这样循环，但是红绿灯k的增长却是1->2->3->1，1为红，2为黄，3为绿，与所需红绿灯的循环对不上，所以需要一个数组将红绿灯的变化存下来。

思路理清之后其实就很简单了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>

using namespace std;
int light[4];
int get(int k, int t)
{
    if(k==1)
    {
        return t;
    }
    else if(k==2)
    {
        return t+light[1];
    }
    else
    {
        return 0;
    }
}

int main(){
    int n;
    cin >> light[1] >> light[2] >> light[3];
    cin >> n;
    int k;
    int roll_time=light[1]+light[2]+light[3];
    long long t;
    long long time=0;
    int shunxu[4]={0,3,1,2};
    for(int i = 0; i < n; i++)
    {
        cin >> k >> t;
        long long tmp;
        if(k==0)
        {
            time+=t;
        }
        else
        {
            if(t>time)
            {
                time+=get(k,t-time);
                continue;
            }
            else
            {
                tmp=time-t;
                k=shunxu[k];
            }
            tmp%=(roll_time);
            while(tmp>=light[k])
            {
                tmp-=light[k];
                k=shunxu[k];
            }
            t=light[k]-tmp;
            time+=get(k,t);
        }
    }
    cout << time << endl;
    return 0;
}

201803-2 碰撞的小球

仔细看题目，每个小球的运动方向每个时刻都有可能不一样，因此毫无疑问要一个数组储存小球的方向了。并且需要遍历时间，每一秒小球的位置先进行改变，之后进行判断是否需要进行方向的改变，方向的改变只有三种情况：

  • 小球位置等于长度
  • 小球位置等于0
  • 小球重合

小球重合从前往后进行判断即可，题目已经说了不可能有三个小球同时重合，所以就会简单很多，那么就直接上代码吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>

using namespace std;
int main(){
    int n,L,t;
    cin >> n >> L >> t;
    int sphere[101],where[101];
    for(int i = 0; i < n; i++)
    {
        cin >> sphere[i];
        where[i]=1;
    }
    while(t--)
    {
        for(int i = 0; i < n; i++)
        {
            sphere[i]+=where[i];
            if(sphere[i]==L)
            where[i]=-1;
            if(sphere[i]==0)
            where[i]=1;
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = i+1; j < n; j++)
            {
                if(sphere[i]==sphere[j])
                {
                    where[i]=-where[i];
                    where[j]=-where[j];
                }
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        cout << sphere[i] << " ";
    }
    return 0;
}

2017年

201709-2 公共钥匙盒(未写出)

这道题一开始没有写出来，一开始为了防止超时，思路是双指针，一个指针指向开始时间一个指针指向结束时间。但是忘记按开始时间在前的先取了，也就是没有进行排序，最后写出来全是错的，惨不忍睹，最后上网搜了题解才勉强写出。

思路便是按照时刻进行大循环处理，先还再借。还的时候先遍历知道有多少是还的，然后按照编号进行排序，然后进行还钥匙的处理，改变数组a和b,借的时候同样，进行遍历，只是不需要统计借的人数，按照数组r的顺序进行处理即可。这里用到一个search因为经过很多次的借还导致制定编号的钥匙不能直接知道它所在的钩子，导致不知道应该如何处理下标为几的数组a和b。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <cstdlib>
using namespace std;
 
int search(int a[], int b, int n)
{
	for (int i = 0; i < n; i++) 
	{
		if (a[i] == b) 
		{
			return i;
		}
	}
}
int main(void) 
{
	int n;
	int k;
	cin >> n;
	cin >> k;
	int a[1000];
	bool b[1000];
	for (int u = 0; u < n; u++) 
	{
		a[u] = u + 1;
		b[u] = true;
	}//钥匙部分初始化，true表明钥匙放在钥匙盒里
	int s[10000][3];
	int r[10000];//用来处理多位老师同时还钥匙的情况
	int max = 0;//最晚结束时间
	//进行内容的输入
	for(int i = 0;i < k;i++)
	{
		cin >> s[i][0];
		cin >> s[i][1];
		cin >> s[i][2];
		s[i][2] = s[i][1] + s[i][2];
		if (s[i][2] > max) 
		{
			max = s[i][2];
		}
	}
	//cout << "max的值为" << max << endl;
	int count = 0;
	for (int t = 0; t <= max; t++) 
	{
		//每一个时刻都要处理，先还再取，还按钥匙的编号大小还
		count = 0;
		for(int m = 0;m < k;m++)
		{
			if (s[m][2] == t) //统计出所有在该时刻要还钥匙的人的钥匙号，因为要按照编号还
			{
				
				r[count] = s[m][0];
				count++;
			}
		}
		//排序
		/*if (count > 0) 
		{
			qsort(r, count - 1, sizeof(int), comp);
		}*/
		//cout << "打印r数组" << endl;
		//进行冒泡排序
		int temp;
		for (int ii = 0; ii < count-1; ii++) 
		{
			for (int jj = 0; jj < count - 1 - ii; jj++) 
			{
				if (r[jj] > r[jj + 1]) 
				{
					temp = r[jj];
					r[jj] = r[jj + 1];
					r[jj + 1] = temp;
				}
			}
		}
		
		//还钥匙
		
		for (int p = 0; p < count; p++) 
		{
			for (int q = 0; q < n; q++)
			{
				if (b[q] == false) 
				{
					a[q] = r[p];
					b[q] = true;
					break;
				}
			}
		}
		//拿钥匙
		int id;
		for (int w = 0; w < k; w++) 
		{
			if (s[w][1] == t) 
			{
				id = search(a, s[w][0], n);
				b[id] = false;
				a[id] = 0;
			}
		}
		//cout <<t<< " 时刻的状态为:" << endl;
		/*for (int r = 0; r < n; r++)
		{
			cout << a[r] << " ";
		}
		cout << endl;*/
	}
	for (int r = 0; r < n; r++)
	{
		cout << a[r] << " ";
	}
	
	system("pause");
	return 0;
}

2016年

201609-2 火车购票

这题不难，只需要

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
using namespace std;
int main()
{
    int n,p;
    int count;
    int sit[21];
    cin >> n;
    for(int i = 0; i < 21; i++)
    {
        sit[i]=5;
    }
    for(int i = 0; i < n; i++)
    {
        cin >> p;
        for(count = 1; count < 21; count++)
        {
            if(sit[count]>=p)
            {
                for(int j = 1; j <= p; j++)
                {
                    cout << (count-1)*5+(5-sit[count])+j << " ";
                }
                sit[count]-=p;
                break;
            }
        }
        if(count == 21)
        {
            for(count = 1; count < 21 && p >=0; count++)
            {
                if(sit[count])
                {
                    if(sit[count]<=p)
                    for(int j = 1; j <= sit[count]; j++)
                    {
                        cout << (count-1)*5+(5-sit[count])+j << " ";
                    }
                    else
                    {
                        for(int j = 1; j <= p; j++)
                        {
                            cout << (count-1)*5+(5-sit[count])+j << " ";
                        }
                    }
                }
                int num = p;
                p-=sit[count];
                sit[count]-=num;
            }
        }
        cout << endl;
    }

    return 0;
}

201604-2 俄罗斯方块

这个题目也是很需要思路的，暴力肯定写不出来，我的想法就是找到这个方块的左下角定位，随后每次让其对于整体而言下降1，并且逐个遍历方块与背景，如果有冲突的地方那么说明上一个位置就是答案，思路理清之后开写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
int main()
{
    bool bb=false;
    int x;
    int lowx=0,lowy;
    int square[20][10];
    int n[4][4] = {0};
    memset(square, 1, sizeof(square));
    for (int i = 0; i < 15; i++)
    {
        for(int j = 0; j < 10; j++)
        {
            cin>>square[i][j];
        }
    }

    for (int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            cin>>n[i][j];
        }
    }
    cin >> x;
    for (int y = 0; ; y++)
    {
        for(int i=0; i<4; i++)
        {
            for(int k = 0; k <4; k++)
            {
                if(n[i][k]&&square[i+y][k+x-1])
                {
                    bb=true;
                    break;
                }
            }
            if(bb) break; 
        }
        if (bb) 
        {
            for(int i=0; i<4; i++)
            {
                for(int k = 0; k <4; k++)
                {
                    if(n[i][k])
                    square[i+y-1][k+x-1]=n[i][k];
                }
            }
            break;
        }
    }

    for (int i = 0; i < 15; i++)
    {
        for(int j = 0; j < 10; j++)
        {
            cout << square[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

2014年

201412-2 Z字型扫描

这道题的思路主要在于向上扫描和向下扫描的切换，如果碰到上边界就得往右边走，如果碰到的是右边界就要往下面走，依次类推，走完之后转变方向。如果是向上走就每次x-1和y+1，向下走就是x+1而y-1，得到规律之后就很好写了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>

using namespace std;
int main(){
    int n;
    int arr[501][501];
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> arr[i][j];
        }
    }
    int x=1,y=1;
    bool w = false;//转弯
    bool up=true;//方向
    printf("%d",arr[x][y]);
    while(x!=n||y!=n)
    {
        if(up)
        {
            if(x-1>=1&&y+1<=n)//没碰到边界
            {
                x--;
                y++;
            }
            else if(y<n&&x==1)//碰到上边界未转弯
            {
                y++;
                up=false;
            }
            else if(y==n)//右边界
            {
                x++;
                up=false;
            }
        }
        else
        {
            if(y-1>=1&&x+1<=n)//没碰到边界
            {
                y--;
                x++;
            }
            else if(x<n&&y==1)//碰到左边界
            {
                x++;
                up=true;
            }
            else if(x==n)//下边界
            {
                y++;
                up=true;
            }
        }
        printf(" %d",arr[x][y]);
    }
    return 0;
}

201403-2 窗口

这道题目的思路也不难，就是每次输入的时候从最高层进行判断落在哪个区域，随后便将该区域置为最上层，也就是优先级最高，其他比其高的窗口全部向后挪一位即可，可以使用一个数组保存第i个等级为哪个窗口，这样就可以每次都从最高等级窗口开始遍历。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>

using namespace std;
int main(){
    int n,m,windows[11][4],pri[10];
    bool yes;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        pri[i]=0;
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            cin >> windows[i][j];
        }
        pri[i]=i;
    }
    int x,y;
    for(int i = 0; i < m; i++)
    {
        cin >> x >> y;
        yes = false;
        for(int j = n-1; j >= 0; j--)//从最高级开始遍历 pri[]数组代表第j个等级是哪个窗口
        {
            if(x>=windows[pri[j]][0]&&x<windows[pri[j]][2]&&y>=windows[pri[j]][1]&&y<windows[pri[j]][3])
            {
                int tmp = pri[j];
                for(int k =j+1; k < n; k++)
                {
                    pri[k-1]=pri[k];
                }
                pri[n-1]=tmp;
                yes=true;
                cout << pri[n-1]+1 << endl;
                break;
            }
            if(x>windows[pri[j]][0]&&y>windows[pri[j]][1]&&x<=windows[pri[j]][2]&&y<=windows[pri[j]][3])
            {
                int tmp = pri[j];
                for(int k =j+1; k < n; k++)
                {
                    pri[k-1]=pri[k];
                }
                yes=true;
                pri[n-1]=tmp;
                cout << pri[n-1]+1 << endl;
                break;
            }
        }
        if(!yes)
        cout << "IGNORED" << endl;
    }
    return 0;
}