经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C » 查看文章
牛客国庆集训day6 B Board (模拟标记思维或找规律或分块???)
来源:cnblogs  作者:ACMerszl  时间:2018/10/8 9:14:31  对本文有异议

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

题目描述

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

输入描述:

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

输出描述:

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

输入

复制
  1. 3
  2. 1 2 1
  3. 0 -1 0
  4. 0 1 0

输出

复制
  1. 1



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

 

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

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

 

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

 

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

 

 

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号