漂亮字符串
题目分析
如果(maxO == 0) 说明只有(X)， 答案就是(maxX)
如果(X)不够用，说明每次都是放(maxO)个(O)，用一个(X)隔开 (OOOOOXOOOOOX cdots)
此时有(countO ge (countX + 1) * maxO)
因此，最大是 (countX + (countX + 1) * maxO)
注意更新
代码实现
#include <iostream>
#include <cstdio>
long long CountO, CountX, maxO, maxX;
int main() {
freopen("bs.in","r",stdin);
freopen("bs.out","w",stdout);
while (scanf("%lld%lld%lld%lld", &CountO, &CountX, &maxO, &maxX)) {
maxX = std::min(maxX, CountX);
maxO = std::min(maxO, CountO);
if (maxO == 0)
printf("%lld
", maxX);
else if (maxX == 0)
printf("%lld
", maxO);
else if (CountO > (CountX + 1) * maxO)
printf("%lld
",CountX + (CountX + 1) * maxO);
else if (CountX > (CountO + 1) * maxX)
printf("%lld
", CountO + (CountO + 1) * maxX);
else
printf("%lld
", CountX + CountO);
}
return 0;
}
Set
题目分析
有倍数关系的加入同一集合
一个线性筛 + 并查集 （有倍数关系）
代码实现
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 100001;
bool pflag[maxn];
int prime[maxn>>1];
int fa[maxn];
int A, B;
int prime_cnt = 0;
int ans;
int P;
inline void Prime_Filter() {
for (int i = 2; i <= B; ++ i){
if(!pflag[i]) prime[ ++ prime_cnt] = i;
for (int j = 1; j <= prime_cnt && prime[j] * i <= B; ++ j){
pflag[prime[j] * i] = true;
if ( i % prime[j] == 0) break;
}
}
}
inline int getRoot(int x) {
if (x == fa[x]) return x;
return fa[x] = getRoot(fa[x]);
}
bool judgeEqual(int x,int y) {
return getRoot(x)==getRoot(y);
}
inline void join(int x,int y) {
x = getRoot(x), y = getRoot(y);
fa[y] = x;
}
inline void init() {
cin >> A >> B >> P;
ans = 0;
for (int i = 1; i <= B; ++ i) {
fa[i] = i;
}
Prime_Filter();
}
inline void solve() {
int begin = 1;
for (; prime[begin] < P; ++ begin);
for (int k = prime[begin]; k <= B && k > 1; k = prime[++ begin]){
for (int i = A/k*k, start = i; i <= B; start = i, i += k) {
if (i < A || start < A) continue;
if(!judgeEqual(i,start)) {
join(i,start);
}
}
}
for (int i =A; i <= B; ++ i)
if (fa[i] == i) ans ++;
}
int main() {
freopen("set.in","r",stdin);
freopen("set.out","w",stdout);
init();
solve();
cout << ans;
}
Prison
题目分析
动态规划经典题目，考的时候没有想出来优化，A得很水。。。。
用(DP[i][j])表示在([i,j])区间所有该被释放的人都被释放的最小支付代价。
若是释放(k)，那么代价为(DP[i][k-1]+DP[k+1][j]+(j-i))
这里的(sum[i])指的是前i个位置中有多少犯人无法被释放。
代码实现
#include <iostream>
#include <cstdio>
#include <algorithm>
const int MAX = 1010;
const int Inf = 0x7fffffff;
int n, m, a[MAX], sum[MAX], DP[MAX][MAX];
inline void init() {
for (int i = 0; i < MAX; ++ i) {
std::fill(DP[i], DP[i] + MAX, Inf);
DP[i][i] = 0;
}
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++ i)
scanf("%d", &a[i]);
std::sort(a + 1, a + m + 1);
for (int i = 1; i <= m; ++ i)
sum[i] = a[i] - a[i - 1] - 1;
sum[m + 1] = n - a[m];
for (int i = 1; i <= m + 1; ++ i)
sum[i] = sum[i] + sum[i-1];
}
inline void solve() {
for (int i = m + 1; i >= 1; -- i)
for (int j = i + 1; j <= m + 1; ++ j)
for (int k = i; k < j; ++ k)
DP[i][j] = std::min(DP[i][j], DP[i][k] + DP[k + 1][j] + sum[j] - sum[i - 1] + j - i - 1);
}
int main() {
freopen("prison.in","r",stdin);
freopen("prison.out","w",stdout);
init();
solve();
printf("%d
", DP[1][m+1]);
return 0;
}
Tree
题目分析
难度：省选/省选+
最大匹配 : 在一个无向图中，定义一条边覆盖的点为这条边的两个端点。找到一个边集S包含最多的边，使得这个边集覆盖到的所有顶点中的每个顶点只被一条边覆盖。S的大小叫做图的最大匹配。
我们发现，一颗树的最大匹配取决于它的子树的匹配情况，因此很容易想到以子树为阶段，当前节点是否已经匹配为状态进行DP
首先考虑求最大匹配是多少
记(f[i][0/1])表示以(i)为根的子树,当前节点是/否已经匹配的最大匹配数，用(g[i][0/1])表示方案数
记(A_i)为(i)节点儿子的集合
显然对于 ((j in A_i))我们有如下转移
[f[i][0] = sum max{f[j][0], f[j][1]},
]
[g[i][0] = prod_{f[j][0] > f[j][1]}g[j][0] imes prod_{f[j][0] > f[j][1]} g[j][1] imes prod_{f[j][0] == f[j][1]} (g[j][0] + g[j][1])
]
如果当前节点要选的话，那就是一个儿子必须要连，剩下的取最大值
[f[i][1] = max{f[i][0] - max(f[j][0], f[j][1])+f[j][0]}+1
]
(g[i][1]) 的转移，类似于(g[i][0])的求法，分三种情况乘在一起就可以了
高精度DP一下吧(此题代码超级毒瘤)
我先放一个简单的
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 1000
#define HMAX (MAX*4)
#define DMAX (MAX/10)
#define BASE 1000
struct number {
int digits;
int values[DMAX];
};
char names[HMAX][11];
int next_sibling[HMAX];
int first_subord[HMAX];
int withn[HMAX];
int woutn[HMAX];
int active[HMAX];
int root;
struct number with[HMAX];
struct number wout[HMAX];
void bug(void) {
fprintf(stderr,"There is a bug walking around...
");
exit(0);
}
void zero(struct number *result) {
result->digits=0;
}
void unit(struct number *result) {
result->digits=1;
result->values[0]=1;
}
void add(struct number *result, struct number *what) {
int k;
while (result->digits<what->digits) result->values[result->digits++]=0;
for (k=0; k<what->digits; k++) {
if (k&&(result->values[k-1]>=BASE)) {
result->values[k]+=result->values[k-1]/BASE;
result->values[k-1]%=BASE;
}
result->values[k]+=what->values[k];
}
if (!k) return;
for (; (result->values[k-1]>=BASE)&&(k<result->digits); k++) {
result->values[k]+=result->values[k-1]/BASE;
result->values[k-1]%=BASE;
}
if (result->values[k-1]>=BASE) {
if (k!=result->digits) bug();
result->values[k]=result->values[k-1]/BASE;
result->values[k-1]%=BASE;
result->digits++;
}
}
void mul(struct number *result, struct number *what) {
int i,j;
struct number aux,what2;
zero(&what2);
add(&what2,result); // copy
zero(result);
for (i=0; i<what->digits; i++) {
for (j=0; j<what2.digits; j++) aux.values[i+j]=what->values[i]*what2.values[j];
for (j=0; j<i; j++) aux.values[j]=0;
aux.digits=what2.digits+i;
add(result,&aux);
}
}
void print(struct number *what) {
int i;
if (!what->digits) {
printf("0");
exit(0);
}
printf("%d",what->values[what->digits-1]);
for (i=what->digits-2; i>=0; i--) printf("%03d",what->values[i]);
}
int hash(char *name) {
int i,r;
for (i=0, r=0; name[i]; i++) {
r=(13*r+name[i]-'0')%HMAX;
}
return r;
}
int create(char *name) {
int i=hash(name);
while (active[i]) {
i++;
if (i>=HMAX) i=0;
}
active[i]=1;
strcpy(names[i],name);
next_sibling[i]=-1;
first_subord[i]=-1;
return i;
}
int find(char *name) {
int i=hash(name);
while (strcmp(name,names[i])&&active[i]) {
i++;
if (i>=HMAX) i=0;
}
if (!active[i]) return -1;
return i;
}
void read_in(void) {
int i,j,N,k,children;
char name[11];
root=create("1");
scanf("%d",&N);
for (i=0; i<N; i++) {
scanf("%s",name);
k=find(name);
scanf("%d",&children);
while (children--) {
scanf("%s",name);
j=create(name);
next_sibling[j]=first_subord[k];
first_subord[k]=j;
}
} // endfor i
}
void compute(int which) {
int i,k;
struct number aux;
for (k=first_subord[which]; k!=-1; k=next_sibling[k]) compute(k);
woutn[which]=0;
unit(&wout[which]);
for (k=first_subord[which]; k!=-1; k=next_sibling[k]) {
woutn[which]+=withn[k];
mul(&wout[which],&with[k]);
}
if (first_subord[which]==-1) {
withn[which]=0;
unit(&with[which]);
return;
}
for (k=first_subord[which]; k!=-1; k=next_sibling[k])
if (withn[k]==woutn[k]) break;
if (k==-1) {
withn[which]=woutn[which];
zero(&with[which]);
for (k=first_subord[which]; k!=-1; k=next_sibling[k]) {
unit(&aux);
for (i=first_subord[which]; i!=-1; i=next_sibling[i])
mul(&aux,i==k?&wout[i]:&with[i]);
add(&with[which],&aux);
} // endfor k
add(&with[which],&wout[which]);
} else {
withn[which]=woutn[which]+1;
zero(&with[which]);
for (k=first_subord[which]; k!=-1; k=next_sibling[k]) {
if (withn[k]!=woutn[k]) continue;
unit(&aux);
for (i=first_subord[which]; i!=-1; i=next_sibling[i])
mul(&aux,i==k?&wout[i]:&with[i]);
add(&with[which],&aux);
} // endfor k
} // endif k==-1
}
int main(void) {
read_in();
compute(root);
printf("%d
",withn[root]);
print(&with[root]);
printf("
");
return 0;
}