整数进制转化的三种情况（根据难度由易到难）： 1、小整数的八进制、十进制、十六进制的相互转换； 2、小整数任意进制之间的相互转换； 3、大整数任意进制相互转换 第一种：小整数8、10、16进制转换 这种情况我们可以直接使用C语言自身的输入输出即可实现： 八进制: %o输入输出, 数字前缀0, 如int 015;（为十进制13） 十进制: %d输入输出, 可不加前缀 十六进制: %x或%X输入输出, 前缀0x或0X （大写X输出的数字中字母为大写,反之为小写,据说较老的编译器不支持大写） 第二种: 整数之间任意进制转换（m进制转换为n进制, 2 <= n,m <= 36） ...

题目考点：归并排序、二维偏序都可以写，也都是模板题 题目大意：给定一个数组，对于数组中的每一个数ai,如果前面有一个数aj大于ai,那么(aj,ai)组成一组逆序对,数组中逆序数的个数为数组的逆序数，求逆序数的数量。 思考：既然有不少同学写了归并排序，我就写一写二维偏序吧！思路很简单，我们把数字一个一个放入另一个数组，对于当前数字，我们只用看已经放入的数字中有多少是大于当前数字的就好。放入和统计个数交给树状数组去维护即可。 插一句：逆序数也是二维偏序的经典问题，即有类似 (ai,aj) 和 (bi,bj), ai < bi , aj < bj的限制。 代码: #in...

题目考点:二维偏序 题目大意：对于二维坐标里面每个点，寻找该点左下角的点的个数（包括同X、同Y轴上面的点） 先说WA思路（还没想好为什会错，后面知道了再来补充）：把所有坐标先按X轴优先排序，再按Y轴优先排序，取两次排序该点最小的位置，于是出现了下图。。。 思路乍一看好像没什么问题，但越想越奇怪，究竟什么原因还不知道。 AC思路：二维偏序，将X轴排序后，离散化Y轴，用树状数组维护每个Y轴的前缀数量即可。 代码： #include<iostream> #include<cstring> #include<algorithm> using na...

题目考点：KMP 题目大意：给定n个字符串，对于每一个字符串，计算出其在n个字符串中出现的次数的乘积 普通（超时）思路：O(n^2)进行KMP for(int i = 0; i < n; i++) { int ans = 1, cnt = 0; for(int j = 0; j < n; j++) { cnt = kmp(r[i], r[j]); ans = ans * cnt % mod; } cout << ans <...

题目考点：STL、栈（或队列），另外注意多组输入 题目大意：给出一系列泡泡，两个小泡泡在一起会变成大泡泡，两个大泡泡在一起会爆炸；求这些泡泡的最终状态。 题目分析: 依次从前往后遍历压入栈即可（入栈时将当前泡泡与栈顶泡泡相比较，两小泡泡变成大泡泡，两大泡泡爆炸），唯一注意点就是两个小泡泡变成大泡泡后，如果前面一个依然是大泡泡，把栈顶弹出即可。 #include<iostream> #include<cstring> #include<algorithm> #include<stack> #include<queue> u...

【T1】出租 签到题，没什么考点，第二个数组找第一个数组的下标就好 #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<queue> #include<set> #include<map> #include<vector> #define ft first #define sd second #define js std::ios::sync_with_stdio(false);cin...

【没有K、L，还是太弱了QAQ】 【T1 考试周破防】 特判周五即可 【T2 咖啡店】 优先花5元，若5元足够，用1元凑零；若不够，剩下的都用1元 【T3 取石子】 题目考点：博弈论基础 题目分析：1、若只有1、2、3个石子，先手必赢； 2、若有4个，先手必输； 3、若有5、6、7个，先手可让状态变成4个，则后手面对4个石子的局面必输； 4、若有8个，先手会让后手面对第三种情况，则自己必输；后面以此类推； 总结：若有((3+1)*n)个石子，先手必输； 代码链接 【T4 分桃子】 若n存在一个倍数在[...

【没有K、L，还是太弱了QAQ】 【T1 考试周破防】 特判周五即可 【T2 咖啡店】 优先花5元，若5元足够，用1元凑零；若不够，剩下的都用1元 【T3 取石子】 题目考点：博弈论基础 题目分析：1、若只有1、2、3个石子，先手必赢； 2、若有4个，先手必输； 3、若有5、6、7个，先手可让状态变成4个，则后手面对4个石子的局面必输； 4、若有8个，先手会让后手面对第三种情况，则自己必输；后面以此类推； 总结：若有((3+1)*n)个石子，先手必输； 代码链接 【T4 分桃子】 若n存在一个倍数在[...

题目考点：因数、枚举 题目大意：将数字拆成因数相乘的形式，问有多少个不同因子。 分析：暴力枚举即可（以为会被大素数卡掉实际上数据不大） 代码： #include<iostream> #include<cstring> #include<algorithm> using namespace std; int t, n; bool primer(int n) { if(n < 2) return false; for(int i = 2; i <= n/i; i++) if(n % i == 0) return ...

题目考点：前缀和、枚举 题目大意：两组糖糖站一排，顺序任意。遍历这一排时，当前糖糖会消除前面与他不同组而且数值比自己小的糖糖，遍历一个糖糖用时1秒。另外有m次施法，第x秒的施法可使前x个糖糖数值+1，求最后没有被消除的糖糖的个数。 核心思想：设j > i, 若a[ j ] + 收益 > a[ i ]，且a[ j ]、a[ i ]不同组，a[ i ]就会被消除。其中“收益”指的是i到j秒时间内施法的次数 代码： #include<iostream> #include<algorithm> #include<cstring> using names...

题目考点：枚举 题目分析：将数字用数量尽量少的01串表示，表示的结果是每一个01串相加后得到原数字即可； 例如样例：103 需要用3个01串表示： 101 1 1 注意：100 1 1 1也可以表示，但是需要花费4个不是最优解 还有就是本题输出的01串不唯一，但最少数量一定唯一 代码： #include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N = 15; int cnt[N]; int...

题目考点：前缀和、位运算 题目大意：找到一个数X，使得X和数列区间内所有数字异或后，得到的值最大。 题目分析：暴力解法O(d * 2e10)，其中d为区间长度、2e10为int正整数范围，用派蒙的脑子想想就知道不可取吧？换个想法来看，统计一下区间内的数字的第i位0的个数和1的个数： 若第i位1的个数大于0的个数，X的第i位应当是0 若第i位1的个数小于0的个数，X的第i位应当是1 若第i位1的个数等于0的个数，X的第i位应当是0（题目中说若有多个解，输出较小者） 例如题目中的第一次询问2 5： 位数: 10-31 9 8 7 6 5 4 3 2 1 78: 0 0 0 1 0...

题目考点：bfs or dfs or dijkstra(蒟蒻优先想到bfs，就先粘上bfs吧，日后有时间补上其他的) 题目大意：走迷宫起点到终点至少需要转90度弯共几次 题目分析：优先队列按照转弯次数从小到大，基于贪心思想得到最优解。在bfs版子的基础上，在结点中多加一个该点是从哪个方向走来的即可。 需要注意的是，我们走过的点不能单纯的标记走过后就不能再走，而是说走过该点之后，如果下次走到该点时，需要的转弯次数更少，或者走到该点时方向不同的话，还是要维护进队列的。（如下方样例） 卡bfs模板样例： 4 A . . . . . . . x x B . . . . . // 该样例从（2,2）或（...

（截止2020-9-3题目有说是多组输入吗？？？？） 题目考点：数位DP（小学奥数分情况讨论？） 题目大意：统计0 ~ n中的所有数字中，0到9在每个数字的每一位上出现的次数。 题目分析： 1、举例分析： 统计数字2在（0 ~ n=324）的个位上出现的次数，个位有（32 * 1+1）次，在十位上出现（3 * 10+5）次，在百位上出现（0 * 100+100）次；所以数字2共出现（33+35+100=168）次； 如何计算？ 我们在计算2在（0 ~ n=324）的十位的时候，可以看到百位上是3，即324之前出现了02X、12X、22X，共30个，然后有320、321、322、323、32...