洛谷7月月赛

第一次参加洛谷月赛有点小紧张，刚开始做题脑子有点乱，第一题卡了一个小时。。

最终成绩

第一题 P5461 赦免战俘

题目描述

这一题的思路就是递归！
然而中间不知怎么的想去找规律，一次性赋值，浪费了很长时间。

由于‘1’的个数小于‘0’的个数，所以目标是将矩阵中所以填‘1’的位置给找出来。
1.判断矩阵大小能否分割，若不能分割则置‘1’；
2.能分割的话，就将矩阵分割为四部分，把右上，左下，右下，这三个部分进行递归。

那么我们需要传入哪些参数来使函数知道当前所判断的小矩阵在原矩阵的哪个位置呢？
我们传入x,y作为当前矩阵最左上角的横纵坐标，bc为当前矩阵的边长。
代码如下

#include <bits/stdc++.h>
using namespace std;

int a[1030][1030];

void fillone(int x,int y,int bc)
{
    if(bc == 1)
    {
        a[x][y] = 1;
        return;
    }
    fillone(x+bc/2,y,bc/2);
    fillone(x,y+bc/2,bc/2);
    fillone(x+bc/2,y+bc/2,bc/2);
}

int main()
{
    int n;
    cin>>n;
    memset(a,0,sizeof(a));
    int bc = pow(2,n);
    fillone(0,0,bc);
    for(int i = 0 ; i < bc ; i++)
    {
        for(int j = 0 ; j < bc ; j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
    return 0;
}

第二题 P5462 X龙珠

题目描述

测试点说明

思路一样，用数组超时了，需要用链表或者堆去实现，这里用了一个数组模拟链表的解法。

#include <bits/stdc++.h>
using namespace std;

//h为哈希表i元素对应队列中的位置为h[i],a为位置i对应元素a[i](只能用来寻找一个元素的位置，而不能通过位置i的+，-来寻找前后的位置),l模拟左链表指针，r模拟右链表指针
int a[100005];
int h[100005];
int l[100005];
int r[100005];


int main()
{
    int n;
    cin>>n;
    memset(a,0,sizeof(a));
    memset(h,0,sizeof(h));
    vector<int> output;
    for(int i = 0 ; i < n ; i++)
    {
        int item;
        cin>>item;
        h[item] = i;
        a[i] = item;
        l[i] = i-1;
        r[i] = i+1;
    }
    for(int i = n ; i>= 1 ; i--)
    {
        if(h[i] == -2||r[h[i]] == n)
        {
            continue;
        }
        int m = r[h[i]];
        int v = h[i];
        int j = a[r[h[i]]];
        output.push_back(i);
        output.push_back(j);
        r[l[h[i]]] = r[h[j]];
        l[r[h[j]]] = l[h[i]];
        h[i] = -2;
        h[j] = -2;
    }
    for(int i = 0 ; i < output.size() ; i++)
    {
        cout<<output[i]<<" ";
    }
    cout<<endl;
    return 0;
}

第三题 P5463 小鱼比可爱（加强版）

题目描述

本题的核心是求逆序对数
介绍一个暴力的方式，能过前六个测试点。

方法是求每个逆序对为整体做的贡献值，每个逆序对在以其为子序列的序列中都能作出贡献，所以在遍历到每个逆序对时就通过他的位置算出这个逆序对的贡献。
代码是sum += (i+1)*(n-j);
整体代码如下：

#include <bits/stdc++.h>
using namespace std;

bool isnixu(int a,int b)
{
    return a > b;
}

int main()
{
    int n;
    long long sum = 0;
    cin>>n;
    vector<int> vec;
    for(int i = 0 ; i < n ; i++)
    {
        int item;
        cin>>item;
        vec.push_back(item);
    }
    for(int i = 0; i < n - 1 ; i++)
    {
        for(int j = i + 1 ; j < n ; j++)
        {
            if(vec[i] <= vec[j])
            {
                continue;
            }
            sum += (i+1)*(n-j);
        }
    }
    cout<<sum<<endl;
    return 0;
}