sgu专题

【SGU】180. Inversions(归并排序求逆序数)

以前一般用树状数组和线段树做这种题 这次换个思路试试,归并排序! #include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 111111;int n;int array[maxn];int tmp[maxn];L

【SGU】271. Book Pile(双端队列模拟)

一摞书,2个操作,一个操作是在书堆上加一本,第二个将前K个书翻转 看别人用Splay树做的,但是可以用双端队列模拟,因为K个书之后的书位置已经定下来了,所以只需要记录在队列头加书还是尾加书 #include<cstdio>#include<string>#include<algorithm>#include<queue>#include<stack>#include<cstrin

【SGU】115. Calendar 水题= =

传送门:【SGU】115. Calendar 题目分析:2001年1月1号星期1,然后就没什么好说的了= = 代码如下: #include <map>#include <vector>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespac

【SGU】 114. Telecasting station 中位数

传送门:【SGU】 114. Telecasting station 题目分析:一个位置多个城市可以看成多个城市在同一位置,然后就可以求中位数了,易知最优的位置一定在中位数上。 代码如下 : #include <map>#include <vector>#include <cstdio>#include <cstring>#include <iostream>

【SGU】113. Nearly prime numbers 合数分解

传送门:【SGU】113. Nearly prime numbers 题目分析:O(sqrt(N))。。 代码如下: #include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std ;#define rep( i , a , b ) for

SGU 495. Kids and Prizes 期望

n个盒子 m个人轮流选 拿走盒子里的奖品 盒子再放回去 求得到奖品的期望 可以求没有被选到的奖品的期望 用n减去就是答案 #include <stdio.h>#include <iostream>#include <algorithm>#include <math.h>using namespace std;int main(){int n,m;while(scanf("%d%

SGU 108. Self-numbers 2 离线+位优化

可以像筛选法那样标记 但是内存最多只能开1024的int数组 我用了位优化 用一个int 32 位标记32个数字 接下来就离线 排个序 算出第k大的哪个数 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;int a[10000000/32];struct node{int x, y,

SGU 106. The equation 扩展欧几里德

求解的个数 对应ax+by=c 根据裴蜀定理c%gcd(a, b) == 0有解 假设d = gcd(a, b) 用扩展欧几里德求出方程aax+bb*y=cc 的解x0 y0 那么原方程的一个解就是x0*c/d和y0*c/d 通解为  x = x0+i*b/d y = y0+i*a/d 分别讲x1 x2 带入得到i 满足最小的左区间 y1 y2一样 #include <cstd

SGU 103. Traffic Lights 带限制最短路

每个点有2中颜色 只有一条路上的两个点颜色一样才能通过这条路 最短路加上等待的时间处理 处理的是参考别人的 唉还是太弱了 #include <cstdio>#include <cstring>#include <vector>#include <queue>#include <algorithm>using namespace std;int s, e;int n, m;in

SGU 390 Tickets (数位DP, k进制树)

这题数位DP很不一样。。首先不能像常规的数位DP 用[0,R] 减去[0, L] 用类似字典树的方法,一个10进制数的区间也可以表示成一棵十叉树,每条路径就是一个数字,那么令 dp[h][sum][rem],代表当前h位下,前几位的和为sum,前一个子树剩余的数字个数,这样去进行数位DP,把在边界的值搜到底,然后其他位置就可以进行记忆化,时间复杂度可以接受 代码: #include <c

SGU 108 (空间优化)

这题本来觉得是道没什么的水题,结果没想到空间卡得这么死 于是注意观察式子,发现每个推到后面最多加7 * 9 (7位数,每位是9) 于是就只要开64的空间,利用滚动数组去优化即可 另外还要注意,答案表全打出来也是会MLE的,只能根据输入的k去存放k个答案 代码: #include <cstdio>#include <cstring>#include <algorithm>usin

SGU 106 The equation(拓展欧几里得)

通解形式 然后利用x,y去求出范围,就能得到解的个数 注意特判a和b都为0的情况 代码: #include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;typedef long long ll;ll a, b, c;double a1, a2, b1

SGU 101 Domino(欧拉路径)

0-6作为结点,那么每个骨牌相当于一条无向边了 建图,进行欧拉路径判断, 然后dfs找出路径打印即可 代码: #include <cstdio>#include <cstring>#include <vector>using namespace std;const int N = 7;int n;struct Edge {int u, v, tp, id, vis;Edge()

SGU 223. Little Kings

原题: 223. Little Kings time limit per test: 0.5 sec. memory limit per test: 65536 KB input: standard output: standard After solving nice problems about bishops and rooks, Petya decided that he wo

史上最全的SGU题目分类

由于SGU上神题遍地,特列此表,便于训练时分类训练。 101 Domino 欧拉路 102 Coprime 枚举/数学方法 103 Traffic Lights 最短路 104 Little Shop of Flowers 动态规划 105 Div 3 找规律 106 The Equation 扩展欧几里德 107 987654321 Problem 找规律 108 Self-number

SGU 125. Shtirlits(dfs)

There is a checkered field of size N x N cells (1 Ј N Ј 3). Each cell designates the territory of a state (i.e. N2 states). Each state has an army. Let A [i, j] be the number of soldiers in the stat

SGU 126. Boxes

题面Codeforces. Programming competitions and contests, programming communityhttps://codeforces.com/problemsets/acmsguru/problem/99999/126大意:给出A,B(0<A+B<2^31),每次操作可以将其中一个数减去另一个数,并让另一个数乘2,即(A,B)->(2A,B-A)

sgu 180. Inversions (树状数组+离散化,第一道需要改模板的题目,好题)

1、http://blog.csdn.net/sdjzping/article/details/20381665 2、题目大意: 有n个数字,定义i<j并且a[i]>a[j]这样的一对数为逆序对,求这个数中有多少逆序对, 3、题目分析 看着题目很简单,但是n=65537,两重for循环找必超时,所以想到了用树状数组,但是交了好几遍都错了,runtime error,原因就是数组中的数字可以

SGU 206 Roads KM算法 匹配模型的转化

这是一道非常好的题目 题目大意: 给了一个图,n个点,m条边,其中前n-1条边保证是生成树,现在你可以修改每条边的边权,花费为修改量,然后用最小的花费修改使得前n-1条边为最小生成树 这题乍一看无从下手 实际上可以这么分析 边可以分为两类,一种是前n-1条边,构成了一个生成树,其他的边是另外一种边 显然如果我们要达到最小生成树的目的,就要让生成树上的边变小,而另外的边变大 从第n条边