sgu专题

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

题面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条边