首页 > 代码库 > hdu--4022--multimap<别人用快排+二分,没学好>
hdu--4022--multimap<别人用快排+二分,没学好>
本来 我是想直接开2个计数数组 存下 行 列各自的元素个数的..
可是 数据达到了 10^9 但是数据个数 只有10^5 虽然可以考虑用 离散化...但我想先map试下 毕竟 离散化烦~
关于multimap的使用 和map还是有点差别的..但是 我们单纯地只是使用 stl中的函数的话 还是不存在什么难度吧
听说 <<STL源码剖析>>不错...可是 不太适合初学者~ =_= 大师 经典..
我这题的wa错误 太难找了 厌死....
我因为一开始想使用数组的原因 多此一举地 将 c d中的d取 绝对值了 ..我也是醉了
还有一个错误...就是 待会在代码注释你们将会看到的
在输出 col[x] 与 row[x]后 将它们重置为0了 这是 致命的错误 =_= 因为我的If判断条件是 >=0 那么如果下次 又询问到它的时候 会导致重复计算该行 或 列上的点..
就会导致后续的错误.
1 #include <iostream> 2 #include <map> 3 using namespace std; 4 5 multimap<int,int>rowMp; 6 multimap<int,int>colMp; 7 map<int,int>row; 8 map<int,int>col; 9 10 int main()11 {12 int n , m , op , x , y;13 while( ~scanf("%d%d",&n,&m) )14 {15 if(!n&&!m)16 break;17 row.clear();18 rowMp.clear();19 col.clear();20 colMp.clear();21 while( n-- )22 {23 scanf("%d%d",&x,&y);24 col[x] ++;25 row[y] ++;26 colMp.insert( pair<int,int>(x,y) );27 rowMp.insert( pair<int,int>(y,x) );28 }29 multimap<int,int>::iterator rowIt;30 multimap<int,int>::iterator colIt;31 while( m-- )32 {33 scanf("%d%d",&op,&x);34 if( op )//y = d 清空行 35 {36 if( row[x]>=0 )37 {38 printf("%d\n",row[x]);39 //row[x] = 0;40 row[x] = -1;41 rowIt = rowMp.find( x );42 int num = rowMp.count( x );43 while(num--)44 {45 col[rowIt->second] --;46 rowIt ++;47 }48 }49 else50 {51 printf("0\n");52 }53 }54 else //x = d清空 列 55 {56 if( col[x]>=0 )57 {58 printf( "%d\n",col[x] );59 //col[x] = 0;60 col[x] = -1;61 colIt = colMp.find( x );62 int num = colMp.count( x );63 while( num-- )64 {65 row[colIt->second] --; 66 colIt ++; 67 }68 }69 else70 {71 printf("0\n");72 }73 }74 }75 printf("\n");76 }77 return 0;78 }
我再去学习 人家用 快排+二分的做法.
today:
我是个 得意忘形 的人
hdu--4022--multimap<别人用快排+二分,没学好>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。