T1
找规律，得到规律
联立得
结束
#include<bits/stdc++.h>
using namespace std;long long n;int main(){cin>>n;if(n<=31) cout<<(1ll<<n)-1;else cout<<(long long)(n*(log(2)/log(10)));}
T2
每个人有四个数字，朋友的定义是两人至少有一个数字相同，求每个人与左边的人有几个朋友，数字<=50
因为数字很小，直接开四维数组统计，根据小学奥数思想，最终答案应是calc1()-calc2()+calc3()-calc4()
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int num=0,fs=1;
char ch;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') fs=-1,ch=getchar();
while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
return num*fs;
}
int n,a[100009][5];
int tot1[51],tot2[51][51],tot3[51][51][51],tot4[51][51][51][51];
int ans;
int main ()
{
//freopen("friend.in","r",stdin);
//freopen("friend.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=4;j++)
{
a[i][j]=read();
}
sort(a[i]+1,a[i]+5);
ans=0;
for(int j=1;j<=4;j++)
{
ans+=tot1[a[i][j]];
}
for(int j=1;j<=3;j++)
{
for(int k=j+1;k<=4;k++)
{
ans-=tot2[a[i][j]][a[i][k]];
}
}
for(int a1=1;a1<=2;a1++)
{
for(int a2=a1+1;a2<=3;a2++)
{
for(int a3=a2+1;a3<=4;a3++)
{
ans+=tot3[a[i][a1]][a[i][a2]][a[i][a3]];
}
}
}
ans-=tot4[a[i][1]][a[i][2]][a[i][3]][a[i][4]];
printf("%d\n",ans);
for(int j=1;j<=4;j++)
{
tot1[a[i][j]]++;
}
for(int j=1;j<=3;j++)
{
for(int k=j+1;k<=4;k++)
{
tot2[a[i][j]][a[i][k]]++;
}
}
for(int a1=1;a1<=2;a1++)
{
for(int a2=a1+1;a2<=3;a2++)
{
for(int a3=a2+1;a3<=4;a3++)
{
tot3[a[i][a1]][a[i][a2]][a[i][a3]]++;
}
}
}
tot4[a[i][1]][a[i][2]][a[i][3]][a[i][4]]++;
}
return 0;
}
拓展：当k增大时，可以使用散列表进行统计
T3
裸的背包，不说了
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int num=0,fs=1;
char ch;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') fs=-1,ch=getchar();
while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
return num*fs;
}
int m,n,a[309],b[309],ans=1;
int f[1009][1009];
int main ()
{
//freopen("psolve.in","r",stdin);
//freopen("psolve.out","w",stdout);
m=read(),n=read();
memset(f,-1,sizeof(f));
f[1][m]=0;
for(int i=1;i<=n;i++)
{
a[i]=read(),b[i]=read();
}
while(1)
{
//cout<<ans<<endl;
for(int i=0;i<=m;i++)
{
if(f[ans][i]==-1) continue;
f[ans+1][m]=max(f[ans+1][m],f[ans][i]);
int nowcost=0,ntcost=0;
for(int k=1;f[ans][i]+k<=n;k++)
{
nowcost+=a[f[ans][i]+k],ntcost+=b[f[ans][i]+k];
if(nowcost<=i&&ntcost<=m)
{
//if(f[ans][i]+k>f[ans+1][m-ntcost]) cout<<ans+1<<" "<<m-ntcost<<" "<<f[ans][i]+k<<endl;
f[ans+1][m-ntcost]=max(f[ans+1][m-ntcost],f[ans][i]+k);
if(f[ans+1][m-ntcost]==n)
{
printf("%d",ans+2);
return 0;
}
}
else break;
}
}
ans++;
}
return 0;
}
T4
给定一棵树，每个点都有权值，查询在根为k的情况下节点x的子树权值和
分块，将sqrt(n)作为块大小，将一块点看作一个点，这样的话查询就分为块内查询，块外查询，块内统计，块外统计四部分，代码很长，但很好想，而且该算法优点很大（拓展的时候讲）
#include<bits/stdc++.h>
using namespace std;
int n,m;
int blong[100009],block,lenblock[100009],blockbh=1;
int fto[100009],f[100009];
int head[100009],to[200009],nt[200009],bh;
int bkhead[100009],bkto[100009],bknt[100009],bkfrom[100009],bknext[100009],bkbh;
int val[100009];
int nowroot=1;
int ans;
bool hasbkfinden,hasfinden;
int superx;
inline int read()
{
int num=0,fs=1;
char ch;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') fs=-1,ch=getchar();
while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
return num*fs;
}
inline void add(int u,int v)
{
bh++;
nt[bh]=head[u];
head[u]=bh;
to[bh]=v;
}
inline void bkadd(int u,int v,int x,int y)
{
bkbh++;
bknt[bkbh]=bkhead[u];
bkhead[u]=bkbh;
bkto[bkbh]=v;
bkfrom[bkbh]=x;
bknext[bkbh]=y;
}
void dfs2(int now,int fa)
{
if(lenblock[blong[fa]]>block) blockbh++;
blong[now]=blockbh;
lenblock[blockbh]++;
f[blockbh]+=val[now];
for(int i=head[now];i;i=nt[i])
{
if(to[i]!=fa)
{
dfs2(to[i],now);
}
}
}
void dfs3(int now,int fa)
{
for(int i=head[now];i;i=nt[i])
{
if(to[i]!=fa&&blong[to[i]]!=blong[now])
{
bkadd(blong[to[i]],blong[now],to[i],now);
bkadd(blong[now],blong[to[i]],now,to[i]);
//cout<<now<<" "<<to[i]<<" %%%"<<endl;
fto[to[i]]=blong[now];
fto[now]=blong[to[i]];
dfs3(to[i],now);
}
else if(to[i]!=fa) dfs3(to[i],now);
}
}
void bkdfs(int now,int fa)
{
ans+=f[now];
for(int i=bkhead[now];i;i=bknt[i])
{
if(bkto[i]!=fa)
{
bkdfs(bkto[i],now);
}
}
}
void dfs(int now,int fa)
{
//cout<<now<<" @@@"<<endl;
ans+=val[now];
for(int i=head[now];i;i=nt[i])
{
if(to[i]!=fa)
{
if(blong[to[i]]!=blong[now])
{
//cout<<blong[to[i]]<<" "<<blong[now]<<" &&&"<<endl;
bkdfs(blong[to[i]],blong[now]);
}
else
{
dfs(to[i],now);
}
}
}
}
void ffind(int now,int fa,int k)
{
if(hasfinden) return;
if(now==k)
{
hasfinden=1;
dfs(now,fa);
return;
}
for(int i=head[now];i;i=nt[i])
{
if(to[i]!=fa)
{
if(to[i]==k)
{
hasfinden=1;
//cout<<to[i]<<" "<<now<<" !!!"<<endl;
dfs(to[i],now);
}
ffind(to[i],now,k);
if(hasfinden) return;
}
}
}
void bkfind(int now,int fa,int k)
{
for(int i=bkhead[now];i;i=bknt[i])
{
if(bkto[i]!=fa)
{
if(bkto[i]==k)
{
//cout<<bknext[i]<<" "<<bkfrom[i]<<" "<<superx<<endl;
hasbkfinden=1;
ffind(bknext[i],bkfrom[i],superx);
}
bkfind(bkto[i],now,k);
if(hasbkfinden) return;
}
}
}
int main ()
{
//freopen("transform.in","r",stdin);
//freopen("transform.out","w",stdout);
n=read(),m=read();
block=sqrt(n)*1.6;
for(int i=1;i<n;i++)
{
int u=read(),v=read();
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++)
{
val[i]=read();
}
dfs2(1,0);
dfs3(1,0);
/*for(int i=1;i<=n;i++)
{
cout<<blong[i]<<" ";
}
cout<<endl;*/
nowroot=read();
for(int i=1,opt,x;i<=m;i++)
{
opt=read(),x=read();
superx=x;
if(opt==1)
{
nowroot=x;
}
else
{
ans=0;
hasbkfinden=hasfinden=0;
if(blong[nowroot]!=blong[x])
{
bkfind(blong[nowroot],0,blong[x]);
}
else
{
ffind(nowroot,0,x);
}
printf("%d\n",ans);
}
}
return 0;
}
拓展：
1、增加区间修改权值
2、改变连边
