T1 彩虹
题目
【题目描述】
Mr.Raju和他的一个大家庭外出度假，他们想要乘着彩虹欣赏周围的景色，但是这样最会有一些问题。
在他们家族中，如果一个人想要骑上彩虹，那么他喜欢的所有人和喜欢他的所有人都必须一同骑上彩虹。如果一个人没有喜欢的人，也没有人喜欢他，那么他也可以乘上彩虹。
你被请来解决这个难题，我们会提供给你家族所有成员的体重，以及每个人喜欢的人的列表，同样给出的还有彩虹能承受的总重量，你需要计算出在以上条件下彩虹所能承载的最多人数。
为了方便描述，所有的家庭成员都被标号，从1到n。
【输入格式】
有多组数据，每组数据之间有一空行。
对于每一组数据，第一行为整数n(1≤n≤1000)和c(0≤c≤1000),n表示家庭成员的总人数，c表示彩虹的承载量。
第二行为n个数为1到n个家庭成员的体重（体重是1000以内的正整数）。
接下来n行，每行第一个数k[i]表示第i个人有多少喜欢的人，接下来k[i]个整数为他喜欢的人的编号。
当n=0，c=0是表示数据结束。保证数据组数不超过3。
【输出格式】
对于每一组数据，输出可以同时骑彩虹的最大人数。（输出的每个答案之间不要空行）。
【输入样例】
5 200 50 50 50 50 50 1 2 1 3 0 1 5 1 4 3 200 100 100 100 1 2 1 3 1 1 0 0
【输出样例】
3 0
【数据规模】
对于20%的数据：n≤8；
对于100%的数据：n,c≤1000。
解析
先用并查集将每个人与其喜欢的人合并起来，计算他们的总重量与总人数。
再跑一遍01背包即可。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } const int N=1010; int n,C,a[N],b[N],c[N],fa[N],f[N],maxn; int get(int x) { if(fa[x]==x) return x; return fa[x]=get(fa[x]); } int main() { //freopen("rainbow.in","r",stdin); //freopen("rainbow.out","w",stdout); while(1) { n=read(),C=read(),maxn=0; if(n==0&&C==0) break; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) a[i]=read(),b[i]=0,c[i]=0,fa[i]=i; for(int i=1;i<=n;i++) { int k=read(); for(int j=1;j<=k;j++) { int x=read(); fa[get(i)]=get(x); } } for(int i=1;i<=n;i++) { int temp=get(i); b[temp]+=a[i],c[temp]++; } for(int i=1;i<=n;i++) if(b[i]!=0) for(int j=C;j>=b[i];j--) f[j]=max(f[j],f[j-b[i]]+c[i]); for(int i=0;i<=C;i++) maxn=max(maxn,f[i]); cout<<maxn<<endl; } return 0; }
T2 红十字
题目
【题目描述】
通往藏宝库的通道打开了，走下一段长长的楼梯，钻过一条矮矮的地道，你和小可可终于来到了藏宝库的门前。随之而来的就是最后一个挑战，只要能打开宝库的门，里面的宝藏就是你们的了。
宝库的门依然是通过机关打开，这个门很奇怪，是一个正方形，被划分成许多大小一致的正方形的小方格，这些方格不是红色就是白色，猛看上去这些方格组成了许多红十字状的标志。根据藏宝图记载，只要找到门上最大的红十字，按下它中心的方格，宝库的门就能打开了。
红十字标志也是一个正方形，边长为(2k+1)*(2k+1)，其中k为非负整数。它的四条边与门的边平行，而且恰由门上的(2k+1)*(2k+1)个小方格组成。这里，红十字标志是以白色为底色，红色为十字的颜色。假设用1表示红色，用0表示白色。对应到计算机处理的数据中，就是除了正中列与正中行全为1外，其余方格均为0。
以下是几种不同大小的标志：
1*1:
1
3*3
010
111
010
5*5
00100
00100
11111
00100
00100
小可可被这个机关难到了，现在只有靠你了，请你帮助他在这个门上找到一个最大的红十字标志，输出它的边长即可。
【输入格式】
本题输入量巨大，推荐使用以下输入方法：
scanf("%d\n", &n);
for (i = 1; i<= n; i++) scanf("%s", s[i] + 1);
for (i = 1; i<= n; i++)
for (j = 1; j <= n; j++)
a[i][j] = s[i][j] - '0';
其中n是宝库的门的边长，s是字符数组，a[i][j]是第i行第j列的数值。
【输出格式】
对于每个询问输出一行表示答案。
【输入样例】
5 00011 01011 11100 01001 00010
【输出样例】
3
【数据规模】
对于30%的数据，n≤100。
对于50%的数据，n≤500。
对于100%的数据，n≤2000。
解析
用sum纪录子矩阵的值。
对于以(x,y)为中心且长度为k的矩阵，如果是红十字，那么以(x,y)为中心且长度为k-2(k>=3)的矩阵必然也是红十字。
所以可以枚举红十字的中心，求出以(x,y)为中心的最大红十字的边长，具体可以用二分实现。
Code
#include<bits/stdc++.h> using namespace std; const int N=2005; int n,a[N]