danihao123's Blog

肉肉肉肉，，，

碰置换群啥的不是第一次了……这个题就是给你一堆置换（不要忘记还有一个幺元啊），然后限制颜色数量，求本质不同解个数。那么考虑使用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;
}

论如何把一个完全背包出的高大上……

这个题啊……细节特别多……

首先，不建议开滚动数组，细节处理就会疯。

然后呢……真的不太好说了……还是看代码吧（尽管代码还是有明显的滚动数组痕迹）。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=1005;
const int INF=0x7f7f7f7f;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)

int GZ[maxn][2];
bool haveGZ[maxn];
int A[maxn][2];
int d[maxn][maxm];
int main(){
    int n,m,k,temp;
    register int i,j,v,now,pre,ans=INF,cnt;
    scanf("%d%d%d",&n,&m,&k);
    cnt=k;
    REP(i,n){
        scanf("%d%d",&A[i][0],&A[i][1]);
    }
    for(i=0;i<=n;i++){
        GZ[i][0]=0;
        GZ[i][1]=m+1;
    }
    REP_B(i,k){
        scanf("%d",&temp);
        haveGZ[temp]=true;
        scanf("%d%d",&GZ[temp][0],&GZ[temp][1]);
    }
    memset(d,0x7f,sizeof(d));
    memset(d[0],0,sizeof(d[0]));
    d[0][0]=INF;
    REP_B(i,n){
        now=i;
        pre=i-1;
        d[now][0]=INF;
        int& X=A[i-1][0];
        int& Y=A[i-1][1];
        REP_B(j,m){
            if(j-X>0 && d[pre][j-X]<INF)
                d[now][j]=min(d[now][j],d[pre][j-X]+1);
            if(j-X>0 && d[now][j-X]<INF)
                d[now][j]=min(d[now][j],d[now][j-X]+1);
            if(j==m)
                for(v=j-X;v<=m;v++){
                    if(d[pre][v]<INF)
                        d[now][j]=min(d[now][j],d[pre][v]+1);
                    if(d[now][v]<INF)
                        d[now][j]=min(d[now][j],d[now][v]+1);
                }
        }
        for(j=GZ[i][0]+1;j<GZ[i][1];j++){
            if(j+Y<=m && d[pre][j+Y]<INF)
                d[now][j]=min(d[now][j],d[pre][j+Y]);
        }
        if(haveGZ[i]){
            REP_B(j,GZ[i][0])
                if(d[now][j]<INF){
                    d[now][j]=INF;
                }
            for(j=GZ[i][1];j<=m;j++)
                if(d[now][j]<INF){
                    d[now][j]=INF;
                }
        }
    }
    for(i=n;i>=1;i--){
        for(j=m;j>=1;j--){
            ans=min(ans,d[i][j]);
        }
        if(ans<INF)
            break;
        if(haveGZ[i])
            cnt--;
    }
    if(cnt==k){
        printf("1\n%d\n",ans);
    }else{
        printf("0\n%d\n",cnt);
    }
    return 0;
}

哎……现在才敢说真正会背包DP……

这个题可以分成三类问题分别处理，然后用一个一维数组一起递推。

0-1背包和完全背包都很简单。多重背包直接递推的话复杂度很高，可以考虑单调队列优化……然而窝太弱……不过还是用了

代码：

#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=201,maxv=200001;
struct DQueue{
    deque<int> D;
    queue<int> Q;
    void push(int x){
        Q.push(x);
        while(!D.empty() && x>D.back())
            D.pop_back();
        D.push_back(x);
    }
    int top(){
        return D.front();
    }
    void pop(){
        if(D.front()==Q.front())
            D.pop_front();
        Q.pop();
    }
    int size(){
        return Q.size();
    }
    void clear(){
        while(!Q.empty())
            Q.pop();
        D.clear();
    }
};
int d[maxv];
int v;
void pack(int V,int W,int c){
	register int i,j,m;
	if(c==1){
		for(i=v;i>=V;i--)
			d[i]=max(d[i],d[i-V]+W);
	}else{
		if(c==-1){
			for(i=V;i<=v;i++)
				d[i]=max(d[i],d[i-V]+W);
		}else{
			c=min(c,v/V);
			for(i=0;i<V;i++){
				m=(v-i)/V;
				DQueue Q;
				for(j=0;j<=m;j++){
					if(Q.size()==c+1)
						Q.pop();
					Q.push(d[j*V+i]-j*W);
					d[j*V+i]=Q.top()+j*W;
				}
			}
		}
	}
}
int main(){
	register int i;
	int n,x,y,z;
	scanf("%d%d",&n,&v);
	for(i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&z);
		pack(x,y,z);
	}
	printf("%d\n",d[v]);
	return 0;
}