ACM-ICPC 2014北京邀请赛 H Happy Reverse [模拟]

2024-06-17 03:32

本文主要是介绍ACM-ICPC 2014北京邀请赛 H Happy Reverse [模拟],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:给出n个二进制串,可以把其中的一些0和1反转(即0变1,1变0),找出转化后n个串中的最大值和最小值的差值。


分析:思路就是把所有的串和反转的存在一个数组中,然后排序,找最大值和最小值的差,(如果是同一个串反转的就找第二大的和最小的或第二小和最大的中的最大值)。注意假如只有一个串的话结果为0


DEBUG:

这题写了好久

1.第一次用vim,很爽,但是还没熟练

2.忽视了这题的范围,显然要用longlong

3.用了longlong后还WA,用脚本跑出来数据发现在longlong下,min的值要变成(1<<63)-1但是不能这么写,应该写个longlong 是1<<30,然后在这个longlong基础上再移位


最后不得不说句 BNUOJ真的比POJ好看很多哈

    #include <iostream>#include <cmath>#include <cstring>#include <cstdio>using namespace std;char str[111111][222];long long tmp=1<<30;const long long MAX_LONG=(tmp<<33)-1;long long num[111111];long long m,n;void getRev(char* to,char* source,long long len){for(long long i=0;i<len;i++)to[i]=source[i]=='0'?'1':'0';to[len]='\0';}long long getNum(char* s,long long len){long long sum=0;for(long long i=0;i<len;i++){sum*=2;sum+=s[i]-'0';}return sum;}int main(){long long test;cin>>test;for(long long time=1;time<=test;time++){cin>>m>>n;for(long long i=1;i<=m;i++)cin>>str[i];/*if(m==1){printf("Case #%d: 0\n",time);continue;}*/for(long long i=m+1;i<=2*m;i++)getRev(str[i],str[i-m],n);long long minn=MAX_LONG;long long maxn=0;for(long long i=1;i<=2*m;i++)num[i]=getNum(str[i],n);long long max1=0,max1index,min1=MAX_LONG,min1index;long long max2=0,max2index,min2=MAX_LONG,min2index;for(long long i=1;i<=2*m;i++){    if(num[i]>max1){max1=num[i];max1index=i;}if(num[i]<min1){min1=num[i];min1index=i;}}for(long long i=1;i<=2*m;i++){    if(i!=max1index&&num[i]>max2){max2=num[i];max2index=i;}if(i!=min1index&&num[i]<min2){min2=num[i];min2index=i;}}if(abs(min1index-max1index)!=m){maxn=max1;minn=min1;}else{if(max1-min2>max2-min1){//cout<<"1"<<endl;maxn=max1;minn=min2;}else{//cout<<"2"<<endl;maxn=max2;minn=min1;}}//cout<<maxn<<' '<<minn<<endl;printf("Case #%lld: %lld\n",time,maxn-minn);}return 0;}


这篇关于ACM-ICPC 2014北京邀请赛 H Happy Reverse [模拟]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1068372

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

ZOJ Monthly, August 2014小记

最近太忙太忙,只能抽时间写几道简单题。不过我倒是明白要想水平提高不看题解是最好的了。 A  我只能死找规律了,无法证明 int a[50002][2] ;vector< vector<int> > gmax , gmin ;int main(){int n , i , j , k , cmax , cmin ;while(cin>>n){/* g

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数