【题解】10-1入门组模拟

666，OI给我当ccf整，这个memset太吃操作了

A.[EC Final 2021] DFS Order

link

这题很简单，观察样例就可以得出结论（这是我第一次自己想出来）：

• 最小的位置就是节点的深度
• 最大的位置就是所有节点减掉自己节点子树和

// Problem:Luogu P9872 [EC Final 2021] DFS Order

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100010;
vector <int> g[MAXN];
int tsize[MAXN],dep[MAXN],n;
void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1;
	tsize[u]=1;
	for(auto v:g[u])
	{
		dfs(v,u);
		tsize[u]+=tsize[v];
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)g[i].clear();
		for(int i=1;i<n;i++)
		{
			int u,v;
			cin>>u>>v;
			g[u].push_back(v);
		}
		dfs(1,0);
		for(int i=1;i<=n;i++)
		{
			cout<<dep[i]<<" "<<tsize[1]-tsize[i]+1<<'\n';
		}
	}
}

666，原先我在这里加了一个memset清空dep和tsize，然后提交完以为这题过了，实则被这个猎奇玩意儿搞tle了

B.[COCI 2011/2012 #1] MATRIX

link

这题通过简简单单的模拟就可以过了……

#include<bits/stdc++.h>
using namespace std;
int n,a[410][410],ans=-0x3f3f3f3f;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
            
    for(int len=1;len<=n;len++)
        for(int i=1;i<=n-len+1;i++)
            for(int j=1;j<=n-len+1;j++)
            {
                int suma=0,sumb=0;
                for(int k=0;k<len;k++)
                    suma += a[i+k][j+k];
                for(int k=0;k<len;k++)
                    sumb += a[i+k][j+len-1-k];
                ans=max(ans,suma-sumb);
            }
    cout<<ans;
    return 0;
}

（吗？）

很显然，这个黄题肯定不会让我们这么随便就过了，肯定会tle的

所以，就要用上前缀和啦！

// Problem:Luogu P7626 [COCI 2011/2012 #1] MATRIX

#include<bits/stdc++.h>
using namespace std;
int n,a[410][410],ans=-0x3f3f3f3f;
int sum1[410][410],sum2[410][410];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			sum1[i][j]=sum1[i-1][j-1]+a[i][j],
			sum2[i][j]=sum2[i-1][j+1]+a[i][j];
	for(int len=1;len<=n;len++)
		for(int i=1;i<=n-len+1;i++)
			for(int j=1;j<=n-len+1;j++)
			{
				int ii=i+len-1,jj=j+len-1;
				int a=sum1[ii][jj]-sum1[i-1][j-1];
				int b=sum2[ii][j]-sum2[i-1][jj+1];
				ans=max(ans,a-b);
			}
	cout<<ans;	
	return 0;
}

为什么这题满分是80分呢

C. [CCC 2016] 合并饭团

link

第一眼CCF

这一题是一个区间dp再加点料的（黑暗料理）

关键在于它要将饭团合并（这对于你们这些神犇估计不是什么关键吧）

// Problem:Luogu P4805 [CCC 2016] 合并饭团

#include<bits/stdc++.h>
using namespace std;
int n,a[410],dp[410][410],f[410][410];
//f表示i,j这个区间可以合并成一个饭团
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],dp[i][i]=a[i],f[i][i]=1;
	for(int len=1;len<=n;len++)
		for(int i=1;i<=n-len+1;i++)
			for(int mid=i;mid<i+len-1;mid++)
			{
				int j=i+len-1;
				if(dp[i][j]<dp[i][mid])dp[i][j]=dp[i][mid];
				if(dp[i][j]<dp[mid+1][j])dp[i][j]=dp[mid+1][j];
                //设置初值
				if(f[i][mid]&&f[mid+1][j]&&dp[i][mid]==dp[mid+1][j]) 
				{
					dp[i][j]=dp[i][mid]+dp[mid+1][j];
                    //更新
					f[i][j]=1;
					break;
				}
				else 
				{
					bool flag=0;
					for(int midd=mid+1;midd<=j;midd++)
					{
						if(f[i][mid]&&f[mid+1][midd]&&f[midd+1][j]&&dp[i][mid]==dp[midd+1][j])	
						{
							dp[i][j]=dp[i][mid]+dp[mid+1][midd]+dp[midd+1][j];
							f[i][j]=1;
							flag=1;
							break;
						}
					}
					if(flag)break;
				}
			}
	cout<<dp[1][n];
	return 0;
	
}

D.【MX-J8-T3】水星湖

link

这题我在比赛的时候看过，但是因为当时太🥬了，所以没做。

这题需要用一个优先队列记录事件的要素：

1. 事件
2. 类型（树生长/种下 or 死亡）
3. 发生的地点

然后就可以快乐的打磨你了

// Problem:Luogu P11215 【MX-J8-T3】水星湖

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3010;
int n,m,qq,r,k;
int mp[N][N];
struct happening
{
    int t;//时间
    int thing;//类型
    int x,y;//坐标
    bool operator <(const happening& xx) const { return t > xx.t; }//按照时间进行排序
    //运算符重载
};
priority_queue <happening> q;
bool check_grow(int x,int y) 
{
    return x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]==0&&
    (mp[x-1][y]==1||mp[x+1][y]==1||mp[x][y-1]==1||mp[x][y+1]==1);
    //判断这个地点能不能生长树木
}
void solve()
{
    cin>>n>>m>>qq>>r>>k;
    k*=2;//因为0.5是浮点数，所以乘一个2
    for(int _=1;_<=qq;_++)
    {
        int xa,xb,ya,yb;
        cin>>xa>>ya>>xb>>yb;
        for(int x=xa;x<=xb;x++)
            for(int y=ya;y<=yb;y++)
                mp[x][y]=1;
    }
    for(int _=1;_<=r;_++)
    {
        int t,x,y;
        cin>>t>>x>>y;
        q.push({t*2,0,x,y});
    }
    int ans=0;
    while(!q.empty())
    {
        happening tmp=q.top();
        q.pop();
        if(tmp.thing==0)
        {
            if(mp[tmp.x][tmp.y]==0)
            {
                mp[tmp.x][tmp.y]=2;
                if(mp[tmp.x-1][tmp.y]==0&&
                   mp[tmp.x+1][tmp.y]==0&&
                   mp[tmp.x][tmp.y-1]==0&&
                   mp[tmp.x][tmp.y+1]==0)
                    q.push({tmp.t+k+1,1,tmp.x,tmp.y});//是否满足树的死亡条件
                //向四周扩散
                if(check_grow(tmp.x-1,tmp.y))q.push({tmp.t+2,0,tmp.x-1,tmp.y});
                if(check_grow(tmp.x+1,tmp.y))q.push({tmp.t+2,0,tmp.x+1,tmp.y});
                if(check_grow(tmp.x,tmp.y-1))q.push({tmp.t+2,0,tmp.x,tmp.y-1});
                if(check_grow(tmp.x,tmp.y+1))q.push({tmp.t+2,0,tmp.x,tmp.y+1});
            }
        }
        else if(tmp.thing==1)
        {
            if(mp[tmp.x-1][tmp.y]==0&&
               mp[tmp.x+1][tmp.y]==0&&
               mp[tmp.x][tmp.y-1]==0&&
               mp[tmp.x][tmp.y+1]==0)
                mp[tmp.x][tmp.y]=0;//树死亡
        }
    }
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)
            if(mp[i][j]==2)ans++;
    cout<<ans<<endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    solve();
    return 0;
}