problem专题
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）
这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
uva 10025 The ? 1 ? 2 ? ... ? n = k problem（数学）
题意是 ? 1 ? 2 ? ... ? n = k 式子中给k，? 处可以填 + 也可以填 - ，问最小满足条件的n。 e.g k = 12 - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明，令 S（n） = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n，搜出当 S（n） >=
11991 - Easy Problem from Rujia Liu?
题意： 输入一串整型数列，再输入两个数k，v，输出第k个v的序号。不存在则输出0，如第一个样例 8 41 3 2 2 4 3 2 11 3 //第1个3，序号为2，输出22 4 //第2个4，不存在，输出03 2 //第3个2，序号为7，输出74 2 思路： struct num {
HDU 1016 Prime Ring Problem （深搜）
OJ题目 ： click here ~~ 大概题意：n个数，形成一个环，使得相邻两个数的和为素数。以1开始，按字典序输出序列。 很简单的深搜。 AC_CODE int n;int visit[22];int num[22];int len;bool Is_prime(int x){for(int i = 2;i*i <= x;i++)if(x%i == 0) return
LVM 'Can’t open /dev/sdb1 exclusively. Mounted filesystem?' Problem
在将几块盘做LVM时，遇到一个之前都没遇到过的问题: root@ubuntu:~# pvcreate /dev/sdc1Can't open /dev/sdc1 exclusively. Mounted filesystem? 首先第一反应就是查看这个分区是否已经在使用了，但是没有。 查看硬盘的一些信息: root@ubuntu:~# cat /proc/partitionsmajo
【HDU】3861 The King’s Problem 强连通缩点+有向图最小路径覆盖
传送门：【HDU】3861 The King’s Problem 题目分析：首先强连通缩点，因为形成一个环的王国肯定在一条路径中，这样才能保证拆的少。 然后缩点后就是DAG图了，由于题目要求的是最小路径覆盖，那么二分匹配即可。 代码如下： #include <cstdio>#include <cstring>#include <algorithm>#includ
【ZOJ】3362 Beer Problem 最小费用流
传送门：【ZOJ】3362 Beer Problem 题目分析：这道题本来应该很快就AC的，但是！因为我以前犯的一个致命错误导致我这题一天了到现在才调出来！唉。。失策。。貌似给的模板也有这个错误。。。马上就去改。。但是这个错误竟然还能过掉那么多的题。。害我还要一题一题的改回去。。 本题就是赤裸裸的最小费用流。 新建汇点t（源点即1），将所有的n-1个城市和汇点建边，容量为无穷大，
【HDU】4975 A simple Gaussian elimination problem. 网络流——行列建边
传送门：【HDU】4975 A simple Gaussian elimination problem. 题目分析：这题和某一场的多校的题目出奇的像啊！重要的是我一开始还以为不可能会出一样的题。。结果迟迟没写啊。。。后来觉得实在想不出什么对策了，虽然觉得给的是0~9很特殊，但是利用不起来，果断还是敲了网络流了。。首先建图很简单，源点向行建边，容量为行和，列向汇点建边，容量为列和，然后所有的
Splay树（区间更新）—— POJ 3468 A Simple Problem with Integers
对应POJ 题目：点击打开链接 A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072KTotal Submissions: 72765 Accepted: 22465Case Time Limit: 2000MS Description You have N integers, A1
系统设计：Top K Problem (Heavy Hitters)
System Design Interview - Top K Problem (Heavy Hitters) https://www.youtube.com/watch?v=kx-XDoPjoHw&t=1068s
P problem、NP problem、NP-complete problem、NP-hard problem是什么
时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当程序所处理的问题规模扩大后，程序需要的时间长度对应增长得有多快。 一、多项式时间（Polynomial time） 多项式复杂度 容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者。 像等，我们把它叫做多项式级复杂度，因为它的规模n出现在底数的位置； 非多项式级的复杂度 另一种像是等，它
leetcode --- 2 sum , 3 sum , 4 sum , k sum problem
K Sum Problem Leetcode上有2 sum problem，3 sum problem， 4 sum problem，K sum problem等问题，为方便讨论，从最简单的2 sum入手，讨论到更一般的K sum problem，这类问题一般具有这样的形式： 给定一个n长度的数组array和一个target，在数组中寻找k个数，使这k个数的和等于target，并且
【贪心】codeforces30D King‘s problem
直接上中文题面 King's Problem? 时间限制：3.0s 内存限制：256.0MB Special Judge 问题描述 每一个真正的国王在他的一生中，一定会征服世界，取得 codeforces 的世界冠军，在射击场赢得粉色的熊猫（= =），并游历整个王国。 国王 Copa 已经完成了前三件事。现在他只需要游历完整个王国了。他的王国在一个无限大的笛卡尔坐标系上，每
Codeforces Round #328 (Div. 2)Problem A. PawnChess（模拟）
题目连接 题意：一个8*8的棋盘，A，B两个人下棋，每次是A先手，A希望最早把W移到第一排，B希望能最早把B移到最后一行，每次只能移动一步，且只能移到空的位置，问谁赢。 解法：直接模拟 #include<bits/stdc++.h>using namespace std;#define LL long long#define pb push_back#define P pair<in
HDU 3861 The King’s Problem
http://acm.hdu.edu.cn/showproblem.php?pid=3861 The King’s Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1828 Accepted Submission
HDU 5328 Problem Killer
。。。。 Problem Killer Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 252 Accepted Submission(s): 97 Problem Description You are a "Prob
UESTC 1712 Easy Problem With Numbers 除法对和数取模，分解，线段树
附上神牛原版思路： 如果这个题只有乘法，那么你肯定会做吧？线段树更新区间查找区间。 那么有除法呢？当一个数x和m互质的时候，除以x可以改为乘以x的逆元。（至于互质的数求逆元用扩展欧几里德，这个网上可以随便找到） 但是这题并不能保证除的数与m互质吧？什么时候x与m不互质呢？就是x与m含有公因子吧？ 那么我们一开始就把m分解，分解出来m有p1,p2,p3,p4...pn等一
F - Problem where +s Separate Digits
算第三遍了。。都没有想透 。。 而且这题的解法非常多样。。有正序 逆序 递推的方式也非常多。 下面是找到的一个感觉相对比较简洁的。（核心代码） 有兴趣再看吧。。先pass了。 //上面都是mod的模版部分 省略掉 下面才是核心代码Z base[N], p[N];void solve() {string s;cin >> s;n = s.size();base[0] = 1;p[0] = 1
hdu5371（2015多校7）--Hotaru's problem（Manacher+线段树）
题目链接：点击打开链接 题目大意：定义一个子串，子串由三部分组成，其中第一部分和第三部分相同，第一部分和第二部分对称。给出一个n个数的序列，问序列中最长的符合要求的子串的长度。 例如2 3 4 4 3 2 2 3 4，第一部分2 3 4，第二部分4 3 2 ，第三部分2 3 4，符合条件。 题目的大意可以转化成求两个回文串，其中第一个回文串的右侧和第二个回文串的左侧重叠。 首先使用Mana
HDU 1086 You can Solve a Geometry Problem too(判断线段相交）
题目地址：HDU 1086 就这么一道仅仅判断线段相交的题目写了2k多B的代码。。是不是有点浪费。。。但是我觉得似乎哪里也优化不了了。。。。 判断线段相交就是利用的叉积。假如现在两条线段分别是L1和L2，先求L1和L2两个端点与L1的某个端点的向量的叉积，如果这两个的叉积的乘积小于0的话，说明L1在是在L2两个端点之间的，但此时并不保证一定相交。此时需要用同样的方法去判断L2是否在L1的两个端
Check Android SDK has encountered a problem
打开android项目中布局文件xml文件时报错： 原因可能是前面的xml文件有错误，检查并保存就好了。--这是我自己做的时候烦的错 网上的一些解决办法： 发android项目过程中，设计完layout，去acitivity中findViewById,R下没有VIEW的id，重新打开layout xml文件，就报错误： "Check Android SDK" has encoun
POJ 3468 A Simple Problem with Integers 树状数组 区间修改 区间查询
题目链接点这儿 给你一个数列，最多10W次操作，要么区间统一加上某个值，要么查询某个区间的和。 第一反应肯定是线段树，但是呢，这个能不能用树状数组做呢？ 如果是单点修改，区间查询，我们直接在原数列上进行树状数组的操作。 如果是区间修改，单点查询。由于树状数组每次update一个单点x之后，会对n>x的getsum(n)（或者说树状数组的Query(n)操作）都有影
【HDU】1402 A * B Problem Plus 【FFT】
传送门：【HDU】1402 A * B Problem Plus 题目分析： 这就是大数乘法题，问两个大数相乘的结果，由于O(n2)的算法复杂度太大，所以我们用FFT来优化他。关于FFT网上资料很多，我就不多说啦。 这是我做的第一道FFT，FFT是看算法导论学来的，前面几篇文章是从july大神那边转载来的，感觉都讲的很不错，简单易懂~ // whn6325689//
uva10026 - Shoemaker's Problem（贪心）
题目：10026 - Shoemaker's Problem 题目大意：有个鞋匠在同一天接到了一堆的生意。可是他每天只能做一双鞋，给出做每双鞋需要的时间和推辞做鞋的赔偿。问怎样合理的分配才能使得赔偿最小。 解题思路：鞋子编号 要花的时间 需要的赔偿（每天） 1 1
UVA11991Easy Problem from Rujia Liu?（map + vector)
题目：UVA11991Easy Problem from Rujia Liu?（map + vector) 题目大意：给你N个数字，这些数字可能有重复，然后M个查询，问第k个V的下标是，如果不存在这样的数字输出0。 解题思路：用map来将每个数字和下标做一一映射，但是因为相同数字会出现多次，所以需要一个数组，并且长度不一定，所以用vector。 代码： #includ
第八届湘潭大学程序设计比赛 Problem C Cipher Lock
Cipher Lock Accepted : 33 Submit : 130Time Limit : 2500 MS Memory Limit : 65536 KB 题目描述 守护着神秘宝藏One Piece的是一把非常神秘的密码锁，这个密码锁有n排滚轮，每个滚轮有m个格子，刻着0，1两种数字。作为一把神秘的密码锁，开锁的方式却非常的简单，只要向左或向右转动滚轮使某一列的数字全