第一题是一个很水的题目，其实就是让你求有多少个J右边的O的数量乘下面的I的数量之和。

最开始的想法，显然是写一个暴力，外面两层枚举J，中间两层枚举O，后面两层枚举I，这样复杂度显然是O(N^6)次方级别的，你就获得了15.36分左右的好成绩。

有没有O(1)查询每一个J的方法吗？很简单我们只需要维护一个二位前缀和即可，这样复杂度可以降到O(N^2)，可以通过N<=3000的数据。

顺便吐槽一下，这题为什么要卡常啊，我谔谔。。。

所以这题需要IO优化，否则你只能获得，71.79~84.69得分

MY CODE

#include<bits/stdc++.h>
using namespace std;
long long ans=0;
long long s[3005][3005];//分别记录O和I
long long t[3005][3005];
char c[3005][3005];
int main()
{
    ios::sync_with_stdio(false);//IO优化
    int n;
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>c[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=1;j--)
        {
            s[i][j]=s[i][j+1]+(c[i][j]=='O');//算每一个O
        }
    }
    for(int j=1;j<=m;j++)
    {
        for(int i=n;i>=1;i--)
        {
            t[i][j]=t[i+1][j]+(c[i][j]=='I');//算每一个I
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(c[i][j]=='J')
            ans+=s[i][j]*t[i][j];//统计答案就可以了了
        }
    }
    cout<<ans;
    return 0;
    //完美的结束
}

很多同学看到这，可能会觉得可以用树状数组来维护，但是这样复杂度是O(NlogN)的，所以可能会被卡掉。

第二题是一个贪心，

先考虑暴力，我们可以外层枚举画，里层枚举画框，之后挨个试，这样复杂度显然是O(NM)的可以获得53.25左右的高分。

我们可以看正解：我们可以先将画排一下序，使用一个结构体（这样数据不会乱），之后再将画框排一下序，之后挨个扫描，如果可以装进当前画框，那么答案就加，否则将画框的编号加一下，知道能放下，如果画框编号已经到N个说明后面的画一定都装不下，所以只要输出i-1就行了，如果最后编号还是没到N，就说明所有画都可以装进去只要输出M就可以啦！

由于我们已经将画（按美观程度排序），画框也都排序了，所以不需要考虑，题面中说的那两个条件。这样复杂度显然是排序的复杂度即O(NlogN+MlogM)，可以通过本题。

MY CODE

#include <bits/stdc++.h>
using namespace std;
struct h{
    int x;
    int y;
}a[100005];
bool cmp(h p,h q)
{
    if(p.y==q.y)
    return p.x>q.x;
    return p.y>q.y;
}
bool compare(int p,int q)
{
    return p>q;
}
int main()
{
    int n;
    int m;
    cin>>n>>m;
    int c[100005];
    for(int i=1;i<=n;i++)
    cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);//将画排序
    for(int i=1;i<=m;i++)
    cin>>c[i];
    sort(c+1,c+m+1,compare);//将画框排序
    int o=1;
    for(int i=1;i<=m;i++)
    {
        while(o<=n&&a[o].x>c[i]) //看能否装得下
        o++;
        if(o>n)//看是否编号已到N
        {
            cout<<i-1<<endl;//输出当前编号-1
            return 0;
        }
        o++;
    }
    cout<<m<<endl;
    return 0;
}

第三道题是一个垃圾DP，我不会（哭

第四题相对比较简单，是一个纯模拟

对于前36个点，我们可以纯爆搜去做，复杂度较玄学，可以拿到34.92的高分。

而对于满分，我们可以将硬币先移动到离他最近的格子，这是会有一些地方有很多，而一些地方却没有，我们可以扫描一下每一列，可以类似的理解为一个贪心，如果有空的地方，就移过来一些，否则将这列多余的硬币全部拿走。复杂度也比较玄学差不多O(N)的，可以通过此题。

MY CODE

#include <bits/stdc++.h>
using namespace std;
int b[1000005][3];
int main()
{
    int n;
    cin>>n;
    long long ans=0;
    for(int x,y,i=1;i<=2*n;i++)
    {
        cin>>x>>y;
        if(x<1)
        {
            ans+=1-x;
            x=1;
        }
        if(x>n)
        {
            ans+=x-n;
            x=n;
        }
        if(y<1)
        {
            ans+=1-y;
            y=1;
        }
        if(y>2)
        {
            ans+=y-2;
            y=2;
        }
                //往近的地方放
        b[x][y]++;//将有硬币的地方加一下（类似于一个桶）
    }
    for(int i=1,x=0,y=0;i<=n;i++) 
    {
                x+=b[i][1]-1;
        y+=b[i][2]-1;
                while(x<0&&y>0)
                {
                    x++;
                    y--;
                    ans++;
            }
                while(x>0&&y<0)
                {
                    x--;
                    y++;
                    ans++;
            }
                //按照上过程模拟即可
                if(i<n)
                ans+=abs(x)+abs(y);//计算答案
        }
        cout<<ans;
    return 0;
}

第五题是一道长链剖分的模板题，可是我不会这种高级的玩意，其实思路并不是很难，大家可以自己去思考思考。

希望大家，理解了再抄。

谢谢观看，再见啦！