1571 例题3 凸多边形的划分(LOJ10149) 区间动规思想40分 区间动归 dp 两定点一动点50分 int128使用100分 uint128使用100分

总目录

在线测评地址(ybt)

在线测评地址(LOJ)

1.区间动规思想40分

ybt

未通过

LOJ

 问题比较陌生，样例还是要好好模拟

 该题的数据范围N≤50，每个点权值小于 10^9

数据极限(50-2)*10^9*10^9*10^9=4.8*10^28，unsigned long long(2^64=18446744073709551616)也必溢出，需使用高精度算法。

在上述模拟过程，感觉纯暴力即可AC.

编写，提交40分，代码如下：

#include 
#define ULL unsigned long long
#define maxn 110
using namespace std;
ULL a[maxn],b[maxn],mx;
int main(){
	int i,j,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%llu",&a[i]),a[i+n]=a[i];
	for(i=1;i<=n;i++){//以i作为三角形顶点
		for(j=i+1;j<=i+n-2;j++)
			b[i]+=a[j]*a[j+1];
		b[i]*=a[i];
	}
	mx=(ULL)18e18;
	for(i=1;i<=n;i++)mx=min(mx,b[i]);
	printf("%llun",mx);
	return 0;
} 

2.区间动归 dp 两定点一动点 50分

ybt

未通过

LOJ

 哪出错？估计还是在划分上，猜测应该在n比较大时，漏考虑了些情况。

反例很快找到，如下图，以六边形为例，以a为顶点的三角形划分，是之前的想法，漏考虑了，以a为顶点，以d为顶点的三角形划分。

 感觉情况挺多，复杂多变，如何思考？

难想之处在于，三角形，有两顶点相邻，但第三个顶点存在跨越，这个难办，以什么为束缚？

六边形的思考过程：

 区间动归 dp 两定点一动点 50分 代码如下：

#include 
#define ULL unsigned long long
#define maxn 110
#define INF 18e18
using namespace std;
ULL a[maxn],dp[maxn][maxn],mx;
int main(){
	int n,lt,rt,k,len,i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%llu",&a[i]),a[i+n]=a[i];
	for(i=1;i<=2*n;i++)
		for(j=i+2;j<=2*n;j++)
			dp[i][j]=INF;
	for(len=2;len2*n)break;
			for(k=1;k 
3.区间动归 int128使用(不使用高精度)100分
 
ybt
 
通过
 
测试点
结果
内存
时间
测试点1
答案正确
652KB
2MS
测试点2
答案正确
684KB
2MS
测试点3
答案正确
748KB
2MS
测试点4
答案正确
740KB
2MS
测试点5
答案正确
772KB
2MS
测试点6
答案正确
692KB
2MS
测试点7
答案正确
744KB
2MS
测试点8
答案正确
780KB
2MS
测试点9
答案正确
788KB
2MS
测试点10
答案正确
780KB
2MS
LOJ
 
 
花了一晚上时间，翻了2021CSP复赛代码，基本确认，比赛中int128是可以使用的。
 
比赛建议，高精尽量不编，因没有一定的熟练程度，比赛中的成功率是比较低的。
 
翻看了int128的读写，之后，独立编码，区间动归 int128使用(不使用高精度)100分 代码如下：
 
#include 
#define maxn 110
#define INF 1e30
using namespace std;
__int128 a[maxn],dp[maxn][maxn],mx;
inline __int128 read(){
	__int128 x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){//读出负号，去除其他无用符号 
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){//读取数字 
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
inline void print(__int128 x){
	if(x<0){
		putchar('-');//打印负号 
		x=-x;//变为正数 
	}
	if(x){//请注意此处是if不是while 
		print(x/10);//自高位到低位输出，采用递归形式 
		putchar(x%10+'0');//以字符形式打印 
	}
}
int main(){
	int n,lt,rt,k,len,i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)a[i]=read(),a[i+n]=a[i];
	for(i=1;i<=2*n;i++)
		for(j=i+2;j<=2*n;j++)
			dp[i][j]=INF;
	for(len=2;len2*n)break;
			for(k=1;k 
__int128能写成_int128吗，编码后，报错如下：
 
 
 __int128能写成int128吗，编码后，报错如下：
 
 
测试int128最大值代码如下：
 
#include 
using namespace std;
__int128 mx;
inline __int128 read(){
	__int128 x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){//读出负号，去除其他无用符号 
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){//读取数字 
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
inline void print(__int128 x){
	if(x<0){
		putchar('-');//打印负号 
		x=-x;//变为正数 
	}
	if(x){//请注意此处是if不是while 
		print(x/10);//自高位到低位输出，采用递归形式 
		putchar(x%10+'0');//以字符形式打印 
	}
}
int main(){
	mx=1;
	printf("mx=");
	print((mx<<127)-1);
	printf("n");
}
 
上述代码对应的输入输出数据如下：
 
mx=170141183460469231731687303715884105727
 
计算器中按出的2^127-1=1.7014118346046923173168730371588e+38基本吻合。
 
以下代码在处理数据溢出时有问题，亟待解决
 
#include 
using namespace std;
__int128 mx;
inline __int128 read(){
	__int128 x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){//读出负号，去除其他无用符号 
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){//读取数字 
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
inline void print(__int128 x){
	if(x<0){
		putchar('-');//打印负号 
		x=-x;//变为正数 
	}
	if(x){//请注意此处是if不是while 
		print(x/10);//自高位到低位输出，采用递归形式 
		putchar(x%10+'0');//以字符形式打印 
	}
}
int main(){
	mx=1;
	printf("mx=");
	print(mx<<127);
	printf("n");
}
 
请看对应的输入输出数据：
 
mx=--17014118346046923173168730371588410572(
 
开始有2个'-'号，结尾有一个'('号
 
上述代码证明，int128最大值是2^127-1=1.7*10^38
 
4.区间动归 uint128使用(不使用高精度)100分
 
ybt
 
通过
 
测试点
结果
内存
时间
测试点1
答案正确
652KB
4MS
测试点2
答案正确
672KB
3MS
测试点3
答案正确
744KB
2MS
测试点4
答案正确
736KB
2MS
测试点5
答案正确
776KB
2MS
测试点6
答案正确
680KB
2MS
测试点7
答案正确
744KB
2MS
测试点8
答案正确
776KB
2MS
测试点9
答案正确
776KB
2MS
测试点10
答案正确
780KB
2MS
LOJ
 
 
再接再励，继续攻克uint128.
 
区间动归 uint128使用(不使用高精度)100分 代码如下：
 
#include 
#define maxn 110
#define INF 1e30
using namespace std;
__uint128_t a[maxn],dp[maxn][maxn],mx;
inline __uint128_t read(){
	__uint128_t x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){//去除其他无用符号 
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){//读取数字 
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
inline void print(__uint128_t x){
	if(x){//请注意此处是if不是while 
		print(x/10);//自高位到低位输出，采用递归形式 
		putchar(x%10+'0');//以字符形式打印 
	}
}
int main(){
	int n,lt,rt,k,len,i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)a[i]=read(),a[i+n]=a[i];
	for(i=1;i<=2*n;i++)
		for(j=i+2;j<=2*n;j++)
			dp[i][j]=INF;
	for(len=2;len2*n)break;
			for(k=1;k 
__uint128_t能写成__uint128吗，报错如下:
 
 
 __uint128_t能写成_uint128_t吗，报错如下:
 
 
uint128最大值时多少，测试代码如下：
 
#include 
#define maxn 110
#define INF 1e30
using namespace std;
__uint128_t mx;
inline __uint128_t read(){
	__uint128_t x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){//去除其他无用符号 
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){//读取数字 
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
inline void print(__uint128_t x){
	if(x){//请注意此处是if不是while 
		print(x/10);//自高位到低位输出，采用递归形式 
		putchar(x%10+'0');//以字符形式打印 
	}
}
int main(){
	mx=1;
	print((mx<<127)-1+(mx<<127));
	return 0;
}
 
上述代码对应的输入输出数据如下：
 
340282366920938463463374607431768211455
 
计算器中对应的2^128-1=3.4028236692093846346337460743177e+38与上述数据基本吻合。
 
目前在比赛中，没有见到uint128,稳妥起见，还是使用int128.
 
该题习得了什么？
 
陌生场景下的建模能力。
 
int128,uint128的读写，个人还是建议，比赛时要尽量避免高精度算法，尽量用int128(最大值在1.7*10^38),uint128(最大值在3.4*10^38).
 
目前在比赛中，没有见到uint128,稳妥起见，还是使用int128.