沐妖的博客

题意：在一个赛车比赛中，赛道有n（n <= 300）个交叉点和m(m <= 50000)条单向道路。有趣的是：每条路都是周期性关闭的。每条路用5个整数u,v,a,b,t表示(1<=u,v<=n,1<=a,b,t<=1e5)，表示起点是u，重点是v，通过时间为t秒。另外这条路会打开a秒，然后关闭b秒，然后再打开a秒，以此类推。当比赛开始时，每条道路刚刚打开。你的赛...

题意：输入两个整数L,U(1<=L,U<=1e9,U-L<=10000),统计区间[L,U]的整数中那一个的正约数最多，如果有多个，输出最小值#include <bits/stdc++.h>#define ll long long#define ull unsigned long long#define INF 0x3f3f3f3f#define mod...

题意：借助一个n层的高楼确定气球的硬度(所有气球硬度相同)。试验过程是这样的：每次你拿着一个气球爬到第f层楼，将它摔到地面。如果气球破了，说明它的硬度不超过f；如果没破，说明硬度至少为f。注意：气球不会被试验所磨损。换句话说，如果在某层楼上往下摔，气球没破，那么在同一层楼不管再摔多少次它也不会破。给你n个气球用来试验（可以打破它们）。你的任务是求出至少需要多少次实验，才能确定气球的硬度（或者得...

题意：输入一个1~n(1<=n<=10000)的序列，用不超过9的6次方把它变成升序，每次操作都可以选一个长度为偶数的连续区间，交换前一半和后一半，例如，输入5,4,6,3,2,1可以执行1,2先变成4,5,6,3,2,1，然后执行4,5变成4,5,6,3,2,1，然后执行5,6变成4,5,6,2,1,3，然后执行4,5变成4,5,6,2,3,1最后执行操作变成1,6，即可提示：2...

题意：一个W*H(1<=W,H<=10000)网格里有有n(0<=n<=100)棵树，要求找一个最大空正方形思路：枚举y坐标，每次遍历所有点，判断是否有点落在正方形内，有的话维护最优解#include <bits/stdc++.h>//#define ll long long#define ll unsigned long long#define...

题意：如果两个人相互打电话(直接或间接)，则说他们在同一个电话圈里。例如a打给b，b打给c，c打给d，d打给a，则这四个人在同一个圈里；如果e打给f，f不打给e，则不能推出e和f在同一个电话圈里。输入n（n<=25）个人的m次电话，找出所有电话圈。人名只包含字母，且不重复。思路：首先用floyd求出传递闭包，即g[i][j]表示i是否直接或间接给j打过电话，则当且仅当g[i][j]=g[...

题意：一个长度为n(n <= 100000)的序列，满足1<=ai<=i,要求确定每个数的正负号，使得所有数的总和为0.思路：1.若所有数总和为0必有正的一半和负的一半，无论一半是奇数还是偶数，最后所有数绝对值之和必为偶数，因此所有数之和ans为奇数时直接输出No2.ans为偶数时只需p = 0，遍历一遍若(p + a[i]) * 2 <= ans,则该数a[i]就...

题意：n个湖，每个湖都装满了水。不久的将来会有暴雨，在接下来的m天内，每天要么不下雨，要么恰好忘一个湖里下暴雨。如果这个湖里已经装满了水，将会引发水灾。没了避免水灾，神龙可以在每个不下雨的天里喝干一个湖的水（也可以不喝）。如果以后再往这个干枯的湖里下暴雨，湖会重新被填满，但不会引发水灾。神龙应当如何喝水才能避免水灾？n<=1e6,.<=1e6思路：贪心，因为要优化时间复杂度，所以用...

题意：有两个盒子各有n(n<=2e5)个糖，每天随机选一个(概率分别为p,1-p)，然后吃一颗糖，直到有一天，打开盒子一看，没糖了！输入n,p，求此时另一个盒子里糖的个数的数学期望。思路：根据期望的定义，不妨设最后打开第一个盒子，此时第二个盒子有i颗，则这之前打开过n + (n - i)次盒子，其中有n次取得是盒子1，其余n - i次取得盒子2，概率为C（2 * n - i,n）* p的...

题意：你住在村庄A，每天需要过很多条河到另一个村庄B上班。B在A的右边，所有的河都在中间。幸运的是，每条河都有匀速移动的自动船。因此每当到达一条河的左岸时，只需等船过来，载着你过河，然后在右岸下船。你很瘦(谢谢!)，因此上船之后船速不变。日复一日年复一年，你问自己：从A到B，平均情况下需要多长时间？假设在出门时所有船的位置都是均匀随机分布。如果为止不是在河的端点处，则朝向也是均匀随机。在陆地上的行...

题意：对于给定的n个数a1,a2,...an,依次求出相邻两数之和，将得到一个新数列。重复上述操作时，最后结果将变成一个数。问这个数除以m的余数与那些数无关？思路：1.在一般情况下，最后ai的系数是C(i - 1,n - 1)。这样问题就变成了C(0,n -1),C(1,n - 1),...C(n -1 ,n - 1)那些是m的倍数，可以用C(n,k) = C(k - 1,n) * (n - ...

题意：输入整数n(1<=n<=30000000)，有多少对整数(a,b)满足1<=b<=a<=n,且gcd(a,b) = a ^ b.思路：1.a ^ b = c,那么a ^ c = b,枚举a 和 c，算出b = a ^ c，验证gcd(a,b)是否等于c2.发现规律gcd(a,b) = a ^ b = c   =>   a - b = c。gcd(a...

题意：第一象限里有一个角，把n(n<=10)个给定边长的正方形摆在这个角里，使得阴影部分面积最大思路：参考链接#include <bits/stdc++.h>#define ll long long#define ull unsigned long long#define INF 0x3f3f3f3f#define mod 1000000007;using n...

题意：输入两个格子的编号a和b（a,b<=10000），求最短距离思路：建坐标系找规律，参考他人思路思路链接#include <bits/stdc++.h>#define ll long long#define ull unsigned long long#define INF 0x3f3f3f3f#define mod 1000000007;using na...

题意：有一块椭圆形的地。在边界上选n(0<=n<=2的31次方)个点并两两连接得到n*(n - 1) / 2条线段。它们最多能把地分成多少个部分？思路：欧拉公式，自己没推出来看了别人的import java.math.*;import java.util.Scanner;public class Main{ public static void main(Stri...

题意：输入一个n * m 矩阵，每个格子里都有1个[1,1e9]的正整数。再输入T个整数ti(0<=t1<=t2<=...<=tT<=1e9),对于每个ti，输出大于ti的正整数组成多少个四连块。思路：1.并查集计算有多少连通块2.因为T个整数是按大小顺序已经排好的，所以可以倒着来在算完ti的基础上计算t(i - 1)，每个格子记为一个点，将格子按照格子内的值...

题意：给出整数a,b，统计a和b（包含a和b）之间的整数中，数字0,1,2,3,4,5,6,7,8,9分别出现了多少次。1<=a,b<=1e8。注意a有可能大于b思路：看别人的题解愣是看了一个多小时才想明白，惭愧思路链接#include <bits/stdc++.h>#define ll long long#define ull unsigned long...

题意：有高为1,2,3,...n的杆子各一根排成一行。从左边能看到l根，从右边能看到r根，求有多少种可能(1<=l,r<=n<=20)思路;紫书332页#include <bits/stdc++.h>#define ll long long#define ull unsigned long long#define INF 0x3f3f3f3f#def...

题意：有一些装有铀（用U表示）和铅（用L表示）的盒子，数量均足够多。要求把(n <= 30)个盒子放成一行，但至少有三个U放在一起，有多少种方法思路：紫书P331#include <bits/stdc++.h>#define ll long long#define ull unsigned long long#define INF 0x3f3f3f3f#defi...

题意：有一个n（n<=1000）位密码锁，每位都是0~9，可以循环旋转。每次可以让1~3个相邻数字同时往上或者往下转一格，问最少要转几次；思路:1.记忆化搜索。d[cur][x][y][z]代表当前第cur位为x，右边两位是y，z并且一定要把第cur位转到正确位置2.第cur位必须要转tmp位，但是右边相邻的第一位可以有0~tmp位和第cur位一起转，设右边相邻第一位转了i次，右边相...

题意：无限大的奶酪里有n(0<=n<=100)个球形的洞。帮助小老鼠A用最短的时间到达小老鼠O所在的位置。奶酪里的移动速度为10秒一个单位，但是在洞里可以瞬间移动。洞和洞可以相交。输入n个球的位置和半径，以及A和O的坐标，求最短时间思路：1.因为n的大小最多为100，可以用flord2.注意i和j的距离d[i][j]应该为double，此题答案是四舍五入，floor是向下取整，...

题意：。。。思路：1.百度标准差式子，将式子展开2.直接暴力算#include <bits/stdc++.h>#define ll long long#define ull unsigned long long#define INF 0x3f3f3f3f#define mod 1000000007;using namespace std;// freop...

题意：输入n(n<=1000),统计有多少个n结点的有根树，使得每个深度中所有节点得子节点数相同思路：除掉第一个节点必须被放置为根节点之外，还剩下n-1个节点，那么这n-1个节点可以平均（注意是平均）分为多少个等分，那么每个等分也就可以继续等分划分，将所有的这些情况求和即可。递推无能，烦死了#include <bits/stdc++.h>#define ll long...

题意：36张牌分成9堆，每堆四张牌。每次可以拿走某两堆顶部的牌，但需要点数相同。如果有多种拿法则等概率的随机拿。例如9堆顶部的牌分别为KS,KH,KD,9H,8S,8D,7C,7D,6H，则有五种拿法(KS,KH),(KS,KD),(KH,KD),(8S,8D),(7C,7D),每种拿法的概率均为1/5,。如果最后拿完所有牌则游戏成功。按顺序给出每堆牌的四张牌，求成功概率。思路：记忆化搜索，学...

题意：有n个人准备去超市逛，其中第i个人买东西的频率是Pi。逛完以后得知有r个人买了东西，计算每个人实际买了东西的频率。输入n(1<=n<=20)和r(0<=r<=n)，输出每个人实际买了东西的频率。思路：“r个人买了东西”这个事件叫做E，“第i个人买东西”这个事件为Ei，要求P(Ei|E) = P(EiE) / P(E).条件概率公式1.计算P(E).递归方式计算...

题意：选择K个质数，使它们的和等于N。给出N和K(N<=1120,K<=14),问有多少种满足条件的方案，注意1不是素数，因此n = k = 1时答案为0思路：1.素数筛法求出所有范围内的素数2.0-1背包动态规划有点不太明白三重循环的嵌套和顺序问题，还需要再看看#include <bits/stdc++.h>#define ll long long#...

题意:给出整数n，给出一个序列中的部分数据t1,t3,t5...t(2 * n)，有公式ti = (t(i - 1) * a + b) % 10001，0<=n,a,b<=10000，求出t2,t4,...t(2 * n - 1)思路：暴力枚举a和b进行计算序列，若计算得出的值和给出数据不同，则继续尝试，知道找的正确答案#include <bits/stdc++.h&g...

注意事项：0-1背包的转化，题目说t<=1e9，但是一共有n首歌(n<=50)，每首歌不超过30分钟，所有n+1首歌的总长度严格大于t，也就是说t不会超过180n+678#include <bits/stdc++.h>#define ll long long#define ull unsigned long long#define INF 0x3f3f3f3f...

题意：有等长小木棍，将木棍随意砍成几段，直到每段的长度都不超过50.现在将木棍拼接成原来的样子，但是不记得最开始有多少木棍和它们的分别长度。给出每根小木棍的长度，编程找出原始木棍的最小可能长度，例如若砍完后有四根·，长度分别为1,2,3,4，则原来可能是2根长度为5的木棍，也可能是1根长度为10的木棍。思路：1.统计所有木棍总长度sum，则原来木棍数每根木棍长度maxd必须被sum整除，即su...

埃及分数稍微加了一点限制条件，我是拿它作为埃及分数，IDA*算法的连习题来做的，结果也改了很长时间，是因为忘记了改成long long了#include <bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;typedef long long ll;const int maxn = 100;int maxd;...

#include <bits/stdc++.h>using namespace std;const int maxn = 80 + 2;int n,l,cnt,s[maxn];//cnt表示第几个困难串，cur表示字符串长度int dfs(int cur){ if(cnt == n) { for(int i = 0; i < cur;...

#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <sstream>#include <iomanip>#include <vector>#include <cmath&a

双向链表接触的第一个题目，思路还是很好理解的，不过还是有一些不理解的地方以及一些坑。1.因为命令4操作起来很麻烦，所以并没有真正进行命令4，而是设一个sign来判断执行命令4的奇偶次数。当执行命令4为奇数时，...

同样是栈的运用，紫书的例题。1.在中转站c中，车厢符合后进先出的原则，因此是一个栈。2.以给出的特定的顺序为标准吧，以下几种情况若B中的数与A相同则B++，查看B中下一个数若C中的栈顶元素与B中的数相同，则栈顶元素出栈，B++，查看B中下一个数A不超过n时，将A入栈以上都不满足时则说明不能以特定顺序进入B方向的铁轨并出车站#include <iostream> #include &...

1.射了虚拟结点，从s+1开始输入，字符串长度也从s+1开始计算2.next[i] = next[cur]大致是把下一个字符的位置设为0next[cur] = i是将cur与i连接起来，相当于在cur后插入i，即cur->i3.遇到'['时，令cur = 0，即在0后插入元素遇到']'时，令cur = last，即在最后一个元素后继续插入元素4.last始终表示已插入的最后一个元素#incl...

是我接触树类的第一道题呀，还是比较好理解的。还是注意找规律，对于一个结点k，其左子结点，右子结点的编号分别是2k和2k+1，好了直接上代码吧。#include <cstdio>#include <cstring>#include <iostream>using namespace std;int main(){ int n; while...

应该算是一个很水的一道题了，可我是个渣渣呀，还是弄了两节晚自习，就是栈的简单应用。具体思路分析如下：       建立一个栈，当遇到'('或'['时入栈，当遇到')'或']'并且栈为空时入栈，若遇到')'或']'栈不为空并且栈的栈顶元素与之匹配时，就删去栈顶元素。最后若集合为空就说明括号平衡，否则就不平衡。至于让我卡两节晚自习的点：空字符串也是平衡符号，所以要用getline输入一行。#inclu...

题目很简单暴力枚举就可以，不过认真分析问题可以使程序更加简单，提高运算速率。不过通过这道题学到了sprintf的一个用法：将数字转化成字符串。int main(){ int i = 1234,j = 678; char s[12]; sprintf(s,"%05d%05d",i,j); printf("%s\n",s); return 0;}下面是题目代...

这道题是紫书上的一道例题，在看刘汝佳老师的代码时对几个循环有些似懂非懂，后来从网上找到了一位大神的代码，讲解很仔细，想了一下就明白了，附上大神讲解的链接，希望有所帮助。点击打开链接#include <iostream>#include <string>#include <sstream>#include <vector>#include &l...

题意：有一篇由n(2<=n<=9)个自然段组成的文章，希望将它们排列成1,2......n。可以用剪切和粘贴快捷键来完成任务。每次可以剪切一段连续的自然段，粘贴时按照顺序粘贴。注意粘贴板只有一个，所以不能连续剪切两次，只能剪切和粘贴交替。例如为了将2,4,1,5,3,6变为升序，可以剪切1将其放到2前，然后剪切3放到4前，。再如对于排列3,4,5,1,2，只需一次剪切和一次粘贴即可--...