1 Zlun_Yan

尚未进行身份认证

暂无相关简介

等级
TA的排名 24w+

【Codeforces 1352C】K-th Not Divisible by n(暴力)

原题链接:K-th Not Divisible by n原题截图:题目大意:输入n和k,求第k个不能被n整除的正整数解题思路:直接暴力就好了计算从1到k的所有可以被n整除的正整数个数temp用cnt记录在前面的过程中已经生效了的被n整除的正整数个数,k=k+temp-cnt,cnt=cnt+temp重复操作1和操作2,知道temp-cnt=0AC代码:#include<cstdio>using namespace std;int main(){ int t,n,

2020-05-15 12:04:47

【Codeforces 1349A】Orac and LCM(数论⭐)

原题链接:A. Orac and LCM原题截图:题目大意:输入一个数组a,由a中的任意两个元素s[i]和s[j]的最小公倍数构成另一个数组t,求t中所有元素的最大公约数题目中算是有一个小提示吧 t = { lcm(aia_iai​,aja_jaj​) | i<j },让人容易想到固定i,aia_iai​与ai+1a_{i+1}ai+1​到ana_nan​的所有元素的最小公倍数构成一个子集m,这样所有子集m的最大公约数构成一个新的集合q,那么集合q的所有元素的最大公约数就等于集合t的所有

2020-05-14 17:35:01

图论(二)——拓扑排序

就一个题目来讲一讲拓扑排序:拓扑排序·一题目大意:有n门课,对这n门课一共有m个约束条件,约束

2020-05-07 15:52:56

【Codeforces 1348D】Phoenix and Science(思维)

原题链接:D. Phoenix and Science原题截图:题目大意:某人一开始有1个混乱度(mess)为1的细菌,在白天时,每个细菌都可以将其分裂为两个混乱度相同的细菌,并将其混乱度均分给这两个细菌【例如:一个混乱度为1的细菌可以变成两个混乱度为0.5的细菌】在晚上时,每个细菌的混乱度均会增加1假设这个人可以控制每天会有几个细菌将会分裂问:最少经过d个夜晚,使得所有细...

2020-05-06 18:40:41

【Codeforces 1348B】Phoenix and Beauty(思维)

原题链接:B. Phoenix and Beauty原题截图:题目大意:大概就是给出一个长度为n数组a,需要在其中加入一些元素,使得这个数组的任意一段长度为k的子数组(subarray)的元素之和都相等输出加入这些元素后,数组的长度并输出数组解题思路:既然在题目中说,不存在方案的情况输出-1,那么就想一想需要怎么判断是否存在解决方案:假设数组处理完之后的结果为数组b,那么来看看这...

2020-05-05 09:10:53

图论(五)——最小生成树之Prim算法

最小生成树对于一张边带权的连通图 G = (V , E),由numNode-1条边和numNode个节点连通子图,且这个子图的边权值之和最小,则称这个子图为图G的最小生成树Prim算法该算法的思想简述如下:在图中取一点x,将其看作一个集合M,将其他的所有节点看作一个集合N遍历x的所有边,找到终点位于集合N中且权值最小的边,将这个终点y加入到集合M中遍历y的所有边,找到终点位于集合N...

2020-04-30 16:01:47

【Codeforces 1340A】Nastya and Strange Generator(思维)

原题链接:A. Nastya and Strange Generator原题截图:题目大意:有一个长度为n的数组s,然后要把1~n这n个整数从小到大、按照“规则”填入数组中,然后判断能否得到input中的目标数组“规则”:r数组:r[i]代表此时数组s中从下标r[i]到n的第一个未填入的位置(若没有未填入的位置,则r[i]为undefined,用*表示)count数组:count[...

2020-04-30 10:46:32

【Codeforces 1342D】Multiple Testcases(思维+暴力)

原题链接:D. Multiple Testcases原题截图:题目大意:有一个有n的元素的数组m,要将其分成若干组,其中每一组中大于等于i的元素不超过c[i]个,问:最少划分为几个组并输出分组的方案解题思路:首先找出最少分成几组,因为在每一组中大于等于i的元素最多为c[i]个,所以不妨统计数组m中[i,k]的元素为p个,那么最少分组的个数就是ans=max(ans, ⌈p/c[i...

2020-04-29 15:07:53

【Codeforces 1343E】Weights Distributing(最短路)

原题链接:E. Weights Distributing原题截图:题目大意:给出一张有n个节点和m条边的无向连通图,再给定m的权值,要求将这m个权值分配到m条边上,使得从a到b再从b到c的距离最短,输出最短距离解题思路:这个问题的难点有两个:路径要求从a到b再从b到c要自己分配边权值那么首先简化问题:如果是从x到y,得出一个分配的方案使得路径距离最小那么自然想到的...

2020-04-27 11:12:09

【Codeforces 1343D】Constant Palindrome Sum(打标记)

原题链接:D. Constant Palindrome Sum原题截图:题目大意:对于一串长度为n的数组a(n为偶数),要求修改其中的若干元素,使得对于任意i,有a[i]+a[n-i+1]=x,问:最少修改多少个元素解题思路:因为x不是一个确定的值,那么对于任意一对a[i]+a[[n-i+1],通过改变这两个的值,都可以变成从2到2*k的任意一个值,只是改变的次数有区别,假设两个数中...

2020-04-24 16:08:26

图论(十)——网络流的最大最小费用最大流问题

费用流在求网络的最大流的同时加上一个条件:每条边的流过流的单位费用,由此得出费用流的问题【其实费用流就可以算是最大流和最短路最长路的综合】费用流问题分为两类:最小费用最大流(最大流+最短路)最大费用最大流(最大流+最长路)最小费用最大流为什么说最小费用最大流就是最大流+最短路呢,可以这样想:有一条流量为f的增广路,对于其中的每一条边都有一个单位费用cost[i],每条边的流量都...

2020-04-08 16:34:49

图论(九)——网络流的最大流问题之Dinic算法

最大流图论(五)——网络流的最大流问题引入Dinic算法回顾EK算法【图论(六)——网络流的最大流问题之Edmonds-Karp算法】,发现EK算法在每次BFS搜索全图的过程中,只会得出一条增广路,这样的效率比较低,所以需要优化,优化之后的算法就叫做Dinic算法节点的层次:从起点S到节点i所需要经过的最少的边的数目如果用BFS在网络中得到节点层次的分层图,再用DFS搜索这个分层图(...

2020-04-07 21:54:16

图论(六)——最小生成树之Kruskal算法

最小生成树对于一张边带权的无向连通图 G = (V , E),由numEdge-1条边和numNode个节点无向连通子图,且这个子图的边权值之和最小,则称这个子图为图G的最小生成树Kruskal算法该算法的思想简述如下:建立并查集,每个点自己为一个集合将所有边(from , to , weight),按权值weight从小到大排序,依次扫描对于边(from , to , weigh...

2020-03-30 22:46:51

图论(七)——网络流的最大流问题引入

网络流一个网络 G= (V , E) 是一张有向图,图中的每一条边 (x , y) ∈ E,其权值w的意义为 最多可以将w个物品从节点x运输到节点y,所以这个权值又称为边的 容量,记为c(x , y);此外,在图中没有标出的边,即 (x , y) ∉ E,则c(x , y) = 0然后还有两个指定的特殊的节点 S ∈ V,T ∈ V(S != T)分别...

2020-03-30 22:06:00

图论(八)——网络流的最大流问题之Edmonds-Karp算法

增广路为了解决最大流问题,再引入一个概念:剩余容量【c(x , y)-f(x , y)】如果可以找到一条从源点出发,经过中间节点,流向汇点,且其中每一条边的剩余容量均大于0的路,就称这条路为一条增广路,假设可以知道这一条增广路中所有的边的最小剩余容量为p,那么对于整个网络系统而言,就可以增加一个流量为w的流从源点通过这一条路流向汇点,那么这个网络的流量就增加了w。如果找到了所有的增广路,已...

2020-03-30 22:04:37

图论(四)——单源最短路径之Bellman-Ford算法和SPFA算法

单源最短路径问题,即给定一张有向图(其实无向图也可以看作是有向图,即将无向的一条边看成是两条有向的边),设1号节点为起点,求其到i号节点的最短距离先来给出一个具体的题目,然后看看这两种算法是怎么写出代码来解决的【使用Dijkstra算法的解决方案:图论(二)——单源最短路径之Dijkstra算法】HDU最短路Bellman-Ford算法这个算法很好理解,它的操作的主要思想如下:...

2020-03-25 12:02:43

图论(三)——单源最短路径之Dijkstra算法

单源最短路径问题,即给定一张有向图(其实无向图也可以看作是有向图,即将无向的一条边看成是两条有向的边),设1号节点为起点,求其到i号节点的最短距离Dijkstra 算法Dijkstra 算法,算是这种单源最短路径问题中最为经典的一种算法了,其主要思想大致如下:设1号节点为起点,设一个长度为numNode的数组dis,其中dis[i]表示从起点1到节点i的最短距离,设一个长度为numNod...

2020-03-24 21:09:06

图论(一)——边的储存(邻接矩阵、邻接表、链式向前星)

对于图论而言,一共有三种存边的方式:邻接矩阵、邻接表、链式向前星邻接矩阵邻接矩阵即用二维数组储存int graph[Len][Len];graph[i][j] //这个表示的即是表示从节点i到节点j的边权值/*用一个二维数组存边,可以将数组的所有元素的值都初始化为某一个数k(要保证后面输入边权值时不会出现k),表示此时从i节点到j节点的边不存在*/优点:适合稠密图,...

2020-03-23 23:03:04

【Codeforces 1296D】Fight with Monsters(简单模拟)

D. Fight with Monsters题意:有n个野兽 排成一排第i个野兽有hi点生命值你的攻击力等于 a点生命值 你的对手的攻击力等于b点生命值你和你的对手现在正在对抗这些野兽一开始 你和你的对手都到第一个野兽那里打它 直到打死然后去第二个野兽那里 知道打死它以此类推当一个野兽的生命值小于等于0时 则认为这个野兽死了然后你和你的对手轮流打这个怪兽 如果你打...

2020-02-06 17:51:06

【Codeforces 1294D】MEX maximizing 题解(简单数学)

MEX maximizing 题解(简单数学)MEX maximizing这个题是一个比较简单的题目 稍作分析即可:题意:MEX:给出一个数组 求出除去这个数组中的元素之外的最小的非负整数此时 在给定一个x 可以对数组中的任意一个元素加上或减去x(但是进行这个操作之后要保证这个元素仍然是一个非负整数) 使得这个数组的MEX最大思路:这个题想一想也没什么巧妙的方法 应该就是直...

2020-01-27 14:09:38

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 技术圈认证
    技术圈认证
    用户完成年度认证,即可获得
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。