Lvat_s Blog

这是一个坑……晚上理解了Splay然后写出来再填坑吧……(那你为什么要开坑？怕忘了这件事啊……)

暂时无法理解splay……先放着吧过一阵子再填坑

今天现学了置换群……知道了Burnside引理……（还在最初级的阶段啊）

Burnside引理：给一些置换，本质不同的染色方案数等于每种置换的不变元素的个数的平均数。

然后自然就是代码了。（我写了两种方法求逆元）

#include<cstdio>
#include<cstring>

int Sr,Sg,Sb,n,m,p,a[65][65],f[65][65][65],ans,b[65],d[65];

void Read(int &x){
char c;
while((c=getchar())<'0' || c>'9');
x=c-'0';
while((c=getchar())>='0' && c<='9'){
    x=x*10+c-'0';
}
}

int QuickPow(int a,int b){
int base=a,ans=1;
while(b){
    if(b%2)ans=(ans*base)%p;
    base=(base*base)%p;
    b/=2;
}
return ans;
}

void exgcd(int a,int b,int &x,int &y){
if(b==0){x=1;y=0;return;}
exgcd(b,a%b,x,y);
int tp=x;
x=y;
y=tp-a/b*y;
}

int DP(int x){
memset(b,0,sizeof(b));
int Sum=0,last=0;
for(int i=1;i<=n;i++){
    if(!b[i]){
        b[i]=1;
        d[++Sum]=1;
        last=i;
        while(!b[a[x][last]]){
            d[Sum]++;
            b[a[x][last]]=1;
            last=a[x][last];
        }
    }
}
memset(f,0,sizeof(f));
f[0][0][0]=1;
for(int i=1;i<=Sum;i++){
    for(int j=Sr;j>=0;j--){
        for(int k=Sg;k>=0;k--){
            for(int l=Sb;l>=0;l--){
                if(j>=d[i]){f[j][k][l]=(f[j][k][l]+f[j-d[i]][k][l])%p;}
                if(k>=d[i]){f[j][k][l]=(f[j][k][l]+f[j][k-d[i]][l])%p;}
                if(l>=d[i]){f[j][k][l]=(f[j][k][l]+f[j][k][l-d[i]])%p;}
            }
        }
    }
}
return f[Sr][Sg][Sb];
}

int main(){
freopen("1004.in","r",stdin);
freopen("1004.out","w",stdout);
Read(Sr);Read(Sb);Read(Sg);Read(m);Read(p);
n=Sr+Sg+Sb;
for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
        Read(a[i][j]);
    }
}
m++;
for(int i=1;i<=n;i++)a[m][i]=i;
for(int i=1;i<=m;i++){
    ans=(ans+DP(i))%p;
}
ans=(ans*QuickPow(m,p-2))%p;
printf("%d\n",ans);
return 0;
}

这是一个坑……得过一阵子再填……

NOIP爆炸了心情不好……

现在打算填坑了。

这题是一个树链剖分，据说LCT也行。但是蒟蒻我啥也不会，于是强行学了一个晚上的树链剖分，总算A掉了这题。

我觉得网上题解已经烂大街了……所以就不发题解了，只（懒）放（癌）代（发）码（作）。

树链剖分+线段树

#include<cstdio>
#include<algorithm>
using namespace std;

int n,w[30005],dep[30005],h[30005],en,data[30005],Q,id[30005],siz[30005],fa[30005],son[30005],top[30005],pre[30005],segn;
char ask[10];

struct Edge{
int b,next;
}e[60005];

struct SegTree{
int l,r,v,sum;
}tr[120005];

void add(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void dfs1(int u,int father,int deep){
dep[u]=deep;
fa[u]=father;
son[u]=0;
siz[u]=1;
//printf("ZZT:%d %d %d\n",u,father,deep);
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==father)continue;
    dfs1(v,u,deep+1);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]]){
        son[u]=v;
    }
}
}

void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(son[u])dfs2(son[u],ux);
else return;
//printf("Tr:%d %d\n",u,ux);
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fa[u] || v==son[u])continue;
    dfs2(v,v);
}
}

void Build(int root,int l,int r){
tr[root].l=l;
tr[root].r=r;
if(l==r){
    tr[root].v=data[pre[l]];
    tr[root].sum=data[pre[l]];
    return;
}
int mid=(l+r)/2;
Build(root*2,l,mid);
Build(root*2+1,mid+1,r);
tr[root].v=max(tr[root*2].v,tr[root*2+1].v);
tr[root].sum=tr[root*2].sum+tr[root*2+1].sum;
}

void Update(int root,int pos,int val){
if(tr[root].l==tr[root].r){
    tr[root].v+=val;
    tr[root].sum+=val;
    //printf("Tx:%d %d %d\n",root,tr[root].v,tr[root].sum);
    return;
}
int mid=(tr[root].l+tr[root].r)/2;
if(pos<=mid)Update(root*2,pos,val);
if(pos>=mid+1)Update(root*2+1,pos,val);
tr[root].sum=tr[root*2].sum+tr[root*2+1].sum;
tr[root].v=max(tr[root*2].v,tr[root*2+1].v);
}

int QuerySum(int root,int l,int r){
if(tr[root].l>=l && tr[root].r<=r){
    return tr[root].sum;
}
int mid=(tr[root].l+tr[root].r)/2;
int ans=0;
if(l<=mid)ans+=QuerySum(root*2,l,r);
if(r>=mid+1)ans+=QuerySum(root*2+1,l,r);
return ans;
}

int QueryMax(int root,int l,int r){
if(tr[root].l>=l && tr[root].r<=r){
    return tr[root].v;
}
int mid=(tr[root].l+tr[root].r)/2;
int ans=-2147483647;
if(l<=mid)ans=max(ans,QueryMax(root*2,l,r));
if(r>=mid+1)ans=max(ans,QueryMax(root*2+1,l,r));
return ans;
}

int AskSum(int u,int v){
int f1=top[u],f2=top[v],ans=0;
while(f1!=f2){
    if(dep[f1]<dep[f2]){
        swap(f1,f2);
        swap(u,v);
    }
    ans+=QuerySum(1,id[f1],id[u]);
    u=fa[f1];
    f1=top[u];
}
if(dep[u]>dep[v]){
    swap(u,v);
}
ans+=QuerySum(1,id[u],id[v]);
return ans;
}

int AskMax(int u,int v){
int f1=top[u],f2=top[v],ans=-2147483647;
while(f1!=f2){
    if(dep[f1]<dep[f2]){
        swap(f1,f2);
        swap(u,v);
    }
    ans=max(ans,QueryMax(1,id[f1],id[u]));
    u=fa[f1];
    f1=top[u];
}
if(dep[u]>dep[v]){
    swap(u,v);
}
ans=max(ans,QueryMax(1,id[u],id[v]));
return ans;
}

int main(){
freopen("1036.in","r",stdin);
freopen("1036.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    add(sa,sb);
    add(sb,sa);
}
for(int i=1;i<=n;i++){
    scanf("%d",&data[i]);
}
dfs1(1,0,1);
dfs2(1,1);
Build(1,1,n);
scanf("%d",&Q);
while(Q--){
    int sa,sb;
    scanf("%s %d %d",&ask,&sa,&sb);
    if(ask[0]=='C'){
        Update(1,id[sa],sb-data[sa]);
        data[sa]=sb;
    }
    if(ask[0]=='Q'){
        if(ask[1]=='S'){
            printf("%d\n",AskSum(sa,sb));
        }
        if(ask[1]=='M'){
            printf("%d\n",AskMax(sa,sb));
        }
    }
}
return 0;
}

树链剖分+树状数组（正在填坑中……）

LCT（正在填坑中……）

水题大法好！

有几天没写blog了呢。因为这几天颓废了。

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,w[3500],c[3500],f[25000];

int main(){
freopen("1625.in","r",stdin);
freopen("1625.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    scanf("%d %d",&w[i],&c[i]);
}
for(int i=1;i<=n;i++){
    for(int j=m;j>=w[i];j--){
        f[j]=max(f[j],f[j-w[i]]+c[i]);
    }
}
printf("%d\n",f[m]);
return 0;
}

有几天没写题解了啊……

这几天在复习以前写过的题目。以后隔一阵子也要去看一看。

记忆化搜索大法好！

#include<cstdio>
#include<cstring>

const long long MOD=9999973;
long long n,m,f[105][105][105],c[105][105];

long long C(long long i,long long j){
	if(j==0)return 1;
	if(i==0)return 0;
	if(i==1)return j==1?1:0;
	if(j==1)return i;
	if(c[i][j]!=-1)return c[i][j];
	return c[i][j]=(C(i-1,j-1)%MOD+C(i-1,j)%MOD)%MOD;
}

long long dfs(long long a,long long b,long long c){
	if(a>n)return 1;
	if(f[a][b][c]!=-1)return f[a][b][c];
	f[a][b][c]=dfs(a+1,b,c)%MOD;
	if(c>=1){
		f[a][b][c]=(f[a][b][c]+dfs(a+1,b+1,c-1)%MOD*c%MOD)%MOD;
	}
	if(m-b-c>=1){
		f[a][b][c]=(f[a][b][c]+dfs(a+1,b,c+1)%MOD*(m-b-c)%MOD)%MOD;
		f[a][b][c]=(f[a][b][c]+dfs(a+1,b+1,c)%MOD*(m-b-c)%MOD*c%MOD)%MOD;
	}
	if(c>=2){
		f[a][b][c]=(f[a][b][c]+dfs(a+1,b+2,c-2)%MOD*C(c,2)%MOD)%MOD;
	}
	if(m-b-c>=2){
		f[a][b][c]=(f[a][b][c]+dfs(a+1,b,c+2)%MOD*C(m-b-c,2)%MOD)%MOD;
	}
	return f[a][b][c];
}

int main(){
	freopen("1801.in","r",stdin);
	freopen("1801.out","w",stdout)
	scanf("%lld %lld",&n,&m);
	memset(f,-1,sizeof(f));
	memset(c,-1,sizeof(c));
	printf("%lld\n",dfs(1,0,0));
	return 0;
}

最近感觉颓废指数直线上升。所以为了每日一以上题解，我又来做大水题了。

这题是一个完全背包，令初始的价格为负然后按照正常完全背包处理即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,v,c[5005],f[500005],w[5005];

int main(){
freopen("1618.in","r",stdin);
freopen("1618.out","w",stdout);
scanf("%d %d",&n,&v);
for(int i=1;i<=n;i++){scanf("%d %d",&w[i],&c[i]);c[i]=-c[i];}
memset(f,-127,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++){
    for(int j=w[i];j<=v+5000;j++){
        f[j]=max(f[j],f[j-w[i]]+c[i]);
        //printf("%d %d %d",f[j],j,f[j-w[i]]+c[i]);
    }
}
for(int i=v+1;i<=v+5000;i++)f[v]=max(f[v],f[i]);
printf("%d\n",-f[v]);
return 0;
}

一开始不知道什么意思，看了hzwer的博客才知道：什么奇怪的题。

我都有些不好意思传代码了。

#include<cstdio>

int n,x,y=0;

int main(){
freopen("1603.in","r",stdin);
freopen("1603.out","w",stdout);
scanf("%d",&n);
n--;
while(n--){
    scanf("%d",&x);
    scanf("%d",&x);
    scanf("%d",&x);
    y^=x;
}
printf("%d\n",y);
return 0;
}

这是一个很裸的LCA。

觉得hzwer的LCA模版更加优美，于是膜拜了一下。

#include<cstdio>
#include<algorithm>
using namespace std;

int fa[1005][12],f[1005],n,q,en,h[1005],deep[1005],flg[1005];

struct Edge{
int b,v,next;
}e[2005];

void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

void Yuchuli(int u){
flg[u]=1;
for(int i=1;i<=10;i++){
    if(deep[u]<(1<<i))break;
    fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(flg[v])continue;
    f[v]=f[u]+e[i].v;
    fa[v][0]=u;
    deep[v]=deep[u]+1;
    Yuchuli(v);
}
}

int LCA(int u,int v){
if(deep[u]<deep[v])swap(u,v);
int dep=deep[u]-deep[v];
for(int i=0;i<=10;i++)if((1<<i)&dep)u=fa[u][i];
for(int i=10;i>=0;i--){
    if(fa[u][i]!=fa[v][i]){
        u=fa[u][i];
        v=fa[v][i];
    }
}
return u==v?u:fa[u][0];
}

int main(){
freopen("1602.in","r",stdin);
freopen("1602.out","w",stdout);
scanf("%d %d",&n,&q);
for(int i=1;i<n;i++){
    int sa,sb,sc;
    scanf("%d %d %d",&sa,&sb,&sc);
    add(sa,sb,sc);
    add(sb,sa,sc);
}
Yuchuli(1);
while(q--){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    printf("%d\n",f[sa]+f[sb]-2*f[LCA(sa,sb)]);
}
return 0;
}

这题是一个打表找规律。

据说这题可以dp，但是我并不想写。(懒癌晚期)

具体的找规律方式：点击这里

dp:点击这里

#include<cstdio>

int n,f[2505];

int main(){
freopen("1600.in","r",stdin);
freopen("1600.out","w",stdout);
scanf("%d",&n);
f[4]=1;
for(int i=5;i<=n;i++){
    if(i&1)f[i]=f[i-1]+(i-2)*(i/2-1);
    else f[i]=f[i-1]+i/2-1;
}
printf("%d\n",f[n]);
return 0;
}

这是一个筛法。

#include<cstdio>
#include<algorithm>
using namespace std;

int n,a[1000005],s[1000005],c[1000005],mx;

int main(){
freopen("1607.in","r",stdin);
freopen("1607.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    c[a[i]]++;
    mx=max(a[i],mx);
}
for(int i=1;i<=mx;i++){
    if(c[i]){
        for(int j=i;j<=mx;j+=i)s[j]+=c[i];
    }
}
for(int i=1;i<=n;i++)printf("%d\n",s[a[i]]-1);
return 0;
}