问题模型 现在有一个这样的问题：有一个数组a，，现在给你w次修改，q次查询，修改的话是修改数组中某一个元素的值；查询的话是查询数组中任意一个区间的和。 这个问题很常见，首先分析下朴素做法的时间复杂度，修改是O(1)的时间复杂度，而查询的话是O(n)的复杂度，总体时间复杂度为O(qn) 可能你会想到前缀和来优化这个查询，我们也来分析下，查询的话是O(1)的复杂度，而修改的时候修改一个点，那么在之后的所有前缀和都要更新，所以修改的时间复杂度是O(n)，总体时间复杂度还是O(qn)。 可以发现，两种做法中，要么查询是O(…
题目描述 如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。 输入输出格式 输入格式： 第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。 接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。 输出格式： 一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647） 输入输出样例 输入样例#1： 4 6 1 1 2 2 2 3 2 …
一、查看运行时间 头文件 #include<ctime> #include <ctime> #include <iostream> using namespace std; int main(){ int a,b; cin>>a>>b; int t=clock(); printf("%d\n",a-b); printf("Time："); cout << clock()-t << endl; …
性质 并查集算法（union_find sets）支持分割一个集合,求连通子图、求最小生成树（克鲁斯卡尔） 输入输出格式 输入格式： 第一行包含两个整数N、M，表示共有N个元素和M个操作。 接下来M行，每行包含三个整数Zi、Xi、Yi 当Zi=1时，将Xi与Yi所在的集合合并 当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N 输出格式： 如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N 输入输出样例 输入样例#1： 4 7 2 1 2 1 1 2 2 1 2 1…
题目描述 C 市火车站最近出现了一种新式自动售票机。买票时，乘客要先在售票机上输入终点名称。一共有N 处:目的地，随着乘客按顺序输入终点名称的每个字母，候选终点站数目会逐渐减少。 在自动售票机屏幕上，有一个4 行8 列的键盘，如下图所示。 在乘客每输入一个字母后，键盘上只有有效字符是可选的（取决于还有哪些候选终点站），其余的字母会被字符'*' 取代。 告诉你N 处目的地的名称，以及乘客已经输入的若干字符，请你输出键盘目前的状态。 输入输出格式 输入格式： 第一行为一个整数N (1≤N ≤50)。接下来N 行，每行一…
题目描述 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1n−1次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 11 ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少…
声明方式 库：#include<string> string s;//声明一个string 对象 string ss[10];//声明一个string对象的数组 操作方式 s.begin() s.end为迭代器，类似指针的东西，没怎么搞清楚 1、substr(a,b) 返回从a到b的字符串 2、substr(a) 返回a及a以后的字符串 3、insert(a,str) 在a的位置插入str 4、erase(s.begin()+a) 删除a处字符 5、erase(s.begin()+a,s.begin()…
题目描述 为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 n 张地毯，编号从 1 到n 。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。 地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。 输入输出格式 输入格式： 输入文件名为carpet.in 。 输入共n+2 行。 第一行，一个整数n ，表示总共有 n 张地毯。 接下来的n…
题目背景 本题为提交答案题，您可以写程序或手算在本机上算出答案后，直接提交答案文本，也可提交答案生成程序。 题目描述 将1，2，…，9共9个数分成三组，分别组成三个三位数，且使这三个三位数构成1：2：3的比例，试求出所有满足条件的三个三位数。 输入输出格式 输入格式： 木有输入 输出格式： 若干行，每行3个数字。按照每行第一个数字升序排列。 本人提供的题解 机智的九循环 #include<cstdio> #include<iostream> using namespace std; bool…
