洛谷官方题单——数组题解（部分水题警告）

今天之后，题目会开始变得困难了一些，但是就现在为止还是抵挡不住我们的刷题节奏。废话不多说，直接开搞。

题目0：小鱼比可爱

十分简单，存到一个数组中，然后从0往n-1依次遍历，记录当前位置；然后从0到当前位置遍历，当数字比他小，则cnt++，然后输出cnt和一个空格即可。

#define MAXN 105   //这里应该是大家都知道的小技巧了，就是数组稍微开大一些
int array[MAXN];      //但是注意不一定开大一些就+5,+50，有些题目会存在开一倍甚至更多的情况（后面就会有体现）
int main(){
    int n,cnt=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&array[i]);
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++) if(array[j]<array[i]) cnt++;
        printf("%d ",cnt);
        cnt=0;            //毕竟下一轮循环cnt就是新生了
    }
    return 0;
}

题目1：小鱼的数字游戏

可以考虑两个办法，一个是开一个stack s;然后存进去再依次输出（栈）。
另外一个办法就是记录到一个数组，同时记录个数（因为以0为结尾，所以需要额外记录数字个数），然后从最后往前输出即可。

long long int num[105];   //long long 没必要，但是我就是要加
int main() {
    int i = 0;
    do {scanf("%lld", &num[++i]);} while (num[i] != 0);
    for (int j = i - 1; j > 0; j--) printf("%lld ", num[j]);
    return 0;
}

题目2：冰雹猜想

纯粹的模拟题，由于最后需要倒着输出，所以是需要存在一个数组里面的(当然可以利用递归在系统中是需要栈空间的特性来使用递归输出）。

//递归版本
#include<stdio.h>
void print(int n){
    if(n==1){
        printf("1");
        return;
    }
    if(n&1) print(n*3+1);
    else print(n>>1);
    printf(" %d",n);
}
int main(){
    int n;
    scanf("%d",&n);
    print(n);
    return 0;
}

//非递归版本，使用栈
#include<cstdio>
#include<stack>
using namespace std;
stack<int> s;
int main(){
    int n;
    scanf("%d",&n);
    while(n!=1){
        s.push(n);
        if(n&1) n>>=1;
        else n=n*3+1;
    }
    printf("1 ");
    while(!s.empty()){
        int ans=s.top();
        printf("%d ",ans);
        s.pop();
    }
    return 0;
}

//非递归，普通实现
#include<stdio.h>
int memo[1000];
int main() {
    int n, cnt = 1;
    scanf("%d", &n);
    while (n != 1) {
        memo[cnt++] = n;
        if (n & 1) n = 3 * n + 1;
        else n >>= 1;
    }
    memo[cnt] = 1;
    for (int i = cnt; i >= 1; i--) printf("%d ", memo[i]);
    return 0;
}

题目3：校门外的树

按照题目模拟一边即可（线段树/分块啥的暂时就别搞这些花里胡哨的嗷）。

#include<stdio.h>
#define MAXN 10002
int path[MAXN];
int main(){
    int L, M;
    int st, en, count;
    count = 0;
    scanf("%d%d", &L, &M);
    for (int i = 0; i <= L; i++) path[i] = 1;
    while (M){
        scanf("%d%d", &st, &en);
        for (int i = st; i <= en; i++) path[i] = 0;
        M--;
    }
    for (int i = 0; i <= L; i++) if (path[i] == 1) count++;
    return 0*printf("%d", count);
}

题目4：旗鼓相当的对手

我这里使用的是结构体，也可以使用二维数组，然后遍历就行了

#include<stdio.h>
typedef struct student {
    int Chinese, Math, English, sum;
}student;
student memo[1005];
int abs(int x) { return x >= 0 ? x : -x; }
int check(int i, int j) {
    return (abs(memo[i].Chinese - memo[j].Chinese) <= 5) &&
        (abs(memo[i].Math - memo[j].Math) <= 5) &&
        (abs(memo[i].English - memo[j].English)) <= 5 &&
        (abs(memo[i].sum - memo[j].sum) <= 10);
}
int main() {
    int n,ans=0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &memo[i].Chinese, &memo[i].Math, &memo[i].English);
        memo[i].sum = memo[i].Chinese + memo[i].Math + memo[i].English;
    }
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) 
            ans += check(i, j);
    return 0 * printf("%d\n", ans);
}

题目5：工艺品制作

需要使用标记数组book确定这部分切割的地方有没有“蒸发”，然后模拟即可。

#include<stdio.h>
const int MAXN = 25;
int book[MAXN][MAXN][MAXN];
int main() {
    int w, x, h, q, ans = 0;
    scanf("%d%d%d%d", &w, &x, &h, &q);
    while (q--){
        int x1, y1, z1, x2, y2, z2;
        scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
        for (int i = x1; i <= x2; i++)
            for (int j = y1; j <= y2; j++)
                for (int k = z1; k <= z2; k++) book[i][j][k] = 1;
    }
    for (int i = 1; i <= w; i++)
        for (int j = 1; j <= x; j++)
            for (int k = 1; k <= h; k++)
                if (book[i][j][k] == 0) ans++;
    return 0 * printf("%d\n", ans);
}

题目6：彩票摇奖

采用一个数组来确定哪些号码已经被选取，这样在后续可以直接用输入得到的号码当做索引来查看是否买了这个数。

#include<stdio.h>
const int MAXN = 35;
int book[MAXN], ans[8];
int main() {
    int n, temp;
    scanf("%d", &n);
    for (int i = 0; i < 7; i++) {
        scanf("%d", &temp);
        book[temp] = 1;
    }
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < 7; j++) {
            scanf("%d", &temp);
            if (book[temp] == 1) cnt++;
        }
        ans[cnt]++;
    }
    for (int i = 7; i >= 1; i--) printf("%d ", ans[i]);
    return 0;
}

题目7：幻方

注意通过取模来达到循环的技巧也是经常使用的（尤其在字符串和循环队列中），其余按照题目一个一个写就行了。

//取模，此代码来自洛谷的HsKr 
#include<stdio.h>
int n, a[40][40], x, y;
int main() {
    scanf("%d", &n);
    x = 1, y = (n + 1) / 2;
    for (int i = 1; i <= n * n; i++) {
        a[x][y] = i;
        if (a[(x - 2 + n) % n + 1][y % n + 1] == 0) x = (x - 2 + n) % n + 1, y = y % n + 1;
        else x = x % n + 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) 
            printf("%d ", a[i][j]);
        printf("\n");
    }
    return 0;
}

//非取模
#include<stdio.h>
int ans[40][40];
int main() {
    int n, x, y;
    scanf("%d", &n);
    x = 1, y = (n + 1) / 2;
    for (int i = 1; i <= n * n; i++) {
        ans[x][y] = i;
        if (x == 1 && y != n) x = n, y++;
        else if (x != 1 && y == n) y = 1, x--;
        else if (x == 1 && y == n) y = n, x++;
        else if (ans[x - 1][y + 1] == 0) x--, y++;
        else x++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d ", ans[i][j]);
        }
        printf("\n");
    }
}

题目8：显示屏

打表题，可以提前将对应的存在一个string（或者string的二维数组）里，然后输入的字符串读一位输出一位，中间加列点。
这道例题不放代码，因为打表题代码都是大同小异。

题目9：梦中的统计

输入开始和结束的数字，遍历一遍并在book数组里面统计对应出现的数即可。

#include<stdio.h>
int main(){
    int book[10] = { 0 }, start, end;
    scanf("%d%d", &start, &end);
    for (int i = start; i <= end; i++)
        for (int temp = i; temp != 0; temp /= 10)
            book[temp % 10]++;
    for (int i = 0; i <= 9; i++)
        printf("%d ", book[i]);
    return 0;
}

题目10：珠心算测验

这里有个坑，注意要防止存在重复的（例如1+7=8，2+6=8，3+5=8都是重复的），因此最后的比较只看他是不是为0而不是简单粗暴的加起来。

#include<stdio.h>
#define MAXN 20005
int answer[MAXN],book[MAXN],store[105];
int main() {
    int n;
    int cnt = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &store[i]);
        book[store[i]] = 1;
    }
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            answer[store[i] + store[j]]++;
    for (int i = 1; i < MAXN; i++)
        if (book[i] > 0 && answer[i]) cnt++;
    return 0 * printf("%d", cnt);
}

题目11：爱与愁的心痛

就按照题目要求直接写就行了，我这里相当于构造了一个滑动窗口。

#pragma warning(disable:4996)
#include<stdio.h>
int memo[3050];
int min(int x, int y) { return x > y ? y : x; }
int main() {
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    int n, m, mmin = 1e9, sum = 0;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &memo[i]);
    for (int i = 0; i < m; i++) sum += memo[i];
    if(n==m) return 0 * printf("%d\n", sum);
    mmin = min(mmin, sum);
    for (int i = m; i < n; i++) {
        sum = sum - memo[i - m] + memo[i];
        mmin = min(mmin, sum);
    }
    return 0 * printf("%d\n", mmin);
}

题目12：Bovine Bones G

简单的骰子模拟题，直接暴力就行了（数据范围很小，n^3也能接受的）。

#include<stdio.h>
int book[65];
int main() {
    int s1, s2, s3, K = 0, mmax = -1;
    scanf("%d%d%d", &s1, &s2, &s3);
    for (int i = 1; i <= s1; i++) 
        for (int j = 1; j <= s2; j++) 
            for (int k = 1; k <= s3; k++) 
                book[i + j + k]++;
    for (int i = 1; i <= s1 + s2 + s3; i++) 
        if (mmax < book[i]) K = i, mmax = book[i];
    return 0 * printf("%d\n", K);
}

题目13：开灯

这里我们可以将题目视作，寻找数组仅出现过奇数次的题目。由于aXORa=0，开关灯相当于是有两个a，则所有数据异或后只有一个数字就是这个开灯的编号。
网络上关于位运算的题目有很多，后续有机会写个blog。

#pragma warning(disable:4996)
#include<stdio.h>
int book[65];
int main() {
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    int n,t,ans=0;
    double a;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf%d", &a, &t);
        for (int j = 1; j <= t; j++) ans ^= int(j * a);
    }
    return 0 * printf("%d\n", ans);
}

题目14：蛇形方阵

这是《算法竞赛入门经典》的最开始的几道例题，十分简单，但是方法有很多，注意天杀的输出格式。

#include<stdio.h>
int memo[10][10];
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int main() {
    int n;
    scanf("%d", &n);
    for (int x = 0, y = 0, num = 1, d = 0; num <= n * n; num++) {
        memo[x][y] = num;
        int a = x + dx[d], b = y + dy[d];
        if (a < 0 || a >= n || b < 0 || b >= n || memo[a][b] != 0) {//换方向了
            d = (d + 1) % 4;
            a = x + dx[d], b = y + dy[d];
        }
        x = a, y = b;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) printf("%3d", memo[i][j]);
        printf("\n");
    }
    return 0;
}

题目15：杨辉三角

基础递推题，在后面求组合数十分有用。

#pragma warning(disable:4996)
#include<stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    int a[22][22] = { 0 };
    a[0][0] = 1, a[1][0] = 1, a[1][1] = 1;
    for (int i = 2; i < n; i++) {
        a[i][0] = 1;
        for (int j = 1; j < n - 1; j++) {
            a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
        }
        a[i][i] = 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (i == j) printf("%d\n", a[i][i]);
            else printf("%d ", a[i][j]);
        }
    }
    return 0;
}

题目16：插火把

具体就按照题目来，十字遍历和方形遍历，最后遍历整个二维数组就可以那些地方会刷怪。

#include <stdio.h> 
int map[5005][5005];
int abs(int x) { return x >= 0 ? x : -x; }
bool check(int x, int y, int n) {
    if (x < 1 || y < 1 || x > n || y > n) return 0;
    return 1;
}
int main() {
    int n, m, k, a, b, ans;
    scanf("%d%d%d", &n, &m, &k); 
    for (int i = 1; i <= m + k; i++) { 
        scanf("%d%d", &a, &b); 
        for (int x = -2; x <= 2; x++)
            for (int y = -2; y <= 2; y++)
                if ((i > m || abs(x) + abs(y) <= 2) && check(x + a, b + y, n))//i>m就说明是萤石
                    map[x + a][b + y]++;
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (map[i][j] == 0) ans++;
    return 0 * printf("%d\n", ans);
}

题目17：压缩技术

按照题目要求暴力做就行了，直接按照一维方式来做，二维反而更麻烦。

#include<iostream>
int book[42000];
using namespace std;
int main(){
    int n, temp, bit = 0, cur = 0, i = 0;
    cin >> n;
    while (cin >> temp){
        for (i = cur; i < cur + temp; i++) book[i] = bit;
        cur = i;
        bit = !bit;
    }
    cur = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++)
            cout << book[cur++];
        cout << endl;
    }
    return 0;
}

题目18：压缩技术（续集版）

存在一个string数组里面，这样就不需要后面求个平方根了，然后遍历每一个string，注意不要在循环内使用局部变量，因为其换行不影响cnt的累计。

#include <iostream>
using namespace std;
string memo[205];
int main() {
    char bit = '0';
    int cnt = 0;
    cin >> memo[0];
    for (int i = 1; i < memo[0].size(); i++) cin >> memo[i];
    cout << memo[0].size() << " ";
    for (int i = 0; i < memo[0].size(); i++) {
        for (int j = 0; j < memo[0].size(); j++) {
            if (memo[i][j] == bit) cnt++;
            else {
                bit = memo[i][j];
                cout << cnt << " ";
                cnt = 1;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

题目19：方块转换

最后一道可以说是一个搜索，亦可以说是一个模拟，由于代码长度过长，建议直接看洛谷的题解。

模拟

首先对于模拟，只需要对1-7的所有内容写一个接口，然后依次调用，一旦在某个地方返回了true/1就可立即输出这个接口对应的数字。

搜索

如果是用搜索的方式，建议学会剪枝后再继续向下看：
1.首先整个数字的变换实际上是不需要完全变换的，我们以1作为例子，在（1）中，（1,1）的位置会变换（1,3），在进行比对的时候如果发现两者不等，直接进入下个接口，不浪费时间。
2.同时，我们只需要存储开始和结束，然后使用常数的空间就可以检验是否能够匹配成功。
也就是说，搜索可以整个过程减少时空开销，但是，极端情况下，我们是不能减少时间的（由于空间从n^2变为了常数，所以一定是减少的），因为假设都在最后一步才能判断是否正确变换的情况下，那么时间和模拟是一样的。

以上就这个题单的全部内容啦，突然难度开始微微上调做题速度都慢了不少，明天一定早起早点把新的题单刷完。