专栏文章

10.1模拟赛

mmiller2014
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minqebkd
此快照首次捕获于
2025/12/02 06:39
3 个月前
此快照最后确认于
2025/12/02 06:39
3 个月前
查看原文

分数

估分

T1:100pts
T2:100pts
T3:100pts
T4:1pts

实际

T1:70pts
T2:100pts
T3:100pts
T4:1pts

主要原因

T1:死了。我将题目中对于字符类型的判断与对于相同字符去重的判断写在了一起。。。导致将重复字符判成了特殊字符。。。
T4:算了一下部分分的时间，结果算错了没打暴力，让后就搞第三题动归了。最后把第三题切掉之后没想第四题，痛失50pts。

题解

T1

太简单了

T2

太简单了

T3

一道动归。
不难发现 O(nm)O(nm) 不超时，所以设 dpi,jdp_{i,j} 表示只看排序后前 ii 个数，且只选 jj 组数求差时的最小值。
答案即为 dpn,mdp_{n,m} 。
边界即为 dpi,1=min⁡j=2iabs(aj−aj−1)dp_{i,1}=\min\limits_{j=2}^{i}{abs(a_j-a_{j-1})} 。
方程即为
dpi,j=min⁡(dpi−1,j,dpi−2,j−1+∣ai−ai−1∣)dp_{i,j}=\min(dp_{i-1,j},dp_{i-2,j-1}+|a_i-a_{i-1}|)

T4

只会暴力。。。
暴力太简单了。。。
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,q,qw,er,ty,ui,ans;
struct node
{
    int x,y,l;
};
vector<node> a;
string s[5005];
void push(int x,int y,int l)
{
    a.push_back({x,y,l});
    if(x==0||y==0||x+l==n-1||y+l==m-1)return;
    for(int i=0;i<=(l+1)/2;i++)
    {
        if(s[x-1+i][y-1]!='B'||s[x-1][y-1+i]!='B'||s[x+l+1-i][y-1]!='P'||s[x+l+1][y-1+i]!='P'||s[x+l+1][y+l+1-i]!='G'||s[x+l+1-i][y+l+1]!='G'||s[x-1+i][y+l+1]!='W'||s[x-1][y+l+1-i]!='W')
			return;
	}
	push(x-1,y-1,l+2);
}
int main()
{
    // freopen("shirt.in","r",stdin);
    // freopen("shirt.out","w",stdout);
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    for(int i=0;i<n;i++)cin>>s[i];
    for(int i=1;i<n;i++)
    	for(int j=1;j<m;j++)
            if(s[i][j]=='G'&&s[i-1][j]=='W'&&s[i-1][j-1]=='B'&&s[i][j-1]=='P')
				push(i-1,j-1,1);
    while(q--)
    {
        ans=0;
        cin>>qw>>er>>ty>>ui;
        er--,ui--,qw--,ty--;
        for(int i=0;i<a.size();i++)
            if(a[i].x>=qw&&a[i].y>=er&&a[i].x+a[i].l<=ty&&a[i].y+a[i].l<=ui)
                ans=max(ans,(a[i].l+1)*(a[i].l+1));
        cout<<ans<<"\n";
    }
    return 0;
}
以后还是要多读题！！！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...