HAOI2010解题报告

解题报告

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

#include 
#include 
#include 
#include 
#include 
#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 
#include 
#include 
#include 
#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 
#include 
#include 
#include 
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 
#include 
#include 
#include 
#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 
#include 
#include 
#include 
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的计数题真的很烦。 还是自己太弱,连最小费用最大流都不会写,感觉吃枣药丸。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理