前言

本篇博客,笔者只会对若干较简单的题目直接给出思路要点
其他需要详细记录的题目,笔者会另开文章进行记录。

做题记录

BZOJ1601 [Usaco2008 Oct]灌水
BZOJ1601
若不考虑新开水库的问题就是一个最小生成树,抽象出一个虚拟节点$0$,将新开水库视作从$0$连到$i$的操作,做一遍最小生成树即可。
时间复杂度 $O(n)$

#include <bits/stdc++.h>
#define For(i, s, t) for (int i = s; i <= t; i++)
#define eb emplace_back
#define mp make_pair

using namespace std;

const int N = 305;
const int M = N * N + N;

struct Ed {
  int u, v, w;
} ed[M];

int n;
int fa[N];

int main() {
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
#endif
  cin >> n;
  int cnt = 0;
  For (i, 1, n) {
    ++cnt;
    cin >> ed[cnt].w;
    ed[i].u = n + 1, ed[i].v = i;
  }
  For (i, 1, n) {
    For (j, 1, n) {
      cnt++;
      ed[cnt].u = i, ed[cnt].v = j;
      cin >> ed[cnt].w;
    }
  }
  sort(ed + 1, ed + 1 + cnt, [](Ed a, Ed b) {
    return a.w < b.w;
  });
  For (i, 1, n + 1) {
    fa[i] = i;
  }
  function<int(int)> get;
  get = [&](int x) {
    return x == fa[x] ? fa[x] : fa[x] = get(fa[x]);
  };
  long long ans = 0;
  For (i, 1, cnt) {
    int p = get(ed[i].u), q = get(ed[i].v);
    if (p != q) {
      fa[p] = q;
      ans += ed[i].w;
    }
  }
  cout << ans << '\n';
  return 0;
}

BZOJ1192 [HNOI2006]鬼谷子的钱袋
BZOJ1192
考虑二进制的表示数的性质,显然可得答案为 $\lceil log_2 n\rceil$
时间复杂度 $O(1)$

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
#endif
  long long n;
  cin >> n;
  int ans = ceil(log2(n));
  cout << ans << '\n';
  return 0;
}

BZOJ1303 [CQOI2009]中位数图
BZOJ1303
考虑答案的构成,原来的序列按照$b$的位置一分为二,将$>b$和$<b$的连续串统计出来,遍历一遍即可。
时间复杂度 $O(nlog_2n)$。

#include <bits/stdc++.h>
#define For(i, s, t) for (int i = s; i <= t; i++)
#define eb emplace_back
#define mp make_pair

using namespace std;

const int N = 100005;

int n, b;
int a[N];
int buk[N];
unordered_map<int, int> cnt[2];

int main() {
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
#endif
  cin >> n >> b;
  int md = 0;
  For (i, 1, n) {
    cin >> a[i];
    if (a[i] == b) {
      md = i;
    }
  }
  for (int i = md - 1; i >= 1; i--) {
    if (a[i] > b) {
      buk[i] = buk[i + 1] + 1;
    } else {
      buk[i] = buk[i + 1] - 1;
    }
    cnt[0][buk[i]]++;
  }
  For (i, md + 1, n) {
    if (a[i] > b) {
      buk[i] = buk[i - 1] + 1;
    } else {
      buk[i] = buk[i - 1] - 1;
    }
    cnt[1][buk[i]]++;
  }
  int ans = 0;
  For (i, 1, n) {
    if (buk[i] == 0) {
      ans++;
    }
  }
  For (i, -100000, 100000) {
    ans += cnt[0][i] * cnt[1][-i];
  }
  cout << ans << '\n';
  return 0;
}

BZOJ3903 玉蟾宫
BZOJ3903
考虑单调栈,先预处理出每个点向上扩展的边界。
考虑维护一个高度单调递增的栈,如果入栈的元素高度低于栈顶,则一边计算答案一边删去多余部分的矩形。
时间复杂度 $O(n)$。

#include <bits/stdc++.h>
#define For(i, s, t) for (int i = s; i <= t; i++)
#define inf 0x3f3f3f3f
#define mp make_pair

using namespace std;

typedef pair<int, int> pii;

const int N = 1e3 + 5;

int a[N][N], ly[N][N];
pii stk[N];
int ans, top, n, m;

template <class T> 
void chkMax(T& x, T y) {
  x = x > y ? x : y;
}

int main() {
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
#endif
  freopen("3.in", "r", stdin);
  memset(a, 0, sizeof a);
  cin >> n >> m;
  ans = 0;
  For (i, 1, n) {
    For (j, 1, m) {
      char s[5];
      cin >> s;
      if (s[0] == 'F') {
        a[i][j] = 1;
      }
    }
  }
  For (j, 1, m) {
    For (i, 1, n) {
      if (a[i][j] == 1) {
        ly[i][j] = ly[i - 1][j] + 1;
      } else {
        ly[i][j] = 0;
      }
    }
  }
  stk[0] = mp(0, 0);
  top = 0;
  For (i, 1, n) {
    ly[i][m + 1] = top = 0;
    For (j, 1, m + 1) {
      if (ly[i][j] > stk[top].first) {
        stk[++top] = mp(ly[i][j], 1);
      } else if (ly[i][j] <= stk[top].first) {
        int wd = 0;
        while (top && ly[i][j] < stk[top].first) {
          wd += stk[top].second;
          chkMax(ans, wd * stk[top].first);
          top--;
        }
        stk[++top] = mp(ly[i][j], wd + 1);
      }
    }
  }
  cout << 3 * ans << '\n';
  return 0;
}

BZOJ1059 [ZJOI2007]矩阵游戏
BZOJ1059
考虑二分图匹配,一个结论为只要保证有独立的大小为$n$的点集$(i,j)$,满足行和列都出现过一次,那么原图就合法。
时间复杂度 $O(n^2)$

#include <bits/stdc++.h>
#define For(i, s, t) for (int i = s; i <= t; i++)
#define eb emplace_back

using namespace std;

const int N = 405;

int n;
int vis[N], mtc[N];
vector<int> g[N];

int main() {
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
#endif
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    memset(mtc, 0, sizeof mtc);
    For (i, 1, n) {
      g[i].clear();
    }
    For (i, 1, n) {
      For (j, 1, n) {
        int x;
        cin >> x;
        if (x) {
          g[i].eb(n + j);
          g[n + j].eb(i);
        }
      }
    }
    int ans = 0;
    For (i, 1, n) {
      function<int(int)> match;
      match = [&](int u) {
        for (auto v : g[u]) {
          if (!vis[v]) {
            vis[v] = 1;
            if (!mtc[v] || (mtc[v] && match(mtc[v]))) {
              mtc[v] = u;
              return 1;
            }
          }
        }
        return 0;
      };
      memset(vis, 0, sizeof vis);
      ans += match(i);
    }
    cout << (ans == n ? "Yes" : "No") << '\n';
  }
  return 0; 
}

BZOJ1051 [HAOI2006]受欢迎的牛
BZOJ1051
将原图缩点后若只存在一个出度为$0$的环,那么答案为此环的大小,否则答案为$0$。
时间复杂度 $O(n)$

#include <bits/stdc++.h>
#define For(i, s, t) for (int i = s; i <= t; i++)
#define eb emplace_back

using namespace std;

template <class T> 
void chkMin(T& x, T y) {
  x = x < y ? x : y;
}

const int N = 10005;
const int M = 50005;

int n, m, dfc, top, scc;
vector<int> g[N];
int dfn[N], low[N], stk[N], cnt[N], otd[N], bel[N];
bool inStk[N];

void tarjan(int u) {
  dfn[u] = low[u] = ++dfc;
  stk[++top] = u;
  inStk[u] = 1;
  for (auto v : g[u]) {
    if (!dfn[v]) {
      tarjan(v);
      chkMin(low[u], low[v]);
    } else if (inStk[v]) {
      chkMin(low[u], low[v]);
    }
  }
  if (dfn[u] == low[u]) {
    ++scc;
    int v = 0;
    do {
      v = stk[top--];
      bel[v] = scc;
      inStk[v] = 0;
      cnt[scc]++;
    } while (u != v);
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cin >> n >> m;
  For (i, 1, m) {
    int u, v;
    cin >> u >> v;
    g[u].eb(v);
  }
  For (i, 1, n) {
    if (!dfn[i]) {
      tarjan(i);
    }
  }
  For (i, 1, n) {
    for (auto v : g[i]) {
      if (bel[v] != bel[i]) {
        otd[bel[i]]++;
      }
    }
  }
  int ans = 0, res = 0;
  For (i, 1, scc) {
    if (otd[i] == 0) {
      res++;
      ans = cnt[i];
    }
  }
  if (res > 1) {
    cout << 0 << '\n';
  } else {
    cout << ans << '\n';
  }
  return 0;
}

BZOJ1006 神奇的国度
题解

BZOJ1242 Zju1015 Fishing Net弦图判定
题解

BZOJ1180 [CROATIAN2009]OTOCI
BZOJ1180
LCT 裸题。

#include <bits/stdc++.h>
#define For(i, s, t) for (int i = s; i <= t; i++)

using namespace std;

const int N = 30005;

struct Node {
  int fa, ch[2], rev;
  int sum, val;  
};

struct Lct {
  Node tr[N];
  int stk[N];
  
  bool isRoot(int x) {
    return tr[tr[x].fa].ch[0] != x && tr[tr[x].fa].ch[1] != x;
  }
  
  int get(int x) {
    return tr[tr[x].fa].ch[1] == x;
  }
  
  void reverse(int x) {
    swap(tr[x].ch[0], tr[x].ch[1]);
    tr[x].rev ^= 1;
  }
  
  void pushup(int x) {
    tr[x].sum = tr[tr[x].ch[0]].sum + tr[tr[x].ch[1]].sum + tr[x].val;
  }
  
  void pushdown(int x) {
    if (tr[x].rev) {
      reverse(tr[x].ch[0]);
      reverse(tr[x].ch[1]);
      tr[x].rev = 0;
    }
  }
  
  void rotate(int x) {
    int y = tr[x].fa, z = tr[y].fa, r = get(x);
    if (!isRoot(y)) tr[z].ch[get(y)] = x;
    tr[x].fa = z;
    tr[y].ch[r] = tr[x].ch[r ^ 1];
    if (tr[x].ch[r ^ 1]) tr[tr[x].ch[r ^ 1]].fa = y;
    tr[x].ch[r ^ 1] = y, tr[y].fa = x;
    pushup(y), pushup(x);
  }
  
  void splay(int x) {
    int y = 0, z = x;
    stk[++y] = x;
    while (!isRoot(z)) stk[++y] = tr[z].fa, z = tr[z].fa;
    while (y) pushdown(stk[y--]);
    while (!isRoot(x)) {
      y = tr[x].fa;
      if (!isRoot(y)) (get(x) ^ get(y)) ? rotate(x) : rotate(y);
      rotate(x);
    } 
  }
  
  void access(int x) {
    for (int y = 0; x; y = x, x = tr[x].fa) splay(x), tr[x].ch[1] = y, pushup(x);
  }
  
  void makeRoot(int x) {
    access(x), splay(x), reverse(x);
  }
  
  int findRoot(int x) {
    access(x), splay(x);
    while (tr[x].ch[0]) pushdown(x), x = tr[x].ch[0];
    splay(x);
    return x;
  }
  
  void split(int x, int y) {
    makeRoot(x), access(y), splay(y);
  }
  
  void link(int x, int y) {
    makeRoot(x);
    tr[x].fa = y;
  }
  
  void modify(int x, int y) {
    makeRoot(x);
    tr[x].val = y;
    splay(x);
  }
} lct;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n, q;
  cin >> n;
  For (i, 1, n) {
    cin >> lct.tr[i].val;
    lct.tr[i].sum = lct.tr[i].val;
  }
  cin >> q;
  while (q--) {
    char opt[10];
    int x, y;
    cin >> opt >> x >> y;
    if (opt[0] == 'b') {  
      if (lct.findRoot(x) == lct.findRoot(y)) {
        cout << "no" << '\n';
      } else {
        lct.link(x, y);
        cout << "yes" << '\n';
      }
    } else if (opt[0] == 'p') {
      lct.modify(x, y);
    } else {
      if (lct.findRoot(x) != lct.findRoot(y)) {
        cout << "impossible" << '\n';
      } else {
        lct.split(x, y);
        cout << lct.tr[y].sum << '\n';
      }
    }
  }
  return 0; 
}

BZOJ2794 [Poi2012]Cloakroom
题解

BZOJ1563 [NOI]诗人小G
题解

BZOJ2200 [Usaco2011 Jan]道路和航线
题解

BZOJ1013 [JSOI2008]球形空间产生器sphere
每两个相邻的点列出方程,然后高斯消元暴力解。

namespace gauss {
const double eps = 1e-6;

bool trans(vector<vector<double>>& a) { // size must be n * (n + 1)
  int n = a.size();
  for (int i = 0; i < n; i++) {
    int t = -1;
    for (int j = i; j < n; j++)
      if (abs(a[j][i]) > eps) {
        t = j;
        break;
      }
    if (t == -1) 
      return 0;
    swap(a[i], a[t]);
    for (int j = 0; j < n; j++) {
      if (i == j)
        continue; 
      for (int k = n; k >= i; k--) 
        a[j][k] -= a[i][k] * (a[j][i] / a[i][i]);
    }
  }
  return 1;
}
}

咕咕咕

最后修改:2020 年 04 月 05 日 07 : 35 PM
如果觉得我的文章对你有用,请随意赞赏