D题，每次计算一行和一列，不妨设现在第i次计算，那么横纵坐标有一个小于i的话前面就已经求出来了，第i行，第i列都是猪。对于第i行，通过前面的状态又可以找到最后一步分别是1至i的状态（1表示只有猪，2表示只有人，3表示既有人也有猪）。所以现在只要判断最后的位置是多少，然后如果存在猪，那么就是人；否则是猪。第i列也是如此。这要用动态数组
#include<stdio.h>
#include<string.h>
#include<vector>
#include<iostream>
using namespace std;
const int maxn=42000;
vector<int> e[maxn];//e[i][j]表示第i行，第j+1列的数，如果是1则是
int x[maxn],y[maxn];
int main()
{
int t=1,n,m,i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<=n;i++)//清空vector
{
while(!e[i].empty())
e[i].pop_back();
}
e[1].push_back(0);//
for(i=2;i<=n;i++)
e[i].push_back(1);
for(i=1;i<m;i++)
e[1].push_back(1);
for(i=2;i<=n;i++)
{
if(i>m) break;
e[i].push_back(0);
for(j=1;j<i;j++)
{
x[j]=1<<e[i][j-1];
y[j]=1<<e[j][i-1];
}
x[0]=1,y[0]=1;
for(j=i+1;j<=m;j++)
{
if(x[j%i]&1!=0)
{
x[j%i]=x[j%i]|2;
e[i].push_back(1);
}
else
{
x[j%i]=x[j%i]|1;
e[i].push_back(0);
}
}
for(j=i+1;j<=n;j++)
{
if(y[j%i]&1!=0)
{
y[j%i]=y[j%i]|2;
e[j].push_back(1);
}
else
{
y[j%i]=y[j%i]|1;
e[j].push_back(0);
}
}
}
printf("Case #%d:\n",t++);
for(i=1;i<=n;i++)
{
for(j=0;j<m;j++)
{
if(!e[i][j])
printf("P");
else printf("H");
}
printf("\n");
}
}
return 0;
}
G题就是求子树中，权值最大的三个结点。只要每个结点保存三个状态即可，注意比较起来很麻烦，所以我重新开了一维数组，把要比较的六个数存起来，排序，取最大的三个数更新即可。
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=11000;
int dp[maxn][3],n,v[maxn],a[6];
vector<int> e[maxn];
void DFS(int t)
{
int i,j,k;
for(i=0;i<e[t].size();i++)
{
j=e[t][i];
DFS(j);
}
dp[t][0]=v[t];
for(i=0;i<e[t].size();i++)
{
j=e[t][i];
for(k=0;k<3;k++)
a[k]=dp[t][k];
for(k=0;k<3;k++)
a[k+3]=dp[j][k];
sort(a,a+6);
for(k=0;k<3;k++)
dp[t][k]=a[5-k];
}
}
int main()
{
int i,j,m;
while(scanf("%d",&n)!=EOF)
{
scanf("%d",&v[0]);
for(i=0;i<n;i++)
e[i].clear();
for(i=1;i<n;i++)
{
scanf("%d%d",&j,&v[i]);
e[j].push_back(i);
}
for(i=0;i<n;i++)
for(j=0;j<3;j++)
dp[i][j]=-1;
DFS(0);
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d",&j);
if(dp[j][2]==-1) printf("-1\n");
else
{
printf("%d %d %d\n",dp[j][0],dp[j][1],dp[j][2]);
}
}
}
return 0;
}
I题：求有一个好的一个坏的连续的最大的长度。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=110000;
struct edge
{
int a,b;
}e1[maxn],e2[maxn];
int n1,n2,a[4*maxn];
bool in1[8*maxn],in2[8*maxn];
bool cmp(edge a,edge b)
{
if(a.a!=b.a) return a.a<b.a;
return a.b<b.b;
}
int main()
{
int i,j,k,num,l,lmax,l1,r1;
while(scanf("%d%d%d",&l,&n1,&n2)!=EOF)
{
for(num=0,i=0;i<n1;i++)
{
scanf("%d%d",&e1[i].a,&e1[i].b);
a[num++]=e1[i].a;//接收点的坐标
a[num++]=e1[i].b;
}
for(i=0;i<n2;i++)
{
scanf("%d%d",&e2[i].a,&e2[i].b);
a[num++]=e2[i].a;
a[num++]=e2[i].b;
}
sort(e1,e1+n1,cmp);//排序
sort(e2,e2+n2,cmp);
sort(a,a+num);
if(!num) k=0;
else k=1;
for(j=1;j<num;j++)//去重
if(a[j]!=a[j-1])
a[k++]=a[j];
num=k;
for(i=1;i<n1;i++)//如果两线段直接相邻，合为一条线段
{
if(e1[i].a<=e1[i-1].b+1)
{
e1[i].a=e1[i-1].a;
e1[i-1].a=-1;
}
}
for(i=1;i<n2;i++)
{
if(e2[i].a<=e2[i-1].b+1)
{
e2[i].a=e2[i-1].a;
e2[i-1].a=-1;
}
}
//下面划分为2*num-1条线段，其中num条线段表示离散化的点，num-1条表示中间的部分
memset(in1,false,sizeof(in1));
memset(in2,false,sizeof(in2));
for(j=0,i=0;j<n1&&i<num;j++)
{
if(e1[j].a==-1) continue;
if(a[i]>e1[j].b)
continue;
while(i<num&&a[i]<e1[j].a)
i++;
while(i<num&&a[i]<e1[j].b)
{
in1[2*i]=true;
in1[2*i+1]=true;
i++;
}
if(i<num&&a[i]==e1[j].b)
in1[2*i]=true;
}
for(j=0,i=0;j<n2&&i<num;j++)
{
if(e2[j].a==-1) continue;
if(a[i]>e2[j].b)
continue;
while(i<num&&a[i]<e2[j].a)
i++;
while(i<num&&a[i]<e2[j].b)
{
in2[2*i]=true;
in2[2*i+1]=true;
i++;
}
if(i<num&&a[i]==e2[j].b)
in2[2*i]=true;
}
for(lmax=0,i=0;i<2*num-1;i++)
{
if((in1[i]&&!in2[i])||(!in1[i]&&in2[i]))//开始位置
{
j=i;
while(j<2*num-1&&(in1[j]&&!in2[j])||(!in1[j]&&in2[j]))
{
if(j%2==0&&a[j/2+1]==a[j/2]+1)//一定要注意(a[j/2],a[j/2]+1)这条线段不存在
j++;
j++;
}
if(i%2==0) l1=a[i/2];
else l1=a[i/2]+1;
if(j%2==0) r1=a[j/2]-1;
else r1=a[j/2];
if(r1-l1+1>lmax)
lmax=r1-l1+1;
i=j-1;
}
}
printf("%d\n",lmax);
}
return 0;
}