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--;
		else
			j--;
	}
	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++];
			} else
				con[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;
	else
		f[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)