青烟绕指柔 - 个人主页动态

2019-12-27 14:25

Given a maze, find a shortest path from start to goal. Input consists serveral test cases. First line of the input contains number of test case T. For each test case the first line contains two integers N , M ( 1 <= N, M <= 100 ). Each of the following N lines contain M characters. Each ch...

0 点赞评论收藏

2019-12-27 14:25

中央美术学院算法工程师

还是畅通工程

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。 INPUT 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。 OUTPUT 对每个测试用例，在1行里输出最小的公路总长度。 Sampl...

0 点赞评论收藏

2019-12-27 14:25

中央美术学院算法工程师

畅通工程再续

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。 INPUT 输入包括多组数据。输入首先包括一个整数T(T <= 200)，代表有T组数据。 每组数据首先是一个整数C(C <= 100...

0 点赞评论收藏

2019-12-27 14:24

已编辑

中央美术学院算法工程师

背包问题

这篇博客主要讲解3个比较简单的背包问题 01背包问题 完全背包问题 多重背包问题 01背包问题 01背包就是有n个物品，你有一个背包可以装体积和为v的物品，同时每个物品都具有价值和体积且只有一件，让你在背包可以装得下的情况下，获得最大的价值。 我们对于每一个物品都有两种决策，装和不装这个物品。 同时我们用 dp[i][j] 表示前 i 个物品，体积为 j 的最大价值。 那么 dp[n][v] 就是我们的答案。 对于每个物品，如果我们不装它，那么dp[i][j] = dp[i-1][j]。因为我们不装就考虑前 i-1个物品就可以了。 相反，如果我们装它，那么dp[i][...

0 点赞评论收藏

2019-12-27 14:24

中央美术学院算法工程师

背包问题拓展

这篇博客主要讲解当背包装满时，使得背包总价值最小的方案。 这个问题主要涉及到两个问题。 背包必须装满。 总价值最小 以前的背包都是体积最大是多少时，总价值多大。并不一定要装满。 那，我们怎么解决呢？ 我们让dp赋值为INF（最大值），dp[0]为0，这样每次状态转移时，都求最小值，我们就可以保证每次的转移都是由dp[0]转移过来，就可以确定是刚好体积为v的时候的最小价值。 #include<bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; int t,E,F,n,p,w,dp[10010...

0 点赞评论收藏

2019-12-27 14:24

已编辑

中央美术学院算法工程师

卡特兰数

卡特兰数是组合数学中，很经典的一类问题，一般可以解决一下问题 n个左括号和n个右括号组成的合法括号序列的数量为 Cat(n); 1,2，3，……，n 经过一个栈，形成的合法出栈序列的数量为 Cat(n); n 个节点构成的不同二叉树的数量为 Cat(n); 在平面直角坐标系上，每一步只能向上走或向右走，从 (0,0) 走到 (n,n) 并且除两个端点外不接触直线 y = x的路线数量为 2Cat(n-1); 给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的合法序列的个数 知道了这么多，那么卡特兰数应该怎么求呢？ ...

0 点赞评论收藏

2019-12-27 14:23

中央美术学院算法工程师

线段树

线段树是一个基于分治思想的二叉树结构，同于再区间上进行信息统计，便于区间修改和区间求值的数据结构。 比如线段树可以： 求任意区间的最大值 求任意区间和 求区间连续最大和 线段树结构一般用数组就可以表示 struct node { int l,r,data;//l,r分别表示当前节点表示的区间[l,r]，data表示这个区间的最大值，根据不同的问题可以不同的表示 }a[10000*4+10]; 若 a[p] 表示当前的节点 a[p*2] 就是这个节点的左节点 a[p*2+1] 就是当前节点的右节点。 下面给出线段树模板： #include<bits/st...

0 点赞评论收藏

2019-12-27 14:23

中央美术学院算法工程师

银河英雄传说

有一个划分为N列的星际战场，各列依次编号为1,2,…,N。 有N艘战舰，也依次编号为1,2,…,N,其中第i号战舰处于第i列。 有T条指令，每条指令格式为以下两种之一： 1、M i j，表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j号战舰所在列的尾部。 2、C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。 现在需要你编写一个程序，处理一系列的指令。 输入格式 第一行包含整数T，表示共有T条指令。 接下来T行，每行一个指令，指令有两种形式：M i j或C i j。 其中M和C为大写字母表示指令类型，i和j为整数，表...

0 点赞评论收藏

2019-12-27 14:22

中央美术学院算法工程师

同余方程

线性同余方程,也就是给定a,b,m,求一个整数x满足a*x≡b(mod m)a*x≡b(mod m),然后因为ax≡b(mod m)ax≡b(mod m)等价于 ax−b是m的倍数,不妨设y为一个负数,那么这个方程可以改写为ax+m*y=b 于是 我们可以通过拓展欧几里得算法求出特解,然后(x%b+b)%b(x%b+b)%b来达到最小值的效果. 如例题： 题目描述 求关于x的同余方程ax≡1(modb)ax≡1(modb)的最小正整数解。 输入格式 输入只有一行，包含两个正整数a,b,用一个空格隔开。 输出格式 输出只有一行,包含一个正整数x，表示最小正整数解。 输入数据保证一定...

0 点赞评论收藏

2019-12-27 14:22

已编辑

中央美术学院算法工程师

计算系数

给定一个多项式(ax+by)k,请求出多项式展开后x^n * y^m项的系数。 输入格式 共一行，包含 5 个整数，分别为 a，b，k，n，m，每两个整数之间用一个空格隔开。 输出格式 输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对10007 取模后的结果。 数据范围 0≤n,m≤k≤1000, n+m=k, 0≤a,b≤106 输入样例： 1 1 3 1 2 输出样例： 3 一道很简单的二项式定理，高中学过的应该都能做出来， 二项式定理：(ax+by)^k 求 x^n * y^m的系数直接用公式就可。（不知道的百度） #include<bits/...

0 点赞评论收藏

2019-12-27 14:22

中央美术学院算法工程师

第k大的数

在许多题目中都会出现寻找第k大的数的类似问题，最简单的做法就是先排序在找位置就可以找到第k大的数，但是排序的做法显然不能满足我们的要求，排序的时间复杂度是O(nlogn)，不够快，我们一般可以用快速排序的思想，用O(n)的时间内就可以找到第k大的数，这里我们只讲解C++ STL的函数nth_element。 先看一下STL template<class _RanIt, class _Pr> inline void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred) template<...

0 点赞评论收藏

2019-12-27 14:21

中央美术学院算法工程师

Mod and Sum

线段树+区间更新+单点更新+区间查询 Mod and Sum 30000(ms) 65535(kb) 给出n个数ai（下标从1开始），系数k，m种操作 操作分为3种： 1 a b :将下标为a的数加上b（1<=a<=n,0<=b<=10^9） 2 a b :将区间[a,b]内每个数对k取模（1<=a,b<=n） 3 a b :询问区间[a,b]内每个数的和（1<=a,b<=n） 输入 第一行一个整数T(T<=10)，表示有T组测试数据 接下来每组测试数据第一行三个整数n,k,m 下面有m组操作。 1<=n,m,k<=10^5 ...

0 点赞评论收藏

2019-12-27 14:21

已编辑

中央美术学院算法工程师

棋盘

题目描述: 有一个m×mm×m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。 任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 11个金币。 另外， 你可以花费 22 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只有当你离开这个位置，走到...

0 点赞评论收藏

2019-12-27 14:20

中央美术学院算法工程师

O(1)快速乘

求两个数相乘并取模，但是乘积超过了long long怎么办呢？ 一般都是快速幂的思想快速乘，时间复杂度为log(n)很快了，这里提供一个更快的O(1)算法 inline long long multi(long long x,long long y,long long mod) { long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod); return tmp<0 ? tmp+mod : tmp; }

0 点赞评论收藏

2019-12-27 14:20

中央美术学院算法工程师

最小环问题（无向图）

什么是最小环？就是所有组成环的环，边权值最小的环，就是最小环。 我们由一道题，进入这个问题。 链接：hdu1599 find the mincost route Time Limit: 1000/2000 MS (Java/Others) ， Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8189 ， Accepted Submission(s): 3100 Problem Description 杭州有N个景区，景区之间有一些双向的路来连接，现在8600想找一条旅游路线，这个路线从A点出发并且最后回到A...

0 点赞评论收藏

关注他的用户也关注了：