欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

牛客国庆集训day6 B Board (模拟标记思维或找规律或分块???)

程序员文章站 2022-04-15 08:59:48
链接:https://www.nowcoder.com/acm/contest/206/B来源:牛客网 题目描述 恬恬有一个nx n的数组。她在用这个数组玩游戏: 开始时,数组中每一个元素都是0。 恬恬会做某些操作。在一次操作中,她可以将某一行的所有元素同时加上一个值,也可以将某一列的所有元素同时加 ......

链接:https://www.nowcoder.com/acm/contest/206/b
来源:牛客网

题目描述

恬恬有一个nx n的数组。她在用这个数组玩游戏:
开始时,数组中每一个元素都是0。
恬恬会做某些操作。在一次操作中,她可以将某一行的所有元素同时加上一个值,也可以将某一列的所有元素同时加上一个值。
在几次操作后,一个元素被隐藏了。你能帮助她回忆隐藏的数是几吗?

输入描述:

第一行一个整数n(1≤ n≤ 1000)。
接下来n行每行n个整数表示数组a。
第(i+1)行的第j个元素表示a
ij
(a
ij
=-1或0≤ a
ij
 ≤ 10000)。-1表示隐藏的元素。

输出描述:

仅一个整数表示答案。
示例1

输入

复制
3
1 2 1
0 -1 0
0 1 0

输出

复制
1



-1的位置置为inf  然后跑每一行每一列的最小值,如果不是0,就该行或列减去最小值。然后肯定-1那个位置还有数,其他位置为0. 然后输出inf-a[i][j]。
 
 
标记思维。
 
 
 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 #include <string.h>
 5 #include <stdlib.h>
 6 #include <string>
 7 #include <vector>
 8 #include <set>
 9 #include <map>
10 #include <queue>
11 #include <algorithm>
12 #include <sstream>
13 #include <stack>
14 using namespace std;
15 #define rep(i,a,n) for (int i=a;i<n;i++)
16 #define per(i,a,n) for (int i=n-1;i>=a;i--)
17 #define pb push_back
18 #define mp make_pair
19 #define all(x) (x).begin(),(x).end()
20 #define fi first
21 #define se second
22 #define sz(x) ((int)(x).size())
23 #define fo freopen("in.txt", "r", stdin);
24 #define debug(x) cout << "&&" << x << "&&" << endl;
25 #define lowbit(x) (x&-x)
26 #define mem(a,b) memset(a, b, sizeof(a));
27 typedef vector<int> vi;
28 typedef long long ll;
29 typedef pair<int,int> pii;
30 const ll mod=1000000007;
31 const int inf = 0x3f3f3f3f;
32 ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
33 ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
34 //head
35 
36 const int maxn=1010;
37 int n,a[maxn][maxn];
38 
39 int main() {
40     scanf("%d",&n);
41     rep(i,0,n) {
42         rep(j,0,n) {
43             scanf("%d",&a[i][j]);
44             if(a[i][j]==-1) {
45                 a[i][j]=inf;//-1位置设为inf
46             }
47         }
48     }
49     rep(i,0,n) {//找每一行的最小值
50         int minn=inf;
51         rep(j,0,n) {
52             if(a[i][j]<minn)
53                 minn=a[i][j];
54         }
55         if(minn!=0) rep(j,0,n) a[i][j]-=minn;//最小值不为0 减
56     }
57     rep(i,0,n) {//找每一列的最小值
58         int minn=inf;
59         rep(j,0,n) {
60             if(a[j][i]<minn)
61                 minn=a[j][i];
62         }
63         if(minn!=0) rep(j,0,n) a[j][i]-=minn;//最小值不为0 减
64     }
65     //最后肯定是-1的位置还有数(>0) 其他位置为0
66     int ans=0;
67     rep(i,0,n) {
68         rep(j,0,n) {
69             if(a[i][j]>0)
70                 ans=inf-a[i][j];//差值即原数
71         }
72     }
73     printf("%d",ans);
74 }

 

还有这样的解法,但是不知道为什么?纯找规律?

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[1010][1010];
 4 
 5 int main(){
 6     int n,i,j,x,y;
 7     //freopen("in.txt","r",stdin);
 8     scanf("%d",&n);
 9     for(i=1;i<=n;i++)
10         for(j=1;j<=n;j++)
11         {
12             scanf("%d",&a[i][j]); 
13             if(a[i][j]==-1) x=i,y=j;
14         }
15       int fx,fy;
16       if(x==n) fx=x-1; else fx=x+1;
17       if(y==n) fy=y-1; else fy=y+1;
18       printf("%d\n",a[x][fy]+a[fx][y]-a[fx][fy]);
19     return 0;
20 }

 

还有一种思想,大佬说是分块??有一点点明白,就是分成n块,每行每列加一个数,那么n块都加上了,也就是说,这n块加的数是相同的。 (i+j)%n分块

 

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int ans[1001],n;
 5 int main()
 6 {
 7     scanf("%d",&n);
 8     int x,t;
 9     for(int i=0;i<n;i++)
10     for(int j=0;j<n;j++)
11     {
12         scanf("%d",&x);
13         if(x!=-1)
14         ans[(i+j)%n]+=x;
15         else t=(i+j)%n;//-1的块
16     }
17     printf("%d\n",ans[(t+1)%n]-ans[t]);//其他块 - (-1的块)
18     return 0;
19 }