HAOI2010解题报告 – Ys.T's Blog

woc...这Onedrive好辣鸡啊。。。访问速度真是不敢恭维，强烈建议下载后查看此PPT。
算法什么的PPT里都有，直接贴代码吧。
T1:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#define LL long long
using namespace std;
int a[55], cnt[10];
int len;
void get_line(int *t) {
	char tmp = getchar();
	while (tmp < '0' || tmp > '9') tmp = getchar();
	while (tmp <= '9' && tmp >= '0') {
		t[++len] = tmp - '0';
		cnt[t[len]]++;
		tmp = getchar();
	}
}
LL calc() {
	LL ans = 1;
	int num = 0;
	for (int i = 0; i <= 9; i++) {
		for (int j = 1; j <= cnt[i]; j++) {
			ans *= (++num);
			ans /= j;
		}
	}
	return ans;
}
int main() {
#ifndef LOCAL
	freopen("perm.in", "r", stdin);
	freopen("perm.out", "w", stdout);
#endif
	get_line(a);
	int num;
	LL ans = 0;
	for (int i = 1; i <= len; i++) {
		num = a[i];
		for (int j = 0; j < num; j++) {
			if (!cnt[j]) continue;
			cnt[j]--;
			ans += calc();
			cnt[j]++;
		}
		cnt[num]--;
	}
	printf("%lld\n", ans);
	return 0;
}

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#define LL long long

using namespace std;

int a[55], cnt[10];

int len;

void get_line(int *t) {

char tmp = getchar();

while (tmp < '0' || tmp > '9') tmp = getchar();

while (tmp <= '9' && tmp >= '0') {

t[++len] = tmp - '0';

cnt[t[len]]++;

tmp = getchar();

}

LL calc() {

LL ans = 1;

int num = 0;

for (int i = 0; i <= 9; i++) {

for (int j = 1; j <= cnt[i]; j++) {

ans *= (++num);

ans /= j;

}

return ans;

}

int main() {

#ifndef LOCAL

freopen("perm.in", "r", stdin);

freopen("perm.out", "w", stdout);

#endif

get_line(a);

int num;

LL ans = 0;

for (int i = 1; i <= len; i++) {

num = a[i];

for (int j = 0; j < num; j++) {

if (!cnt[j]) continue;

cnt[j]--;

ans += calc();

cnt[j]++;

}

cnt[num]--;

}

printf("%lld\n", ans);

return 0;

}

T2:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std;
const int MX = 50005;
int m, b, h, n;
int a[MX], hi[MX], cost[MX];
int sum, tot;
class node{
  public:
	  int c, tar;
}ns[MX];
inline bool cmp(node a, node b) {
	return a.c < b.c;
}
const inline int get_num() {
	int aa = 0;
	char tmp = getchar();
	while (tmp < '0' || tmp > '9') tmp = getchar();
	while (tmp <= '9' && tmp >= '0') {
		aa = aa * 10 + tmp - '0';
		tmp = getchar();
	}
	return aa;
}
int Main() {
#ifndef LOCAL
	freopen("factory1.in", "r", stdin);
	freopen("factory1.out", "w", stdout);
#endif
	m = get_num();
	b = get_num();
	h = get_num();
	n = get_num();
	for (int i = 1; i <= m; i++) {
		a[i] = get_num();
		sum += a[i];
	}
	for (int i = 1; i <= n; i++) {
		hi[i] = get_num();
	}
	for (int i = 1; i <= m; i++) {
		cost[i] = get_num();
		tot += cost[i] * a[i];
	}
	int pos;
	LL ans = 0x7fffffff, now, le;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ns[j].tar = j;
			ns[j].c = get_num() - cost[j];
		}
		sort(ns + 1, ns + m + 1, cmp);
		now = tot, le = sum - b;
		for (int j = 1; j <= m; j++) {
			if (le > a[ns[j].tar]) {
				le -= a[ns[j].tar];
				now += a[ns[j].tar] * ns[j].c;
			} else {
				now += le * ns[j].c;
				break;
			}
		}
		if (now + hi[i] < ans) {
			ans = now + hi[i];
			pos = i;
		}
	}
	printf("%d\n%lld\n", pos, ans + h);
	return 0;
}
int AA = Main();
int main() {;}

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define LL long long

using namespace std;

const int MX = 50005;

int m, b, h, n;

int a[MX], hi[MX], cost[MX];

int sum, tot;

class node{

public:

int c, tar;

}ns[MX];

inline bool cmp(node a, node b) {

return a.c < b.c;

}

const inline int get_num() {

int aa = 0;

char tmp = getchar();

while (tmp < '0' || tmp > '9') tmp = getchar();

while (tmp <= '9' && tmp >= '0') {

aa = aa * 10 + tmp - '0';

tmp = getchar();

}

return aa;

}

int Main() {

#ifndef LOCAL

freopen("factory1.in", "r", stdin);

freopen("factory1.out", "w", stdout);

#endif

m = get_num();

b = get_num();

h = get_num();

n = get_num();

for (int i = 1; i <= m; i++) {

a[i] = get_num();

sum += a[i];

}

for (int i = 1; i <= n; i++) {

hi[i] = get_num();

}

for (int i = 1; i <= m; i++) {

cost[i] = get_num();

tot += cost[i] * a[i];

}

int pos;

LL ans = 0x7fffffff, now, le;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= m; j++) {

ns[j].tar = j;

ns[j].c = get_num() - cost[j];

}

sort(ns + 1, ns + m + 1, cmp);

now = tot, le = sum - b;

for (int j = 1; j <= m; j++) {

if (le > a[ns[j].tar]) {

le -= a[ns[j].tar];

now += a[ns[j].tar] * ns[j].c;

} else {

now += le * ns[j].c;

break;

}

if (now + hi[i] < ans) {

ans = now + hi[i];

pos = i;

}

printf("%d\n%lld\n", pos, ans + h);

return 0;

}

int AA = Main();

int main() {;}

T3:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MX = 205;
int m, n;
int dfn[MX], low[MX];
int v[MX], w[MX];
int suv[MX], suw[MX];
int in[MX];
int f[105][505];
class edge{
  public:
	  int to, ne;
}e[MX], e2[MX];
int _tot, _head[MX], tot, head[MX];
class stack_{
  private:
	  int st[MX], tp, _in[MX];
  public:
	  bool instack(int x) {
		  return _in[x];
	  }
	  void push(int x) {
		  st[++tp] = x;
		  _in[x]++;
	  }
	  void pop() {
		  _in[st[tp--]]--;
	  }
	  int top() {
		  return st[tp];
	  }
}s;
void addedge(int a, int b) {
	//e[++tot].fr = a;
	e[++tot].to = b;
	e[tot].ne = head[a];
	head[a] = tot;
}
void addedge2(int a, int b) {
	in[b]++;
	//e2[++tot].fr = a;
	e2[++tot].to = b;
	e2[tot].ne = _head[a];
	_head[a] = tot;
}
int belong[MX];
int cnt, kcnt;
void tarjan(int x) {
	int now = 0;
	dfn[x] = low[x] = ++cnt;
	s.push(x);
	for (int i = head[x]; i; i = e[i].ne) {
		if (!dfn[e[i].to]) {
			tarjan(e[i].to);
			low[x] = min(low[x], low[e[i].to]);
		} else if (s.instack(e[i].to)) {
			low[x] = min(low[x], dfn[e[i].to]);
		}
	}
	if (low[x] == dfn[x]) {
		kcnt++;
		while (now != x) {
			now = s.top();
			s.pop();
			belong[now] = kcnt;
			suv[kcnt] += v[now];
			suw[kcnt] += w[now];
		}
	}
}
void rebuild() {
	tot = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = head[i]; j; j = e[j].ne) {
			if (belong[e[j].to] != belong[i]) {
				addedge2(belong[i], belong[e[j].to]);
			}
		}
	}
}
void dp(int x) {
	for (int i = _head[x]; i; i = e2[i].ne) {
		dp(e2[i].to);
		for (int j = m - suw[x]; j >= 0; j--) {
			for (int k = 0; k <= j; k++) {
				f[x][j] = max(f[x][j], f[x][k] + f[e2[i].to][j - k]);
			}
		}
	}
	for (int i = m; i >= 0; i--) {
		if (i >= suw[x]) f[x][i] = f[x][i - suw[x]] + suv[x];
		else f[x][i] = 0;
	}
}
int main() {
#ifndef LOCAL
	freopen("install.in", "r", stdin);
	freopen("install.out", "w", stdout);
#endif
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%d", &v[i]);
	}
	int x;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		if (x) {
			addedge(x, i);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) tarjan(i);
	}
	rebuild();
	for (int i = 1; i <= kcnt; i++) {
		if (!in[i]) {
			addedge2(kcnt + 1, i);
		}
	}
	dp(kcnt + 1);
	printf("%d\n", f[kcnt + 1][m]);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int MX = 205;

int m, n;

int dfn[MX], low[MX];

int v[MX], w[MX];

int suv[MX], suw[MX];

int in[MX];

int f[105][505];

class edge{

public:

int to, ne;

}e[MX], e2[MX];

int _tot, _head[MX], tot, head[MX];

class stack_{

private:

int st[MX], tp, _in[MX];

public:

bool instack(int x) {

return _in[x];

}

void push(int x) {

st[++tp] = x;

_in[x]++;

}

void pop() {

_in[st[tp--]]--;

}

int top() {

return st[tp];

}

}s;

void addedge(int a, int b) {

//e[++tot].fr = a;

e[++tot].to = b;

e[tot].ne = head[a];

head[a] = tot;

}

void addedge2(int a, int b) {

in[b]++;

//e2[++tot].fr = a;

e2[++tot].to = b;

e2[tot].ne = _head[a];

_head[a] = tot;

}

int belong[MX];

int cnt, kcnt;

void tarjan(int x) {

int now = 0;

dfn[x] = low[x] = ++cnt;

s.push(x);

for (int i = head[x]; i; i = e[i].ne) {

if (!dfn[e[i].to]) {

tarjan(e[i].to);

low[x] = min(low[x], low[e[i].to]);

} else if (s.instack(e[i].to)) {

low[x] = min(low[x], dfn[e[i].to]);

}

if (low[x] == dfn[x]) {

kcnt++;

while (now != x) {

now = s.top();

s.pop();

belong[now] = kcnt;

suv[kcnt] += v[now];

suw[kcnt] += w[now];

}

void rebuild() {

tot = 0;

for (int i = 1; i <= n; i++) {

for (int j = head[i]; j; j = e[j].ne) {

if (belong[e[j].to] != belong[i]) {

addedge2(belong[i], belong[e[j].to]);

}

void dp(int x) {

for (int i = _head[x]; i; i = e2[i].ne) {

dp(e2[i].to);

for (int j = m - suw[x]; j >= 0; j--) {

for (int k = 0; k <= j; k++) {

f[x][j] = max(f[x][j], f[x][k] + f[e2[i].to][j - k]);

}

for (int i = m; i >= 0; i--) {

if (i >= suw[x]) f[x][i] = f[x][i - suw[x]] + suv[x];

else f[x][i] = 0;

}

int main() {

#ifndef LOCAL

freopen("install.in", "r", stdin);

freopen("install.out", "w", stdout);

#endif

scanf("%d%d", &n, &m);

for (int i = 1; i <= n; i++) {

scanf("%d", &w[i]);

}

for (int i = 1; i <= n; i++) {

scanf("%d", &v[i]);

}

int x;

for (int i = 1; i <= n; i++) {

scanf("%d", &x);

if (x) {

addedge(x, i);

}

for (int i = 1; i <= n; i++) {

if (!dfn[i]) tarjan(i);

}

rebuild();

for (int i = 1; i <= kcnt; i++) {

if (!in[i]) {

addedge2(kcnt + 1, i);

}

dp(kcnt + 1);

printf("%d\n", f[kcnt + 1][m]);

return 0;

}

T4:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std;
const int chenyao = 1e8;
int f[5005][5005], g[5005][5005];
char a[5005], b[5005];
int l1, l2;
int get_line(char *tar) {
	int len = 0;
	char tmp = getchar();
	while (tmp < 'A' || tmp > 'Z') tmp = getchar();
	while (tmp != '.') {
		tar[++len] = tmp;
		tmp = getchar();
	}
	return len;
}
int main() {
#ifndef LOCAL
	freopen("lcs.in", "r", stdin);
	freopen("lcs.out", "w", stdout);
#endif
	l1 = get_line(a);
	l2 = get_line(b);
	for (int i = 0; i < max(l1, l2); i++) g[0][i] = g[i][0] = 1;
	for (int i = 1; i <= l1; i++) {
		for (int j = 1; j <= l2; j++) {
			if (a[i] == b[j]) {
				f[i][j] = f[i - 1][j - 1] + 1;
				g[i][j] += g[i - 1][j - 1];
				if (f[i][j - 1] == f[i][j]) g[i][j] += g[i][j - 1];
				if (f[i - 1][j] == f[i][j]) g[i][j] += g[i - 1][j];
			} else {
				f[i][j] = max(f[i][j - 1], f[i - 1][j]);
				if (f[i - 1][j] == f[i][j]) g[i][j] += g[i - 1][j];
				if (f[i][j - 1] == f[i][j]) g[i][j] += g[i][j - 1];
				if (f[i][j - 1] == f[i - 1][j] && f[i][j] == f[i - 1][j - 1]) g[i][j] -= g[i - 1][j - 1];
			}
			g[i][j] = g[i][j] % chenyao;
		}
	}
	printf("%d\n%d\n", f[l1][l2], g[l1][l2]);
}

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define LL long long

using namespace std;

const int chenyao = 1e8;

int f[5005][5005], g[5005][5005];

char a[5005], b[5005];

int l1, l2;

int get_line(char *tar) {

int len = 0;

char tmp = getchar();

while (tmp < 'A' || tmp > 'Z') tmp = getchar();

while (tmp != '.') {

tar[++len] = tmp;

tmp = getchar();

}

return len;

}

int main() {

#ifndef LOCAL

freopen("lcs.in", "r", stdin);

freopen("lcs.out", "w", stdout);

#endif

l1 = get_line(a);

l2 = get_line(b);

for (int i = 0; i < max(l1, l2); i++) g[0][i] = g[i][0] = 1;

for (int i = 1; i <= l1; i++) {

for (int j = 1; j <= l2; j++) {

if (a[i] == b[j]) {

f[i][j] = f[i - 1][j - 1] + 1;

g[i][j] += g[i - 1][j - 1];

if (f[i][j - 1] == f[i][j]) g[i][j] += g[i][j - 1];

if (f[i - 1][j] == f[i][j]) g[i][j] += g[i - 1][j];

} else {

f[i][j] = max(f[i][j - 1], f[i - 1][j]);

if (f[i - 1][j] == f[i][j]) g[i][j] += g[i - 1][j];

if (f[i][j - 1] == f[i][j]) g[i][j] += g[i][j - 1];

if (f[i][j - 1] == f[i - 1][j] && f[i][j] == f[i - 1][j - 1]) g[i][j] -= g[i - 1][j - 1];

}

g[i][j] = g[i][j] % chenyao;

}

printf("%d\n%d\n", f[l1][l2], g[l1][l2]);

}

T5:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 1e9 + 7;
int n, m, s;
int f[55][10005];
int u[55];
int d[55];
int main() {
#ifndef LOCAL
	freopen("order.in", "r", stdin);
	freopen("order.out", "w", stdout);
#endif
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &u[i]);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%d", &d[i]);
	}
	for (int i = 1; i <= s; i++) f[0][i] = INF;
	for (int i = 1; i <= n; i++) {
		int tmp = INF, k = 0;
		for (int j = 0; j <= s; j++) {
			for (; k <= min(u[i] + j, s); k++) tmp = min(tmp, f[i - 1][k] + k * (m - d[i]));
			f[i][j] = tmp + (u[i] + j) * d[i];
		}
	}
	printf("%d\n", f[n][0]);
	return 0;
}

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int INF = 1e9 + 7;

int n, m, s;

int f[55][10005];

int u[55];

int d[55];

int main() {

#ifndef LOCAL

freopen("order.in", "r", stdin);

freopen("order.out", "w", stdout);

#endif

scanf("%d%d%d", &n, &m, &s);

for (int i = 1; i <= n; i++) {

scanf("%d", &u[i]);

}

for (int i = 1; i <= n; i++) {

scanf("%d", &d[i]);

}

for (int i = 1; i <= s; i++) f[0][i] = INF;

for (int i = 1; i <= n; i++) {

int tmp = INF, k = 0;

for (int j = 0; j <= s; j++) {

for (; k <= min(u[i] + j, s); k++) tmp = min(tmp, f[i - 1][k] + k * (m - d[i]));

f[i][j] = tmp + (u[i] + j) * d[i];

}

printf("%d\n", f[n][0]);

return 0;

}

总结一下，HAOI2010的题不算很难，但是奇怪的DP和需要用到DP的计数题真的很烦。
还是自己太弱，连最小费用最大流都不会写，感觉吃枣药丸。

发表回复 取消回复

发表回复取消回复