HDU 4602 Partition
f[i]表示和为i的方案数。已知f[i]=2i-1。
dp[i]表示和为i，k有多少个。那么dp[i]=dp[1]+dp[2]+...+dp[i-1]+f[i-k]。
考虑与f有关的项：
f[n-k]是答案的一部分，即2n-k-1是答案的一部分。
把与dp有关的项：
令s[i-1]=dp[1]+dp[2]+...+dp[i-1]，那么s[n-1]是答案的一部分。
s[i]=s[i-1]+dp[i]，又dp[i]=s[i-1]+f[i-k]。推出s[i]=2*s[i-1]+f[i-k]，dp[k]=s[k]=1。
可以推出s[n-1]=2n-k-1+(n-k-1)*2n-k-2。
#include<iostream>
typedef long long LL;
LL MOD = 1000000007LL;
using namespace std;
LL powmod(LL a, LL b) {
LL ans;
a %= MOD;
for (ans = ; b; b >>= ) {
if (b & ) {
ans *= a;
ans %= MOD;
}
a *= a;
a %= MOD;
}
return ans;
}
int main() {
int T;
LL n, k;
LL ans;
cin >> T;
while (T--) {
cin >> n >> k;
if (k > n) {
ans = ;
} else if (k == n) {
ans = ;
} else if (n - k == ) {
ans = ;
} else if (n - k == ) {
ans = ;
} else {
ans = powmod(, n - k - )
+ (n - k - ) * powmod(, n - k - ) % MOD;
ans += powmod(, n - k - );
ans = (ans % MOD + MOD) % MOD;
}
cout << ans << endl;
}
return ;
}
HDU 4604 Deque
枚举第i个数，假设它最早出现且在队列里，那么以i为起点的最长非降子序列一定在队列里（push_back），以i为起点的最长非升子序列也一定在队列里(push_front)。
#include<cstdio>
#include<algorithm>
#define MAXN 100010
#define oo 123456789
using namespace std;
int arr[MAXN];
int up[MAXN], down[MAXN], cnt[MAXN];
int st[MAXN], top;
void LIS(int n, int dp[]) {
int i;
int pos;
top = -;
for (i = ; i < n; i++) {
if (top < || st[top] <= arr[i]) {
st[++top] = arr[i];
dp[i] = top + ;
} else {
pos = upper_bound(st, st + top + , arr[i]) - st;
st[pos] = arr[i];
dp[i] = pos + ;
}
cnt[i] = min(cnt[i],
upper_bound(st, st + top + , arr[i])
- lower_bound(st, st + top + , arr[i]));
}
}
int main() {
int T;
int n;
int i;
int ans;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (i = ; i < n; i++) {
scanf("%d", &arr[i]);
cnt[i] = oo;
}
reverse(arr, arr + n);
LIS(n, up);
for (i = ; i < n; i++) {
arr[i] = -arr[i];
}
LIS(n, down);
ans = ;
for (i = ; i < n; i++) {
ans = max(ans, up[i] + down[i] - cnt[i]);
}
printf("%d\n", ans);
}
return ;
}
HDU 4605 Magic Ball Game
统计树上一个节点到根，权值大于/小于某个数的个数：数状数组/线段树。
离线处理询问，对所有w的值离散化。
从树根开始DFS，第一次到达一个节点时，回答所有询问。
向儿子DFS时，更新往左/右的数状数组。
最后一次离开一个节点时，还原现场。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#define MAXN 200010
using namespace std;
int w[MAXN], tmp[MAXN];
struct node {
int pre;
int next[];
void init() {
pre = -;
next[] = next[] = -;
}
} tree[MAXN];
struct Ask {
int weight;
int pos;
};
vector<Ask> q[MAXN];
pair<int, int> res[MAXN];
bool stop[MAXN];
multiset<int> myset;
inline int lowbit(int x) {
return x & -x;
}
void update(int arr[], int i, int val) {
for (; i < MAXN; i += lowbit(i)) {
arr[i] += val;
}
}
int sum(int arr[], int i) {
int ans;
for (ans = ; i > ; i -= lowbit(i)) {
ans += arr[i];
}
return ans;
}
int left[MAXN], right[MAXN];
void dfs(int x) {
int i, j;
for (i = ; i < (int) q[x].size(); i++) {
j = q[x][i].pos;
if (myset.count(q[x][i].weight)) {
res[j].first = -;
} else {
res[j].first = sum(right, q[x][i].weight - );
res[j].second = * sum(left, q[x][i].weight - )
+ * sum(right, q[x][i].weight - ); res[j].second += sum(left, MAXN - ) - sum(left, q[x][i].weight);
res[j].second += sum(right, MAXN - ) - sum(right, q[x][i].weight);
}
} myset.insert(w[x]);
if (tree[x].next[] != -) {
update(left, w[x], );
dfs(tree[x].next[]);
update(left, w[x], -);
}
if (tree[x].next[] != -) {
update(right, w[x], );
dfs(tree[x].next[]);
update(right, w[x], -);
}
myset.erase(myset.find(w[x]));
}
int main() {
int T;
int n, m;
int i, j;
int u, a, b;
int size;
Ask ask;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
size = ;
for (i = ; i <= n; i++) {
scanf("%d", &w[i]);
tree[i].init();
q[i].clear();
tmp[size++] = w[i];
}
scanf("%d", &m);
while (m--) {
scanf("%d%d%d", &u, &a, &b);
tree[u].next[] = a;
tree[u].next[] = b;
tree[a].pre = u;
tree[b].pre = u;
}
scanf("%d", &m);
for (i = ; i < m; i++) {
scanf("%d%d", &u, &ask.weight);
ask.pos = i;
q[u].push_back(ask);
tmp[size++] = ask.weight;
}
sort(tmp, tmp + size);
size = unique(tmp, tmp + size) - tmp;
for (i = ; i <= n; i++) {
w[i] = lower_bound(tmp, tmp + size, w[i]) - tmp + ;
for (j = ; j < (int) q[i].size(); j++) {
q[i][j].weight = lower_bound(tmp, tmp + size, q[i][j].weight)
- tmp + ;
}
}
myset.clear();
memset(left, , sizeof(left));
memset(right, , sizeof(right));
for (i = ; i <= n; i++) {
if (tree[i].pre < ) {
dfs(i);
break;
}
}
for (i = ; i < m; i++) {
if (res[i].first < ) {
puts("");
} else {
printf("%d %d\n", res[i].first, res[i].second);
}
}
}
return ;
}
HDU 4606 Occupy Cities
预处理出任意两个城市的最短距离。
若士兵可以从一个城市i到达另一个城市j，且i比j先占领，才连i->j的边。
二分士兵背包的容量，可以得到一个有向图。二分条件是有向图的最小路径覆盖与士兵人数的关系。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 310
#define MAXM 10010
#define oo 123456789
#define eps 1e-6
using namespace std; struct point {
double x, y;
};
struct line {
point a, b;
};
point city[MAXN];
line barr[MAXN]; double dis[MAXN][MAXN];
int first[MAXM], next[MAXM], v[MAXM], e;
int order[MAXN];
int cx[MAXN], cy[MAXN];
bool mk[MAXN]; int dbcmp(double x, double y) {
if (fabs(x - y) < eps) {
return ;
} else {
return x > y ? : -;
}
}
bool zero(double x) {
return fabs(x) < eps;
}
double dist(point p1, point p2) {
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
double xmult(point p1, point p2, point p0) {
return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
int dots_inline(point p1, point p2, point p3) {
return zero(xmult(p1, p2, p3));
}
int same_side(point p1, point p2, line l) {
return xmult(l.a, p1, l.b) * xmult(l.a, p2, l.b) > eps;
}
int same_side(point p1, point p2, point l1, point l2) {
return xmult(l1, p1, l2) * xmult(l1, p2, l2) > eps;
}
inline int dot_online_in(point p, point l1, point l2) {
return zero(xmult(p, l1, l2)) && (l1.x - p.x) * (l2.x - p.x) < eps
&& (l1.y - p.y) * (l2.y - p.y) < eps;
}
int dot_online_in(point p, line l) {
return zero(xmult(p, l.a, l.b)) && (l.a.x - p.x) * (l.b.x - p.x) < eps
&& (l.a.y - p.y) * (l.b.y - p.y) < eps;
}
int intersect_in(point u1, point u2, point v1, point v2) {
if (!dots_inline(u1, u2, v1) || !dots_inline(u1, u2, v2))
return !same_side(u1, u2, v1, v2) && !same_side(v1, v2, u1, u2);
return dot_online_in(u1, v1, v2) || dot_online_in(u2, v1, v2)
|| dot_online_in(v1, u1, u2) || dot_online_in(v2, u1, u2);
} void floyd(int n) {
int i, j, k;
for (k = ; k < n; k++) {
for (i = ; i < n; i++) {
for (j = ; j < n; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
inline void addEdge(int x, int y) {
v[e] = y;
next[e] = first[x];
first[x] = e++;
}
int path(int x) {
int y;
for (int i = first[x]; i != -; i = next[i]) {
y = v[i];
if (!mk[y]) {
mk[y] = true;
if (cy[y] == - || path(cy[y])) {
cx[x] = y;
cy[y] = x;
return ;
}
}
}
return ;
}
int match(int n) {
int res, i;
memset(cx, -, sizeof(cx));
memset(cy, -, sizeof(cy));
for (res = i = ; i < n; i++) {
if (cx[i] == -) {
memset(mk, false, sizeof(mk));
res += path(i);
}
}
return res;
}
int main() {
int T;
int n, m, p;
int i, j, k;
double low, high, mid;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &p);
for (i = ; i < n; i++) {
scanf("%lf%lf", &city[i].x, &city[i].y);
}
for (i = ; i < m; i++) {
scanf("%lf%lf%lf%lf", &barr[i].a.x, &barr[i].a.y, &barr[i].b.x,
&barr[i].b.y);
}
for (i = ; i < n; i++) {
scanf("%d", &order[i]);
order[i]--;
} for (i = ; i < n + m + m; i++) {
for (j = ; j <= i; j++) {
dis[i][j] = dis[j][i] = oo;
}
} for (i = ; i < n; i++) {
dis[i][i] = ;
for (j = i + ; j < n; j++) {
for (k = ; k < m; k++) {
if (intersect_in(city[i], city[j], barr[k].a, barr[k].b)) {
break;
}
}
if (k >= m) {
dis[i][j] = dis[j][i] = dist(city[i], city[j]);
}
}
} for (i = ; i < n; i++) {
for (j = ; j < m; j++) {
for (k = ; k < m; k++) {
if (j == k) {
continue;
}
if (intersect_in(city[i], barr[j].a, barr[k].a,
barr[k].b)) {
break;
}
}
if (k >= m) {
dis[i][n + (j << )] = dis[n + (j << )][i] = dist(city[i],
barr[j].a);
}
for (k = ; k < m; k++) {
if (j == k) {
continue;
}
if (intersect_in(city[i], barr[j].b, barr[k].a,
barr[k].b)) {
break;
}
}
if (k >= m) {
dis[i][n + (j << | )] = dis[n + (j << | )][i] = dist(
city[i], barr[j].b);
} }
} for (i = ; i < m; i++) {
for (j = ; j < i; j++) {
for (k = ; k < m; k++) {
if (k == i || k == j) {
continue;
}
if (intersect_in(barr[i].a, barr[j].a, barr[k].a,
barr[k].b)) {
break;
}
}
if (k >= m) {
dis[n + (i << )][n + (j << )] = dis[n + (j << )][n
+ (i << )] = dist(barr[i].a, barr[j].a);
} for (k = ; k < m; k++) {
if (k == i || k == j) {
continue;
}
if (intersect_in(barr[i].a, barr[j].b, barr[k].a,
barr[k].b)) {
break;
}
}
if (k >= m) {
dis[n + (i << )][n + (j << | )] =
dis[n + (j << | )][n + (i << )] = dist(
barr[i].a, barr[j].b);
} for (k = ; k < m; k++) {
if (k == i || k == j) {
continue;
}
if (intersect_in(barr[i].b, barr[j].a, barr[k].a,
barr[k].b)) {
break;
}
}
if (k >= m) {
dis[n + (i << | )][n + (j << )] = dis[n + (j << )][n
+ (i << | )] = dist(barr[i].b, barr[j].a);
} for (k = ; k < m; k++) {
if (k == i || k == j) {
continue;
}
if (intersect_in(barr[i].b, barr[j].b, barr[k].a,
barr[k].b)) {
break;
}
}
if (k >= m) {
dis[n + (i << | )][n + (j << | )] = dis[n
+ (j << | )][n + (i << | )] = dist(barr[i].b,
barr[j].b);
}
}
} floyd(n + m + m); low = ;
high = oo;
while (dbcmp(low, high) < ) {
e = ;
memset(first, -, sizeof(first));
mid = (low + high) * 0.5;
for (i = ; i < n; i++) {
for (j = i + ; j < n; j++) {
if (dbcmp(dis[order[i]][order[j]], mid) <= ) {
addEdge(order[i], order[j]);
}
}
}
if (n - match(n) > p) {
low = mid;
} else {
high = mid;
}
} printf("%.2lf\n", mid); }
return ;
}
HDU 4607 Park Visit
最长链上的边走一次，其他边都必须走两次。
dp[i][0]表示以i为根的子树的最大深度，dp[i][1]表示以i为根的子树的次大深度。
答案就是max(dp[i][0]+dp[i][1])。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 200010
using namespace std;
int first[MAXN], next[MAXN], v[MAXN], e;
int dp[MAXN][];
bool vis[MAXN];
inline void addEdge(int x, int y) {
v[e] = y;
next[e] = first[x];
first[x] = e++;
}
void dfs(int x) {
vis[x] = true;
dp[x][] = dp[x][] = ;
for (int i = first[x]; i != -; i = next[i]) {
int y = v[i];
if (!vis[y]) {
dfs(y);
if (dp[y][] + >= dp[x][]) {
dp[x][] = dp[x][];
dp[x][] = dp[y][] + ;
} else if (dp[y][] + >= dp[x][]) {
dp[x][] = dp[y][] + ;
}
}
}
}
int main() {
int T;
int n, m;
int i;
int x, y;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
e = ;
memset(first, -, sizeof(first));
for (i = ; i < n; i++) {
scanf("%d%d", &x, &y);
addEdge(x, y);
addEdge(y, x);
}
memset(vis, false, sizeof(vis));
dfs();
x = ;
for (i = ; i <= n; i++) {
x = max(x, dp[i][] + dp[i][]);
}
while (m--) {
scanf("%d", &y);
if (y <= x + ) {
printf("%d\n", y - );
} else {
printf("%d\n", x + * (y - x - ));
}
}
}
return ;
}
HDU 4608I-number
因为y不会比x大多少，所以直接高精度加法暴力。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 200010
using namespace std;
int digit[MAXN];
char str[MAXN];
int main() {
int T;
int i;
int len;
int sum;
scanf("%d", &T);
while (T--) {
scanf(" %s", str);
len = strlen(str);
memset(digit, , sizeof(digit));
for (i = ; str[i]; i++) {
digit[i] = str[i] - '';
}
reverse(digit, digit + len);
while () {
digit[]++;
sum = ;
for (i = ; i < len; i++) {
if (digit[i] > ) {
digit[i] -= ;
digit[i + ]++;
if (i == len - ) {
len++;
}
}
sum += digit[i];
}
if (sum % == ) {
break;
}
}
for (i = len - ; i >= ; i--) {
printf("%d", digit[i]);
}
putchar('\n');
}
return ;
}
HDU 4609 3-idiots
对于多项式乘法，普通做法需要O(n2)的时间复杂度。
而FFT仅需要O(nlogn)的时间复杂度。
把三角形边长作为多项式的指数，边长的出现次数作为多项式的系数。
把两个多项式相乘，即可得到任意两边长之和(i)出现的次数(num[i])。
由于一条边只能使用一次，所以num[arr[i]+arr[i]]--。
由于“先a后b”与“先b后a”属于同一种方案，所以num[i]>>=1。
不妨假设a<=b<=c，要构成三角形只要满足a+b>c。
由于a+b>c不容易统计，但是a+b<=c的方案数很容易统计，枚举c就可以做到。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 400010
#define EPS 1e-8
typedef long long LL;
using namespace std;
double PI = acos(-1.0);
int arr[MAXN];
LL num[MAXN], sum[MAXN];
struct complex {
double r, i;
complex(double _r = , double _i = ) {
r = _r;
i = _i;
}
complex operator+(const complex &b) {
return complex(r + b.r, i + b.i);
}
complex operator-(const complex &b) {
return complex(r - b.r, i - b.i);
}
complex operator*(const complex &b) {
return complex(r * b.r - i * b.i, r * b.i + i * b.r);
}
};
complex x[MAXN];
void change(complex y[], int len) {
for (int i = , j = len >> ; i < len - ; i++) {
if (i < j) {
swap(y[i], y[j]);
}
int k = len >> ;
for (; j >= k; k >>= ) {
j -= k;
}
if (j < k) {
j += k;
}
}
}
void FFT(complex y[], int len, int on) {
change(y, len);
for (int h = ; h <= len; h <<= ) {
complex wn(cos(-on * * PI / h), sin(-on * * PI / h));
for (int j = ; j < len; j += h) {
complex w(, );
for (int k = j; k < j + (h >> ); k++) {
complex u = y[k];
complex t = w * y[k + (h >> )];
y[k] = u + t;
y[k + (h >> )] = u - t;
w = w * wn;
}
}
}
if (on == -) {
for (int i = ; i < len; i++) {
y[i].r /= len;
}
}
}
int main() {
int T;
int n;
int len, len1;
double ans;
scanf("%d", &T);
while (T--) {
memset(num, , sizeof(num));
scanf("%d", &n);
for (int i = ; i < n; i++) {
scanf("%d", &arr[i]);
num[arr[i]]++;
}
sort(arr, arr + n);
len1 = arr[n - ] + ;
for (len = ; len <= (len1 << ); len <<= )
;
for (int i = ; i < len1; i++) {
x[i] = complex(num[i], );
}
for (int i = len1; i < len; i++) {
x[i] = complex(, );
}
FFT(x, len, );
for (int i = ; i < len; i++) {
x[i] = x[i] * x[i];
}
FFT(x, len, -);
for (int i = ; i < len; i++) {
num[i] = (LL) (x[i].r + 0.5 + EPS);
}
for (int i = ; i < n; i++) {
num[arr[i] + arr[i]]--;
}
for (int i = ; i < len; i++) {
num[i] >>= ;
}
sum[] = ;
for (int i = ; i < len; i++) {
sum[i] = sum[i - ] + num[i];
}
ans = ;
for (int i = ; i < n; i++) {
ans += sum[arr[i]];
}
printf("%.7lf\n", - ans * / (n * (n - 1.0) * (n - 2.0)));
}
return ;
}
4610 Cards
通过筛素数可以快速判定素数。
条件1，条件2可以快速解决；
条件3，一个数约数之和可能大于该数的好几倍；
条件4，一个数约束的乘积可能爆longlong，要通过分解素因子，判是否是平方数。
由于N的总数不超过20000，N个数的范围都在106内，所以可以O(sqrt(n))的复杂度处理出约数。
由于条件只有4个，所以K个数中，只有24=16个不同种类的数。因此可以枚举每种数是否出现216，贪心的选择。
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#define oo 987654321
#define MAXP 5000010
#define MAXN 1000010
#define MAXM 4
typedef long long LL;
using namespace std;
bool p[MAXP];
int num[ << MAXM];
int satisfy[MAXN];
int add[MAXM];
vector<int> prime;
void init() {
int i, j;
memset(p, true, sizeof(p));
p[] = p[] = false;
for (i = ; i * i < MAXP; i++) {
if (p[i]) {
for (j = i * i; j < MAXP; j += i) {
p[j] = false;
}
}
}
for (i = ; i < MAXP; i++) {
if (p[i]) {
prime.push_back(i);
}
}
}
bool isSquare(int val, int cnt, int flag) {
map<int, int> mymap;
int i;
for (i = ; prime[i] * prime[i] <= val; i++) {
while (val % prime[i] == ) {
mymap[prime[i]]++;
val /= prime[i];
}
}
if (val > ) {
mymap[val]++;
}
map<int, int>::iterator it;
for (it = mymap.begin(); it != mymap.end(); it++) {
(*it).second *= cnt;
}
for (i = ; prime[i] * prime[i] <= flag; i++) {
while (flag % prime[i] == ) {
mymap[prime[i]]++;
flag /= prime[i];
}
}
if (flag > ) {
mymap[flag]++;
}
for (it = mymap.begin(); it != mymap.end(); it++) {
if ((*it).second & ) {
return false;
}
}
return true;
}
void getSatisfy(int val) {
if (satisfy[val] < ) {
int res = ;
int i;
int amount = ;
int sum = ;
int product = ;
int flag = ;
for (i = ; i * i < val; i++) {
if (val % i == ) {
amount += ;
sum += i + val / i;
product++;
}
}
if (i * i == val) {
amount++;
sum += i;
flag = i;
}
if (p[val]) {
res |= << ;
}
if (p[amount]) {
res |= << ;
}
if (p[sum]) {
res |= << ;
}
if (isSquare(val, product, flag)) {
res |= << ;
}
satisfy[val] = res;
}
}
int numOfOne(int val) {
int res;
for (res = ; val; val >>= ) {
res += val & ;
}
return res;
}
bool cmp(int x, int y) {
return numOfOne(x) > numOfOne(y);
}
int main() {
int T;
int n, k;
int i, j;
int tmp, cnt;
int ans, res;
int sum;
bool flag;
vector<int> g;
init();
memset(satisfy, -, sizeof(satisfy));
scanf("%d", &T);
while (T--) {
memset(num, , sizeof(num));
scanf("%d%d", &n, &k);
for (i = ; i < n; i++) {
scanf("%d%d", &tmp, &cnt);
getSatisfy(tmp);
num[satisfy[tmp]] += cnt; printf("%d", numOfOne(satisfy[tmp]));
if (i < n - ) {
putchar(' ');
} else {
putchar('\n');
}
}
for (i = ; i < MAXM; i++) {
scanf("%d", &add[i]);
}
ans = -oo;
for (i = ; i < ( << ( << MAXM)); i++) {
g.clear();
for (tmp = i, j = ; tmp; tmp >>= , j++) {
if (tmp & ) {
g.push_back(j);
}
}
if ((int) g.size() > k) {
continue;
}
flag = true;
sum = ;
tmp = ;
for (j = ; flag && j < (int) g.size(); j++) {
if (num[g[j]] <= ) {
flag = false;
}
sum += num[g[j]];
tmp |= g[j];
}
if (flag && sum >= k) {
sort(g.begin(), g.end(), cmp);
res = ;
for (j = ; j < MAXM; j++, tmp >>= ) {
if (!(tmp & )) {
res += add[j];
}
}
for (j = ; j < (int) g.size(); j++) {
res += numOfOne(g[j]);
}
tmp = k - g.size();
for (j = ; tmp && j < (int) g.size(); j++) {
cnt = min(tmp, num[g[j]] - );
res += cnt * numOfOne(g[j]);
tmp -= cnt;
}
ans = max(ans, res);
}
}
printf("%d\n", ans);
}
return ;
}