Albert_lob--P9117

Albert_lob · 2025-07-26 17:27:05 · 休闲·娱乐

这是我的第一篇文章

P9117 题解及注释

这一题很多人都会按照惯例使用二维数组,但由于此题的空间范围堪称~变态~，所以使用二维数组不是空间不足就是空间超限((10^5)^2的空间啊!!!)；
其实两个一维数组也可以完成这个二维问题，但需要把是这一行的颜色还是这一列的颜色搞清楚；
下面用一个例子来判断是行优先还是列优先：

if(y[i].深层数>z[j].深层数){//判断是行数深还是纵数深； 
        cout<< y[i].color<<endl;
        //这一个点以行的深度定色；
}else {
        cout<< z[i].color<<endl;//换行不能忘！
        //这一个点以列的深度标色；
}

面对时间复杂度的问题，cout在正式代码建议别用，不然很容易TIE掉；
这个语句叫memset(),如果不想打下面的代码，可以用它：

for(int i=0;i<n;i++){
    cin>>a[i];
}
for(int j=0;j<m;j++){
    cin>>b[j];
}

memset(a,b,c)可以把a~c内的内存全部初始化为值b；
由于后面的程序中有memset()，所以提前介绍一下；

源代码：

#include<bits/stdc++.h>//懒得写那么多头文件 
#define ll long long
using namespace std;
//define真好用！；
struct paint{
    ll color, p;//两个longlong变量：颜色，层数； 
}z[100010], y[100010];//z为横，y为纵；
//至于为什么要用两个一维数组是因为二位数组太占空间了，直接空间超限；
ll n,m,q;
// 纵数、横数、操作数； 
int main(){
     int T;//T组样例 ； 
     scanf("%d", &T);// 时间超限的痛； 
     while(T--){
         memset(z,0,sizeof(z));
         memset(y,0,sizeof(y));
         //memset内存初始化为0；
         //以后再也不用做如下操作：
            /*
              for(int i=0;i<n;i++){
                  ablablabl....;
              }
              for(int j=0;j<m;j++){
                  ablablabl....;
              }
            */ 
         scanf("%lld%lld%lld",&n,&m,&q);
         for(int i=1;i<=q;i++){
             ll opt,x,c;//定义方式（纵还是横）、行数（或列数）、颜色； 
             scanf("%lld%lld%lld",&opt,&x,&c);// 时间超限的痛；
             if(opt==0){//判断是纵是横； 
                 y[x].color=c;//把第x行的颜色定为c; 
                 y[x].p=i;//把第x行的层数加深； 
             }
             else {
                 z[x].color=c;//把第x列的颜色定为c; 
                 z[x].p=i;//把第x列的层数加深； 
             }
         }
         for(int i=1;i<=n;i++){
             for(int j=1;j<=m;j++){
                 if(y[i].p>z[j].p){//判断是行数深还是纵数深； 
                     printf("%lld ", y[i].color);// 时间超限的痛；
                     //这一个点以行的深度定色；
                 }else{
                      printf("%lld ", z[j].color);// 时间超限的痛；
                      //这一个点以列的深度标色；
                 }
             }
             printf("\n");//换行；（这行注释是废话，可以不看）
         }
    }
    return 0;
}