CF1156A Inscribed Figures 题解

原题目链接

---

PS：

这题比赛时当场出锅……

std被hack……

整场比赛最后unrated……

---

对于每两个相邻的图形，交点数是固定的

也就是说我们可以打表

     1   2   3
   
1    /   3   4
2    3   /  inf
3    4  inf  /

但是！直接打表是错误的！std就是这样被hack的！

考虑这样一组数据：

3
3 1 2

按照上面的那张表计算，答案是7

但是实际上，三角形，圆形，正方形共用了一个交点

所以答案是6

所以对于每组这样的情况，要进行特判

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

template<typename T> inline void read(T &x)
{
	char ch=getchar();
	T f=1;
	x=0;
	while(!('0'<=ch&&ch<='9'))
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9')
	{
		x=(x<<3)+(x<<1)+ch-48;
		ch=getchar();
	}
	x*=f;
}
int n;
long long ans;
const int inf=0x3f3f3f3f;
const int res[4][4]={0,0,0,0,
                     0,0,3,4,
                     0,3,0,inf,
                     0,4,inf,0,};//打表
int a[110];
int main()
{
	read(n);
	for(int i=1;i<=n;++i)
	{
		read(a[i]);
	}
	for(int i=2;i<=n;++i)
	{
		ans+=res[a[i-1]][a[i]];//计算交点数
	}
	for(int i=3;i<=n;++i)
	{
		if(a[i-1]==1&&a[i-2]==3&&a[i]==2)//特判特殊情况
			--ans;
	}
	if(ans>=inf)
	{
		printf("Infinite\n");
	}
	else
	{
		printf("Finite\n");
		cout<<ans;
	}
	return 0;
}