Pikachu_杨京 - 个人主页动态 - 牛客网

发布(44) 评论刷题

2019-07-24 17:51

已编辑

长沙学院 Java

The 14-th BIT Campus Programming Contest L. 旅行的意义

旅行的意义 参考于：xls tql d[i]表示以i为起点的期望天数， 对于节点u，首先需要在u玩一天，第二天我可以有1 / (son + 1)概率去u的某一个子节点，也有1 / (son + 1)概率待在u，d[u] = 1，d[u] = d[u] + （d[vi] + 1）* 1 / (son + 1) + 1 / (son + 1)，坐车需要一天所以是d[vi] + 1，如果第二天我还在u，那么第三天我必须要走了，去u的某一个子节点，概率为1 / (son + 1) * 1 / son ,d[u] = d[u] +  1 / (son + 1) * 1 / son * (d[vi]...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

RMQ 算法 Balanced Lineup

Balanced Lineup RMQ： RMQ（Range Minimum/Maximum Query），即区间最值查询，这是一种在线算法，所谓在线算法，是指用户每次输入一个查询，便马上处理一个查询。RMQ算法一般用较长时间做预处理，时间复杂度为O(nlogn)，然后可以在O（1）的时间内处理每次查询。 f[i][j]表示从i开始长度为（(1<<j)-1）的区间最值。 f[i][0]表示从i开始长度为1<<0的最值，f[i][0]=a[i]; 递推方程：f[i][j]=max/min( f[i][j-1] ,f[i+(1<<j)][j-1]...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

Codeforces Round #267 (Div. 2) C George and Job

George and Job 给你n个数，每一段有m个数，取k段，并且每一段区间没有交叉。 dp[i][j]表示到第i个数时取了j段区间的最大和。 dp[i][j]=max(不取区间[i-m+1,i]，取区间[i-m+1,i]); dp[i][j]=max(dp[i-1][j]，dp[i-m][j-1]+区间[i-m+1,i]的区间和) #include<bits/stdc++.h> using namespace std; const int N=5e3+100; typedef long long ll; ll a[N]; ll p[N]; ll dp[N][N]...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

牛客练习赛49 D筱玛爱线段树

筱玛爱线段树 差分数组、前缀和 定义一个tg[i]表示在i处操作需要进行多少次 对于操作一，将Al~Ar的每一项的值加上1。 在l处标记+1*tg[i]，在r+1处标记-1*tg[i]，求前缀和，可以实现l~r间每一项+1*tg[i] 对于操作二，在tg[r]处标记+1*tg[i]，在tg[l-1]处标记-1*tg[i]，求后缀和，求得tg[i]   #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; const int N=1e5+100; typedef long long ll; ...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

Codeforces Round #273 (Div. 2) D. Red-Green Towers dp+滚动数组

D Red-Green Towers 题意：有红绿两色的方块，数量分别为r个和g个。有0<=r,g<=2e5，r+g>=1，我们想用这红绿两色的方块（不一定全部，可以是一部分），构成一个高度尽可能高的积木块。 这个积木块需要满足—— 假设高度为h，那么第一层有1个，第二层有2个，……，第h层有h个。 每层方块的颜色，不是全部为红色，就是全部为绿色。 让你输出，有多少种方案，可以构成高度最高的积木块 分析：先算出塔的高度h，用dp[i][j]表示0~i层使用j个红色积木块的方案数，很容易得到状态转移方程 dp[i][j]=d[i-1][j]+d[i-1][...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

Codeforces Global Round 2 A B C D

链接：Codeforces Global Round 2 A:Ilya and a Colorful Walk 从后往前找到第一个不等于a[1]的长度，从前往后找到第一个不等于a[n]的长度；取最大值 #include<bits/stdc++.h> using namespace std; const int MAXN = 3e5 + 7; int a[MAXN] , n; signed main(){ scanf("%d",&n); for(int i = 1 ; i <= n ; ++i) scanf...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

Tachibana Kanade Loves Game 牛客练习赛43 容斥原理

题目链接：Tachibana Kanade Loves Game 当k+（n- n中是2~m倍数的个数）<q 输出QAQ 所以只要找到n中是2~m倍数的个数题目就可以解决。 2<=m<=20  但是可以排除一些数，比如6，如果x是2的倍数，那么x肯定是6的倍数，所以找到n中是m中素数的倍数个数就行，m的取值为a[]={2,3,5,7,11,13,17,19}。 然后用容斥原理解题。 kjj,今天数学老师讲了欧拉函数才懂这题；这题和用容斥原理证明欧拉函数的过程差不多。 n中a[i]倍数的个数为n/a[i]  , n-n中是2~m倍数的个数=n-(n/a[0]+n/...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

Tachibana Kanade Loves Review 牛客练习赛43

链接：https://ac.nowcoder.com/acm/contest/548/C 最小生成树 题目求能不能在t天内学完所有知识点，将每个知识点看成一个顶点，知识点间的联系看成边，这样问题就简化成了一个求最小生成树的问题了。但是还有一些点之间是没有联系的，即图是不连通的，所以我们需要引入一个节点0，将(0,i)这条边的权值定为Ti，这样图就联通了。另外就是条件k了，k个已经学习的知识点表明（0，ki）这条路径已经加入到最小生成树中，只需用并查集合并就好。 #include<bits/stdc++.h> using namespace std; const int N=...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

Tachibana Kanade Loves Probability 牛客练习赛43 快速幂+快速除

链接：https://ac.nowcoder.com/acm/contest/548/B 快速幂取模+快速除 #include<bits/stdc++.h> using namespace std; long long m,n,k1,k2; long long powerMod(int a,long long b){ long long ans=m; a=a%n; while(b>0){ if(b&1) ans=(long long)ans*a%n; a=(long long)a*a%n; b/=2; } return ans; } int...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

P1546 最短网络 Agri-Net 最小生成树 prim kruskal

题目：P1546 最短网络 Agri-Net kruskal代码： #include<bits/stdc++.h> using namespace std; #define maxl 100000 int n,a[110][110],f[110],sum=0; struct Edge{ int st,en,w; }e[10010]; bool cmp(Edge x1,Edge x2){ return x1.w<x2.w; } int find (int x){ return x==f[x] ? x:f[x]=find(f[x]); } int main(){...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

P1144 最短路计数 spfa

P1144 最短路计数 #include<bits/stdc++.h> using namespace std; #define maxn 1000010 const int inf = 0x7fffffff; int n, m, x, y; struct Edge{ int next; int to; }e[maxn]; int head[maxn],t=0; void addEdge(int u,int v){ e[++t].to=v; e[t].next=head[u]; head[u]=t; } int vis[maxn]={0},d[maxn]...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

P1119 灾后重建 Floyd

题目背景 B地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。 题目描述 给出B地区的村庄数N，村庄编号从0到N-1，和所有M条公路的长度，公路是双向的。并给出第i个村庄重建完成的时间ti，你可以认为是同时开始重建并在第ti天重建完成，并且在当天即可通车。若ti为0则说明地震未对此地区造成损坏，一开始就可以通车。之后有Q个询问(x,y,t)，对于每个询问你要回答在第t天，从村庄x到村庄y的最短路径长度为多少。如果无法...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

P1346 电车 floyd

P1346 电车 题目描述 在一个神奇的小镇上有着一个特别的电车网络，它由一些路口和轨道组成，每个路口都连接着若干个轨道，每个轨道都通向一个路口（不排除有的观光轨道转一圈后返回路口的可能）。在每个路口，都有一个开关决定着出去的轨道，每个开关都有一个默认的状态，每辆电车行驶到路口之后，只能从开关所指向的轨道出去，如果电车司机想走另一个轨道，他就必须下车切换开关的状态。 为了行驶向目标地点，电车司机不得不经常下车来切换开关，于是，他们想请你写一个程序，计算一辆从路口A到路口B最少需要下车切换几次开关。 输入输出格式 输入格式： 第一行有3个整数2<=N<=100，1<...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

P1339 热浪Heat Wave Dijkstra

https://www.luogu.org/problemnew/show/P1339 题目描述: 德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。 FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路...

0 点赞评论收藏

分享

2019-07-24 17:51

已编辑

长沙学院 Java

P1462 通往奥格瑞玛的道路

P1462 通往奥格瑞玛的道路 题目背景 在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量 有一天他醒来后发现自己居然到了联盟的主城暴风城 在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛 题目描述 在艾泽拉斯，有n个城市。编号为1,2,3,...,n。 城市之间有m条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。 每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。 假设1为暴风城，n为奥格瑞玛，而他的血量最多为b，出发时他的血量是满的。 歪嘴哦不希望花很多钱，他想知道，在可以到达奥...

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务