SGU题目总结

SGU还是个不错的题库…但是貌似水题也挺多的..有些题想出解法但是不想写代码, 就写在这里吧…不排除是我想简单想错了, 假如哪位神犇哪天发现请告诉我..

101.Domino(2015.12.16)

102.Coprimes 求φ(N). 1<=N<=10^4

按欧拉函数的公式直接算..O(N^0.5)(2015.12.16)

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int N, ans;int main() {scanf("%d", &N);ans = N;for(int i = 2; i * i <= N; i++) if(N % i == 0) {ans = ans / i * (i - 1);while(N % i == 0) N /= i;}if(N > 1)ans = ans / N * (N - 1);printf("%d\n", ans);return 0;}

104.Little shop of flowers F朵花放进V个花瓶(排成一列)中,要求第i朵花放在第j(j>i)多花前每朵花在每个花瓶中有个值, 求最大值, 输出方案.1 ≤ F ≤ 100, F ≤ V ≤ 100, -50 <= Aij <= 50

dp(i, j) = max( dp(i, j-1), dp(i-1, j-1) + w(i,j) ), 表示前i朵花放在前j个花瓶中的最大值.输出方案就倒着遍历一遍.时间复杂度O(FV).(2015.12.17)

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 109;int F, V, w[maxn][maxn];int dp[maxn][maxn], ans[maxn];int main() {scanf("%d%d", &F, &V);for(int i = 1; i <= F; i++)for(int j = 1; j <= V; j++)scanf("%d", &w[i][j]);memset(dp, -0X3F3F3F3F, sizeof dp);memset(dp[0], 0, sizeof dp[0]);for(int i = 1; i <= F; i++)for(int j = i; j <= V; j++)dp[i][j] = max(dp[i - 1][j - 1] + w[i][j], dp[i][j - 1]);printf("%d\n", dp[F][V]);for(int i = F, j = V; i; ) {if(dp[i][j] == dp[i - 1][j - 1] + w[i][j])ans[i--] = j--;elsej--;}for(int i = 1; i <= F; i++)printf("%d ", ans[i]);return 0;}

106.The equation 求ax+by+c=0的满足x1<=x<=x2,y1<=y<=y2的解(x,y)的个数. 所有数绝对值<=10^8

扩展欧几里德求出方程的一组解(x,y),那么方程其他解(x+kb’,y-ka’), b’=b/gcd(a,b), a’=a/gcd(a,b).就可以算解的个数了.细节还是挺多的.(2015.12.17)

#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<iostream>using namespace std;typedef long long ll;void Gcd(ll a, ll b, ll& d, ll& x, ll& y) {if(!b) {d = a; x = 1; y = 0;} else {Gcd(b, a % b, d, y, x);y -= x * (a / b);}}ll A, B, C, X0, X1, Y0, Y1;int main() {cin >> A >> B >> C >> X0 >> X1 >> Y0 >> Y1;if(A < 0) {A = -A; X0 = -X0; X1 = -X1;swap(X0, X1);}if(B < 0) {B = -B; Y0 = -Y0; Y1 = -Y1;swap(Y0, Y1);}C = -C;ll d, x, y;Gcd(A, B, d, x, y);if(!A || !B) {if(!A && !B) {cout << (C ? 0 : (X1 - X0 + 1) * (Y1 - Y0 + 1));} else if(!A) {cout << ((!(C % B) && C / B <= Y1 && C / B >= Y0) ? (X1 - X0 + 1) : 0);} else {cout << ((!(C % A) && C / A <= X1 && C / A >= X0) ? (Y1 - Y0 + 1) : 0);}return 0;}if(C % d) {puts("0");return 0;}x *= C / d; y *= C / d;A /= d; B /= d;ll L = max((ll) ceil((double) (X0 - x) / B),(ll) ceil((double) (y - Y1) / A));ll R = min((ll) floor((double) (X1 - x) / B), (ll) floor((double) (y - Y0) / A));cout << max(0LL, R - L + 1);return 0;}

108.Self-numbers 2

我只会暴力..或者乱搞打个表之类的?(2015.12.17)

111.Very simple problem

高精度开平方…二分+高精度平方?或许能AC吧…(2015.12.17)

112. a^b-b^a 求a^b-b^a.1≤a,b≤100

高精度乘法和高精度减法, 高精度乘法是高精*单精,应该挺好写的…..(2015.12.17)

113. Nearly prime numbers 给出N个数,分别判断他们是否可以表示成2个质数的乘积的形式。1£N£10, 给出的数<=10^9

对于x, 假如满足题意, 存在p1,p2(p1<=p2)使得p1*p2=x,那么p1<=sqrt(x), p2>=sqrt(x)。O(10^4.5)线性筛出质数表.然后枚举<=sqrt(x)的质数p去检查.时间复杂度O(10^4.5+∑sqrt(x)/log(x^0.5)).应该可以AC….(2015.12.17)

114.Telecasting station 给xi,wi,求ans使得∑abs(xi-ans)*wi有最小值.0<N<15000,0<X, P<50000

假设在端点p0答案为a0,那移到端点p1的贡献是sumw(1~p0)*(p1-p0)-sumw(p0~pn)*(p1-p0), 记录前缀和可以O(1)转移.同时也可以看出某个端点一定是答案.所以O(N)扫一遍,加上排序, 总时间复杂度O(NlogN+N)(2015.12.17)

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;#define w(i) w[r[i]]#define x(i) x[r[i]]const int maxn = 15009;int x[maxn], w[maxn], r[maxn], N;bool cmp(const int &l, const int &r) {return x[l] < x[r];}int main() {scanf("%d", &N);for(int i = 0; i < N; i++) {scanf("%d%d", x + i, w + i);r[i] = i;}sort(r, r + N, cmp);for(int i = 1; i < N; i++) w(i) += w(i - 1);int ans = 0;ll mn = 0, cur;for(int i = 1; i < N; i++)mn += (ll) (w(i) - w(i - 1)) * (x(i) - x(0));cur = mn;for(int i = 1; i < N; i++) {ll Delta = (ll) (w(i - 1) * 2 - w(N - 1)) * (x(i) - x(i - 1));if((cur += Delta) < mn)mn = cur, ans = i;}printf("%d.00000\n", x(ans));return 0;}

117.Counting

裸快速幂.时间复杂度O(NlogM)(2015.12.17)

187.Twist and whirl – want to cheat(2015.12.15)

199.Beautiful People 给N个人和Si,Bi, 对于2个人i,j如果Si>=Sj且Bi<=Bj,或者Si<=Sj且Bi>=Bj那么i,j不能同时选.求能选的最大人数,输出方案.2 ≤ N ≤ 100,000,1 ≤ Si, Bi ≤ 10^9

只有Si<Sj且Bi<Bj可以同时选i,j, 按S排序, 然后考虑B, 就变成了一个最长上升子序列的问题了,按S排序时假如S相同要按B从大到小排.然后记录从哪里来, 输出方案.时间复杂度O(NlogN)(2015.12.18)

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define b(i) b[r[i]]const int maxn = 100009;int p[maxn], d[maxn], From[maxn];int a[maxn], b[maxn], r[maxn], Id[maxn];int N;bool cmp(const int &l, const int &r) {return a[l] < a[r] || (a[l] == a[r] && b[l] > b[r]);}int main() {scanf("%d", &N);for(int i = 0; i < N; i++)scanf("%d%d", a + i, b + i), Id[i] = r[i] = i;sort(r, r + N, cmp);int ans = 0, pos;memset(p, 0X3F3F3F3F, sizeof p); p[0] = 0;memset(d, -1, sizeof d);for(int i = 0; i < N; i++) {int t = upper_bound(p, p + N + 1, b(i)) - p;if(t && p[t - 1] == b(i)) t--;if(t) From[i] = d[t - 1];if(t > ans)ans = t, pos = i;ans = max(ans, t);if(p[t] > b(i))p[t] = b(i), d[t] = i;}int n = 0;for(; ~pos; pos = From[pos]) d[n++] = Id[r[pos]];printf("%d\n", ans);sort(d, d + ans);for(int i = 0; i < n; i++)printf("%d ", ++d[i]);return 0;}

203.Hyperhuffman 从小到大给出N个的字母的各自的出现次数, 求他们哈夫曼编码后文章的长度.2 ≤ N ≤ 500,000,1 ≤ Pi ≤ 10^9

用优先队列当然是随便写, 但是这道题因为给出数据时已经排序好了,所以有O(N)做法..我也是看了forum才发现的…按照哈夫曼的构造方式去构造就行了(2015.12.18)

#include<cstdio>#include<algorithm>#include<cstring>using namespace std;typedef long long ll;const int maxn = 500009;int N, num[maxn], qh, qt;ll con[maxn], q[maxn];int main() {scanf("%d", &N);for(int i = 0; i < N; i++) scanf("%d", num + i);qh = qt = 0;for(int p = 0, v = 1; v < N; v++) {ll t[2];con[qt] = 0;for(int i = 0; i < 2; i++)if(p >= N || (qh < qt && q[qh] < num[p])) {con[qt] += con[qh] + q[qh];t[i] = q[qh++];} elsecon[qt] += (t[i] = num[p++]);q[qt++] = t[0] + t[1];}printf("%lld\n", con[--qt]);return 0;}

222.Little Rooks. N*N的棋盘放K个车不互相攻击方案数.1≤N≤10,0≤k≤n^2

数据范围很小…状压dp应该可以AC..推公式的话, 每行至多放1个车, so K>N就无解, 然后N行放K个车有C(N,K)种方案,放第i个车时有N-i+1种方案. 答案就是C(N,K)*(N!/(N-K)!), 应该是不用高精度的…(2015.12.15)

223.Little Kings N*N的棋盘放K个王(8连通的格子会互相攻击)不互相攻击方案数.1≤N≤10,0≤k≤n^2

看到sample的output是79..是个质数..那应该就是没有公式的吧…状压dp(x,k,s)表示考虑了前x行,已用了k个王,第x行的状态为s时状态数.O(4^N)预处理状态s的转移..时间复杂度O(4^N+K*N*2^N), 应该可以AC的…(2015.12.15)

230. Weighings. 给出N样东西, 然后告诉你M个质量关系(p,q)表示p质量<m质量.问是否矛盾。输出方案.

有点像今年的NOIPday1t2..暴力找环即可, 有环就无解. 有解就从每个入度为0的点开始输出就行了.(2015.12.15)

231.Prime Sum. Find all pairs of prime numbers (A, B) such that A<=B and their sum is also a prime number and does not exceed N.1<=N<=10^6
看起来挺难的样子..a prime应该是奇数(除了2), 奇数+奇数=偶数…所以就筛出质数扫一遍就可以了= = (2015.12.15)

280.Trade centers 一颗N各节点的树.求最小点集S,满足树上任意一点到点集中的点距离的最小值<=K. 1≤ N≤ 30000, 1≤ K≤ 100

贪心, 选出2个点假如距离是2*K+1就是最好的, 以此为基础进行DFS.(2015.12.18)

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 30009;struct edge {int to;edge* next;} E[maxn << 1], *pt = E, *head[maxn];void AddEdge(int u, int v) {pt->to = v;pt->next = head[u];head[u] = pt++;}int N, M, f[maxn], ans;void Init() {scanf("%d%d", &N, &M);for(int i = 1; i < N; i++) {int u, v;scanf("%d%d", &u, &v); u--; v--;AddEdge(u, v);AddEdge(v, u);}ans = 0;}void DFS(int x, int fa = -1) {int mn = maxn, mx = -maxn;for(edge* e = head[x]; e; e = e->next) if(e->to != fa) {DFS(e->to, x);mn = min(mn, f[e->to]);mx = max(mx, f[e->to]);}if(mn == maxn)f[x] = M + 1;elsef[x] = (mx + mn + 2 <= 2 * M + 1 ? mn : mx) + 1;if(f[x] == 2 * M + 1)f[x] = 0, ans++;else if(fa == -1 && f[x] > M)ans++, f[x] = 0;}int main() {Init();DFS(0);printf("%d\n", ans);for(int i = 0; i < N; i++)if(!f[i]) printf("%d\n", i + 1);return 0;}

415.Necessary Coins. 给N个硬币, 求组成X元哪些硬币一定是要选的,保证X元去得到. 1≤N≤200,1≤X≤10^4

处理出前缀背包和后缀背包, 然后枚举每一个硬币去检查.时间复杂度O(NX) (2015.12.15)

499.Greatest Greatest Common Divisor 给出N个数(1~1000000且各不相同), 求任意2个数的最大公因数的最大值.2<=N<=100000.

直接枚举答案, 时间复杂度O(1000000log(1000000)).

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 1000009;bool F[maxn];void Init() {memset(F, 0, sizeof F);int n;scanf("%d", &n);while(n--) {int t;scanf("%d", &t);F[t] = true;}}bool chk(int x) {int cnt = 0;for(int i = x; i <= 1000000; i += x)if(F[i] && ++cnt >= 2) return true;return false;}int main() {Init();for(int ans = 1000000; ans; ans--) if(chk(ans)) {printf("%d\n", ans);return 0;}return 0;}

506.Subsequences Of Substrings (2015.12.15)

548.Dragons and Princesses

一开始看错题了然后完全没思路= =只要弄个优先队列贪心一下就行了…正确性很显然…(2015.12.15)