POJ - 4044 Score Sequence 模拟+贪心

题目链接：点击查看 题意：n个城市节点构成的一棵树，节点i到节点j的电量损耗为 I*I*R*(i到j的路径所含边数)，现在要在某个结点上修建一个供电站，使得这个结点到所有其它节点的总损耗量最小。 题解：I*I*R可以…...

题目链接：点击查看 题意：从一给出的点出发可以向任意方向发出射线，然后现在平面上共有1500条线段，问最多能使射线和几条线段相交 题解：每个线段都有一个对应的角度范围，刚开始想的是离散化一下&#xff0…...

题目链接&#xff1a;点击查看 题意&#xff1a; 给出一个N个数的序列以及一个k&#xff08;0<k<n<200000)&#xff0c;m个操作p,x,y&#xff0c;其中 p0&#xff1a;将x位置的数替换为y p1&#xff1a;将x y位置的数互换 p2: 查询x-y位置区间连续k个数的和的最…...

题目链接&#xff1a;点击查看 题意&#xff1a;给一个图和q个询问&#xff0c;每个询问查询图中两点的&#xff08;距离路径上最大值&#xff09;的最小值。 题解&#xff1a;暴力枚举每个点&#xff0c;以这个点为起点并且为路径上所有经过的点的价值中最大的点来跑最短路&…...

题目链接&#xff1a;点击查看 Kropki&#xff1a; 题目描述&#xff1a; 你有一个11到nn的排列p_1, p_2, \dots, p_np1​,p2​,…,pn​&#xff0c;对于所有的i (1\leq i\leq n-1)i(1≤i≤n−1)&#xff0c;如果p_ipi​和p_{i1}pi1​中&#xff0c;有一个数是另一个的两倍&…...

题目链接&#xff1a;点击查看Here is a function f(x):int f ( int x ) {if ( x 0 ) return 0;return f ( x / 10 ) x % 10;}Now, you want to know, in a given interval [A, B] (1 < A < B < 10 9), how many integer x that mod f(x) equal to 0. Input The fi…...

题目链接&#xff1a;点击查看 题解&#xff1a;我们容易发现到当n,m都为奇数时&#xff0c;是回不到原点的&#xff0c;因为你无论哪个方向走一去一回就是两步&#xff0c;所以n和m必然有一个偶数&#xff0c;那至于我们怎么走呢&#xff0c;看下图&#xff0c;注意的是n1,m2…...

算法讲解&#xff1a;点击查看 核心代码&#xff1a;p[i] maxx > i ? min ( p[id - ( i - id ) ] , maxx - i ) : 1 ; 给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba, abba等 Input 输入有多组case…...

吉哥又想出了一个新的完美队形游戏&#xff01; 　　假设有n个人按顺序站在他的面前&#xff0c;他们的身高分别是h[1], h[2] ... h[n]&#xff0c;吉哥希望从中挑出一些人&#xff0c;让这些人形成一个新的队形&#xff0c;新的队形若满足以下三点要求&#xff0c;则就是新的…...

马拉车算法 推荐博客&#xff1a;点击查看 Andy the smart computer science student was attending an algorithms class when the professor asked the students a simple question, "Can you propose an efficient algorithm to find the length of the largest palin…...

题目链接&#xff1a;点击查看 For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 < i < N) we want to …...

题目链接&#xff1a;点击查看 CC always becomes very depressed at the end of this month, he has checked his credit card yesterday, without any surprise, there are only 99.9 yuan left. he is too distressed and thinking about how to tide over the last days. …...

题目链接&#xff1a;点击查看 Language:Default Power Strings Time Limit: 3000MS Memory Limit: 65536KTotal Submissions: 61784 Accepted: 25534Description Given two strings a and b we define a*b to be their concatenation. For example, if a "abc" and…...

题目链接&#xff1a;点击查看 The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape…...

题目链接&#xff1a;点击查看 It is well known that AekdyCoin is good at string problems as well as number theory problems. When given a string s, we can write down all the non-empty prefixes of this string. For example: s: "abab" The prefixes …...

后缀数组-处理字符串的有力工具 &#xff1a; 点击查看 后缀数组模板及代码详解&#xff1a;点击查看 Given a string, we need to find the total number of its distinct substrings. Input T- number of test cases. T<20; Each test case consists of one string, who…...

题目链接&#xff1a;点击查看 A. 回收卫星 单测试点时限: 1.0 秒 内存限制: 256 MB “这个世上没有无用的齿轮&#xff0c;也只有齿轮本身能决定自己的用途。” 就像太空中的卫星&#xff0c;虽然不计其数&#xff0c;但都各司其职。 但没有一个东西是能够永远无损的。为…...

题目连接&#xff1a;点击查看 Mr. Apple, a gourmet, works as editor-in-chief of a gastronomic periodical. He travels around the world, tasting new delights of famous chefs from the most fashionable restaurants. Mr. Apple has his own signature method of rev…...

题目连接&#xff1a;点击查看 output standard output Asya loves animals very much. Recently, she purchased n kittens, enumerated them from 1 and n and then put them into the cage. The cage consists of one row of n cells, enumerated with integers from 1 …...

题目链接&#xff1a;点击查看 Little Susie loves strings. Today she calculates distances between them. As Susie is a small girl after all, her strings contain only digits zero and one. She uses the definition of Hamming distance: We will define the distan…...

题目链接&#xff1a;点击查看 Little Susie listens to fairy tales before bed every day. Todays fairy tale was about wood cutters and the little girl immediately started imagining the choppers cutting wood. She imagined the situation that is described below…...

题目链接&#xff1a;点击查看 Little girl Susie went shopping with her mom and she wondered how to improve service quality. There are n people in the queue. For each person we know time ti needed to serve him. A person will be disappointed if the time he …...

题目链接&#xff1a;点击查看 Little girl Susie accidentally found her elder brothers notebook. She has many things to do, more important than solving problems, but she found this problem too interesting, so she wanted to know its solution and decided to a…...

题目链接&#xff1a;点击查看 Little Susie, thanks to her older brother, likes to play with cars. Today she decided to set up a tournament between them. The process of a tournament is described in the next paragraph. There are n toy cars. Each pair collid…...

题目连接&#xff1a;点击查看 Background A while ago it was quite cumbersome to create a message for the Short Message Service (SMS) on a mobile phone. This was because you only have nine keys and the alphabet has more than nine letters, so most character…...

题目连接&#xff1a;点击查看 题意&#xff1a;n个字符串最长公共子串&#xff0c;相同长度就找字典序小的&#xff0c;poj那个是长度小于3&#xff0c;输出那句话 题解&#xff1a;以某一字符串为基准&#xff0c;枚举每个子串&#xff0c;然后暴力kmp即可&#xff0c;特记…...

题目链接&#xff1a;点击查看 题意&#xff1a;太他妈难懂了&#xff0c;大致意思就是有k条链&#xff0c;想得到1->2->..>n&#xff0c;这样的链&#xff0c;有两种操作&#xff0c;一种是断开链&#xff0c;需要1秒&#xff0c;一种是可以将1个单独的数字接在链后…...

题目链接&#xff1a;点击查看 题意&#xff1a;有n个桌腿&#xff0c;要砍掉某些桌腿&#xff0c;使剩下的桌腿中长度最大的桌腿的数量如果超过一半。砍掉每个桌腿需要付出代价。求最小的代价和&#xff0c;操蛋&#xff0c;砍掉的意思是直接去掉&#xff0c;我理解成了&…...

题目链接&#xff1a;点击查看 题意&#xff1a;n个数字&#xff0c;可以乘以2&#xff0c;可以除以2&#xff0c;问总共多少次运算&#xff0c;使n个数一样 题解&#xff1a;因为是*2 /2 运算 数最大为1e5&#xff0c;每个数运算最多400次作左右&#xff0c;我们就暴力把每个…...

题目链接&#xff1a;点击查看 题意&#xff1a;有一个n*n的矩形&#xff0c;给你对角线上的坐标&#xff0c;给你一个方向&#xff0c;问能走几个坐标&#xff0c;遇到之前已经经过的坐标就停止 题解&#xff1a;当给你一个坐标(x,y)&#xff0c;方向向上时&#xff0c;他能…...

题目链接&#xff1a;点击查看 Now you are going to play an interesting game. In this game, you are given two groups of distinct integers and C coins. The two groups, named Ga and Gbrespectively, are not empty and contain the same number of integers at firs…...

题目链接&#xff1a;点击查看 When the girl was solving GSSX, a serious of tough problems about data structure on SPOJ, something intriguing once again comes to GYZs mind. That is, for a changing sequences, how to count how many elements in a specific rang…...

题目链接&#xff1a;点击查看 You have n computers numbered from 1 to n and you want to connect them to make a small local area network (LAN). All connections are two-way (that is connecting computers i and j is the same as connecting computers j and i). T…...

题目链接&#xff1a;点击查看 Your boss once had got many copies of a treasure map. Unfortunately, all the copies are now broken to many rectangular pieces, and what make it worse, he has lost some of the pieces. Luckily, it is possible to figure out the p…...

由于本人实在太菜&#xff0c;某题自己瞎鸡巴写实在写不出来了&#xff0c;就学一下tarjan算法了。 算法介绍来自某位15级学长&#xff0c;点击查看&#xff1a;点击查看 核心代码&#xff1a; void targan(int u) {dfn[u]low[u]tot;sta[len]u;vis[u]1;for(int i0;i<v[u]…...

题目链接&#xff1a;点击查看 题意&#xff1a;有N个炸弹&#xff0c;每个炸弹有一个坐标&#xff0c;一个爆炸范围和一个爆炸花费&#xff0c;如果一个炸弹的爆炸范围内有另外的炸弹&#xff0c;那么如果该炸弹爆炸&#xff0c;就会引爆所有爆炸范围内的炸弹&#xff0c;求让…...

题目链接&#xff1a;点击查看 题意&#xff1a;Bessie和Elsie在玩一种卡牌游戏。一共有2N张卡牌&#xff0c;点数分别为1到2N&#xff0c;每头牛都会分到N张卡牌。游戏一共分为N轮&#xff0c;因为Bessie太聪明了&#xff0c;她甚至可以预测出每回合Elsie会出什么牌。每轮游戏…...

题目链接&#xff1a;点击查看 题意&#xff1a;给你s&#xff0c;n&#xff0c;要求给s1,s2...sn&#xff0c;这n个数编号1-n&#xff0c;满足每个数膜编号为0&#xff0c;问是否存在 题解&#xff1a;打表发现两个素数的差值不足300&#xff0c;我们可以发现素数的因子只有…...

文字转自&#xff1a;点击查看 倍增比起树链剖分&#xff0c;代码短&#xff0c;容易查错&#xff0c;时空复杂度也优很多&#xff08;nlogn&#xff09;&#xff0c;只是功能有些欠缺。 倍增的思想是二进制。 首先开一个nlogn的数组&#xff0c;比如f[n][logn],其中…...

题目链接&#xff1a;点击查看 题意&#xff1a;求最近公共祖先 题解&#xff1a;树上倍增模板->点击查看 #include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <cmath> using namespace std; const …...

题目链接&#xff1a;点击查看 题意&#xff1a;找出树的重心&#xff0c;如果多个按编号从小到大输出 树的重心定义&#xff1a;点击查看 题解&#xff1a;树形dp&#xff0c;找出孩子中最大的&#xff0c;n-孩子总数即为向上节点数&#xff0c;求个最大的即可 #include&…...

题目链接&#xff1a;点击查看 题意&#xff1a;l - r 中有多少 最长上升序列为k的个数 不要求连续 题解&#xff1a;因为这个k并不大&#xff0c;所以我们可以想到用二进制来储存&#xff0c;我们再求一般的最长上升子序列时&#xff0c;是先保存在一个数组中&#xff0c…...

题目链接&#xff1a;点击查看 题意&#xff1a;给你n个点的坐标&#xff0c;给你一个矩形的w&#xff0c;h&#xff0c;问最多能圈住多少点 题解&#xff1a;扫描线&#xff0c;按x轴进行扫描&#xff0c;其实就是把一个点的左右范围找出来&#xff0c;一个为正&#xff0c;…...

题目链接&#xff1a;点击查看 题意&#xff1a;给你n*m的矩阵&#xff0c;求从第一行到第n行值加起来的最小路径&#xff0c;(i,j)可以走向(i1,j-1) (i1,j) (i1,j1) &#xff0c;尽可能向右走 题解&#xff1a;dp一遍即可&#xff0c;尽量取右边的 #include<bits/stdc.h…...

题目链接&#xff1a;点击查看 题意&#xff1a;n*m的海洋&#xff0c;o是薄冰&#xff0c;#是冰面&#xff0c;*是海洋&#xff0c;问最多能放多少船&#xff0c;不能同行同列&#xff0c;除非他们之间有冰面&#xff08;#&#xff09; 题解&#xff1a;二分匹配&#xff0c…...

题目链接&#xff1a;点击查看 题意&#xff1a;给你一棵树&#xff0c;DIST a b 查询a到b的距离&#xff0c;KTH a b c 查询a到b的路径上第c个点是啥 题解&#xff1a;树上倍增&#xff0c;先预处理每个dp[u][i]&#xff0c;查询a&#xff0c;b距离时&#xff0c;设他们的最…...

题目链接&#xff1a;点击查看 题意&#xff1a;长度100000的序列&#xff0c;原始都为3&#xff0c;两个操作&#xff0c;1 a b 把p[a] 改为b&#xff0c;0 a b 把[a,b] 区间数相乘&#xff0c;求这个数的欧拉值 题解&#xff1a;因为每个数都可以通过前60个素数表示&#x…...

题目链接&#xff1a;点击查看 题意&#xff1a;有一个带有n个珠子的圆链&#xff0c;起初圆链上的珠子都未被染色。规定两人轮流染色&#xff0c;每人每次只能挑选m个连续的未被染色的珠子进行染色&#xff0c;Aekdycoin先来&#xff0c;最后谁先不能染色谁则输掉了这场比赛&…...

题目链接&#xff1a;点击查看 题意&#xff1a;现在给出一个大圆圈&#xff0c;然后在大圆圈里面要放多个小圆圈&#xff0c;且要求所有的小圆圈必须与大圆圈的内表面相切&#xff0c;两个小圆圈之间的距离要大于等于给定值s。 题解&#xff1a;取两个相邻的小圆&#xff0c…...

题目链接&#xff1a;点击查看 题意&#xff1a;找一个回文串&#xff0c;他的一半也是回文串&#xff0c;并且长度是4的倍数 题解&#xff1a;马拉车算法跑一遍&#xff0c;记录每一个r[i]值&#xff0c;在判断左半部分的是否符合条件&#xff0c;负责度&#xff1f; #incl…...