Bronze
A Cow Gymnastics
题目：https://www.luogu.com.cn/problem/P5831
题解：用数组存一下出现位置，O(n^2)枚举一下就好。
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
#define I inline void
#define IN inline int
typedef long long ll;
I read(int &res){
re g=1;register char ch=getchar();res=0;
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
int n,m,a[100][100],b[100][100],sn,ans;
int main(){
freopen("gymnastics.in","r",stdin);
freopen("gymnastics.out","w",stdout);
read(m);read(n);
F(i,1,m){
F(j,1,n){
read(a[i][j]);
b[i][a[i][j]]=j;
}
}
F(i,1,n-1){
F(j,i+1,n){
sn=1;
if(b[1][i]>b[1][j]){
F(k,2,m)
if(b[k][i]<b[k][j]){
sn=0;
break;
}
}
else{
F(k,2,m){
if(b[k][i]>b[k][j]){
sn=0;
break;
}
}
}
ans+=sn;
}
}
cout<<ans;
return 0;
}
B Where Am I?
题目:https://www.luogu.com.cn/problem/P5832
题解：枚举一下K,哈希一下用map一存就行。复杂度：O(n^2)
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
#define I inline void
#define IN inline int
typedef long long ll;
I read(int &res){
re g=1;register char ch=getchar();res=0;
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
const int Mod=1e9+7,bas=131;
set<int>mp;
char c[110];
int n,m,a[110],j,s;
int main(){
freopen("whereami.in","r",stdin);
freopen("whereami.out","w",stdout);
read(n);
scanf("%s",c+1);
F(i,1,n){
a[i]=c[i]-'A'+1;
}
F(len,1,n){
mp.clear();m=1;
F(i,1,n-len+1){
j=i+len-1;s=0;
F(k,i,j){
s=(ll)s*bas%Mod;
s+=a[k];
}
if(mp.count(s)){
m=0;
break;
}
mp.insert(s);
}
if(m){
cout<<len;
return 0;
}
}
return 0;
}
C Livestock Lineup
题目：https://www.luogu.com.cn/problem/P5833
题解：按字典序爆搜即可。当然，我写的比较麻烦，
建了图，还要用每个点的度数分类讨论，其实复杂度
还是一样，O(8!*8)
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
#define I inline void
#define IN inline int
typedef long long ll;
I read(int &res){
re g=1;register char ch=getchar();res=0;
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
string s[9]={"0","Beatrice","Belinda","Bella","Bessie","Betsy","Blue","Buttercup","Sue"};
char c[100];
int n,m,a[10][10],x,y,du[10],ans[10],v[10];
I D_1(int x){
/* cout<<x<<" ";
F(i,1,x){
cout<<ans[i]<<" ";
}
cout<<endl;*/
if(x==9){
if(du[ans[x-1]]==2)return;
F(i,1,8){
cout<<s[ans[i]]<<endl;
}
exit(0);
}
re sn=0;
if(du[ans[x-1]]>=1){
F(i,1,8){
if(a[ans[x-1]][i]&&!v[i]){
sn++;
}
}
if(sn==2)return;
sn=1;
F(i,1,8){
if(a[ans[x-1]][i]&&!v[i]){
ans[x]=i,v[i]=1,D_1(x+1),v[i]=0;sn=0;
break;
}
}
if(!sn)return;
}
F(i,1,8){
if(v[i])continue;
ans[x]=i,v[i]=1,D_1(x+1);
ans[x]=0;v[i]=0;
}
}
int main(){
freopen("lineup.in","r",stdin);
freopen("lineup.out","w",stdout);
read(n);
memset(a,0,sizeof(a));
memset(du,0,sizeof(du));
F(i,1,n){
cin>>c+1;
m=strlen(c+1);
if(m==3)x=8;
if(m==4)x=6;
if(m==6)x=4;
if(m==7)x=2;
if(m==8)x=1;
if(m==9)x=7;
if(m==5){
if(c[3]=='l')x=3;
else x=5;
}
cin>>c+1>>c+1>>c+1>>c+1>>c+1;
m=strlen(c+1);
if(m==3)y=8;
if(m==4)y=6;
if(m==6)y=4;
if(m==7)y=2;
if(m==8)y=1;
if(m==9)y=7;
if(m==5){
if(c[3]=='l')y=3;
else y=5;
}
du[x]++;du[y]++;
a[x][y]=1;a[y][x]=1;
//cout<<x<<" "<<y<<endl;
}
F(i,1,n){
if(du[i]<2){
ans[1]=i;v[i]=1;
D_1(2);v[i]=0;
}
}
//cout<<"!";
return 0;
}
Silver
A MooBuzz
题目：https://www.luogu.com.cn/problem/P5834
题解：可以明显看出，每15次，有8个数被报出来。
随便写写就过了
复杂度O(1）
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
#define I inline void
#define IN inline int
typedef long long ll;
I read(int &res){
re g=1;register char ch=getchar();res=0;
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
int n,m,ans;
int main(){
freopen("moobuzz.in","r",stdin);
freopen("moobuzz.out","w",stdout);
read(n);
if(n%8==0){
ans=(n/8)*15;
ans--;
cout<<ans;
return 0;
}
ans=(n/8)*15;
n%=8;m=0;
F(i,1,n){
while(m%3==0||m%5==0)m++;
if(i==n){
ans+=m;
break;
}
m++;
}
cout<<ans;
return 0;
}
B Meetings
题目：https://www.luogu.com.cn/problem/P5835
题解：相信这道题的两个套路大家应该都见过：
1.不管这些牛怎么走，他们的相对位置都是不变的（没见过的一定要细细斟酌）
2.两头牛相遇后，可以看做是“擦肩而过”，也就是并没有改变方向。所以，
我们可以直接算出每头牛走到终点的时间。
知道了这两个性质，做法就顺水推舟了：
1.用类似归并排序的方法算出时刻T，由性质1，我们对时间和重量做出贡献的并不是一头牛（一定要小心）;
2.因为时间已经确定，所以可以固定向一个方向走的牛不动，相当于另一个方向走的牛走了2*T个单位距离。
对两种方向的牛分别排序，双指针扫一下即可。具体实现看代码。
复杂度：O(nlogn)
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register ll
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
#define I inline void
#define IN inline ll
typedef long long ll;
I read(ll &res){
re g=1;register char ch=getchar();res=0;
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
struct P{
ll x,w;
}l[50500],r[50500],p[101000];
ll n,m,num,tot,sum,W,X,d,Y,cnt,T,ans,L,R;
inline bool bb1(P a,P b){
return a.x==b.x?a.w>b.w:a.x>b.x;
}
inline bool bb2(P a,P b){
return a.x==b.x?a.w<b.w:a.x<b.x;
}
IN max(ll x,ll y){
return x>y?x:y;
}
int main(){
freopen("meetings.in","r",stdin);
freopen("meetings.out","w",stdout);
read(n);read(m);
tot=sum=num=0;
F(i,1,n){
read(W);read(X);read(d);num+=W;
p[i].x=X;p[i].w=W;
if(d==1)tot++,l[tot].x=X,l[tot].w=W;
else sum++,r[sum].x=X,r[sum].w=W;
}
sort(l+1,l+1+tot,bb1);
sort(r+1,r+1+sum,bb2);
sort(p+1,p+1+n,bb2);
X=1;Y=1;cnt=0;T=0;L=1;R=n;
while(cnt*2<num){
if(m-l[X].x>r[Y].x)cnt+=p[L++].w,T=r[Y].x,Y++;
else cnt+=p[R--].w,T=m-l[X].x,X++;
}
//cout<<X<<" "<<Y<<" "<<T<<endl;
sort(l+1,l+1+tot,bb2);
X=1;Y=1;
F(i,1,sum){
while(X<=tot&&l[X].x<max(0ll,r[i].x-T-T))X++;
while(Y<=tot&&l[Y].x<=r[i].x)Y++;
//cout<<X<<" "<<Y<<endl;
ans+=(Y-X);
}
cout<<ans;
return 0;
}
C Milk Visits
题目：https://www.luogu.com.cn/problem/P5836
题解：树剖+线段树板子题。详细讲解请见下一道Milk Visits。
复杂度：O(nlog^2n)
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
#define I inline void
#define IN inline int
typedef long long ll;
I read(int &res){
re g=1;register char ch=getchar();res=0;
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
char c[101000];
struct E{
int to,nt;
}e[202000];
#define T e[k].to
char sit;
int n,m,head[101000],fa[101000],X,Y,tot=-1,tr[101000],t[101000],siz[101000],top[101000],son[101000],id[101000],dep[101000];
I D_1(int x,int fat,int depth){
siz[x]=1;dep[x]=depth;son[x]=-1;fa[x]=fat;
re maxi=-1;
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fat)continue;
D_1(T,x,depth+1);
siz[x]+=siz[T];
if(maxi<siz[T])maxi=siz[T],son[x]=T;
}
}
IN lbt(int x){
return x&(-x);
}
I modi(int x){
while(x<=n)tr[x]++,x+=lbt(x);
}
I modify(int x){
while(x<=n)t[x]++,x+=lbt(x);
}
I D_2(int x,int fat,int topi){
top[x]=topi;id[x]=++tot;
if(c[x]=='H')modi(id[x]);else modify(id[x]);
if(son[x]!=-1)D_2(son[x],x,topi);
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fat||T==son[x])continue;
D_2(T,x,T);
}
}
IN ques_sum(int x){
re res=0;
while(x)res+=tr[x],x-=lbt(x);
return res;
}
IN query(int x){
re res=0;
while(x)res+=t[x],x-=lbt(x);
return res;
}
IN ques(int x,int y,char S){
re res=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
if(S=='H')res=(ques_sum(id[x])-ques_sum(id[top[x]]-1));
else res=(query(id[x])-query(id[top[x]]-1));
if(res)return 1;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
if(S=='H')res=ques_sum(id[y])-ques_sum(id[x]-1);
else res=query(id[y])-query(id[x]-1);
if(res)return 1;
return 0;
}
int main(){
freopen("milkvisits.in","r",stdin);
freopen("milkvisits.out","w",stdout);
read(n);read(m);
cin>>c+1;
memset(head,-1,sizeof(head));
tot=-1;
F(i,1,n-1){
read(X);read(Y);
e[++tot].to=Y;
e[tot].nt=head[X];
head[X]=tot;
e[++tot].to=X;
e[tot].nt=head[Y];
head[Y]=tot;
}
D_1(1,0,1);
tot=0;
D_2(1,0,1);
while(m--){
read(X);read(Y);cin>>sit;
cout<<ques(X,Y,sit);
}
return 0;
}
Gold
A Milk Pumping
题目：https://www.luogu.com.cn/problem/P5837
题解：从1到1000枚举这个最小流量，跑最短路就好。
复杂度：O(1000*(n+m)logn)
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
#define I inline void
#define IN inline int
typedef long long ll;
I read(int &res){
re g=1;register char ch=getchar();res=0;
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
struct E{
int to,nt,w,v;
}e[2020];
#define T e[k].to
const int INF=1e9+7;
int n,m,head[1010],X,Y,W,V,dis[1010],vis[1010],p,ans,tot;
queue<int>q;
int main(){
freopen("pump.in","r",stdin);
freopen("pump.out","w",stdout);
read(n);read(m);
memset(head,-1,sizeof(head));tot=-1;
F(i,1,m){
read(X);read(Y);read(W);read(V);
e[++tot].to=Y;
e[tot].nt=head[X];
head[X]=tot;
e[tot].w=W;
e[tot].v=V;
e[++tot].to=X;
e[tot].nt=head[Y];
head[Y]=tot;
e[tot].w=W;
e[tot].v=V;
}
ans=0;
F(val,1,1000){
F(i,1,n)dis[i]=INF,vis[i]=0;
dis[1]=0,vis[1]=1;
q.push(1);
while(!q.empty()){
p=q.front();q.pop();vis[p]=0;
for(re k=head[p];k!=-1;k=e[k].nt){
if(e[k].v<val)continue;
if(dis[p]+e[k].w<dis[T]){
dis[T]=dis[p]+e[k].w;
if(!vis[T]){
vis[T]=1;
q.push(T);
}
}
}
}
if(dis[n]!=INF)ans=max(ans,val*1000000/dis[n]);
}
cout<<ans;
return 0;
}
B Milk Visits
题目：https://www.luogu.com.cn/problem/P5838
题解：在上一道Milk Visits中，我们用两个线段树维护了树上的信息，
这里，我们显然不能直接开1e5棵线段树，所以考虑避免这个问题。
Approach 1:可持久化线段树
这个嘛。。。不会的打一下模板题就会了，这里就不讲了。
Approach 2:离线
遇到不强制在线，且无修改的题目，离线算法是一定要take into consideration的。
我们将每个点的点权当做修改，和查询中每个人的喜好牛奶一起排序，按点权排序。
这样，我们就只需要在一棵线段树上进行修改、查询操作了。每次先打个lazytag清空
之前的信息，然后将一个点权的所有点插入线段树，然后查询。
具体实现还是看代码。
复杂度：O(nlog^2n)
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
#define I inline void
#define IN inline int
typedef long long ll;
I read(int &res){
re g=1;register char ch=getchar();res=0;
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
char c[101000];
struct E{
int to,nt;
}e[202000];
struct Q{
int x,y,p,id;
friend bool operator < (Q a,Q b){
return a.p==b.p?a.id<b.id:a.p<b.p;
}
}q[202000];
#define T e[k].to
char sit;
int n,m,now,ans[101000],a[100100],tr[404000],laz[404000],head[101000],fa[101000],X,Y,tot=-1,siz[101000],top[101000],son[101000],id[101000],dep[101000];
I D_1(int x,int fat,int depth){
siz[x]=1;dep[x]=depth;son[x]=-1;fa[x]=fat;
re maxi=-1;
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fat)continue;
D_1(T,x,depth+1);
siz[x]+=siz[T];
if(maxi<siz[T])maxi=siz[T],son[x]=T;
}
}
I D_2(int x,int fat,int topi){
top[x]=topi;id[x]=++tot;
q[tot].x=x;q[tot].y=id[x];q[tot].p=a[x];q[tot].id=-1;
//将每个点看做修改，id为负是为了使其排序时排在查询前面
if(son[x]!=-1)D_2(son[x],x,topi);
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fat||T==son[x])continue;
D_2(T,x,T);
}
}
#define all 1,1,n
#define lt k<<1,l,mid
#define rt k<<1|1,mid+1,r
I modi(int k,int l,int r,int x){
if(l==r){
tr[k]=1;
return;
}
if(laz[k])tr[k<<1]=tr[k<<1|1]=laz[k]=0,laz[k<<1]=laz[k<<1|1]=1;
re mid=(l+r)>>1;
if(x<=mid)modi(lt,x);
else modi(rt,x);
tr[k]=tr[k<<1]|tr[k<<1|1];
}
IN ques_sum(int k,int l,int r,int x,int y){
if(x>r||y<l)return 0;
if(x<=l&&r<=y)return tr[k];
if(laz[k])tr[k<<1]=tr[k<<1|1]=laz[k]=0,laz[k<<1]=laz[k<<1|1]=1;
re mid=(l+r)>>1;
return ques_sum(lt,x,y)|ques_sum(rt,x,y);
}
IN ques(int x,int y){
re res=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
res|=ques_sum(all,id[top[x]],id[x]);
if(res)return 1;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
res|=ques_sum(all,id[x],id[y]);
if(res)return 1;
return 0;
}
int main(){
freopen("milkvisits.in","r",stdin);
freopen("milkvisits.out","w",stdout);
read(n);read(m);
F(i,1,n){
read(a[i]);
}
memset(head,-1,sizeof(head));
tot=-1;
F(i,1,n-1){
read(X);read(Y);
e[++tot].to=Y;
e[tot].nt=head[X];
head[X]=tot;
e[++tot].to=X;
e[tot].nt=head[Y];
head[Y]=tot;
}
D_1(1,0,1);
tot=0;
D_2(1,0,1);
F(i,1,m){
tot++;
read(q[tot].x);read(q[tot].y);read(q[tot].p);q[tot].id=i;
}
sort(q+1,q+1+tot);
now=q[1].p;
F(i,1,tot){
if(q[i].p>now)laz[1]=1,tr[1]=0,now=q[i].p;//点权变化时，清空线段树，打懒标记是一个不错的处理方式
if(q[i].id<0)modi(all,q[i].y);
else ans[q[i].id]=ques(q[i].x,q[i].y);
}
F(i,1,m){
cout<<ans[i];
}
return 0;
}
C Moortal Cowmbat
题目：https://www.luogu.com.cn/problem/P5839
题解：首先观察到m很小，先O(m^3)floyd判一下两两之间的最小代价。
设f[i][j]表示处理了前i个字符，最后一堆字符为j的最小代价。
可以口胡一下转移方程
暴力转移是O(n^2m^2)的，我们无法接受。
考虑优化这个dp。
O(n^2m)
考虑到当前的转移并不需要知道上一次的最后一段的字母是什么，我们
可以先对i的所有的f[i][j]取个min,再进行转移。
O(nm)
发现对于当前的i，可以转移到它的p是从1开始的一段连续区间。
我们设f[i]表示处理完前i个字母的最小代价，sum[i][j]表示从1到i，
将所有字母都变为j的代价。
这样，转移方程就可以写为：
f[i]=min{f[p]+sum[i][j]-sum[p][j},p (in) [1,i-k]
枚举特定的j时，可以将sum[i][j]从这个max里提出来。
发现只需要取f[p]-sum[p][j]的min。
我们设mx[j]表示对于p (in) [1,i-k],f[p]-sum[p][j]的最小值。
这样，转移就变成了O(1)。具体实现还有一些小细节，看代码吧~
复杂度：O(m^3+nm)
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
#define I inline void
#define IN inline int
typedef long long ll;
I read(int &res){
re g=1;register char ch=getchar();res=0;
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
const int INF=1e9+7;
char c[101000];
int n,m,k,a[101000],dis[30][30],mx[30],sum[101000][30],f[101000];
int main(){
freopen("cowmbat.in","r",stdin);
freopen("cowmbat.out","w",stdout);
read(n);read(m);read(k);
cin>>c+1;
F(i,1,n){
a[i]=c[i]-'a'+1;
}
F(i,1,m){
F(j,1,m){
read(dis[i][j]);
}
}
F(k,1,m){
F(i,1,m){
F(j,1,m){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//Floyd
}
}
}
memset(mx,0,sizeof(mx));
memset(sum,0,sizeof(sum));
F(i,1,k-1){
F(j,1,m){
sum[i][j]=sum[i-1][j]+dis[a[i]][j];//预处理sum
}
}
F(i,k,n){
f[i]=INF;
if(i>=(k<<1)){
F(j,1,m){
mx[j]=min(mx[j],f[i-k]-sum[i-k][j]);//i<2k时不存在合法的f
}
}
F(j,1,m){
sum[i][j]=sum[i-1][j]+dis[a[i]][j];
f[i]=min(f[i],mx[j]+sum[i][j]);
}
}
cout<<f[n];
return 0;
}
Platinum
A Greedy Pie Eaters
题目：http://www.usaco.org/index.php?page=viewproblem2&cpid=972
题目大意：有n个派，m头牛，每头牛有一个区间[l,r]和一个权值w。
没有两头牛有相同的[l,r]。
你需要选择一些牛，按一定顺序吃派。每头牛会吃完他的那个区间的所有派。
问在满足每头牛都至少有一个派吃的情况下，能获得的最大权值是多少。
n<=300,m<=45000
题解：n很小，可以想到区间DP。
设f[i][j]表示吃掉的派是[i,j]的子集的最大权值。
显然，f[i][j]=max{f[i][k-1]+f[k][j]}，k(in)[i,j]
但这样的转移不能加入新的牛。
可以考虑待合并的两个状态f[i][k-1]和f[k+1][j],此时k这个派还没有牛动。
我们设mx[k][i][j]表示满足i<=l[k]<=k<=r[k]<=j的所有牛的最大权值。
那么加入新牛的转移方程就出炉了：
f[i][j]=max{f[i][k-1]+mx[k][i][j]+f[k+1][j]},k(in)(i,j)
复杂度O(n^3)
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
template<class D>I read(D &res){
res=0;register D g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
int n,m,mx[330][330][330],f[330][330],W,X,Y;
int main(){
freopen("pieaters.in","r",stdin);
freopen("pieaters.out","w",stdout);
read(n);read(m);
memset(mx,0,sizeof(mx));
F(i,1,m){
read(W);read(X);read(Y);
F(j,X,Y)mx[j][X][Y]=max(W,mx[j][X][Y]);
}
F(i,1,n){
FOR(j,i,1){
F(k,i,n){
if(j>1)mx[i][j-1][k]=max(mx[i][j-1][k],mx[i][j][k]);
if(k<n)mx[i][j][k+1]=max(mx[i][j][k+1],mx[i][j][k]);
}
}
}
FOR(i,n,1){
F(j,i,n){
F(k,i,j-1)f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
F(k,i,j)f[i][j]=max(f[i][j],mx[k][i][j]+(k>i?f[i][k-1]:0)+(k<j?f[k+1][j]:0));
}
}
printf("%d",f[1][n]);
return 0;
}
B Bessie's Snow Cow
题目：http://www.usaco.org/index.php?page=viewproblem2&cpid=973
题目大意：给你一棵树，要求支持两种操作：
1.给定x,c,给x的子树染上颜色c（一个节点可以有多个颜色）
2.给定x,求x的子树的所有节点的所有颜色个数和（每个节点单独算）
题解：这个题有两个难点：
1.修改时，如何更新其对子树内节点的贡献，以及如何上传对祖先的影响；
2.查询时，如何一次性统计子树内所有节点的贡献
我们发现，如果将一个操作的复杂度变为O(logn)甚至O(1),另一个操作的
复杂度将不可避免地到达O(n)。
考虑统计答案。答案可以分为两个部分：一是x或x的祖先已经染过的颜色，
这些的贡献可以一并计算;二是子树内染色的情况。
对于第一个，我们在每次修改时区间加就行了，当然还要撤销之前子树内
的一些修改操作的贡献。
我们以这棵树的dfs序为下标开一个树状数组，用差分维护每个节点已经染
上的颜色个数，再开1e5个set记录下每个颜色的染色情况，避免重复染色。
每次修改操作步骤如下：
1.判断x的祖先是否已经被染上c色。若已经染色，直接退出；
2.查询x子树内是否有节点染上c色。若已经染色，撤销其影响并在set中
删除此节点；
3.将此次修改加入set,进行区间修改。
那对于第二个，又该怎么求呢？
因为这些贡献是一段dfs序连续区间的单点贡献，我们可以另开一个树状数组
记录这个贡献。每次修改只需要单点+siz[x]即可。
修改操作的步骤同上。每次只需要查询[id[x]+1,id[x]+siz[x]-1]这段区间的
贡献即可（也就是x子树除去x节点的贡献）
设两个查询得到的值是ans1和ans2,那么答案即为：siz[x]*ans1+ans2
复杂度：因为每次修改只会被加入和撤销一次，每次都是O(logn),
查询也是O(logn)的，所以总复杂度即为O(nlogn)
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register ll
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline ll
template<class D>I read(D &res){
res=0;register D g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
const ll INF=1e9+7;
struct E{
ll to,nt;
}e[202000];
#define T e[k].to
ll n,m,tot,sit,X,Y,head[101000],siz[101000],id[101000],p[101000],out[101000];
struct BIT{
ll tr[101000],res;
IN lbt(ll x){
return x&(-x);
}
I modi(ll x,ll w){while(x<=n){tr[x]+=w,x+=lbt(x);}}
IN ques(ll x){res=0;while(x){res+=tr[x],x-=lbt(x);}return res;}
}A,B;
set<ll>s[101000];
I modify(ll x,ll sn){
A.modi(id[x],sn);
A.modi(out[x]+1,-1*sn);
B.modi(id[x],sn*siz[x]);
//cout<<id[x]<<" "<<out[x]<<" "<<sn<<endl;
}
I D_1(ll x,ll fa){
id[x]=++tot;siz[x]=1;p[tot]=x;
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fa)continue;
D_1(T,x);siz[x]+=siz[T];
}
out[x]=tot;
}
int main(){
freopen("snowcow.in","r",stdin);
freopen("snowcow.out","w",stdout);
read(n);read(m);
memset(head,-1,sizeof(head));
tot=-1;
F(i,1,n-1){
read(X);read(Y);
e[++tot].to=Y;
e[tot].nt=head[X];
head[X]=tot;
e[++tot].to=X;
e[tot].nt=head[Y];
head[Y]=tot;
}
F(i,0,100000)s[i].insert(INF);
tot=0;
D_1(1,0);
//F(i,1,n)cout<<id[i]<<" "<<siz[i]<<" "<<out[i]<<endl;
while(m--){
read(sit);read(X);
if(sit==1){
read(Y);
auto P=s[Y].upper_bound(id[X]);
if(P!=s[Y].begin()&&out[p[*prev(P)]]>=out[X])continue;
while(1){
P=s[Y].upper_bound(id[X]);
if(*P>out[X])break;
modify(p[*P],-1);
s[Y].erase(P);
}
s[Y].insert(id[X]);
modify(X,1);
}
else printf("%lld
",siz[X]*A.ques(id[X])+B.ques(out[X])-B.ques(id[X]));//printf("%d %d %d %d %d %lld
",id[X],out[X],A.ques(id[X]),B.ques(out[X]),B.ques(id[X]),(ll)siz[X]*A.ques(id[X])+(ll)B.ques(out[X])-(ll)B.ques(id[X]));
}
return 0;
}
C Tree Depth
待填坑~