下一页 »Current position : 首页 >> 图论
程序设计实习实验班2017作业（算法 作业19, 20, 21）
一些以前做过的就不再贴了AFunnyStoneGame发现每一堆的每个石子之间都是相互独立的[crayon-594e852dcccf9484880765/]nnimn阶nim和，在二进制下，每一位求和后对(n+1)取模[crayon-594e852dccd0d032608301/]一个水水的序列在建操作树的过程中就能顺便维护信息每次新加入节点的时候维护一下这个点的倍增数组，询问的时候直接向上倍增[crayon-594e852dccd12410326304/]【poj1523】SPF求割点，并且求删去割点后的连通分量个数[cr...
2017 训练赛 1 by hzwer
【poj1054】TheTroublesomeFrog（恼人的青蛙）【poj1037】decorativefence【hdu2197】本原串【poj2112】OptimalMilkin【bzoj4010】[HNOI2015]菜肴制作【hdu2462】TheLuckiestnumber【bzoj3172】[Tjoi2013]单词【poj1054】TheTroublesomeFrog（恼人的青蛙）首先O(n^3)的算法是显然的，即枚举两个点，check一下这条路径上所有点，由于这道题时限放的比较宽，实际上图可以直接用二维的bool数组存下来网络上的题解大多...
2015程序设计实习实验班免修考试(校内）
【poj1037】decorativefence用f(i,j)表示长度为i，开头为j，开头为上升的序列用g(i,j)表示长度为i，开头为j，开头为下降的序列考虑在序列的第二位放一个数字，改变上升/下降预处理完之后，一位位枚举贪心[crayon-594e852dcedb0662306194/]【poj1011】Sticks经典的搜索剪枝1.长度取值范围是木棍的最长长度到长度总和之间。2.长度总和一定可以整除原来的长度。3.从大到小排序搜索。4.某次组合时，如果不能加入某根木棍，同种长度的木...
2016程序设计实习实验班免修考试(算法)
02:热血格斗场[crayon-594e852dcf3d9901668535/]05:MPIMaelstrom[crayon-594e852dcf3e2355538817/]06:Ultra-QuickSort[crayon-594e852dcf3e8726309559/]08:DrainageDitches[crayon-594e852dcf3ec075699494/] ...
Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)
A.CheckingtheCalendar问有没有可能存在一年中的连续两个月，第一个月的第一天的星期是给定的第一个字符串，第二个月的第一天的星期是给定的第二个字符串模拟即可[crayon-594e852dcf903438012602/]B.BatchSort给你n行，每行都是一个1-m的排列。\(1\leqn\leq20,1\leqm\leq20\)你可以交换任意两列，并且你可以每行最多交换两个元素，问你能不能使得每行都是单增的枚举两列交换，每行贪心[crayon-594e852dcf90d940682288/]C.R...
【codeforces】图论杂题
一些图论简单题：500A.NewYearTransportation437C.TheChildandToy510C.FoxAndNames475B.StronglyConnectedCity639B.BearandForgottenTree3623A.GraphandString449B.JzzhuandCities543B.DestroyingRoads500A.NewYearTransportation有n个城市排成1排，从第i个城市可以走到\(i+a_i\)号城市，并给定一个城市t，问是否能从1到t？\(1\leqn,a_i\leq10^5\)题解将1打个标记，从左往右扫一遍，若i打上标记，...
2016 ACM/ICPC Asia Regional Qingdao Online
大部分都是队友写的代码QAQ我主要是填坑个题解1001ICountTwoThree定义『ICountTwoThreeNumber』为\(2^a3^b5^c7^d\)问超过n的最小的这种数字显然这样的数字数量是很少的，其质因数个数不会超过30个dfs出所有数字，二分查询1002Cure求\(\sum\limits_{k=1}^n\frac{1}{k^2}\)\(\lim_{n\rightarrow\infty}\)\(\sum\limits_{k=1}^n\frac{1}{k^2}=\frac{\pi^2}{6}\)n超过十几万之后就达到精度上限1003FamilyView把一个文本...
【cf715X】Codeforces Round #372 (Div. 1)
A.PlusandSquareRoot推公式可得，可构造每次按完的数为i*(i+1)[crayon-594e852dd0f9d348437595/]B.CompleteTheGraph给一张无向图，要求赋值一些边的边权，使得最终S到T的最短路为L用f(i,j)表示从S到点i，经过j条无边权的边的最短路选择一个最小的j，使得f(T,j)+j<=L更改这条路径上的边权，使得最短路为L，将其它无边权的边赋值为L可以证明不会产生其它的最短路似乎还可以采取一些暴力调整的做法，写起来会短一些...
2016 ACM/ICPC Asia Regional Dalian Online
1002DifferentGCDSubarrayQuery问长为n的序列，m个询问，问区间[L,R]所有子段的不同gcd值个数考虑固定左端点，随着右端点的移动，gcd至多衰减log次（每次至少折半）从n开始添加询问的左端点，用树状数组维护每个gcd右端点的最小值[crayon-594e852dd1467663472772/]1007FriendsandEnemiesn个人，每个人可以用m种颜色中的一部分染色自己的项链两个人是朋友当且仅当他们拥有相同的颜色敌人不拥有任何相同的颜色问对于任意一...
【cf698X】Codeforces Round #363 (Div. 1)
A.Vacations题意：给出每天contest和gym的开关状态，不能连续俩天参加相同活动，问n天最少休息多少天用F(i,0-2)表示前i天，第i天的状态为（rest，contest，sport），最多能有多少天不休息简单dp一下[crayon-594e852dd1933532225995/]B.FixaTree给出n个结点的父亲，问至少修改多少个能够使得其变成一棵树先用拓扑排序消去外向树，剩下的每个环要选出一个当根，然后再把所有的环连成树答案是环数-（是否存在自环）[crayon-594e...
FJ2016集训 day7
题目来自coolinging（orz）Problem1挑选子序列(sequence.cpp/c/pas)题目来源：原创考察要点：搜索与剪枝、dancinglinks、二分、排序涉及要点：动态规划、随机化算法、贪心解题报告：题目可以理解为在串t中选取m个字母，每个字母覆盖串s1和串s2的部分位置，使串s1和串s2被完全覆盖，求满足如上条件时距离的最小值。对于数据点1，n<=10，T<=10，可以直接枚举选取哪m个字母，简单计算即可。由此可知，对于本题来说，判定比求解...
FJ2016集训 day5
打了个酱油，身败名裂0。01冷战1.1题目大意给定一副N个点的图。动态的往图中加边，并且询问某两个点最早什么时候联通。1.2题解考虑并查集。并查集实际上维护了一棵树。那么假如我们按秩合并，这棵树的深度是O(logn)的。我们将一个点连向其父亲的边权设为这条边加入的时间，那么每次询问时，暴力查询树上从u到v所经过边权的最大值即可。时间复杂度为O(nlogn)，常数较小。假如写了常数较大的可以得到80分。[crayon-594e852de89ed1...
Codeforces Round #360 (Div. 1)
A.NP-HardProblem二分图染色[crayon-594e852de912d854598089/]B.RemaindersGame将K分解为a1^p1*a2^p2...an^pn则ai^pi要被c中的某个数整除[crayon-594e852de9137061540983/]C.TheValuesYouCanMake用f(i,j)表示容量i和j的背包能不能同时取得若f(x,K-x)则可以用K中的物品凑出X[crayon-594e852de913b170338015/] ...
近期评论