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
", 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
", 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
", 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
", 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
", 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
", ans);
for(int i = 0; i < N; i++)
if(!f[i]) printf("%d
", 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
", ans);
return 0;
}
return 0;
}
506.Subsequences Of Substrings (2015.12.15)
548.Dragons and Princesses
一开始看错题了然后完全没思路= =只要弄个优先队列贪心一下就行了...正确性很显然...(2015.12.15)