Excelsior_kereo-CSDN博客

原创数论

int euler_phi(int n){ int ans=n; int m=sqrt(n+0.5); for(int i=2;i<=m;i++) if(n % i == 0){ ans=ans/i*(i-1); while( n % i == 0) n/=i; } if(n>1) ans=ans/n*(n-1); //针对

2014-07-17 17:25:32 933

原创 Random Forest & GBDT & XGBOOST & LightGBM面试问题整理

一.知识点二.特征重要性评估    基于树的集成算法有一个很好的特性，就是模型训练结束后可以输出模型所使用的特征的相对重要性，便于理解哪些因素是对预测有关键影响，有效筛选特征。Random Forest袋外数据错误率评估由于RF采用bootstrapping有放回采样, 一个样本不被采样到的概率为 limm→∞(1−1m)...

2018-05-08 10:36:36 1869

原创 Boosting & Bagging & Stacking整理

一. 知识点 Bias-Variance Tradeoffbias-variance是分析boosting和bagging的一个重要角度，首先讲解下Bias-Variance Tradeoff.假设training/test数据集服从相似的分布，即 yi=f(xi)+ϵi,yi=f(xi)+ϵi,y_i = f(x_i) + \epsilon_i, 其中 noise ϵiϵ...

2018-05-07 12:38:47 383 3

原创 LA7147 World Cup 数学

题目链接题意：给定样例数T 给定球队数n，晋级球队数m 给定A,B,C(分别代表获胜、平局、失利获得的分数) 分别求不能晋级的可获得的最大得分，能晋级的可获得的最小得分。思路：考虑不能晋级的可获得的最大分的情况，(1) B>=max(A,C) 那么Max=(n-1)*B; (2) B开后面的队伍,即Ma

2015-04-30 22:30:19 815

原创 codeforces535D Tavas and Malekas kmp

题目链接题意：给定字符串s的长度n, x1, x2, ...xk中选取m个位置给定字符串p y1, y2, ..., ym x1, x2, ...xk中每个xi满足sxisxi + 1...sxi + |p| - 1 = p 求满足条件的字符串有多少种，对10^9+7取

2015-04-20 14:00:02 850

原创 poj2503 Babelfish BKDRhash+链式hash

题目链接题意：给定字符串以及对应的字符串，再给字符串找到对应的字符串，不存在输出"eh"。思路：造模板。/********************************************************* file name: poj2503.cpp author : kereo create time: 2015年04月12日星期日 17时13分1

2015-04-12 20:36:31 585

原创 spoj3267 D-query 主席树(可持久化线段树)

题目链接题意：给n个数，m次查询,求[l,r]之间不重复数的个数。思路：主席树。用一个map记录每个值在当前操作下最新的位置，从前往后插入主席树。对于查询[l,r]，窝们在root[ l ]下查询在r之前的不重复数的个数。详见代码：/********************************************************* file name: spoj3267

2015-04-04 15:29:34 1338

原创 spoj12943 Counting dp

题目链接

2015-02-24 18:39:02 764

原创 poj 1147 Binary codes BWT压缩算法

题意：一个长度为N的01序列，会有N个不同的轮换（当然，字符相同，其中也可能会有相同的），将这N个不同轮换按字典序排序，取排序后的每个轮换的最后一排，组成一个序列。题中给出压缩后的序列，求原始序列，输出的是字典序最小的那个序列。思路：这题基于一个性质：在已经排序好的矩阵中，对于首位相同的两行，经过左移一位的操作后，形成的新的两行的先后次序不发生改变。即:设i行在j行前面，i行左移一位变

2015-02-21 18:36:16 900

原创 hdu2475 Box splay || 动态树

题意：一开始给定n个盒子的摆的嵌套关系。有两种操作，1.MOVE x y：把编号x的箱子及其包含的箱子放进编号为y的箱子；2.QUERY x :查询编号x的箱子所在的最靠外的箱子。思路：将全部的树逐个dfs，这样对于每一棵树都可以得到一个括号序列，对于MOVE操作，我们将那个根所在的左右括号的一整段取出，连接到新的结点的左括号右边，这么做我们可以保证得到的一定也是一个括号序

2015-02-18 17:30:40 708

原创 hdu3081 Marriage Match II 二分+最大流

题意：n个男孩n个女孩，女孩选男孩，每个女孩都要选到不同的人k对女孩有相同选择标准，女孩每轮都选择没选过的男孩，问总共能选几轮。思路：女孩1..n，男孩n+1..2*n编号由女孩到男孩建容量为1的边起点st=2*n+1，到1..n建边；n+1..2*n到终点ed=2*n+2建边二分搜索最大容量即为答案。详见代码：/****************************************

2015-02-17 23:41:13 789

原创 hdu 3998 Sequence LIS+最大流

题意：给定一个序列，求最长上升子序长度以及有多少组，每个元素只能用一次。思路：先求LIS,记为num，求出以每个点为末尾的最长子序列长度。窝们将每个点点拆成i和i',i --> i' 容量为1,源点连接d[ i ]=1的点，容量为1，汇点连接d[ i ]=num的点，容量为1。对于j i 连一条容量为1的边，跑最大流即可。详见代码：/**********************

2015-02-17 17:51:38 718

原创 bzoj 2301 Problem b 莫比乌斯反演+容斥

题意：对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数思路：在hdu1695的基础上加上容斥，即:ans=solve(b/k,d/k)-solve((a-1)/k,d/k)-solve((c-1)/k,b/k)+solve((a-1)/k,(c-1)/k),详见代码：/************

2015-02-17 11:21:52 1731 2

原创 hdu 1853 Cyclic Tour 最小费用最大流

题意：一个有向图，现在问将图中的每一个点都划分到一个环中的最少代价(边权和)。思路：拆点，建二分图，跑最小费用最大流即可。若最大流为n，则说明是最大匹配为n，所有点都参与，每个点的入度和出度又是1，所以就是环。/********************************************************* file name: hdu1853.cpp autho

2015-02-16 18:36:21 664

原创 hdu 4389 X mod f(x) 数位dp

题意：给定函数f(x)为x的数位和，求[A,B]中的x能被f(x)整除的个数。思路：数位dp。设dp[pos][i][j][k]表示当前考虑pos位,考虑对i的整除,之前的数位和为j，之前对i的余数为k，与之后(pos+1)位组合构成满足条件的数的个数。详见代码：/**************************************************

2015-02-13 12:24:21 1011

原创 hdu 1695 GCD 欧拉函数+容斥 ||莫比乌斯反演

题意：给定a,b,c,d,k x属于[1 , c]，y属于[1 , d]，求满足gcd(x,y)=k的对数。其中和算相同。思路：不妨设c 那么假如yc/k，就只能从[ c/k+1 ， d ]枚举，然后利用容斥。详见代码：/*******************************************************

2015-02-11 19:17:48 1502

原创 hdu 4406 GPA 最大费用最大流

题意：给定n,k,m分别代表天数，每天上的课，以及科目数。给定每门课的学分，已经基础分数。给定n天每天有哪些课能学。求如何安排复习，使得GPA尽可能大且没有挂科，算出GPA。思路：最大费用最大流。定义函数f(score,credit)=credit×(4-3.0/1600×(100-score)^2）。每一

2015-02-11 16:37:34 862

原创 poj 2001 Shortest Prefixes trie

题意：给一堆字符串，输出对应字符串能区别于别的字符串的缩写。思路：记录下每个点经过的次数，那么对每个字符串，直到找到p->cnt=1为止。详见代码：/********************************************************* file name: poj2001.cpp author : kereo create time: 2015年

2015-02-11 12:24:01 754

原创 hdu 4507 吉哥系列故事――恨7不成妻数位dp

题意：中文题。思路：设dp[pos][i][j]表示当前考虑pos位，之前的数位和对7的余数为i，之前的数值对7的余数为j，与之后的(pos+1)位组合满足条件的状态(包括之后(pos+1)位满足的个数，后缀和sum,后缀平方和)，详见代码：/********************************************************* file name: h

2015-02-11 11:42:35 836

原创 poj 3630 Phone List trie

题意：判断是否有某字符串是别的字符串的前缀。是则输出NO，不然输出YES。思路：把板子写成结构体版的。。详见代码：/********************************************************* file name: poj3630.cpp author : kereo create time: 2015年02月09日星期一 22时22分

2015-02-09 23:02:22 596

原创 rockethon2015 G2题 Inversions problem 概率dp

题意：给定n,k。k次操作，每次等概率将一个区间翻转，问最后逆序数对的期望。思路：设dp[i][j]表示a[i]在a[j]前面的概率。每次枚举翻转的区间，更新dp[i][j]，复杂度为O(n^4×k)。详见代码：/********************************************************* file name: G.cpp author : k

2015-02-09 21:16:23 922

原创 rockethon2015 C题 Second price auction 概率dp

题意：n个人去竞拍一件商品，下面给出n个区间表示每个人出的价是区间中随机的一个数（概率均等)则第一名需要付的钱是第二名的竞拍价格（允许并列第一名）求支付的钱的期望。思路：参考九野巨的博客：http://blog.csdn.net/qq574857122/article/details/43640187/******************************************

2015-02-09 21:10:34 768

原创 rockethon2015 B题 Permutations 规律+构造

题意：求使所给公式值最大的第m个排列。思路：假设已知使f(p)最大的n-1的排列，那么对于使f(p)最大的n的排列，把n放在(n-1)两边均可。因为n放在(n-1)两边，增值为1+2+...+n,而如果不放在两边，(n-1)到n之间的值n摆放位置，对于i,如果m那么i摆在pos，不然放到可放到的最后面,即last位置。因为接下来(i+1)一定在i左边，而之后比(i+1)大也一定在i左边

2015-02-09 20:52:39 708

原创 hdu 3565 Bi-peak Number 数位dp

题意：各位数字先增后减的数称为峰值数（位数大于等3且第一位非零），然后两个峰值数连在一起是一个Bi-peak数，求两个数之间Bi-peak数的各位数字之和的最大值。思路：设dp[pos][i][j]表示当前考虑pos位，之前的数位为i，状态为j,与之后(pos+1)位组合构成Bi-peak number,这(pos+1)位数位和的最大值。状态总共有7种,st=0,初始状态；st=1，恰

2015-02-09 20:40:29 754

原创 hdu 4067 Random Maze 最小费用最大流

题意：给出n个点，m条边，入口s和出口t，对于每条边有两个值a，b，如果保留这条边需要花费；否则，移除这条边需要花费b。题目要求用最小费用构造一个有向图满足以下条件： 1.只有一个入口和出口 2.所有路都是唯一方向 3.对于入口s，它的出度 = 它的入度 + 1

2015-02-09 15:50:24 830

原创 zoj 3820 Building Fire Stations The 2014 ACM-ICPC Asia Mudanjiang Regional Contest B题树的直径

题意：n个点的树，给出n-1条边，每条边长都是1，两个点建立防火站，使得其他点到防火站的最远距离最短。思路：先求出树的直径，直径上的所有点都存到一个数组里。如果直径是奇数，把中间的那条边删去；如果是偶数，把中间的点，分到两边的子树。对两个子树分别求树直径的中点即可。详见代码：/*******************************************************

2015-02-08 18:31:08 720

原创 2014-2015 CT S02E10 D题 Coin Table dp

题意：给定一个由"C"和"."构成的n×n图给定查询次数m 每次查询给出r1,c1,r2,c2一个矩形求从(1,1)到(n,n)不能走到所给矩形中，问最多可获得多少"C",以及获得这么多"C"的方法数思路：/***********************************************

2015-02-08 12:46:34 586

原创 2014-2015 CT S02E10 C题 Coin Graph 构造+贪心

题意：给定一个数s,构造一个无向图，使得任意两点的最短路径和为s。思路：二分找到n，满足n×(n-1)/2假设现在有n个点，我们按照逆时针方向(顺时针也行)排序编号,那么我们间隔删去不相邻点的的边，比如5个点，我们删去1--3,1--4,...,1--n-2,1---n-1,保留2，删3--5,3--6,...3--n-2,3----n-1,保留4，删5--7,5--8,...,5--

2015-02-08 12:20:21 733

原创 LA 6534 Join two kingdoms 树的直径+twopoint

题意：思路：/********************************************************* file name: LA6534.cpp author : kereo create time: 2015年02月07日星期六 17时55分24秒************************************************

2015-02-07 22:52:28 594

原创 LA 6533 Inverting Huffman 构造+贪心

题意：给定哈夫曼树的n个叶子节点距离根的距离，求文本至少需要多少个字符可以建出这样的哈夫曼树思路：策略：对于第i层的叶子节点，赋值为i+1层的节点中权值最大的点这种情况下字符数最少。详见代码：/********************************************************* file name: LA6533.cpp author : kereo

2015-02-07 22:47:01 769

原创 LA 6530 Football 贪心

题意：给出一系列比赛和结果，可以花钱买任意一场比赛或几场比赛的进球，问买完后最多能得多少分。胜3分，平1分，负0分。思路：贪心。策略：1.赢的直接+3 2.其他的按净胜球升序排序，能买赢就买赢，不然买平。详见代码：/********************************************************* file name: LA6530.cpp a

2015-02-06 23:30:43 594

原创 LA 6531 Go up the Ultras 单调栈+RMQ

题意：已经懒得吐槽了。。有N个山峰，(N它高的山峰都会经过一个最低值（山谷），d代表是h减去这些最低值中的最大值的差（如果不存在比它高的山峰那么d就是它本身的高度），问有多少山峰的d>=150000米。思路：利用单调栈维护每个峰左边第一个比它高的峰的位置l，右边第一个比它高的峰的位置r，对于r，我们从前向后维护一个单调减序列，如果当前考虑的点i比栈顶的元素高度高，那么弹出栈顶元素，

2015-02-06 22:12:36 773

原创 LA 6527 Counting ones 数位dp

题意：给两个数A，B，求二进制表示下，区间[A,B]之前总共有多少个1。思路：设dp[pos][ cnt ]为当前考虑pos位，之前的数中已经有cnt个1的时候，（pos+1）个数位与之前数位组成的含有1的个数。详见代码：/********************************************************* file name: LA6527.cp

2015-02-06 16:15:52 862

原创 LA 6529 Eleven dp

题意：给一个数字串，可以调换数字，问有多少种组合可以让组成的数能被11整除。思路：窝们观察到1%11=1, 10%11=10,100%11=1,1000%11=10，以此类推。。窝们将一偶一奇看作一对，这一对组成对11的余数×100对11的余数(也就是1)，所以实质还是这一对对11的余数，那么奇偶数位的和就可以了。我们可以设奇数位的和为x，偶数位的和为y，则(x+10y)%11的值为0

2015-02-05 22:40:50 733

原创 codeforces 510E Fox And Dinner 奇偶建图+最大流

题意：n个fox，年龄为a[i]。现在要将n个fox分配入座，保证与相邻数的和为质数。一桌至少三个fox。输出要分几桌，每桌几个fox，按顺序输出每桌坐的fox的id思路：我们按奇偶将n个fox分成2类，如果左边的a[i]+右边的a[j]和为质数，那么建i->j建容量为1的边，超级起点0连a[i]为奇数的i，从0->i建容量为2的

2015-02-04 17:12:58 997

原创 codeforces510D Fox And Jumping gcd

题意：n张卡，可跳跃的长度l[i],以及花费c[i]起始点为0，问如果选卡使得可以每个点都能跳到，最小的花费是多少。思路：本质就是选取一些卡，选择卡长度的gcd为1，且花费最小。那么我们用map映射gcd值以及其对应的最小花费。最后输出mp[1]即可。(ps:可能有卡片长度相同)详见代码：/********************************************

2015-02-04 16:59:36 853

原创 codeforces 510C Fox And Names 拓扑

题意：n个姓名，按照某种“字典序”。问如果存在这样的字典序，输出字典序'a'到‘z’26个字母的顺序。思路：拓扑排序。对于str[i]和str[i+1]如果在位置k出现不同，那么x=str[i][k]-'a'+1,y=str[i+1][k]-'a'+1,从x->y连一条边，y的入度in[y]++。然后拓扑排序，如果形成环，就说明不行，不然依次输出对应字符。（ps：len1为st

2015-02-04 16:36:53 917

原创 hdu 5093 Battle ships 二分匹配

题意：在n×m的方格中，‘#’代表iceberg，'*'代表ocean，‘o’代表floating ice。战舰只能放在ocean上，在同一行或者同一列不能放两个战舰除非它们中间有iceberg，求最多能放多少战舰。思路：二分匹配。每行中连续为'*'的作为X集合中一个点，同样，将每列中连续为'*'的点作为Y集合中的一个点。对原图中每个'*'，将其对应的X集合和Y集合中的标号建边，便形成

2015-02-02 15:42:04 890

原创 codeforces 235B Let's Play Osu! 概率dp

题意：给定n表示有n个格子，下面每个格子为O的概率是多少。对于一段连续 x 个O的价值就是 x^2 ;求获得的价值的期望是多少。思路：n^2=n×(n-1)+n，设ai为第i段连续O的长度，∑ai^2 = ∑[ ai+ ai*(ai-1) ] = ∑ ai*(ai-1) + ∑ai = ∑ C(ai, 2)*2 + ∑ai，那么问题可以转化为求长度大于1的连续段数*2+O的个数的总期望。

2015-02-02 13:27:01 1035

原创 codeforces 167B Wizards and Huge Prize 概率dp

题意：给定n个对手，至少要击败其中 l 个人，现在有口袋容量为 k下面n个数字表示击败这个人的概率下面n个数字（若为-1表示击败这个人可以获得一个金币，若>0则表示可以增加口袋容量为这个数字）求：至少击败其中的l个人，且获得的总口袋容量 >= 获得的金币个数的概率是多少。（即任何时候金币都不能放不下）思路：设dp[i][j][k]表示当前前i个人已经战胜j个人，且剩余口袋容量

2015-02-01 22:18:13 916

空空如也

空空如也