公司网站网络营销是什么,创新的企业网站开发,如何制作一个网页,wordpress雪樱主题破解进位制专题 目录 MT2186 二进制#xff1f;不同#xff01;MT2187 excel的烦恼MT2188 单条件和MT2189 三进制计算机1MT2190 三进制计算机2 MT2186 二进制#xff1f;不同#xff01; 难度#xff1a;黄金 时间限制#xff1a;1秒 占用内存#xff1a;128M 题目…进位制专题 目录 MT2186 二进制不同MT2187 excel的烦恼MT2188 单条件和MT2189 三进制计算机1MT2190 三进制计算机2 MT2186 二进制不同 难度黄金 时间限制1秒 占用内存128M 题目描述 小码哥是一个对数很敏感的人即使给他很多个很像的数串他都能找出没有出现过的数串。 或许是有些无聊小码哥给你一个字符串数组 nums里面包含 n n n 个二进制字符串长度都为 n n n )现请你找出不在数组中的二进制字符串。若有多解返回对应十进制最小的一个。 格式 输入格式一行二进制字符串数组字符串之间以空格分割 输出格式一个不在数组中的二进制字符串。 样例 1 输入01 10 输出00 备注 其中 1 ≤ n ≤ 16 1 \le n \le 16 1≤n≤16nums中所有字符互不相同。 相关知识点进位制 题解 本题要求找出尚未在输入数据中出现的最小值所有数据的最小取值为 0。但是题目给出的数据为二进制字符串合法的因此为了找出最小未出现的数我们需要先将所有输入的二进制字符串转换为十进制数并将这些数存放进一个集合 nums 中。接下来从 0 开始逐步向后枚举整数一旦存在某个数不在集合 nums 中就说明这个数是尚未在输入数据中出现的最小数。注意我们还需对这个数进行格式转换即将这个数由十进制再转换为二进制字符串长度需要和输入数据的长度一致。
下面直接给出求解此题的完整代码已 AC
/*MT2186 二进制不同 测试数据001 100 000
*/
#includebits/stdc.h
using namespace std;setint nums;// 该函数将合法的二进制数字串转换为十进制数字
int getDecFromBin(string str)
{int sum 0, base 1;for(int istr.size()-1; i0; i--){sum base*(str[i]-0);base * 2;}return sum;
} // 将一个十进制数转换为指定长度的二进制字符串
string toBinary(int n, int len)
{string str ;while(len--){if(n1) str 1str;else str 0str;n 1;}return str;
} int main( )
{// 输入数据string str;while(cinstr)nums.insert(getDecFromBin(str));// 记录当前输入二进制字符串的长度int binStrlen str.length();// 寻找最小值并在进行格式转换后输出 for(int i0; ; i){// 找到一个尚未在集合中出现的最小数值if(nums.find(i) nums.end()){couttoBinary(i, binStrlen)endl;break;}}return 0;
}MT2187 excel的烦恼 难度钻石 时间限制2秒 占用内存128M 题目描述 你用过 Excel 么? 在 excel 中第一列被标为 A第二列为 B以此类推第 26 列为 Z。接下来为由两个字母构成的列号第 27 列为 AA第 28 列为 AB……在标为 ZZ 的列之后则由三个字母构成列号如此类推。 行号为从 1 开始的整数。 单元格的坐标由列号和行号连接而成。比如BC23 表示位于第 55 列 23 行的单元格。 有时也会采用被称为 RXCY 的坐标系统其中 X 与 Y 为整数坐标 (X, Y) 直接描述了对应单元格的位置。比如R23C55 即为前面所述的单元格。 小码哥请你编写一个程序将所给的单元格坐标转换为另一种坐标系统下面的形式。 格式 输入格式第一行一个整数 T(1≤T≤10^5) 表示将有 T 次询问 接下来 T 行每行一个坐标。 输出格式输出 T 行每行一个被转换的坐标。 样例 1 输入3 R12C3 AE32 BB11 输出C12 R32C31 R11C54 备注 每个坐标都是正确的。保证输入输出数据均在int范围内。输入输出数据字母部分均为大写。 相关知识点 进位制 题解 这道题表面是在对两种坐标形式进行转换但实际上也是在考察进制转换。例如对于 excel 形式的坐标其列号 BC 对应在十进制中为 55 2 × 2 6 1 3 × 2 6 0 55 2×26^13×26^055 2×2613×26055所以题中将 BC23 解析为第 55 行第 23 列的单元格。因此这里的进制转换问题实际上是十进制与以 A − Z A-Z A−Z 表达的二十六进制数之间的互相转换。
对于本题由于输入数据并没有说明其具体是哪一种形式的坐标表达因此我们需要做的第一件事是识别坐标格式。观察两种形式的坐标不难发现excel 形式的坐标是 “字母数字”而 RXCY 形式的坐标是 “字母数字字母数字”这两种形式的本质区别在于RXCY 的格式中会在数字的后面出现字母而 excel 形式下数字后面不可能出现字母。因此可以根据这一本质区别进行格式识别并在后续进行格式转换。
当完成了对输入坐标字符串的格式检测后便能分别进行格式转换了。具体的转换过程并不难详细细节可看这之后的例题MT2189 三进制计算机1、MT2190 三进制计算机2下面直接给出求解本题的完整代码已 AC
/*MT2187 excel的烦恼
*/
#includebits/stdc.h
using namespace std;string str;
int T;
char apt[] ABCDEFGHIJKLMNOPQRSTUVWXYZ;// 检测当前的坐标字符串属于那种格式
// 0 EXCEL 格式
// 1 RXCY 格式
bool getFormat(string str)
{bool flag 0;int strlen str.length();for(int i0; istrlen; i) {// 数字出现标记 if(isdigit(str[i]))flag true;// 检测是否为 RXCY 模式if(flag str[i]C)return true;}return false;
} // 格式转换
void transform(string str)
{// 格式识别bool mode getFormat(str);// 格式转换 int row 0, col 0, len str.length();if(mode){ // mode 1RXCY 转 ECXCEL 格式 // 定位 R 与 C 所在位置 int R str.find(R), C str.find(C);// 取出行号和列号 for(int iR1; iC; i) row row*10str[i]-0;for(int iC1; ilen; i)col col*10str[i]-0;// 将十进制数转换为以 A-Z 表达的二十六进制数 int tmp;string ans;while(col 0){tmp col%26;if(tmp 0){tmp 26;col - 26;}ans apt[tmp];col / 26;} reverse(ans.begin(), ans.end());// 格式化输出 coutansrowendl;}else{ // mode 0ECXCEL 转 RXCY 格式 // 将二十六进制数转换为十进制数 for(int i0; ilen; i)if(!isdigit(str[i]))col col*26str[i]-A1;elserow row*10str[i]-0;// 格式化输出 coutRrowCcolendl;}
}int main( )
{// 输入数据cinT;for(int i1; iT; i){cinstr;// 将当前的坐标表达式转换为另一种格式 transform(str);}return 0;
}MT2188 单条件和 难度黄金 时间限制1秒 占用内存128M 题目描述 “单条件” 是数理逻辑中的5种常用连接词之一记作 “→”。它是二元运算。相当于 “如果…那么…. ”、“因为……所以……”、“只要…就.….” 等。也可称为 “蕴涵”。“p→q” 读作 “如果p那么q”其中 p 称为前件q 称为后件。 其真值表如下 如 “异或和” 为 a 1 ⨁ a 2 ⨁ … ⨁ a n a_1⨁a_2⨁…⨁a_n a1⨁a2⨁…⨁an 我们现在要求 “单条件和”即 a 1 → a 2 → ⋯ → a n a_1→a_2→⋯→a_n a1→a2→⋯→an对 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,…,an 做位意义上的单条件运算求和。 请按 unsigned int 类型进行运算。 格式 输入格式第一行一个整数 n n n表示有 n n n 个需要求单条件和的整数 第二行输入 n n n 个需要求单条件和的整数。 输出格式输出一个 unsigned int 型的整数。 样例 1 输入10 1 2 3 4 5 6 7 8 9 10 输出4294967290 备注 对于100%的数据 1 ≤ n ≤ 5 e 6 1≤n≤5e6 1≤n≤5e6。 相关知识点位运算 题解 观察题目给出的真值表不难发现“p→q” 其实等价于执行位运算 “~p|q”非 p 或 q。在理解这一点后我们便能直接写出以下代码
/*MT2188 单条件和 用 scanf 接受输入才能得满分
*/
#includebits/stdc.h
using namespace std;int main( )
{// 输入数据int n;unsigned ans, tmp;cinnans;// 执行运算for(int i1; in; i) {scanf(%u,tmp);ans ~ans | tmp;}// 输出 coutansendl; return 0;
}MT2189 三进制计算机1 难度黄金 时间限制1秒 占用内存128M 题目描述 三进制计算机是以三进法数字系统为基础而发展的计算机。在光子计算机研究领域也有涉及。 三进制代码的一个特点是对称即相反数的一致性因此它和二进制代码不同不存在无符号数的概念。这样三进制计算机的架构也要简单、稳定、经济得多。其指令系统也更便于阅读而且非常高效。 在一般情况下命题不一定为真或假还可能为未知。在三进制逻辑学中符号 1 代表真符号 -1 代表假符号 0 代表未知。这种逻辑表达方式更符合计算机在人工智能方面的发展趋势它为计算机的模糊运算和自主学习提供了可能。 在本题中请你将输入的对称三进制数转换为对应的十进制数。对称三进制数不是用 0/1/2 表示比较特殊是用 1/0/-1 表示故名对称。本题中 -1 用符号 - 表示而 1 和 0 直接表示即可。 格式 输入格式第一输入一个整数 n n n 表示数据组数 接下来 n n n 行每行输入一个对称三进制整数。 输出格式对于第 2~n1 行输入的每一个对称三进制整数分别输出其十进制形式。 样例 1 输入8 -0 -1 - 0 1 1- 10 1– 输出-3 -2 -1 0 1 2 3 5 备注 样例中 2 3 − 1 3 3 0 × 1 5 9 − 3 − 1 23-1330 \times 159-3-1 23−1330×159−3−1。 对于100%的数据 1 ≤ n ≤ 1 e 6 1≤n≤1e6 1≤n≤1e6输入的对称三进制数对应的整数在 int 类型范围内 。 相关知识点平衡三进制 题解 这道题实际上考察的是进制转换即平衡三进制转换为十进制数。
首先我们要知道任意 k k k 进制数设为 A k a 1 a 2 ⋯ a n A_ka_1 a_2⋯a_n Aka1a2⋯an转换为十进制都遵循下式 n ∑ i 1 n a i k n − i n\sum_{i1}^na_i k^{n-i} ni1∑naikn−i
其中 a i a_i ai 表示该 k k k 进制数在第 i i i 位上的取数 n n n 表示其长度。
例如二进制数 1010 转换为十进制数为 n a 1 k 4 − 1 a 2 k 4 − 2 a 3 k 4 − 3 a 4 k 4 − 4 1 × 2 3 0 × 2 2 1 × 2 1 0 × 2 0 10 na_1 k^{4-1}a_2 k^{4-2}a_3 k^{4-3}a_4 k^{4-4}1×2^30×2^21×2^10×2^010 na1k4−1a2k4−2a3k4−3a4k4−41×230×221×210×2010
十六进制数 AE86 转换为十进制数为 n a 1 k 4 − 1 a 2 k 4 − 2 a 3 k 4 − 3 a 4 k 4 − 4 10 × 1 6 3 14 × 1 6 2 8 × 1 6 1 6 × 1 6 0 44678 na_1 k^{4-1}a_2 k^{4-2}a_3 k^{4-3}a_4 k^{4-4}10×16^314×16^28×16^16×16^044678 na1k4−1a2k4−2a3k4−3a4k4−410×16314×1628×1616×16044678
同样地三进制数也满足该式。但是本题比较特殊因为平衡三进制数中的 2 会用 -1 来表示但这并不影响通式给出的计算方法。例如对于题目给出的平衡三进制数1--其转换过程如下 n a 1 k 3 − 1 a 2 k 3 − 2 a 3 k 3 − 3 1 × 3 2 ( − 1 ) × 3 1 ( − 1 ) × 3 0 9 − 3 − 1 5 na_1 k^{3-1}a_2 k^{3-2}a_3 k^{3-3}1×3^2(-1)×3^1(-1)×3^09-3-15 na1k3−1a2k3−2a3k3−31×32(−1)×31(−1)×309−3−15
根据这样的思路可写出求解本题的完整代码
下面给出基于以上思路写出的完整代码已 AC
/*MT2189 三进制计算机1 输出转换结果时不能用 endl 否则会超时
*/
#includebits/stdc.h
using namespace std;const int N 105;
int w[N], n, ans, len;
char s[N];int main( )
{// 取消cin与stdin的同步加速文件读取速度 ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);// 输入数据cinn; // 构建乘位 w[0] 1;for(int i1; i100; i)w[i] w[i-1]*3;// 进制转换与输出 while(n--){cins;ans 0;len strlen(s);// 进制转换 for(int ilen-1; i0; i--){if(s[i] 1) ans w[len-1-i];if(s[i] -) ans - w[len-1-i];}// 输出转换结果coutans\n;}return 0;
}此外对本题而言还需要特别注意两点
必须取消 cin 与 stdin 的同步以加速文件读取速度否则会超时原理请见C中输入和输出的一些问题输出换行时必须用 “\n” 替代 “endl”否则会超时。
当然你也可以用 C 的方式进行数据输入输出即用scanf和printf替代cin和cout这样就不必担心上面的这些问题。 MT2190 三进制计算机2 难度钻石 时间限制1秒 占用内存128M 题目描述 三进制计算机是以三进法数字系统为基础而发展的计算机。在光子计算机研究领域也有涉及。 三进制代码的一个特点是对称即相反数的一致性因此它和二进制代码不同不存在无符号数的概念。这样三进制计算机的架构也要简单、稳定、经济得多。其指令系统也更便于阅读而且非常高效。 在一般情况下命题不一定为真或假还可能为未知。在三进制逻辑学中符号 1 代表真符号 -1 代表假符号 0 代表未知。这种逻辑表达方式更符合计算机在人工智能方面的发展趋势它为计算机的模糊运算和自主学习提供了可能。 在本题中请你将输入的对称三进制数转换为对应的十进制数。对称三进制数不是用 0/1/2 表示比较特殊是用 1/0/-1 表示故名对称。本题中 -1 用符号 - 表示而 1 和 0 直接表示即可。 格式 输入格式第一输入一个整数 n n n 表示数据组数 接下来 n n n 行每行输入一个十进制整数。 输出格式对于第 2~n1 行输入的每一个十进制整数分别输出其对称三进制形式。 样例 1 输入8 -3 -2 -1 0 1 2 3 5 输出-3 -0 -1 - 0 1 1- 10 1– 备注 样例中 2 3 − 1 3 3 0 × 1 5 9 − 3 − 1 23-1330 \times 159-3-1 23−1330×159−3−1。 对于100%的数据 1 ≤ n ≤ 1 e 6 1≤n≤1e6 1≤n≤1e6输入的对称三进制数对应的整数在 int 类型范围内 。 相关知识点平衡三进制 题解 这道题与前一题的要求刚好相反即要求将输入的每个十进制数转换为对称三进制数并输出。 首先我们要知道任意十进制数 n n n 转换为 k k k 进制都遵循一个过程
当前位取数为n%k为继续向后取数即得到更高位的数更新数 n n k n\frac{n}{k} nkn。若 n 0 则转换结束。
例如将十进制数 10 转换为二进制数的过程如下
第1位 n % 2 10 % 2 0 n\%2 10\%2 0 n%210%20更新 n n 2 10 2 5 n\frac{n}{2}\frac{10}{2}5 n2n2105第2位 n % 2 5 % 2 1 n\%2 5\%2 1 n%25%21更新 n n 2 5 2 2 n\frac{n}{2}\frac{5}{2}2 n2n252第3位 n % 2 2 % 2 0 n\%2 2\%2 0 n%22%20更新 n n 2 2 2 1 n\frac{n}{2}\frac{2}{2}1 n2n221第4位 n % 2 1 % 2 1 n\%2 1\%2 1 n%21%21更新 n n 2 1 2 0 n\frac{n}{2}\frac{1}{2}0 n2n210转换结束。
于是得到十进制数 10 对应的二进制数为 1010。
同样地将十进制数转换为三进制数也遵循该算法例如将十进制数 11 转换为三进制数的过程如下
第1位 n % 3 11 % 3 2 n\%3 11\%3 2 n%311%32更新 n n 3 11 3 3 n\frac{n}{3}\frac{11}{3}3 n3n3113第2位 n % 3 3 % 3 0 n\%3 3\%3 0 n%33%30更新 n n 3 3 3 1 n\frac{n}{3}\frac{3}{3}1 n3n331第3位 n % 3 1 % 3 1 n\%3 1\%3 1 n%31%31更新 n n 3 1 3 0 n\frac{n}{3}\frac{1}{3}0 n3n310转换结束。
于是得到十进制数 11 对应的三进制数为 102。
而本题要求转换的 “平衡三进制” 中所有的 “2” 都要求用 “-1” 来替代。这一替换实际上相当于将指定位上的值减少了 1从这个数的整体来看实际上减少了 1 × k p 1×k^p 1×kp为了保证这个数在整体上的值不变就必须向前一位借位即将这个位前的那个值加 1。例如由十进制数 11 得到的三进制数为 102我们从该数的低位向高位扫描首先末尾存在一个 “2”于是将这个数替换为 “-”并将较高位的 “0” 替换为 “1”即得到 11-接继续向后扫描发现整个序列中的数均合法于是得到由十进制数 11 转换的平衡三进制数为 11-。我们可以进行验证 n a 1 k 3 − 1 a 2 k 3 − 2 a 3 k 3 − 3 1 × 3 2 1 × 3 1 ( − 1 ) × 3 0 9 3 − 1 11 na_1 k^{3-1}a_2 k^{3-2}a_3 k^{3-3}1×3^21×3^1(-1)×3^093-111 na1k3−1a2k3−2a3k3−31×321×31(−1)×3093−111
考虑一种情况三进制数 122。当将末位的 “2” 借位后中间位的 “2” 将变成数字 “3”即此时为 13-对中间位而言“3” 已经达到了这个进制下的最大值因此要进位于是此时该数将变为 20-继续向高位扫描发现最高位为 “2”因此需要将其转换为 “-”并向较高位借位故最终得到 1-0-。我们可以进行验算 122 n 1 × 3 2 2 × 3 1 2 × 3 0 9 6 2 17 122n1×3^22×3^12×3^096217 122n1×322×312×3096217 1 − 0 − n 1 × 3 3 ( − 1 ) × 3 2 0 × 3 1 ( − 1 ) × 3 0 17 1-0-n1×3^3(-1)×3^20×3^1(-1)×3^017 1−0−n1×33(−1)×320×31(−1)×3017
可以看出他们最终转换为十进制均为 17。
最后还需要注意一点平衡三进制的负数与正数之间的转换关系。实际上题目也给出了他们之间关系的一些提示“三进制代码的一个特点是对称即相反数的一致性”。对于平衡三进制的数而言它的相反数与其本身的关系如下所有非 0 数据互相相反。例如平衡三进制数 1-01它对应的负数则为 -10- 1 − 01 n 1 × 3 3 ( − 1 ) × 3 2 0 × 3 1 1 × 3 0 27 − 9 0 1 19 1-01n1×3^3(-1)×3^20×3^11×3^027-90119 1−01n1×33(−1)×320×311×3027−90119 − 10 − n ( − 1 ) × 3 3 1 × 3 2 0 × 3 1 ( − 1 ) × 3 0 − 27 9 0 − 1 − 19 -10-n(-1)×3^31×3^20×3^1(-1)×3^0-2790-1-19 −10−n(−1)×331×320×31(−1)×30−2790−1−19
根据上面的分析可以将求解本题的思路整理如下
将输入的十进制数转换为对应的三进制数为便于处理这一阶段将统一使用该数的正数将三进制数转换为平衡三进制数转换规则如下假设当前的三进制数字符串为num 若 num[i] 2则令 num[i] -, num[i1]数字串的索引大小与数的低位到高位对应若 num[i] 3则令 num[i] 0, num[i1]。 根据输入十进制数的正负性对得到的平衡三进制数进行相应处理。
下面给出基于以上思路得到的完整代码已 AC
/*MT2190 三进制计算机2 思路先将数从十进制转换至正常的三进制然后再转换为平衡三进制
*/
#includebits/stdc.h
using namespace std;const int N 55;
int num[N], n, x, flag, cnt;int main( )
{// 取消cin与stdin的同步加速文件读取速度 ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);// 输入数据cinn; while(n--){cinx;memset(num, 0, sizeof(num));flag 1, cnt 0;// 程序将统一处理正数因此定义标记来记录原始输入数据的正负性 if(x0){flag -1;x -x;}if(x 0){coutx\n;continue;} // 将十进制数转换为三进制数 while(x){num[cnt] x%3;x / 3;}// 将三进制数转换为平衡三进制数 for(int i0; icnt; i){if(num[i] 2){// 借位 num[i] -1;num[i1];}else if(num[i] 3){// 进位 num[i] 0;num[i1]; }}// 判断原始三进制数转换为平衡三进制数后是否出现了位增情况 if(num[cnt]) cnt;// 如果原始输入的十进制数为负数则需要对已经算出的平衡三进制数进行反号 if(flag -1) for(int icnt-1; i0; i--)num[i] -num[i];// 输出转换后的平衡三进制数需要进行格式控制所有的-1都输出- for(int icnt-1; i0; i--)if(num[i] -1) cout-;else coutnum[i];cout\n;}return 0;
}END
