I:QSC and Master
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5900
题意：
给出n对数keyi,vali表示当前这对数的键值和权值，可以操作将连续的两个数合并，如果满足gcd(a[i],a[i+1])>1，得到的价值是两个数的权值和，每次合并两个数之后，这两个数就会消失，然后旁边的数会接上比如1 2 3 4 合并了 2 3 则 剩下1 4也可以合并
思路：区间dp
1：处理出任意区间内的所有数是否可以合并
对于当前的[l,r]区间，如果区间[l+1,r-1]可以合并，且gcd(a[l]+a[r])！=1的话，则整个区间[l,r]可以合并，价值也就是前缀和
同理处理出其他的情况 [l,r-2] [l+1,r]
2：区间dp，对于当前的l,r区间，如果可以合并，则直接加上区间和
反之，则枚举一个中间值k，找出区间内最大满足情况的值
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
typedef long long ll;
ll n;
ll num[maxn],val[maxn];
ll dp[maxn][maxn];
ll out[maxn][maxn];
ll sum[maxn];
ll gcd(ll x,ll y){
return x==?y:gcd(y%x,x);
}
//确定1-n的最大值
void Dp(){
memset(out,,sizeof(out));
for(ll l=;l<=n;l++){
for(ll i=;i+l-<=n;i++){
ll j=i+l-;
if(dp[i][j]==)
out[i][j]=sum[j]-sum[i-];
else{
for(ll k=i;k<j;k++){
out[i][j]=max(out[i][j],out[i][k]+out[k+][j]);
}
}
}
}
}
//判断区间是否能合并
void query(){
memset(dp,,sizeof(dp));
for(ll i=;i<n;i++){
if(gcd(num[i],num[i+])!=)
dp[i][i+]=;
}
for(ll l=;l<=n;l+=){
for(ll i=;i+l-<=n;i++){
ll j=i+l-;
if(gcd(num[i],num[j])!=&&dp[i+][j-]==)
dp[i][j]=;
if(gcd(num[i],num[i+])!=&&dp[i+][j]==)
dp[i][j]=;
if(gcd(num[j-],num[j])!=&&dp[i][j-]==)
dp[i][j]=;
}
}
Dp();
} int main(){
ll t;
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
memset(sum,,sizeof(sum));
for(ll i=;i<=n;i++){
scanf("%lld",&num[i]); }
for(ll i=;i<=n;i++){
scanf("%lld",&val[i]);
sum[i]=sum[i-]+val[i];
}
query();
cout<<out[][n]<<endl;
}
}
odd-even number
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5898
题意：
给你一个区间，问你这个区间中满足连续的偶数的位数为奇数，连续的奇数的位数是偶数的个数
题解：
设dp[i][j][k][l]为考虑当前第i位，上一位的奇偶性为j，已经连续了k位，是否有前导零
然后记忆化搜就行了
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef long long ll; int dig[],len;
ll dp[][][][]; ll dfs(int pos,int pre=,int ln=,bool inf=,bool ze=)//pre 1为奇;0为偶，ze是否有前导零 1代表有，0没有;inf判断当前位最大值 1表示最大值为dig[pos]
{
if(!pos)//搜索完成时，根据连续的长度和当前连续的是奇数还是偶数判断反回1还是0
{
if(pre)return (ln&)==;
else return ln&;
}
if(!inf&&dp[pos][pre][ln][ze]!=-)return dp[pos][pre][ln][ze];
int en=inf?dig[pos]:;//当前位最大放几
//cout<<pos<<" "<<en<<endl;
ll ans=;
F(i,,en)
{
if(i&)//当前数为奇数
{
//cout<<i<<" "<<"?"<<endl;
if(ze)//上一位为0的情况
{
ans+=dfs(pos-,,,inf&&i==en,);
}
else if(pre==)//上一位为偶数,因为本次是奇数，所以ln从1开始
{
if(ln&)
ans+=dfs(pos-,,,inf&&i==en,ze);
}
else if(pre==)//上一位为奇数
{
ans+=dfs(pos-,,ln+,inf&&i==en,ze);
}
}
else//偶数
{
if(ze)
{
if(i==)ans+=dfs(pos-,,,inf&&i==en,);
else ans+=dfs(pos-,,,inf&&i==en,);
}
else if(pre==)ans+=dfs(pos-,,ln+,inf&&i==en,ze);
else if(pre==)
{
if((ln&)==)ans+=dfs(pos-,,,inf&&i==en,ze);
}
}
}
if(!inf)dp[pos][pre][ln][ze]=ans;
return ans;
} int main(){
int t,ic=;ll l,r;
scanf("%d",&t);
while(t--)
{
memset(dp,-,sizeof(dp));
scanf("%lld%lld",&l,&r),l--;
for(len=;l;l/=)dig[++len]=l%;//将数转化为字符串但是逆序存放
ll tp=dfs(len);
for(len=;r;r/=)dig[++len]=r%;
printf("Case #%d: %lld\n",ic++,dfs(len)-tp);
}
return ;
}
List wants to travel
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5893
题目大意：
给出一棵树上的两种操作：
1.将节点a到节点b路径上的边权全部修改为c；
2.查询节点a到节点b路径上边权的段数。
解题思路：
先进行树链剖分，将问题转化到区间上，之后统计段数是经典的线段树区间合并问题。修改操作直接修改就好了，对于查询操作，需要注意链的合并，可以先求一次a与b的LCA，之后将路径分为两段分别查询，最后看拼接处权值是否相同。
#include<bits/stdc++.h>
using namespace std;
#define maxn 40010
const int MAXM = ;
struct Edge
{
int to,next;
int len;
}e[MAXM*];
int first[maxn];
int top[maxn];//top[v]表示v所在的重链的顶端节点
int fa[maxn]; //父亲节点
int deep[maxn];//深度
int num[maxn];//num[v]表示以v为根的子树的节点数
int p[maxn];//p[v]表示v与其父亲节点的连边在线段树中的位置
int fp[maxn];//和p数组相反
int son[maxn];//重儿子
int pos,tot,Lc,Rc;
int c[maxn],a[maxn];
void add(int u,int v,int len)
{
tot++;
e[tot].next=first[u];e[tot].to=v;e[tot].len=len;
first[u]=tot;
}
void dfs1(int u,int pre,int d) //第一遍dfs求出fa,deep,num,son
{
deep[u] = d;
fa[u] = pre;
num[u] = ;
for(int i = first[u];i != -; i = e[i].next)
{
int v = e[i].to;
if(v != pre)
{
a[v]=e[i].len;
dfs1(v,u,d+);
num[u] += num[v];
if(son[u] == - || num[v] > num[son[u]])
son[u] = v;
}
}
}
void getpos(int u,int sp) //第二遍dfs求出top和p
{
top[u] = sp;
if(son[u] != -)
{
p[u] = ++pos;
fp[p[u]] = u;
c[pos]=a[u];
getpos(son[u],sp);
}
else
{
p[u] = ++pos;
fp[p[u]] = u;
c[pos]=a[u];
return;
}
for(int i = first[u] ; i != -; i = e[i].next)
{
int v = e[i].to;
if(v != son[u] && v != fa[u])
getpos(v,v);
}
} //线段树
struct Node
{
int l,r;
int num;
int cl,cr;
int flag;
}segTree[MAXM*];
void push_up(int i)
{
segTree[i].cl=segTree[i<<].cl;
segTree[i].cr=segTree[i<<|].cr;
segTree[i].num=segTree[i<<].num+segTree[i<<|].num;
if(segTree[i<<].cr==segTree[i<<|].cl)
segTree[i].num--;
}
void push_down(int i){
if(segTree[i].flag==){
segTree[i<<].flag=segTree[i<<|].flag=;
segTree[i<<].cl=segTree[i<<].cr=segTree[i<<|].cl=segTree[i<<|].cr=segTree[i].cl;
segTree[i<<].num=segTree[i<<|].num=;
segTree[i].flag=-;
}
}
void build(int i,int l,int r)
{
segTree[i].l = l;
segTree[i].r = r;
segTree[i].flag=-;
if(l == r){
segTree[i].cl=segTree[i].cr=c[l];
segTree[i].num=;
return ;
}
int mid = (l+r)/;
build(i<<,l,mid);
build((i<<)|,mid+,r);
push_up(i);
} void update(int l,int r,int color,int i)
{
if(segTree[i].l == l && segTree[i].r == r)
{
segTree[i].num=;
segTree[i].flag=;
segTree[i].cl=segTree[i].cr=color;
return;
}
push_down(i);
int mid = (segTree[i].l + segTree[i].r)/;
if(r <= mid)update(l,r,color,i<<);
else if(l>mid) update(l,r,color,i<<|);
else{
update(l,mid,color,i<<);
update(mid+,r,color,i<<|);
}
push_up(i);
}
int query(int l,int r,int i,int L,int R)
{
if(segTree[i].l == L )
Lc=segTree[i].cl;
if(segTree[i].r==R)
Rc=segTree[i].cr;
if(segTree[i].l==l&&segTree[i].r==r){
return segTree[i].num;
}
push_down(i);
int mid = (segTree[i].l + segTree[i].r)/;
if(r <= mid)return query(l,r,i<<,L,R);
else if(l > mid)return query(l,r,i<<|,L,R);
else{
int num=query(l,mid,i<<,L,R)+query(mid+,r,i<<|,L,R);
if(segTree[i<<].cr==segTree[i<<|].cl)
num--;
return num;
}
}
int solve(int u,int v)
{
int f1 = top[u], f2 = top[v];
int tmp = ;
int pre1=-,pre2=-;
while(f1 != f2)
{
if(deep[f1] < deep[f2])
{
swap(pre1,pre2);
swap(f1,f2);
swap(u,v);
}
tmp +=query(p[f1],p[u],,p[f1],p[u]);
if(pre1==Rc)
tmp--;
pre1=Lc;
u = fa[f1]; f1 = top[u];
}
if(u!=v){
if(deep[u]<deep[v]){
swap(pre1,pre2);
swap(u,v);
}
tmp+=query(p[son[v]],p[u],,p[son[v]],p[u]);
if(pre1!=- && Rc==pre1)tmp--;
if(pre2!=- && Lc==pre2)tmp--;
}
else if(pre1==pre2)
tmp--;
return tmp;
} void gengxin(int u,int v,int value)
{
int f1,f2;
f1=top[u];f2=top[v];
while(f1!=f2){
if(deep[f1]<deep[f2]){
swap(f1,f2);swap(u,v);
}
update(p[f1],p[u],value,);
u=fa[f1];
f1=top[u];
}
if(deep[u]<deep[v]){
swap(u,v);
}
if(u!=v){
update(p[son[v]],p[u],value,);
}
}
int main()
{
int i,j,n,m,u,v,f,g,h,w;
char s[];
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(first,-,sizeof(first));
memset(son,-,sizeof(son));
pos=;tot=;
for(i=;i<=n-;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
dfs1(,,);
getpos(,); build(,,pos);
for(i=;i<=m;i++){
scanf("%s",s);
if(s[]=='Q'){
scanf("%d%d",&f,&g);
printf("%d\n",solve(f,g));
}
else{
scanf("%d%d%d",&f,&g,&h);
gengxin(f,g,h);
}
} }
return ;
}