Tree http://acm.hdu.edu.cn/showproblem.php?pid=5044
树链剖分，区间更新的时候要用on的左++右--的标记方法，要手动扩栈，用c++交，综合以上的条件可过。
#include<cstdio>
#include<cstring>
#include<algorithm>
#pragma comment(linker, "/STACK:36777216")
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef __int64 LL;
const int M=;
struct G{
struct E{
int v,next;
}e[M<<];
int le,head[M];
void init(){
le=;
mt(head,-);
}
void add(int u,int v){
e[le].v=v;
e[le].next=head[u];
head[u]=le++;
}
}g;
int n,val[M],fa[M],dep[M],num[M],son[M],top[M],sid[M];
void dfs(int u){
num[u]=;
son[u]=;
for(int i=g.head[u];~i;i=g.e[i].next){
int v=g.e[i].v;
if(v!=fa[u]){
fa[v]=u;
dep[v]=dep[u]+;
dfs(v);
if(num[son[u]]<num[v]) son[u]=v;
num[u]+=num[v];
}
}
}
void get(int u,int Top){
sid[u]=++n;
top[u]=Top;
if(son[u]) get(son[u],top[u]);
for(int i=g.head[u];~i;i=g.e[i].next){
int v=g.e[i].v;
if(v!=fa[u]&&v!=son[u]){
get(v,v);
}
}
}
LL lazy[M],ans[M];
void query(){
LL now=;
for(int i=;i<=n;i++){
now+=lazy[i];
ans[i]=now;
}
}
void update(int x,int y,int z){
lazy[x]+=z;
lazy[y+]-=z;
}
void worknode(int x,int y,int z){
int tx=top[x],ty=top[y];
while(tx!=ty){
if(dep[tx]<dep[ty]){
swap(tx,ty);
swap(x,y);
}
update(sid[tx],sid[x],z);
x=fa[tx];
tx=top[x];
}
if(dep[x]>dep[y]) swap(x,y);
update(sid[x],sid[y],z);
}
void workedge(int x,int y,int z){
int tx=top[x],ty=top[y];
while(tx!=ty){
if(dep[tx]<dep[ty]){
swap(tx,ty);
swap(x,y);
}
update(sid[tx],sid[x],z);
x=fa[tx];
tx=top[x];
}
if(x==y) return ;
if(dep[x]>dep[y]) swap(x,y);
update(sid[son[x]],sid[y],z);
}
struct IN{
int type,u,v,w;
}in[M];
struct EDGE{
int u,v;
}edge[M];
int main(){
int t,N,m,u,v;
while(~scanf("%d",&t)){
int cas=;
while(t--){
scanf("%d%d",&N,&m);
g.init();
for(int i=;i<N-;i++){
scanf("%d%d",&u,&v);
g.add(u,v);
g.add(v,u);
edge[i].u=u;
edge[i].v=v;
}
n=fa[]=dep[]=num[]=;
dfs();
get(,);
char op[];
for(int i=;i<m;i++){
scanf("%s%d%d%d",op,&in[i].u,&in[i].v,&in[i].w);
if(op[]=='') in[i].type=;
else in[i].type=;
}
mt(lazy,);
for(int i=;i<m;i++){
if(in[i].type&) worknode(in[i].u,in[i].v,in[i].w);
}
printf("Case #%d:\n",cas++);
query();
for(int i=;i<=N;i++){
if(i>) printf(" ");
printf("%I64d",ans[sid[i]]);
}
puts("");
mt(lazy,);
for(int i=;i<m;i++){
if(in[i].type==) workedge(in[i].u,in[i].v,in[i].w);
}
query();
for(int i=;i<N-;i++){
int u=edge[i].u;
int v=edge[i].v;
if(dep[u]<dep[v]){
swap(u,v);
}
if(i) printf(" ");
printf("%I64d",ans[sid[u]]);
}
puts("");
}
}
return ;
}
Contest http://acm.hdu.edu.cn/showproblem.php?pid=5045
根据题目要求，任意时刻都不能出现两个人做题数量的差大于1，也就是差要<=1，也就是m个问题要分成长度为n的等长的几块，每块里面一人做一个。
问题转化为n个人n题目，如何选一种排列来获得最大价值，若暴力枚举，复杂度是10！，所以用状态压缩，降为2^10，从000推到111.
转移时看哪个人没做过题，那么就可以让他做，状态就是他这位变为1，值就是当前状态的值加上这个人做当前的题目可获得的价值，当前的题目正好等于已做过题的人的个数+1.
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
double a[][],dp[<<];
int one(int x){
int res=;
while(x){
if(x&) res++;
x>>=;
}
return res;
}
int main(){
int t,n,m;
while(~scanf("%d",&t)){
int cas=;
while(t--){
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
for(int j=;j<m;j++){
scanf("%lf",&a[i][j]);
}
}
int s=,num,all=<<n;
bool flag=true;
double ans=;
while(flag){
flag=false;
if(s+n<m){
flag=true;
num=n;
}
else{
num=m-s;
}
mt(dp,);
for(int i=;i<all;i++){
int yi=one(i);
if(yi>=num) continue;
for(int j=;j<n;j++){
if((i>>j)&) continue;
int next=i|(<<j);
dp[next]=max(dp[next],dp[i]+a[j][s+yi]);
}
}
double big=;
if(num==n){
big=dp[all-];
}
else{
for(int i=;i<all;i++){
if(one(i)==num){
big=max(big,dp[i]);
}
}
}
ans+=big;
s+=n;
}
printf("Case #%d: %.5f\n",cas++,ans);
}
}
return ;
}
Sawtooth http://acm.hdu.edu.cn/showproblem.php?pid=5047
根据另一个类似的题目可以猜想出，这种分割方法出来的平面个数应该是个一元二次函数，a*x^2+b*x+c，过3个点，0的时候是1个平面，题目还输入两组，三个进去解出方程的abc，然后输入x就可以输出值了。
#include<cstdio>
#include<cstring>
#define mt(a,b) memset(a,b,sizeof(a))
const int M=;
class Hp { //高精度类
int len,s[M];
public:
void init(char ch[]) {
len=;
mt(s,);
int i=;
while(ch[i]==''&&ch[i]!=) i++;
if(ch[i]!=) {
len=strlen(ch)-i;
for(i=; i<len; i++) {
s[i]=ch[len-i-]-;
}
}
}
void print() { //输出
int i=len-;
while(s[i]==&&i>) i--;
for(; i>=; i--) {
printf("%d",s[i]);
}
}
void add(int x) { //高精度加单精度
int temp=;
s[]+=x;
while(s[temp]>) {
s[temp]-=;
temp++;
s[temp]++;
}
if(s[len]!=) len++;
}
void subtract(Hp a) { //高精度减高精度
for(int i=; i<len; i++) {
s[i]-=a.s[i];
if(s[i]<) {
s[i]+=;
s[i+]--;
}
}
while(len>&&s[len-]==) len--;
}
void multiply(int b) { //高精度乘单精度
int temp=;
for(int i=; i<len; i++) {
temp+=s[i]*b;
s[i]=temp%;
temp/=;
}
s[len++]=temp;
while(s[len-]>) {
s[len]+=s[len-]/;
s[len-]%=;
len++;
}
while(len>&&s[len-]==) len--;
}
void multiply(Hp b) { //高精度乘高精度
Hp c;
mt(c.s,);
for(int i=; i<len; i++) {
for(int j=; j<b.len; j++) {
c.s[i+j]+=s[i]*b.s[j];
c.s[i+j+]+=c.s[i+j]/;
c.s[i+j]%=;
}
}
len=len+b.len;
for(int i=; i<len; i++) {
s[i]=c.s[i];
}
while(len>&&s[len-]==) len--;
}
} A,B;
char a[M];
int main(){
int t;
while(~scanf("%d",&t)){
int cas=;
while(t--){
scanf("%s",a);
A.init(a);
B.init(a);
A.multiply(B);
A.multiply();
B.multiply();
A.subtract(B);
A.add();
printf("Case #%d: ",cas++);
A.print();
puts("");
}
}
return ;
}
那个类似的题目被我找到了
折线分割平面 http://acm.hdu.edu.cn/showproblem.php?pid=2050
一样的解一元二次
#include<cstdio>
int main(){
int t,n;
while(~scanf("%d",&t)){
while(t--){
scanf("%d",&n);
printf("%d\n",*n*n-n+);
}
}
return ;
}
end