10.14
10.13
Bzoj5004开锁魔法II
#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define sep(i, x, y) for(i = x;i <= y;++ i)
#define rep(i , x, y) for(int i = x;i <= y;++ i)
inline int gi() {
int x = 0,f = 1;char c = gc;
while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}
return x * f;
}
const int maxN = 300 + 7;
const int maxM = 600 + 7;
int to[maxN];
bool vis[maxN];
int ska[maxN] , low[maxN] , dfn[maxN], belong[maxN], size[maxN], cnt, top, num;
int n, m;
void dfs(int u) {
dfn[u] = low[u] = ++ cnt;
ska[++ top] = u;
int v = to[u];
if(!dfn[v]) {
dfs(v);
low[u] = min(low[v],low[u]);
}
else if(!belong[v]) low[u] = min(low[v],dfn[u]);
if(dfn[u] == low[u]) {
++ num;
while(ska[top] != u) belong[ska[top --]] = num,size[num] ++;
belong[ska[top --]] = num;
size[num] ++;
}
return ;
}
long double f[maxN][maxN], C[maxN][maxN];
void Pre() {
rep(i , 1 , n) if(!vis[i]) dfs(i);
C[0][0] = 1;
rep(i , 1, n) {
C[i][0] = 1;
rep(j , 1, i) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
}
void Solve() {
f[0][0] = 1.0;
rep(i , 1, num) {
rep(j , 1, m) {
rep(k , 1, size[i]) {
if(j - k >= 0) f[i][j] += f[i - 1][j - k] * C[size[i]][k];
}
}
}
return ;
}
int main() {
n = gi() , m = gi();
rep(i , 1, n) {
int x = gi();
to[i] = x;
}
Solve();
printf("%lf",f[n][m] / C[n][m]);
return 0;
}
BZOJ5091 摘苹果
#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define sep(i, x, y) for(i = x;i <= y;++ i)
#define rep(i , x, y) for(int i = x;i <= y;++ i)
inline int gi() {
int x = 0,f = 1;char c = gc;
while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}
return x * f;
}
const int maxN = 1e6 + 7;
int d[maxN] , a[maxN];
int main() {
int n = gi(), m = gi(), k = gi();
rep(i , 1, n) a[i] = gi();
rep(i , 1, m) {
int u = gi() , v = gi();
d[u] ++;d[v] ++;
}
double ans = 0;
rep(i , 1, n) {
ans += 1.0 * d[i] * a[i] / (2.0 * m);
}
ans *= k;
cout << ans;
return 0;
}
10.4
BZOJ4247 挂饰
const int maxN = 2e3 + 7;
struct Node{
int a , b;
}a[maxN];
int f[maxN][maxN];
bool cmp(Node a, Node b) {
return a.a > b.a;
}
signed main() {
int n = gi();
rep(i , 1, n) {
a[i].a = gi();
a[i].b = gi();
}
sort(a + 1,a + n + 1, cmp);
int ans = 0;
memset(f,-0x3f,sizeof(f));
f[0][1] = 0;
rep(i , 1, n) {
rep(j , 0, n) {
f[i][j] = max(f[i - 1][j] , f[i - 1][max(j - a[i].a , 0LL) + 1] + a[i].b);
}
}
for(int i = 0;i <= n;++ i) ans = max(ans , f[n][i]);
printf("%lld",ans);
return 0;
}
/*
5
0 4
2 -2
1 -1
0 1
0 3
*/
BZOJ 1003 [ZJOI2006]物流运输
const int maxM = 1e5 + 7;
const int maxN = 10000 + 7;
const int inf = 1000000000;
struct Node{
int v , nex, w;
}Map[maxM];
int head[maxN] , num;
void add_Node(int u , int v, int w) {
Map[++ num] = (Node) {v , head[u], w};
head[u] = num;
}
PII a[maxN];
int b[maxN];
int f[maxN],d;
int n, m, k, e;
bool vis[maxN],v[maxN];
int dis[maxN];
queue<int> q;
bool ok[1001][1001];
int cost(int l , int r) {
rep(i , 1, m) dis[i] = inf , v[i] = 0,vis[i] = true;
rep(i , 1, d) {
rep(j , l ,r) {
if(ok[b[i]][j]) {
vis[b[i]] = false;
break;
}
}
}
q.push(1);
dis[1] = 0;v[1] = 1;
while(!q.empty()) {
int now = q.front();q.pop();
v[now] = 0;
for(int i = head[now];i;i = Map[i].nex) {
int y = Map[i].v;
if(!vis[y]) continue;
if(dis[y] > dis[now] + Map[i].w) {
dis[Map[i].v] = dis[now] + Map[i].w;
if(!v[y]) {
v[y] = true;
q.push(y);
}
}
}
}
if(dis[m] == inf) return inf;
return dis[m] * (r - l + 1);
}
int main() {
memset(f , 0x3f, sizeof(f));
n = gi() , m = gi(), k = gi(), e = gi();
while(e --) {
int u = gi() , v = gi(), w = gi();
add_Node(u , v, w);
add_Node(v , u, w);
}
f[0] = 0;
d = gi();
for(int i = 1;i <= d;++ i) {
b[i] = gi(); int t1 = gi() , t2 = gi();
rep(j , t1, t2) ok[b[i]][j] = true;
}
rep(i , 1, n) {
f[i] = cost(1 , i);
rep(j , 1, i - 1) {
f[i] = min(f[j] + cost(j + 1, i) + k ,f[i]);
}
}
printf("%d",f[n]);
return 0;
}