A-赫式几何 问题描述 19世纪的德国数学家赫尔曼●明科夫斯基发现了一种非欧几里德几何空间，称作“出租车几何空间或者曼哈顿距离”。在这种神奇的空间中，定点T1(X1,Y1)与T2(X2,Y2)的距离表示为： D(T1,T2)=|X1-X2|+|Y1-Y2| 其他的定义都同欧几里德几何相同，包括圆的定义： 圆是一个点集，其中的任意一个元素到平面上的一个定点（即圆心）的距离（即圆的半径）相同。 我们现在要研究在赫氏几何和欧氏几何中圆的面积的差别。现在这个重任交给了你。输入格式 只有一个整数R，表示圆的半径。输出格式 输出两行，分别表示圆在欧氏几何中的面积和在赫氏几何中的面积 注：答案精确到0.00...

今天讲了树形dp，正好看到这道题，仔细一看，这不是板题吗（滑稽）。 咳咳，强行切入正题 首先，我们根据样例画出一张无比丑陋的图： 现在我们减去1的右枝就得到了下面这张图： 如果减去1的左枝： 如果保留1的左右枝，左子树保留条，右子树保留条，使得 由此可以推出：对于任意子树，若要保留其条枝，均可按减掉左枝，减掉右枝（剪后判断剩下的枝数是否等于）和将左右子树分为两部分（即上图红***域），分别保留和条边，使得来进行讨论。 既然是树形dp，那就按dp的套路来分析： 首先一遍dfs建好二叉树 阶段：依次讨论以每个节点为根的子树 状态：设f[x][y]表示以x为根的子树共保留y条树枝的最大苹果数 决策：...

题面翻译： 奶牛贝西想连续看L (1 <= L <= 100,000,000)分钟的电影，有 N (1 <= N <= 20)部电影可供选择，每部电影会在一天的不同时段放映。 贝西可以在一部电影播放过程中的任何时间进入或退出放映厅。但她不愿意重复看到一部电影，所以每部电影她最多看到一次。她也不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。 请帮贝西计算她能够做到从0到L分钟连续不断地观看电影，如果能，请计算她最少看几部电影就行了。 好恶心的一道题！！！ 这道题是让我们求最小观看电影个数，那么题意就可以简化成： 每个电影只能看一次，且为了保持观看电影个数最小...

此题是一道十分考察细节的一道题。 此题就是让我们求的矩阵里，分割出条横线和条竖线，要求两两相邻的点，尽可能多的不再相邻。 题目已经告诉你了，这是一道贪心！！！ 为什么是贪心呢？？？ 要使答案最优，肯定要让条横线和条竖线要穿过尽可能多的会讲话的两个人！ 如图： 如果只有一条横线和竖线上图中的最优解，很明显是这样： 所以我们的贪心是成立的 我们需要用结构体维护能穿过的讲话同桌个数和从第几行（列）分割的！然后按照能穿过的同桌个数由大到小排序，最后输出答案。 code： 统计当前行列能穿过的同桌个数 if(x==x2){ int yy=min(y,y2); cy[yy].x++; ...

dijkstra:求单源最短路 算法步骤: 1. 找离起点x最近的未讨论过的点k。 2. 判断经过k点，起点x到其他点的距离是否缩短，如缩短 则更新。将k点标记为已讨论。 3. 重复进行第1步，直到所有点都被讨论过为止。于是我们可以得出: dis[i]=min{dis[k]+Map[k][i]} 1<=i<=n k是未讨论过的，离起点最近的点 dis[i]表示从起点到i点最短距离 :为了方便，此篇文章部分采用邻接矩阵存图，建议各位换成更高效的存图方法。 : void dijkstra(int x){ for(int i=1;i<=n;i++){ 初...

最小生成树 Kruskal算法：（找最小生成树） 首先按照边的长度由小到大排序 每次选出最小的与之前选过的判断在不在同一集合（并查集） 如果m条边都枚举完还没连到n-1条边，则无解。 时间复杂度 O(mlogm) (m为边的数量) 代码： #include<stdio.h> #include<bits/stdc++.h> using namespace std; const int N=1005; const int H=10005; struct node{ int a,b,len; }; node edge[H];//保存所有边的信息 int n,m,f...

图的遍历 方法一：宽搜 queue<int> q; void bfs(int s){ q.push(s); mark[s]=1; while(q.size()){ int x=q.front(); q.pop(); cout<<x<<endl; for(int i=Last[x];i;i=Next[i]){ int y=End[i]; if(!mark[y]){ q.push(y); ...

引例：数列游戏（NKOJ3754） 给定一个长度为N的序列，首先进行A次操作，每次操作在Li和Ri这个区间加上一个数Ci。 然后有B次询问，每次询问Li到Ri的区间和。 初始序列都为0。 第一行三个整数N A B。(1<=N<=1000000,1<=A<=N,A<=B<=N) 接下来A行，每行三个数Li Ri Ci。(1<=Li<=N,Li<=Ri<=N,|Ci|<=100000000000000)。 接下来B行，每行两个数 Li Ri。范围同上。 对于每次询问，输出一行一个整数。 因为最后的结果可能很大，请对结果mod 1...