挖坑
--------------------------
一 序列调整
hdu 3434 Sequence Adjustment
题目大意:给你含有n个数的序列,每次你可以选一个子序列将上面所有的数字加1或者减1,目标是把所有数字变成相同的,问最少步数,和那个相同的数字有多少种可能。
对序列中的相邻元素做差,假设元素i之前的序列已经相等,此时序列值为sum。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=1111111; typedef long long LL; int a[maxn]; LL b[maxn],p[maxn]; int n,m; int ans; int main() { int cas=0; int T; scanf("%d",&T); while (T--){ scanf("%d",&n); for (int i=0;i<n;i++) scanf("%d",&a[i]); m=0; b[m++]=a[0]; for (int i=1;i<n;i++){ if (a[i]!=a[i-1]) b[m++]=a[i]; } n=m-1; for (int i=0;i<n;i++){ p[i]=b[i]-b[i+1]; } //for (int i=0;i<m;i++) cerr<<b[i]<<" ";cerr<<endl; //for (int i=0;i<n;i++) cerr<<p[i]<<" ";cerr<<endl; LL sum=0,ans=0; for (int i=0;i<n;i++){ if (p[i]*sum<0) ans+=min(abs(sum),abs(p[i])); sum+=p[i]; } sum=abs(sum); ans+=sum; printf("Case %d: %I64d %I64d\n",++cas,ans,sum+1); } return 0; }
--------------------------
二 树的同构
HDU 4275 Color the Tree
此题要用到以下知识:
树的中心
树的hash,参考资料:Hash在信息学竞赛中的一类应用
组合数学,ans[u]表示以u为根节点的子树的总的染色方案,设有x个子树同构,则这x个子树总的染色方案为C(ans[v]+x-1,x)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
//定义
typedef pair<int,int>PII;
typedef long long LL;
//常量
const LL MOD=1e9+7;
const LL P=10003;
const int INF=0x3f3f3f3f;
const int maxn=71111;
const int maxm=201111;
const int maxSize=111111;
//图结构
struct EdgeNode{
int to,next;
}edges[maxm];
int head[maxn],edge;
int n;
//图管理
class GraphManager{
public:
void init(){
memset(head,-1,sizeof(head));
edge=0;
}
void addedge(int u,int v){
edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
}
}graph;
//树的中心
class CenterOfTree{
private:
int f[maxn],dp[maxn];
int M,MM,E;
int dfs(int u,int pa){
int m1=0,m2=0;
for (int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
if (v==pa) continue;
int t=dfs(v,u);
if (t>m1){
m2=m1;
m1=t;
f[u]=i;
}
else if (t>m2){
m2=t;
}
}
if (M<m1+m2) MM=u,M=m1+m2;
dp[u]=m1;
return dp[u]+1;
}
public:
void getCenter(int& Ct,int& Eg,bool& Nw){
M=-1;
dfs(1,-1);
if (M&1){
while (dp[MM]*2>M+1) MM=edges[f[MM]].to;
E=f[MM];
graph.addedge(MM,n+1);
graph.addedge(n+1,MM);
graph.addedge(edges[f[MM]].to,n+1);
graph.addedge(n+1,edges[f[MM]].to);
MM=n+1;
Nw=true;
}
else{
E=0;
while (dp[MM]*2>M) MM=edges[f[MM]].to;
Nw=false;
}
Ct=MM;
Eg=E;
}
}center;
//数学管理
class MathManager{
private:
LL fact[maxSize];
LL modPow(LL x,LL n){
if (n==0) return 1;
LL res=modPow(x*x%MOD,n/2);
if (n&1) res=res*x%MOD;
return res;
}
public:
void prepare(){
fact[1]=1;
for (int i=2;i<maxSize;i++){
fact[i]=fact[i-1]*i%MOD;
}
}
LL cal(int n,int m){
if (n==m) return 1;
LL n1=1,n2=fact[m];
for (int i=1;i<=m;i++) n1=n1*(n-i+1)%MOD;
return n1*modPow(n2,MOD-2)%MOD;
}
}math;
//算法管理
class AlgorithmManager{
private:
struct Data{
LL hash,ans;
Data(LL hash,LL ans){
this->hash=hash;
this->ans=ans;
}
bool operator<(const Data& rhs) const{
return hash<rhs.hash;
}
};
int Eg,Color;
vector<Data>q;
LL ans[maxn],hash[maxn],son[maxn];
void dfs(int u,int pa){
son[u]=0;
for (int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
if (v==pa||i==Eg||i==(Eg^1)) continue;
ans[v]=Color;
dfs(v,u);
son[u]++;
}
if (son[u]==0){
hash[u]=1;
return;
}
q.clear();
for (int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
if (v==pa||i==Eg||i==(Eg^1)) continue;
q.push_back(Data(hash[v],ans[v]));
}
sort(q.begin(),q.end());
hash[u]=977872;
for (int i=0,j;i<son[u];i++){
for (j=i;j<son[u]&&q[i].hash==q[j].hash;j++){
hash[u]*=P;
hash[u]^=q[j].hash;
hash[u]%=MOD;
}
j--;
ans[u]*=math.cal(q[i].ans+j-i,j-i+1);
ans[u]%=MOD;
i=j;
}
}
public:
LL solve(int Mt,int Eg,bool Nw,int Cl){
if (Nw) ans[Mt]=1;
else ans[Mt]=Cl;
this->Eg=Eg;
this->Color=Cl;
dfs(Mt,-1);
return ans[Mt];
}
}algo;
int main(){
int Color;
math.prepare();
while (~scanf("%d%d",&n,&Color)){
graph.init();
for (int i=0;i<n-1;i++){
int u,v;
scanf("%d%d",&u,&v);
graph.addedge(u,v);
graph.addedge(v,u);
}
int Mt,Eg;
bool Nw;
center.getCenter(Mt,Eg,Nw);
LL ans=algo.solve(Mt,Eg,Nw,Color);
printf("%I64d\n",ans);
}
}
--------------------------
--------------------------
--------------------------
--------------------------
--------------------------