danihao123's Blog

你有\(n\)个两两不同的串，你要将每个串变成其的一个前缀，使得变换后的所有串仍然两两不同，并且所有串长度和尽可能小，输出这个和。

\(n\leq 10^5\)，所有串长之和不超过\(10^5\)。

ao劲啊这题，，，

看到那个逆序对奇偶性就想到了行列式（考虑行列式的定义）……其实最后要判定的就是该矩阵行列式的正负性（或者是0）。

这个东西肯定可以高消搞成上三角，然后行列式就很好求了。但高消事\(O(n^3)\)的，会T掉。

考虑怎么去优化这个高消。首先在消元顺序合理的情况下，一定可以让矩阵在整个过程中一直是01矩阵。具体的实现方式，就是考虑从小到大对每个变量进行消元的时候，包含该变量的方程很多，并且他们两两之间一定是满足一个的全1段事另一个的前缀。那么用最短的那一段进行消元即可。

考虑到其他方程被消之后最靠左的1的位置会全部变成另一个位置，所以可以考虑使用可并堆维护各个方程。同时，为了求每个方程当前最靠左的1的位置，我搞了个并查集（逃

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <ext/pb_ds/priority_queue.hpp>
using R = double;
// using GG = __gnu_pbds::priority_queue<int>;
const int maxn = 100005;
const R eps = 1e-8;
inline int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    if(x < 0.00) {
      return -1;
    } else {
      return 1;
    }
  }
}
 
int seg[maxn][2];
namespace BF {
  R A[105][105];
  inline int det(int n) {
    int flag = 1;
    for(int i = 1; i <= n; i ++) {
      int r = i;
      for(int j = i + 1; j <= n; j ++) {
        if(fabs(A[j][i]) > fabs(A[i][i])) {
          r = j;
        }
      }
      if(r != i) {
        flag *= -1;
        for(int j = i; j <= n; j ++) {
          std::swap(A[i][j], A[r][j]);
        }
      } else {
        if(sign(A[i][i]) == 0) {
          return 0;
        }
      }
      for(int j = i + 1; j <= n; j ++) {
        if(sign(A[j][i]) == 0) continue;
        double f = A[j][i] / A[i][i];
        for(int k = i; k <= n; k ++) {
          A[j][k] -= A[i][k] * f;
        }
      }
    }
    int ret = flag;
    for(int i = 1; i <= n; i ++) {
      ret *= sign(A[i][i]);
    }
    return ret;
  }
  inline void solve(int n) {
    for(int i = 1; i <= n; i ++) {
      int L = seg[i][0], R = seg[i][1];
      for(int j = 1; j <= n; j ++) {
        if(L <= j && j <= R) {
          A[i][j] = 1;
        } else {
          A[i][j] = 0;
        }
      }
    }
    int v = (det(n));
    if(v == -1) {
      puts("Fedor");
    } else if(v == 0) {
      puts("Draw");
    } else {
      puts("Alex");
    }
  }
};
namespace CT {
  /*
  struct Node {
    int l, r, id;
    bool operator <(const Node &res) const {
      if(l == res.l) {
        if(r == res.r) {
          return id < res.id;
        } else {
          return r < res.r;
        }
      } else {
        return l < res.l;
      }
    }
    bool operator >(const Node &res) const {
      if(l == res.l) {
        if(r == res.r) {
          return id > res.id;
        } else {
          return r > res.r;
        }
      } else {
        return l > res.l;
      }
    }
    bool operator ==(const Node &res) const {
      return (l == res.l) && (r == res.r) && (id == res.id);
    }
  };
  */
  struct N2 {
    int r, id;
    N2() {
      r = 0; id = 0;
    }
    N2(int x, int y) {
      r = x; id = y;
    }
    bool operator <(const N2 &res) const {
      if(r == res.r) {
        return id < res.id;
      } else {
        return r < res.r;
      }
    }
    bool operator >(const N2 &res) const {
      if(r == res.r) {
        return id > res.id;
      } else {
        return r > res.r;
      }
    }
    bool operator ==(const N2 &res) const {
      return (r == res.r) && (id == res.id);
    }
  };
  
  /* struct Node {
    Node *fa, *ch[2];
    N2 v; int l;
    int setv;
    int d() {
      return ((this == fa -> ch[1]) ? 1 : 0);
    }
    void sc(Node *c, int dir) {
      ch[dir] = c;
      c -> fa = this;
    }
    int cmp(const N2 &v2) const {
      if(v == v2) {
        return -1;
      } else {
        if(v2 < v) {
          return 0;
        } else {
          return 1;
        }
      }
    }
    void paint(int x) {
      if(l == -1) return;
      l = x; setv = x;
    }
    void pushdown(int x) {
      if(setv != -1) {
        ch[0] -> paint(setv);
        ch[1] -> paint(setv);
        setv = -1;
      }
    }
  };
  Node pool[maxn]; std::queue<int> FQ;
  Node *nil, *cur;
  void init_pool() {
    nil = cur = pool;
    nil -> l = nil -> setv = -1;
    nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
  }
  Node *alloc_node(N2 x, int L) {
    Node *ret;
    if(FQ.empty()) {
      ret = ++ cur;
    } else {
      ret = FQ.front(); FQ.pop();
    }
    ret -> v = x;
    ret -> l = L; ret -> setv = -1;
    ret -> fa = ret -> ch[0] = ret -> ch[1] = nil;
    return ret;
  }
  
  inline bool is_root(Node *o) {
    return (o -> fa == nil)
  }
  inline void zig(Node *x) {
    int d = x -> d(); Node *y = x -> fa;
    if(is_root(y)) {
      x -> fa = y -> fa;
    } else {
      y -> fa -> sc(x, y -> d());
    }
    y -> sc(x -> ch[d ^ 1], d);
    x -> sc(y, d ^ 1);
  }
  void pdw_path(Node *x) {
    if(!is_root(x)) pdw_path(x -> fa);
    x -> pushdown();
  }
  inline void splay(Node *x) {
    pdw_path(x);
    while(!is_root(x)) {
      Node *y = x -> fa;
      if(!is_root(y)) {
        if((x -> d()) ^ (y -> d())) {
          zig(x);
        } else {
          zig(y);
        }
      }
      zig(x);
    }
  }
  Node *insert(Node *o, Node *x) {
    if(o == nil) return x;
    Node *last = o;
    int d;
    while(o != nil) {
      o -> pushdown(); last = o;
      d = o -> cmp(x -> v);
      o = o -> ch[d];
    }
    x -> ch[0] = x -> ch[1] = nil;
    last -> sc(x, d);
    splay(x); return x;
  }
  Node *top(Node *x) {
    Node *ret = x;
    while(x -> ch[0] == 0) {
      x -> paint
    }
  } */
  
  int par[maxn * 2];
  int get_fa(int x) {
    if(par[x] == x) return x;
    else return (par[x] = get_fa(par[x]));
  }
  void merge(int dir, int src) {
    dir = get_fa(dir); src = get_fa(src);
    if(dir == src) return;
    par[src] = dir;
  }
  bool is_same(int x, int y) {
    return (get_fa(x) == get_fa(y));
  }
  
  using heap = __gnu_pbds::priority_queue<N2, std::greater<N2> >;
  heap Q[maxn];
  int id[maxn], mp[maxn];
  int det(int n) {
    int flag = 1;
    for(int i = 1; i <= n; i ++) {
      Q[i].clear();
    }
    for(int i = 1; i <= 2 * n; i ++) {
      par[i] = i;
    }
    for(int i = 1; i <= n; i ++) {
      id[i] = mp[i] = i;
      int L = seg[i][0], R = seg[i][1];
      Q[L].push(N2(R, i));
      merge(L, n + i);
    }
    for(int i = 1; i <= n; i ++) {
      if(Q[i].empty()) {
        return 0;
      }
      int p = id[i];
      if(!(get_fa(p + n) <= i && seg[p][1] == (Q[i].top()).r)) {
        flag *= -1;
        int np = (Q[i].top()).id;
#ifdef LOCAL
        printf("Swaping %d and %d.\n", p, np);
#endif
        int nv = mp[np];
        std::swap(id[i], id[nv]);
        std::swap(mp[np], mp[p]);
      }
      p = id[i];
      Q[i].pop();
      int r = seg[p][1];
      if(Q[i].size() > 0 && (Q[i].top()).r == r) {
        return 0;
      }
      if(r < n) {
        Q[r + 1].join(Q[i]);
        merge(r + 1, i);
      }
    }
    return flag;
  }
  void solve(int n) {
    int v = det(n);
    if(v == -1) {
      puts("Fedor");
    } else if(v == 0) {
      puts("Draw");
    } else {
      puts("Alex");
    }
  }
};
 
int main() {
  int T; scanf("%d", &T);
  while(T --) {
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
      scanf("%d%d", &seg[i][0], &seg[i][1]);
    }
    if(n <= 100) {
      BF::solve(n);
    } else {
      CT::solve(n);
    }
  }
  return 0;
}

分层图最短路处女作TAT

很明显要求你求一个分层图上的最短路。不过没必要把分层图构出来，手写转移即可。还有卡SPFA是怎么回事？出题人你粗来我保证不打死你……

然而沉迷pb_ds，不能自拔。

代码：

/**************************************************************
    Problem: 2763
    User: danihao123
    Language: C++
    Result: Accepted
    Time:268 ms
    Memory:3136 kb
****************************************************************/
 
#include <cstdio>
#include <queue>
#include <algorithm>
#include <utility>
#include <cstring>
#include <cctype>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
const int maxn=10001,maxm=100001,maxk=11;
typedef pair<int,int> pii;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
inline void Add_Edge(int u,int v,int d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
struct Node{
    pii pnt;
    int d;
    bool operator <(const Node& x) const{
        return d<x.d;
    }
    bool operator >(const Node& x) const{
        return d>x.d;
    }
};
 
typedef __gnu_pbds::priority_queue<Node,greater<Node> > Heap;
Heap::point_iterator ite[maxn][maxk];
Heap Q;
int n,k;
bool vis[maxn][maxk];
int d[maxn][maxk];
inline void relax(int u,int v,int di){
    d[u][v]=di;
    if(ite[u][v]!=0)
        Q.modify(ite[u][v],(Node){make_pair(u,v),di});
    else
        ite[u][v]=Q.push((Node){make_pair(u,v),di});
}
int Dijkstra(int s,int t){
    register int i,u,v;
    pii temp;
    memset(d,0x7f,sizeof(d));
    d[s][0]=0;
    ite[s][0]=Q.push((Node){make_pair(s,0),0});
    while(!Q.empty()){
        temp=Q.top().pnt;
        Q.pop();
        u=temp.first;
        v=temp.second;
        if(vis[u][v])
            continue;
        vis[u][v]=true;
        for(i=first[u];i;i=next[i]){
            if(v<k){
                if(d[u][v]<d[to[i]][v+1]){
                    relax(to[i],v+1,d[u][v]);
                }
            }
            if(d[u][v]+dist[i]<d[to[i]][v]){
                relax(to[i],v,d[u][v]+dist[i]);
            }
        }
    }
    register int ans=0x7f7f7f7f;
    for(i=0;i<=k;i++)
        ans=min(ans,d[t][i]);
    return ans;
}
int main(){
    int m,s,t,u,v,d;
    register int i;
    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&d);
        Add_Edge(u,v,d);
        Add_Edge(v,u,d);
    }
    printf("%d\n",Dijkstra(s,t));
    return 0;
}

这题初看有些棘手。但是毕竟是最短路，[tex]min(abs(x_{1}-x_{2}),abs(y_{1}-y_{2}))[/tex]这样的边，大可以分成两条边来建，于是乎min就形同虚设了。并且我们可以看到这样建图有一个好处：跨越若干点的方案可以一定可以分成图上的若干边。问题大为简化，迎刃而解。

但这提有个丧病的地方：卡SPFA。加了一些优化照样挂。所以我一气之下写了可并堆优化的Dijkstra :)当然可并堆用的是pb_ds辣。

代码：

/**************************************************************
    Problem: 4152
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4888 ms
    Memory:17412 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <utility>
#include <ext/pb_ds/priority_queue.hpp>
#include <cctype>
#include <bitset>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
const int maxn=200001;
int n;
inline int abs(int x){
    return x<0?-x:x;
}
  
int first[maxn];
int next[maxn*4],to[maxn*4],dist[maxn*4];
int graph_cnt=0;
inline void Add_Edge(int x,int y,int d){
    graph_cnt++;
    next[graph_cnt]=first[x];
    first[x]=graph_cnt;
    to[graph_cnt]=y;
    dist[graph_cnt]=d;
}
  
int d[maxn];
bitset<maxn> vis;
typedef pair<int,int> my_pair;
typedef __gnu_pbds::priority_queue<my_pair,greater<my_pair> > Heap;
Heap::point_iterator ite[maxn];
Heap Q;
int dij(){
    register int i,u;
    memset(d,0x7f,sizeof(d));
    d[1]=0;
    ite[1]=Q.push(make_pair(0,1));
    while(!Q.empty()){
        u=Q.top().second;
        Q.pop();
        if(vis[u])
            continue;
        vis[u]=true;
        for(i=first[u];i;i=next[i]){
            if(d[to[i]]>(dist[i]+d[u])){
                d[to[i]]=dist[i]+d[u];
                if(ite[to[i]]!=0)
                    Q.modify(ite[to[i]],make_pair(d[to[i]],to[i]));
                else
                    ite[to[i]]=Q.push(make_pair(d[to[i]],to[i]));
            }
        }
    }
    return d[n];
}
  
int pr[maxn][2];
int order1[maxn],order2[maxn];
int cmp1(const int i,const int j){
    return pr[i][0]<pr[j][0];
}
int cmp2(const int i,const int j){
    return pr[i][1]<pr[j][1];
}
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int main(){
    register int i;
    n=readint();
    for(i=1;i<=n;i++){
        pr[i][0]=readint();
        pr[i][1]=readint();
        order1[i]=i;
        order2[i]=i;
    }
    sort(order1+1,order1+1+n,cmp1);
    sort(order2+1,order2+1+n,cmp2);
    for(i=1;i<=n;i++){
        if(i!=1){
            Add_Edge(order1[i],order1[i-1],pr[order1[i]][0]-pr[order1[i-1]][0]);
            Add_Edge(order2[i],order2[i-1],pr[order2[i]][1]-pr[order2[i-1]][1]);
        }
        if(i!=n){
            Add_Edge(order1[i],order1[i+1],pr[order1[i+1]][0]-pr[order1[i]][0]);
            Add_Edge(order2[i],order2[i+1],pr[order2[i+1]][1]-pr[order2[i]][1]);
        }
    }
    printf("%d\n",dij());
    return 0;
}