2018暑假集训记录（一）

record

　　暑假集训个人日常（好熟悉的开场🙊）。

　　

　　

day1 06.30

  1. Contest：The 2015 ACM-ICPC ChangChun Regional Contest

    [🎈] A Too Rich（贪心）

    [　] B Count a * b

    [　] C Play a game

    [　] D Pipes selection

    [　] E Rebuild

    [🎈] F Almost Sorted Array（递推）

    [🎈] G Dancing Stars on Me（计算几何凸包）

    [🎈] H Partial Tree（完全背包）

    [　] I Chess Puzzle

    [🎈] J Chip Factory（暴力／01Trie树）

    [　] K Maximum Spanning Forest

    [🎈] L House Building（简单计算）

    [　] M Security Corporation

    EveningTraining

    [🎈] A Most Powerful
    [　] B Food Delivery
    [　] C Rugby Football
    [　] D Dice War
    [　] E Magic Squares

  2. Mumbles

    G读完题目不看样例于是就理解错了… J读完题目算算复杂度不敢莽于是隔壁就A了… F边界不好好处理于是1A就没了… 去年day4的A题我写了个恶心的优先队列然后今天写了个优美的线段树还在沾沾自喜然后发现其实只要扫一遍预处理就over了… 滚粗👋。

  3. Solutions

    • 【A】数据范围太大不能背包，但是这题比普通背包更巧妙的条件在于，除了$50$和$500$，其余硬币的价值都是前一个的整数倍，也就是说可以用若干个硬币$i$代替一个硬币$i+1$，所以我们在枚举的时候如果考虑多取一个$50/500$凑成$100/1000$，那就可以保证贪心的正确性。贪心策略是，用尽可能多的小面值硬币，前提是小面值硬币可以凑出当前需要的钱数，所以从大面值的开始决策。

      「查看代码」
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      #include<iostream>
      #include<cstring>
      #include<cstdlib>
      #include<cstdio>
      #include<cmath>
      #include<algorithm>
      using namespace std;
      const int maxn=15;
      int T, p, ans, c[maxn], val[maxn]={0, 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000}, sum[maxn];
      void Dfs(int tot, int id, int cnt)
      {
      	if(tot<0)	return ;
      	if(id==0)
      	{
      		if(tot==0)	ans=max(ans, cnt);
      		return ;
      	}
      	int ret=max(tot-sum[id-1], 0);
      	int tmp=ret/val[id]+(ret%val[id]!=0);
      	if(tmp<=c[id])	Dfs(tot-tmp*val[id], id-1, cnt+tmp);
      	if(tmp+1<=c[id])  Dfs(tot-(tmp+1)*val[id], id-1, cnt+tmp+1);
      	return ;
      }
      int main()
      {
      	scanf("%d", &T);
      	while(T--)
      	{
      		scanf("%d", &p);
      		for(int i=1; i<=10; i++)
      		{
      			scanf("%d", &c[i]);
      			sum[i]=c[i]*val[i]+sum[i-1];
      		}
      		ans=-1;
      		Dfs(p, 10, 0);
      		printf("%d\n", ans);
      	}
      	return 0;
      }

    • 【H】因为$n$个点的树总度数确定为$2n-2$，一个很直接的想法是做完全背包，但最简单的背包不能保证连通。我们可以考虑先把每个点分配$1$度，提前保证连通，剩下的$n-2$度再进行完全背包，因为每次分配相当于把一个点的从$1$度变成了$k$度，所以增加的贡献应该是$a[1]-a[k]$（注意$f$数组不能初始化为-1，因为这里有可能为负数= =），最终答案为$f[n-2]+n*a[1]$。

      「查看代码」
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      #include<iostream>
      #include<cstring>
      #include<cstdlib>
      #include<cstdio>
      #include<cmath>
      #include<algorithm>
      using namespace std;
      const int maxn=2500+10;
      int T, n, m, a[maxn], f[maxn];
      int main()
      {
      	scanf("%d", &T);
      	while(T--)
      	{
      		scanf("%d", &n);
      		
      		for(int i=1; i<n; i++)	scanf("%d", &a[i]);
      		memset(f, 0x8f, sizeof f);
      		f[0]=0;
      		for(int i=2; i<n; i++)
      			for(int j=i-1; j<=n-2; j++)
      				f[j]=max(f[j], f[j-i+1]+a[i]-a[1]);
      		printf("%d\n", f[n-2]+n*a[1]);
      	}
      	return 0;
      }

    • 【J】暴力水，Trie做法后补…

　　

day2 07.01

  1. Contest：The 2015 ACM-ICPC Shenyang Regional Contest

    [　] A Pattern String

    [🎈] B Bazinga（字符串）

    [　] C Minimum Cut-Cut

    [🎈] D Pagodas（数学）

    [　] E Efficient Tree

    [　] F Frogs

    [🎈] G Game of Flying Circus（模拟）

    [　] H Chessboard

    [　] I Triple

    [　] J John’s Fences

    [　] K Kykneion asma

    [　] L Number Link

    [🎈] M Meeting（拆点最短路）

    EveningTraining

    [　] A GT and sequence
    [　] B GT and numbers
    [　] C GT and set
    [　] D GT and strings
    [　] E GT and trees

  2. Mumbles

    一个人做比赛真是菜出天际，其实也是反映出自己有多菜吧= = 折腾了一下午比赛日程和hexo的配置，interesting！

  3. Solutions

    • 【B】暴力一定会T，但是题目的要求是从后往前找到第一个不能覆盖前面所有串的串，很巧妙。我们定义$s[i]\subseteq s[j]$代表$s[i]$是$s[j]$的子串，假设现在枚举到$s[i]$和$s[j]$，如果$s[i]\nsubseteq s[j]$，那么$s[j]$满足条件；否则，对于更往后的$s[k]$串，如果$s[j]\nsubseteq s[k]$的子串那$s[k]$满足条件，否则$s[j]\subseteq s[k]$时必有$s[i]\subseteq s[k]$，那么$s[i]$对$s[k]$的所有影响都可以由$s[j]$代替，则可以跳出$j$这层循环。偷懒没敲kmp用了一下strstr这个函数，后来查了一下看到这个博客里提到它的效率很优秀。

      「查看代码」
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      #include<iostream>
      #include<cstring>
      #include<cstdlib>
      #include<cstdio>
      #include<cmath>
      #include<algorithm>
      using namespace std;
      const int maxn=500+10;
      int T, n;
      char s[maxn][2000+10];
      bool vis[maxn];
      int main()
      {
      	scanf("%d", &T);
      	for(int tt=1; tt<=T; tt++)
      	{
      		scanf("%d", &n);
      		for(int i=1; i<=n; i++)	scanf("%s", s[i]);
      		int ans=-1;
      		memset(vis, 0, sizeof vis);
      		for(int i=1; i<=n; i++)
      			for(int j=i+1; j<=n; j++) if(!vis[j])
      			{
      				if(strstr(s[j], s[i]))	break;
      				else
      				{
      					vis[j]=true;
      					ans=max(ans, j);
      				}
      			}
      		printf("Case #%d: %d\n", tt, ans);
      	}
      	return 0;
      }

    • 【D】想到了去年的省赛= = 每次把最小的两个数作差生成新数，容易发现能得到的最小数就是$gcd(a, b)$，再把$gcd$加在这些数上面生成新数，其实到最后这就是一个等差数列。

    • 【M】把集合E拆成两个点$S_E$和$T_E$，对集合内的每个点$P$，分别连边$$和$$，然后连边$$，建图之后跑单源最短路（突然发现好像不拆点只修改一下边权也是可以的…）。分别求出每个点到$1$和$n$的最短距离，求这两个距离中的最大值的最小值，当时找答案的时候完全在乱写，鬼知道我在想些什么🤦🏻‍♀️。

    • 【G】本来就只是一个题意很恶心的模拟题，结果自己推导的过程太复杂反而把思路搞混乱了，写的时候还搞错一个条件= = 据说这个题目有一点错误，这里有完整题意。

      「查看代码」
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      #include<iostream>
      #include<cstring>
      #include<cstdlib>
      #include<cstdio>
      #include<cmath>
      #include<algorithm>
      using namespace std;
      const double def=1e-6;
      int T;
      double t, va, vs;
      char s[2][5]={"No", "Yes"};
      int main()
      {
      	scanf("%d", &T);
      	for(int tt=1; tt<=T; tt++)
      	{
      		scanf("%lf%lf%lf", &t, &va, &vs);
      		bool flag=false;
      		if(fabs(va-vs)<=def)	flag=true;
      		else
      		{
      			double len=300.0, line=sqrt(2.0)*300.0, vsub=vs*vs-va*va;
      			if(line/va < 2*len/vs)
      			{
      				double delta=(2*vs*len)*(2*vs*len)-4*vsub*(2*len*len), x;
      				if(delta>=0)
      				{
      					x=(2*vs*len-sqrt(delta))/(2*vsub)*vs-len;
      					if(x>=0 && x<len && (x+2*len)/va-t <= (2*len-x)/vs)	flag=true;
      					x=(2*vs*len+sqrt(delta))/(2*vsub)*vs-len;
      					if(x>=0 && x<len && (x+2*len)/va-t <= (2*len-x)/vs)	flag=true;
      				}
      			}
      			
      			if(len/va < 3*len/vs)
      			{
      				double delta=(6*vs*len)*(6*vs*len)-4*vsub*(10*len*len), x;
      				if(delta>=0)
      				{
      					x=(6*vs*len-sqrt(delta))/(2*vsub)*vs-2*len;
      					if(x>=0 && x<=len && (sqrt(x*x+len*len)+3*len)/va-t <= (2*len-x)/vs)	flag=true;
      					x=(6*vs*len+sqrt(delta))/(2*vsub)*vs-2*len;
      					if(x>=0 && x<=len && (sqrt(x*x+len*len)+3*len)/va-t <= (2*len-x)/vs)	flag=true;
      				}
      			}
      		}
      		printf("Case #%d: %s\n", tt, s[flag]);
      	}
      	return 0;
      }

　　

day3 07.02

  1. Contest：The 2015 ACM-ICPC Shanghai Regional Contest

    [🎈] A An Easy Physics Problem

    [　] B Binary Tree

    [　] C Colorful Tree

    [　] D Discover Water Tank

    [　] E Expection of String

    [🎈] F Friendship of Frog

    [　] G Game of Arrays

    [　] H Happiness of Frog

    [　] I Infinity Point Sets

    [　] J Journey of Taku

    [🎈] K Kingdom of Black and White

    [🎈] L LCM Walk

  2. Mumbles

    一觉醒来看到鱼头真是吓死我了= =下午搞计算几何去吧。祭奠死去的A。

  3. Solutions

    • 【L】对于$(x,y)$，必有$x, y\le lcm(x, y)$，显然$x$和$y$中更大的那个数是由上一步变换而来，那么对于当前坐标它的前驱是唯一的。设$x<y$，令$k=gcd(x,y), x=ak,y=bk,lcm(x,y)=abk$，若下一步得到$(x, y+lcm(x,y))=(ak, bk+abk)=(ak,(ak+k)b)=(x,(x+k)b)$，那此时$y_1\%(x+k)==0$且此时$gcd(x, y1)$仍然为$k$；由$x$变换到$x_1$同理。所以只需要不断将$x$和$y$往前变换直到不满足$y\%(x+k)==0$为止。

      「查看代码」
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      #include<iostream>
      #include<cstring>
      #include<cstdlib>
      #include<cstdio>
      #include<cmath>
      #include<algorithm>
      using namespace std;
      int T, x, y;
      int gcd(int a, int b)
      {
      	if(!b)	return a;
      	return gcd(b, a%b);
      }
      int main()
      {
      	scanf("%d", &T);
      	for(int tt=1, x, y; tt<=T; tt++)
      	{
      		scanf("%d%d", &x, &y);
      		
      		int cnt=1, k=gcd(x, y);
      		if(x>y)	swap(x, y);
      		while(y%(x+k)==0)
      		{
      			++cnt, y=y/(x+k)*k;
      			if(x>y)	swap(x, y);
      		}
      		printf("Case #%d: %d\n", tt, cnt);
      	}
      	return 0;
      }

    • 【A】终于写完这个计算几何，论好模版的必要性。感觉整个人都明媚了，刷题刷题gogogo🤣。

      「查看代码」
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      110
      111
      112
      113
      114
      115
      116
      117
      118
      119
      120
      121
      122
      123
      124
      125
      126
      127
      128
      129
      130
      131
      132
      133
      134
      135
      136
      137
      138
      139
      140
      141
      142
      143
      144
      145
      146
      147
      148
      149
      150
      151
      152
      153
      154
      155
      156
      157
      158
      159
      160
      161
      162
      163
      164
      165
      166
      167
      168
      169
      170
      171
      172
      173
      174
      175
      176
      177
      178
      179
      180
      181
      182
      183
      184
      185
      186
      187
      188
      189
      190
      191
      192
      193
      194
      195
      196
      197
      198
      199
      200
      201
      202
      203
      204
      205
      206
      207
      208
      209
      210
      211
      212
      213
      214
      215
      216
      217
      218
      219
      220
      221
      222
      223
      224
      225
      226
      227
      #include<iostream>
      #include<cstring>
      #include<cstdlib>
      #include<cstdio>
      #include<cmath>
      #include<algorithm>
      #define mp(a, b) make_pair(a, b)
      using namespace std;
      const double eps=1e-5, PI=acos(-1.0);
      int sgn(double d) {
      	if(fabs(d)<eps)	return 0;
      	return d>0 ? 1 : -1;
      }
      struct Point
      {
      	double x, y;
      	Point(double _x=0, double _y=0) {
      		x=_x, y=_y;
      	}
      	Point operator +(const Point&b)const {
      		return Point(x+b.x, y+b.y);
      	}
      	Point operator -(const Point&b)const {
      		return Point(x-b.x, y-b.y);
      	}
      	Point operator *(const double&b)const {
      		return Point(x*b, y*b);
      	}
      	Point operator /(const double&b)const {
      		return Point(x/b, y/b);
      	}
      	double operator *(const Point&b)const {
      		//点积，向量a*b=|a||b|cos(angle)，得到a在b上的投影长度
      		//a*b>0则夹角小于90度，a*b=0则向量垂直，a*b<0则夹角大于90度
      		return x*b.x+y*b.y;
      	}
      	double operator ^(const Point&b)const {
      		//叉积，得到垂直于ab平面的向量，返回其长度
      		//a^b>0则a在b顺时针方向，a^b<0则a在b逆时针方向，a^b=0则a、b共线（方向不定）
      		return x*b.y-y*b.x;
      	}
      	void transXY(double B) {
      		//求绕原点旋转B(弧度值)后的点
      		double tx=x, ty=y;
      		x=tx*cos(B)-ty*sin(B);
      		y=tx*sin(B)+ty*cos(B);
      	}
      	double len2() {
      		return x*x+y*y;
      	}
      	double len() {
      		return sqrt(len2());
      	}
      	Point change_len(double r) {
      		//转化为长度为r的向量
      		double l=len();
      		if(sgn(l)==0) return *this;
      		return Point(x*r/l, y*r/l);
      	}
      	void sc()
      	{
      		scanf("%lf%lf", &x, &y);
      		return ;
      	}
      	void pr()
      	{
      		printf("%.2f %.2f\n", x, y);
      	}
      };
      struct Line {
      	Point s, e;
      	double a, b, c, angle;
      	Line(){}
      	Line(Point _s, Point _e) {
      		s=_s, e=_e;
      		a=s.y-e.y, b=e.x-s.x, c=s.x*e.y-e.x*s.y;
      		angle=atan2(e.y-s.y, e.x-s.x);
      	}
      };
      typedef Point Vec;
      typedef Line Seg;
      bool pointOnSeg(Point P, Line L) {
      	//判断点在线段上
      	return 
      		sgn((L.s-P)^(L.e-P))==0 &&
      		sgn((P.x-L.s.x)*(P.x-L.e.x))<=0 &&
      		sgn((P.y-L.s.y)*(P.y-L.e.y))<=0;
      }
      bool pointCollinear(Point P, Line L) {
      	//判断点在直线上，即三点共线
      	return sgn((L.s-P)^(L.e-P))==0;
      }
      int interL2L(Line l1, Line l2) {
      	//判断直线关系，0重合，1平行，2相交
      	if(sgn((l1.s-l1.e)^(l2.s-l2.e))==0) {
      		if(sgn((l1.s-l2.e)^(l2.s-l2.e))==0) return 0;
      		else return 1;
      	}
      	else return 2;
      }
      int dirV2V(Vec a, Vec b) {
      	//判断向量方向，0垂直，1同向，2反向，3其他
      	if(sgn(a*b)==0) return 0;
      	else if(sgn(a*b-a.len()*b.len())==0) {
      		if(sgn(a*b)>0)	return 1;
      		else return 2;
      	}
      	else return 3;
      }
      bool interS2S(Seg l1, Seg l2) {
      	//判断线段是否相交
      	return 
      		max(l1.s.x, l1.e.x)>=min(l2.s.x, l2.e.x) &&
      		max(l2.s.x, l2.e.x)>=min(l1.s.x, l1.e.x) &&
      		max(l1.s.y, l1.e.y)>=min(l2.s.y, l2.e.y) &&
      		max(l2.s.y, l2.e.y)>=min(l1.s.y, l1.e.y) &&
      		sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e))<=0 &&
      		sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e))<=0;
      }
      bool interL2S(Line l1, Seg l2) {
      	//判断直线和线段是否相交
      	return sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e))<=0;
      }
      Point getinterL2L(Line l1, Line l2) {
      	//求直线和直线交点
      	Point ret=l1.s;
      	double t=((l1.s-l2.s)^(l2.s-l2.e))/((l1.s-l1.e)^(l2.s-l2.e));
      	ret.x+=(l1.e.x-l1.s.x)*t;
      	ret.y+=(l1.e.y-l1.s.y)*t;
      	return ret;
      }
      Point getP2L(Point P, Line L) {
      	//求点到直线垂足
      	Point ret=L.s;
      	double t=((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s));
      	ret.x+=(L.e.x-L.s.x)*t;
      	ret.y+=(L.e.y-L.s.y)*t;
      	return ret;
      }
      double disP2P(Point a, Point b) {
      	//求点到点的距离
      	return sqrt((a-b)*(a-b));
      }
      Point getP2S(Point P, Seg L) {
      	//求点到线段最近的点
      	Point ret=L.s;
      	double t=((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s));
      	if(t>=0 && t<=1) {
      		//返回垂足
      		ret.x+=(L.e.x-L.s.x)*t;
      		ret.y+=(L.e.y-L.s.y)*t;
      	}
      	else {
      		//返回最近的端点
      		if(disP2P(P, L.s) < disP2P(P, L.e)) ret=L.s;
      		else ret=L.e;
      	}
      	return ret;
      }
      double disP2L(Point a, Line l) {
      	return disP2P(a, getP2L(a, l));
      }
      double disP2S(Point a, Seg l) {
      	return disP2P(a, getP2S(a, l));
      }
      Point getMirrorP2L(Point P, Line L) {
      	//求点到直线的对称点
      	Point ret=getP2L(P, L);
      	return ret+ret-P;
      }
      Point Projection(Point p, Line l) {
      	Point pr=((l.e-l.s)*((l.e-l.s)*(p-l.s)))/(l.e-l.s).len2();
      	return l.s+pr;
      }
      pair<Point, Point> getinterL2C(Point o, double r, Line l) {
      	Point pr=Projection(o, l), A, B;
      	double d=disP2L(o, l);
      	d=sqrt(r*r-d*d);
      	if(sgn(d)==0) A=pr, B=pr;
      	else {
      		A=pr+(l.e-l.s).change_len(d);
      		B=pr-(l.e-l.s).change_len(d);
      	}
      	return mp(A, B);
      }
      int main()
      {
      	int T;
      	Point A, B, V, O, P, Q, C;
      	scanf("%d", &T);
      	for(int tt=1; tt<=T; tt++)
      	{
      		printf("Case #%d: ", tt);
      		double rad;
      		O.sc(), scanf("%lf", &rad);
      		A.sc(), V.sc(), B.sc();
      		P=A+V;
      		if(pointCollinear(O, Line(A, P)))//与圆心共线
      		{
      			if(pointCollinear(B, Line(A, P)) && dirV2V(Vec(B-O), Vec(A-O)))	printf("Yes\n");//B在AP线上且A、B在O同侧
      			else printf("No\n");
      		}
      		else
      		{
      			if(sgn(disP2L(O, Line(A, P))-rad)>=0)//相切或相离
      			{
      				if(pointCollinear(B, Line(A, P)) && dirV2V(Vec(B-A), Vec(P-A)))	printf("Yes\n");//B在AP线上且B、P在A同侧
      				else printf("No\n");
      			}
      			else
      			{
      				pair<Point, Point> pp=getinterL2C(O, rad, Line(A, P));
      				if(sgn(disP2P(pp.first, A)-disP2P(pp.second, A))<=0)	Q=pp.first;//直线AP与圆离A更近的交点
      				else Q=pp.second;
      				C=getMirrorP2L(A, Line(O, Q));//A关于的对称点
      				if(pointCollinear(B, Line(Q, A)) && pointOnSeg(B, Seg(A, Q)))	printf("Yes\n");//B在QA线上且B在A、Q之间
      				else if(pointCollinear(B, Line(Q, C)) && dirV2V(Vec(B-A), Vec(C-Q)))	printf("Yes\n");//B在QC线上且B、C在Q同侧
      				else printf("No\n");
      			}
      		}
      	}
      	return 0;
      }

　　

day4 07.03

  1. Contest：The 2015 ACM-ICPC Hefei Regional Contest

    [　] A Bus Routes

    [　] B Advanced Calculator

    [　] C Autopilot System

    [　] D Immortality of Frog

    [🎈] E Land of Farms

    [　] F Matching Compressed String

    [　] G Alice’s Classified Message

    [　] H Frog and String

    [　] I The Shields

    [　] J Kingdom of Tree

  2. Mumbles

    打比赛心灰意冷系列，我tm脑壳坏了才去写B。先把昨天的计算几何题过了再考虑接下来的计划吧。

  3. Solutions

    • 【E】将数字相同的格子缩点，相邻格子连边，建图后求最大独立集，也就是求补图的最大团。这里注意一些概念：最小支配集（选择最少的点去覆盖所有点，一个点被覆盖后其相邻点也被覆盖），最小点覆盖（选择最少的点去覆盖所有边，一个点被覆盖后其相邻边也被覆盖），最大独立集（选择最多的点，使得它们互相不连通），最大团（选择最多的点，使得所有点之间都有边相连）。

      「查看代码」
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      #include<iostream>
      #include<cstring>
      #include<cstdlib>
      #include<cstdio>
      #include<cmath>
      #include<algorithm>
      using namespace std;
      const int maxn=100+10;
      int dd[4][2]={0, 1, 0, -1, 1, 0, -1, 0};
      int T, n, m, N, a[maxn][maxn], id[maxn], ch[maxn][maxn];
      int ans, cnt[maxn], group[maxn], vis[maxn];
      char s[maxn];
      void Read()
      {
      	N=0;
      	memset(a, 0, sizeof a);
      	memset(id, 0, sizeof id);
      	for(int i=1; i<=n; i++)
      	{
      		scanf("%s", s+1);
      		for(int j=1; j<=m; j++)
      		{
      			if(s[j]=='.')	ch[i][j]=++N;
      			else
      			{
      				if(!id[s[j]-'0']) id[s[j]-'0']=++N;
      				ch[i][j]=id[s[j]-'0'];
      			}
      		}
      	}
      	for(int i=1; i<=n; i++)
      		for(int j=1; j<=m; j++)
      			for(int k=0; k<4; k++)
      			{
      				int x=i+dd[k][0], y=j+dd[k][1];
      				if(x>=1 && x<=n && y>=1 && y<=m)
      				{
      					a[ch[i][j]][ch[x][y]]=1;
      					a[ch[x][y]][ch[i][j]]=1;
      				}
      			}
      	for(int i=1; i<=N; i++)
      		for(int j=1; j<=N; j++)
      			a[i][j]^=1;
      	return ;
      }
      bool Dfs(int u, int pos)
      {
      	for(int i=u+1, j; i<=N; i++)
      	{
      		if(cnt[i]+pos<=ans)	return 0;
      		if(a[u][i])
      		{
      			for(j=0; j<pos; j++) if(!a[i][vis[j]])	break;
      			if(j==pos)
      			{
      				vis[pos]=i;
      				if(Dfs(i, pos+1))	return 1;
      			}
      		}
      	}
      	if(pos>ans)
      	{
      		for(int i=0; i<pos; i++) group[i]=vis[i];
      		ans=pos;
      		return 1;
      	}
      	return 0;
      }
      int Work()
      {
      	ans=-1;
      	for(int i=N; i>0; i--)
      	{
      		vis[0]=i;
      		Dfs(i, 1);
      		cnt[i]=ans;
      	}
      	return ans==-1 ? 0 : ans;
      }
      int main()
      {
      	scanf("%d", &T);
      	for(int tt=1; tt<=T; tt++)
      	{
      		scanf("%d%d", &n, &m);
      		Read();
      		printf("Case #%d: %d\n", tt, Work());
      	}
      	return 0;
      }