[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的二进制长度！
让我偷着乐一会
[要证明？我这先挖个坑]
代码：
