APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
OI
OI

#NOIP提高组#模板整理

高精度运算 高精度加法: int main() { scanf("%s%s",&a1,&b1); if(a1[0] == '0' && b1[0] == '0') { cout << "0"; return 0; } for(int i = 0;i < strlen(a1);++i) a[strlen(a1) - i - 1] = a1[i] - '0'; for(i…

2018年11月4日 1条评论 2280点热度 2人点赞 神楽坂 みずき 阅读全文
OI

HDU 1806 Frequent values(区间RMQ问题)题解

洛谷:https://www.luogu.org/problemnew/show/U50167 Description 给定一个非降序的由 n 个整数构成的序列以及 q 个由整数i 和 j 构成的询问。对于每一个询问,输出在 a[i],a[i+1], ... ,a[j-1],a[j]里面出现次数最多的那个(些)整数出现的次数。 Input 第一行包含两个整数, n 和 q。第二行包括 n 个整数 a[1],a[2], ... ,a[n],由空格分开。以下 q 行每一行包括一个询问,一个询问由两个整数 i 和 j 构…

2018年11月3日 0条评论 2168点热度 0人点赞 神楽坂 みずき 阅读全文
OI

POJ 3233 Matrix Power Series(矩阵快速幂+二分)题解

洛谷:https://www.luogu.org/problemnew/show/U50124 Description 给定一个 n*n 的矩阵 A 以及一个正整数 k,计算\(S = A^1 + A^2 + A^3+...+A^k\) Input 输入只有一组测试数据。输入的第一行包括三个正整数 n, k, m。接下来的 n 行每行包括 n 个非负整数,按照行优先的顺序输入矩阵 A 的元素。 Output 输出 S 中每一个元素 mod(%)m 以后的值 Sample Input 2 2 4 0 1 1 1 Sa…

2018年11月3日 0条评论 2280点热度 0人点赞 神楽坂 みずき 阅读全文
OI

动态规划(DP)方法学习

动态规划 维基百科上给出的动态规划的定义是:动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。 动态规划和递推有些相似,而递推求出的是数据,所以只是针对数据进…

2018年10月19日 0条评论 2193点热度 1人点赞 神楽坂 みずき 阅读全文
OI

#C/C++#二分图匹配匈牙利算法模板(邻接表/邻接矩阵)

洛谷:P3386 题目背景 二分图 题目描述 给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数 输入输出格式 输入格式: 第一行,n,m,e 第二至e+1行,每行两个正整数u,v,表示u,v有一条连边 输出格式: 共一行,二分图最大匹配 输入输出样例 输入样例#1: 1 1 1 1 1 输出样例#1: 1 邻接矩阵(老码风) #include <cstdio> #include <iostream> #include <algorithm> #include &…

2018年10月17日 0条评论 2651点热度 2人点赞 神楽坂 みずき 阅读全文
OI

#笔记#二进制与位运算

二进制 计算机是使用二进制进行存储和计算的。二进制运算遵循的规则是“进二”。 原码,指一个二进制数左边加上符号位后所得到的码,且当二进制数大于0时,符号位为0;二进制数小于0时,符号位为1;二进制数等于0时,符号位可以为0或1。 反码:正数的反码与其原码相同;负数的反码是对其原码逐位取反,但符号位除外。 补码:正数的补码与原码相同,负数的补码是其对应正数二进制所有位取反后加1。 在计算机中通常使用补码进行储存。 位运算 左移右移运算: 在二进制运算中,这东西叫做“左移”“右移”运算,顾名思义,就是将一个二进制数向左…

2018年10月17日 0条评论 1999点热度 2人点赞 神楽坂 みずき 阅读全文
OI

#笔记#进制转换

二进制&十进制 1、二进制—>十进制:二进制数按权展开、相加即得十进制数。 \(10110\) -> \(0*{2^0} + 1*{2^1} + 1*{2^2} + 0*{2^3} + 1*{2^4}\) 所以答案是\({\rm{22}}\) 2、十进制—>二进制:十进制数除2取余法,即十进制数除2,余数为权位上的数,得到的商值继续除2,依此步骤继续向下运算直到商为0为止。 二进制&它进制 1、二进制—>八进制:3位二进制数按权展开相加得到1位八进制数。(注意事项,3位二进制…

2018年10月13日 0条评论 2034点热度 1人点赞 神楽坂 みずき 阅读全文
OI

#C/C++#数据结构:树状数组/线段树/并查集/树链剖分

数据结构 树状数组,堆 线段树  单点,区间 动态开结点 并查集 加了路径压缩之后不能随便撤销 使用启发式合并复杂度是 O(n log n),按秩合并是 O(nα(n))。 平衡树 treap 比较好写 splay 比较难写, noip 也不会考这么高级的东西 只能说 (开了 O2 的)set 秒杀一切 dfs 序与树链剖分 非传统方法 点事件 分块 cdq 分治 树状数组 具体思想就是要维护一个序列 a 的前缀和,我们可以维护一个辅助序列 s,使得 si = ∑j2(i-lowbit(i);i] aj,然后我们发…

2018年10月3日 0条评论 2121点热度 0人点赞 神楽坂 みずき 阅读全文
OI

#C/C++#数据结构:一维树状数组/二维树状数组模板

模板 #define lowbit(x) x & -x //1D void add(int x,int t) { while(x <= n) { v[x] += t; x += lowbit(x); } } int query(int x) { int res = 0; while(x) { res += v[x]; x -= lowbit(x); } return res; } //2D n * m void add(int x,int y,int t) { while(x <= n) { f…

2018年10月2日 0条评论 2123点热度 0人点赞 神楽坂 みずき 阅读全文
OI

#C/C++#DFS深度优先搜索/剪枝/迭代加深搜索/A*搜索

搜索问题 搜索是玄学,最稳定的应用是写暴力 or 骗分。 一个搜索问题的基本模型有以下几个要素: 状态:表示当前搜索到的局面。一般用x,y,z表示。一开始我们处于初始状态。 代价:表示对当前状态好坏的一个衡量。一般用f(x),g(x)表示,指代状态代价。 扩展(转移):表示从当前状态出发,我们再进行一步搜索的过程。在扩展过程结束以后,我们可能会转移到若干个新的状态。一步转移也会带来代价,称为转移代价。 搜索问题可以分为两类:可行性搜索与最优性搜索。 在可行性搜索问题当中,目标是搜索到某些给定状态,问是否能够从初始状…

2018年10月1日 0条评论 2883点热度 3人点赞 神楽坂 みずき 阅读全文
1234

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
上岸 Star Divine 现代前端工程师发展方向不完全指北 站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话
来自国外的优秀远控Darktrack Alien推荐 #笔记#二进制与位运算 KikoPlay:开源的全功能弹幕播放器(动漫推荐) 家中组无线网络全覆盖 POJ 3233 Matrix Power Series(矩阵快速幂+二分)题解 现代前端工程师发展方向不完全指北
标签聚合
动漫 日常 C++ C/C++ HTML 洛谷 ST OI
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share
友情链接
  • APTX部落
  • 翰林的小站

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang