top1编程
← 返回题目
题解

NOIP201709宝藏

1 条题解

  • 0
    @ 2026-7-28 22:31:39
    #include<bits/stdc++.h>
    using namespace std;
    long long x[301000], y[301000], xx[301000], yy[301000], maxx=LONG_LONG_MIN, n, m, k, maxx_x=-1, maxx_y=-1;
    // x[i]: 第i行的宝藏数量
    // y[i]: 第i列的宝藏数量  
    // xx[i]: 第i个宝藏的行坐标
    // yy[i]: 第i个宝藏的列坐标
    // maxx: 未使用的变量
    // n,m,k: 行数、列数、宝藏数量
    // maxx_x: 当前找到的最大行宝藏数
    // maxx_y: 当前找到的最大列宝藏数
    
    int main(){
        cin >> n >> m >> k;
        int flagx, flagy;  // flagx:最大行对应的行号, flagy:最大列对应的列号
        int flag = 0;      // 标记(flagx, flagy)位置是否有宝藏,0表示无,1表示有
        
        // 读入所有宝藏位置并统计每行每列的宝藏数
        for(int i = 1; i <= k; i++){
            cin >> xx[i] >> yy[i];
            x[xx[i]]++;  // 第xx[i]行宝藏数+1
            y[yy[i]]++;  // 第yy[i]列宝藏数+1
            
            // 更新最大行和最大列(边读边更新,存在逻辑缺陷)
            if(maxx_y < y[yy[i]] && maxx_x < x[xx[i]]){
                // 当前宝藏所在的行和列都创下新高,同时更新行和列
                flagx = xx[i];
                maxx_x = max(maxx_x, x[xx[i]]);
                flagy = yy[i];
                maxx_y = max(maxx_y, y[yy[i]]);
            }
            else if(maxx_x <= x[xx[i]]){
                // 仅当前行创下新高,更新最大行
                flagx = xx[i];
                maxx_x = max(maxx_x, x[xx[i]]);
            }
            else if(maxx_y <= y[yy[i]]){
                // 仅当前列创下新高,更新最大列
                flagy = yy[i];
                maxx_y = max(maxx_y, y[yy[i]]);
            }
        }
        
        // 检查(flagx, flagy)这个位置是否有宝藏
        // 如果有宝藏,激活该位置时会重复计算,需要减1
        for(int i = 1; i <= k; i++){
            if(xx[i] == flagx && yy[i] == flagy){
                flag = 1;  // 该位置有宝藏
                break;
            }
        }
        
        // 输出:最大行宝藏数 + 最大列宝藏数 - flag
        // flag=1表示交点有宝藏需要减1,flag=0表示交点无宝藏直接相加
        cout << maxx_x + maxx_y - flag;
        return 0;
    }
    
    • 1