[BZOJ 1004][HNOI2008]Cards

肉肉肉肉,,,

碰置换群啥的不是第一次了……这个题就是给你一堆置换(不要忘记还有一个幺元啊),然后限制颜色数量,求本质不同解个数。那么考虑使用Burnside引理,接下来考虑怎么计算每个置换的不动点数量,这个要求每个循环的颜色一致(不就事Polya定理了吗),所以说可以用背包DP搞一搞。

代码:

/**************************************************************
    Problem: 1004
    User: danihao123
    Language: C++
    Result: Accepted
    Time:156 ms
    Memory:3172 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
int sr, sb, sg, m, p;
int pow_mod(int a, int b) {
  int ans = 1, res = a;
  while(b) {
    if(1 & b) ans = (ans * res) % p;
    res = (res * res) % p; b >>= 1;
  }
  return ans;
}
int inv(int x) {
  return pow_mod(x % p, p - 2);
}
 
int d[65][21][21][21];
std::vector<int> len;
int dp() {
  int n = len.size();
  d[0][0][0][0] = 1;
  for(int i = 1; i <= n; i ++) {
    int l = len[i - 1];
    for(int j = 0; j <= sr; j ++) {
      for(int k = 0; k <= sb; k ++) {
        for(int t = 0; t <= sg; t ++) {
          d[i][j][k][t] = 0;
          if(j >= l) d[i][j][k][t] += d[i - 1][j - l][k][t];
          if(k >= l) d[i][j][k][t] += d[i - 1][j][k - l][t];
          if(t >= l) d[i][j][k][t] += d[i - 1][j][k][t - l];
          d[i][j][k][t] %= p;
        }
      }
    }
  }
  return d[n][sr][sb][sg];
}
 
int next[65]; bool vis[65];
int main() {
  scanf("%d%d%d%d%d", &sr, &sb, &sg, &m, &p);
  int n = sr + sb + sg;
  int ans = 0;
  for(int i = 1; i <= n; i ++) {
    len.push_back(1);
  }
  ans = dp();
  for(int i = 1; i <= m; i ++) {
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i ++) {
      scanf("%d", &next[i]);
    }
    len.clear();
    for(int i = 1; i <= n; i ++) {
      if(!vis[i]) {
        int p = i, cnt = 0;
        do {
          vis[p] = true; cnt ++;
          p = next[p];
        } while(p != i);
        len.push_back(cnt);
      }
    }
    ans = (ans + dp()) % p;
  }
  ans = (ans * inv(m + 1)) % p;
  printf("%d\n", ans);
  return 0;
}

[LibreOJ 2383][HNOI2013]游走

本野蛮人竟然没做过高消期望DP,,,泪,流了下来,,,

根据期望线性性,答案就是所有边的期望被走的次数乘上边的编号的和。一条边期望经过的次数可以根据他两个端点期望经过的次数来算(但是\(n\)要特判一下),要求所有点期望走过的次数当然就可以列\(n\)个方程然后高消力。然后期望走的次数多的边编号应该小,反之亦然,所以求完每条边走的次数的期望之后就贪心一下就好力。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <utility>
#include <cmath>
const int maxn = 505;
const int maxm = maxn * maxn;
using R = double;
const R eps = 1e-9;
int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    return ((x < 0.00) ? -1 : 1);
  }
}
R D[maxn][maxn];
int n;
void gauss() {
#ifdef LOCAL
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n + 1; j ++) {
      printf("%.3lf ", D[i][j]);
    }
    puts("");
  }
#endif
  for(int i = 1; i <= n; i ++) {
    int r = i;
    for(int j = i + 1; j <= n; j ++) {
      if(fabs(D[j][i]) > fabs(D[r][i])) {
        r = j;
      }
    }
    assert(sign(D[r][i]) != 0);
    if(r != i) {
      for(int j = 1; j <= n + 1; j ++) {
        std::swap(D[i][j], D[r][j]);
      }
    }
    for(int k = i + 1; k <= n; k ++) {
      R rate = D[k][i] / D[i][i];
      for(int j = i; j <= n + 1; j ++) {
        D[k][j] -= D[i][j] * rate;
      }
    }
  }
  for(int i = n; i >= 1; i --) {
    for(int j = i + 1; j <= n; j ++) {
      D[i][n + 1] -= D[j][n + 1] * D[i][j];
      D[i][j] = 0;
    }
    D[i][n + 1] /= D[i][i]; D[i][i] = 1;
#ifdef LOCAL
    printf("E[%d] : %.3lf\n", i, D[i][n + 1]);
#endif
  }
}

int E[maxm][2], deg[maxn];
R tms[maxm];
void add_edge(int u, int v) {
  if(u != n) D[v][u] += 1.00 / (R(deg[u]));
}

int main() {
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i ++) {
    D[i][i] = -1;
  }
  D[1][n + 1] = -1;
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d", &E[i][0], &E[i][1]);
    deg[E[i][0]] ++; deg[E[i][1]] ++;
  }
  for(int i = 1; i <= m; i ++) {
    int u = E[i][0], v = E[i][1];
    add_edge(u, v); add_edge(v, u);
  }
  gauss();
  for(int i = 1; i <= m; i ++) {
    tms[i] = 0;
    int u = E[i][0], v = E[i][1];
    if(u != n) tms[i] += D[u][n + 1] / (R(deg[u]));
    if(v != n) tms[i] += D[v][n + 1] / (R(deg[v]));
  }
  std::sort(tms + 1, tms + 1 + m, [&](const R &i, const R &j) { return i > j; });
  R ans = 0;
  for(int i = 1; i <= m; i ++) {
    ans += tms[i] * (R(i));
  }
  printf("%.3lf\n", ans);
  return 0;
}

[BZOJ 1010][HNOI2008]玩具装箱toy

很久之前是学过并写过斜率优化的……但是很快就忘了。现在感觉自己理解了,感觉是真的懂了……抽空写篇文章解释一下吧……

先单独说这一个题。将DP方程完全展开,并且设\(P_i = S_i + i\),\(c = L + 1\),可得:

\[f_i = c^2 + P_i^2 - 2P_i c + max(P_j^2 + 2P_j c + f_j - 2P_i P_j)\]

然后\(c^2 + P_i^2 - 2P_i c\)这部分是常数项不需要管了,我们就想想max里面那些(姑且设之为\(d_i\))咋整好了。

设\(d_i = P_j^2 + 2P_j c + f_j - 2P_i P_j\),稍作移项,得:

\[2P_i P_j + d_i = P_j^2 + 2P_j c + f_j\]

于是乎,\(d_i\)可以看做斜率为\(2P_i\)的直线过点\((P_j, P_j^2 + 2P_j c + f_j)\)得到的截距。而那些点我们之前都知道了,问题就变成了已知斜率,求过某点集中的点的最大截距。

想象一个固定斜率的直线从下往上扫,那么碰到的第一个点就是最优解。首先这个点一定在下凸壳上,其次下凸壳上这点两侧的线段的斜率肯定一个比\(2P_i\)大另一个比它小。并且最好的一点是这个斜率还是单调的,那么分界点一定是单调递增的。

代码:

/**************************************************************
    Problem: 1010
    User: danihao123
    Language: C++
    Result: Accepted
    Time:132 ms
    Memory:2416 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <deque>
#include <cmath>
typedef long long ll;
typedef ll T;
struct Point {
  T x, y;
  Point(T qx = 0LL, T qy = 0LL) {
    x = qx; y = qy;
  }
};
typedef Point Vector;
Vector operator +(const Vector &a, const Vector &b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
  return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
  return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
  return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
  return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
  return (a.x * b.y - a.y * b.x);
}
 
const int maxn = 50005;
T C[maxn], S[maxn], P[maxn];
T f[maxn];
int n; ll c;
void process() {
  for(int i = 1; i <= n; i ++) {
    S[i] = S[i - 1] + C[i];
    P[i] = S[i] + (ll(i));
  }
}
void dp() {
  std::deque<Point> Q;
  Q.push_back(Point(0LL, 0LL));
  for(int i = 1; i <= n; i ++) {
    ll k = 2 * P[i];
    Vector st(1, k);
    while(Q.size() > 1 && times(Q[1] - Q[0], st) > 0LL) {
      Q.pop_front();
    }
    f[i] = c * c + P[i] * P[i] - 2LL * P[i] * c;
    f[i] += Q.front().y - k * Q.front().x;
#ifdef LOCAL
    printf("f[%d] : %lld\n", i, f[i]);
#endif
    Vector ins(P[i], f[i] + P[i] * P[i] + 2LL * P[i] * c);
    while(Q.size() > 1 && times(ins - Q.back(), Q.back() - Q[Q.size() - 2]) > 0LL) {
#ifdef LOCAL
      printf("Deleting (%lld, %lld)...\n", Q.back().x, Q.back().y);
#endif
      Q.pop_back();
    }
    Q.push_back(ins);
#ifdef LOCAL
    printf("Inserting (%lld, %lld)...\n", ins.x, ins.y);
#endif
  }
}
 
int main() {
  scanf("%d%lld", &n, &c); c ++;
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &C[i]);
  }
  process(); dp();
  printf("%lld\n", f[n]);
  return 0;
}

[BZOJ 2733][HNOI2012]永无乡

我这题竟然很早就做了……

求k小显然可以用平衡树。但是这个题还需要快速的合并平衡树,那就需要启发式合并了。

继续阅读

[BZOJ 1483][HNOI2009]梦幻布丁

做了很久了吧,但现在才写题解……(斜眼

首先记录一个起始的颜色段数,然后每种颜色都要用链表顺序记下该颜色有哪些点。然后合并的时候合并两个链表——最优策略显然是启发式合并。

但是,很多时候并不是把小链表的扔到大的里面的情况,而是恰好反过来的情况,如何处理?

这种时候,我们可以交换两个颜色的“真实身份”。合并的时候,把每个点当成它的“真实身份”处理即可。

继续阅读

[BZOJ 1009][HNOI2008]GT考试

好劲啊这题……

首先先想DP的做法,我们用[tex]p[i][j][/tex]表示若字符串已匹配前缀[tex][1,i][/tex],有多少种方案使得追加上一个数后匹配[tex][1,j][/tex],这个用KMP可以很方便的求出(事实上暴力也可以)

然后再来看DP的做法,转移方程大致是这样的:

[tex]d[i][j]=\Sigma_{k=0}^{m-1}(d[i-1][k]\times p[k][j])[/tex]

但是n非常大,这么做注定要TLE。

不过看这个转移方程,是不是和矩阵乘法的定义很像?是的。

我们可以用一个[tex]1\times m[/tex]的矩阵[tex]D[/tex]来表示某一个阶段的DP值,我们可以把[tex]p[/tex]组织成一个[tex]m\times m[/tex]矩阵[tex]P[/tex]。然后我们可以发现:

[tex]D_i\times P=D_{i+1}[/tex]

由于矩阵乘法满足结合律,所以:

[tex]D_n=D_0\times P^n[/tex]

很明显可以快速幂搞出来。

代码:

/**************************************************************
    Problem: 1009
    User: danihao123
    Language: C++
    Result: Accepted
    Time:80 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[22][22];
ull MOD;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))
 
inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
    register int i,j,k;
    Matrix C;
    CL_ARR(C,0);
    REP(i,m){
        REP(j,p){
            REP(k,n){
                C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
            }
        }
    }
    CP_ARR(C,res);
}
void MatrixPow(Matrix A,int m,ull p,Matrix& res){
    Matrix a,temp;
    register int i;
    CL_ARR(a,0);
    memcpy(a,A,sizeof(a));
    CL_ARR(temp,0);
    REP(i,m){
        temp[i][i]=1;
    }
    while(p){
        if(1&p){
            MatrixMul(temp,a,m,m,m,temp);
        }
        p>>=1;
        MatrixMul(a,a,m,m,m,a);
    }
    CP_ARR(temp,res);
}
 
char buf[25];
int f[25];
int main(){
    register int i,u,j;
    register ull ret=0;
    ull n;
    int m;
    Matrix ans,P;
    scanf("%llu%d%llu",&n,&m,&MOD);
    scanf("%s",buf+1);
    CL_ARR(ans,0);
    ans[0][0]=1;
    CL_ARR(P,0);
    P[0][0]=9;P[0][1]=1;
    // f[0]=f[1]=0;
    for(i=1;i<m;i++){
        u=f[i];
        while(u && buf[u+1]!=buf[i+1]){
            u=f[u];
        }
        if(buf[u+1]==buf[i+1]){
            f[i+1]=u+1;
        }else{
            f[i+1]=0;
        }
        for(j=0;j<10;j++){
            u=i;
            while(u && buf[u+1]!=j+'0'){
                u=f[u];
            }
            if(buf[u+1]==j+'0'){
                P[i][u+1]=(P[i][u+1]+1)%MOD;
            }else{
                P[i][0]=(P[i][0]+1)%MOD;
            }
        }
    }
    MatrixPow(P,m,n,P);
    MatrixMul(ans,P,1,m,m,ans);
    for(i=0;i<m;i++){
        ret=(ret+ans[0][i])%MOD;
    }
    printf("%llu\n",ret);
    return 0;
}

[BZOJ 1212]L语言

这个感觉本质上和那个Remember a Word很像吧……

不过这个只是求最长可行前缀,递推即可。

代码:

/**************************************************************
    Problem: 1212
    User: danihao123
    Language: C++
    Result: Accepted
    Time:660 ms
    Memory:45072 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1048581;
const int maxW=4005,maxL=105;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
 
vector<int> AnsList;
namespace Trie{
    const int maxnode=400005;
    const int sigma_siz=26;
    int Tree[maxnode][sigma_siz];
    int val[maxnode];
    int siz;
    inline int idx(char c){
        return c-'a';
    }
    inline void InitTrie(){
        siz=0;
        val[0]=0;
        CL_ARR(Tree[0],0);
    }
    void Insert(char *s,int v){
        register int u=0,n=strlen(s);
        register int i,c;
        REP(i,n){
            c=idx(s[i]);
            if(!Tree[u][c]){
                siz++;
                Tree[u][c]=siz;
                val[siz]=0;
                CL_ARR(Tree[siz],0);
            }
            u=Tree[u][c];
        }
        val[u]=v;
    }
    void Query(char *s,int len){
        register int i,c,u=0;
        AnsList.clear();
        REP(i,len){
            if(!s[i])
                break;
            c=idx(s[i]);
            if(!Tree[u][c])
                break;
            u=Tree[u][c];
            if(val[u])
                AnsList.push_back(val[u]);
        }
    }
};
 
char Text[maxn];
int len[maxW];
char buf[maxL];
bool d[maxn];
int main(){
    int n,m;
    int length;
    register int i,j,k;
    bool flag;
    Trie::InitTrie();
    scanf("%d%d",&n,&m);
    REP_B(i,n){
        scanf("%s",buf);
        len[i]=strlen(buf);
        Trie::Insert(buf,i);
    }
    REP_B(i,m){
        scanf("%s",Text);
        length=strlen(Text);
        CL_ARR(d,0);
        d[0]=true;
        for(j=0;j<=length;j++){
            if(d[j]){
                Trie::Query(Text+j,length-j);
                REP(k,AnsList.size()){
                    d[j+len[AnsList[k]]]=true;
                }
            }
        }
        flag=false;
        for(j=length;j>=0;j--){
            if(d[j]){
                flag=true;
                printf("%d\n",j);
                break;
            }
        }
        if(!flag)
            puts("0");
    }
    return 0;
}

[BZOJ 1196]公路修建问题

挺简单的二分答案题……然而到现在才A

思路很明显,直接二分最终答案。那么判定如何做呢?

假设判定谓词为[tex]C(x)[/tex],那么我们首先考虑选白边。贪心加入边权小于[tex]x[/tex]的边(当然是否有必要就要用并查集判定了。并且这样就算加的超过了[tex]k[/tex]条也不会对答案造成影响)。然后白边加的不够[tex]k[/tex]谓词就是假了。

然后再考虑黑边,接下来的事情就很简单了。

代码:

/**************************************************************
    Problem: 1196
    User: danihao123
    Language: C++
    Result: Accepted
    Time:672 ms
    Memory:1212 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define RAP(i,n) for(i=1;i<=(n);i++)
const int maxn=10001,maxm=20001;
 
struct Edge{
    int u,v,d1,d2;
};
bool cmp1(const Edge& x,const Edge& y){
    return x.d1<y.d1;
}
bool cmp2(const Edge& x,const Edge& y){
    return x.d2<y.d2;
}
 
int n;
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
inline void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    register int i;
    for(i=1;i<=n;i++)
        p[i]=i;
    memset(rank,0,sizeof(rank));
}
 
int k,m;
Edge E[maxm];
inline bool check(int x){
    register int i,first_cnt=0,cnt=0;
    init_set();
    sort(E,E+m,cmp1);
    REP(i,m){
        if(E[i].d1>x){
            break;
        }else{
            if(!is_same(E[i].u,E[i].v)){
                first_cnt++;
                cnt++;
                union_set(E[i].u,E[i].v);
            }
        }
        if(cnt==n-1){
            return true;
        }
    }
    if(first_cnt<k)
        return false;
    sort(E,E+m,cmp2);
    REP(i,m){
        if(E[i].d2>x){
            break;
        }else{
            if(!is_same(E[i].u,E[i].v)){
                cnt++;
                union_set(E[i].u,E[i].v);
            }
        }
        if(cnt==n-1)
            return true;
    }
    return false;
}
int main(){
    register int i,L=1,M,R=0;
    scanf("%d%d%d",&n,&k,&m);
    m--;
    REP(i,m){
        scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].d1,&E[i].d2);
        R=max(R,E[i].d1);
    }
    R++;
    while(L<R){
        M=L+(R-L)/2;
        if(check(M))
            R=M;
        else
            L=M+1;
    }
    printf("%d\n",L);
    return 0;
}

 

[BZOJ 1192]鬼谷子的钱袋

这题真是interesting极了!

建议先在纸上实践一下,然后你会发现问题的解就是n的二进制长度!

让我偷着乐一会

[要证明?我这先挖个坑]

代码:

继续阅读