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

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

总目录

在线测评地址(ybt)

在线测评地址(LOJ)

1.区间动规思想40分

ybt

未通过

测试点结果内存时间测试点1答案错误620KB3MS测试点2答案正确616KB4MS测试点3答案正确608KB2MS测试点4答案正确620KB2MS测试点5答案正确616KB2MS测试点6答案错误616KB2MS测试点7答案错误612KB2MS测试点8答案错误616KB2MS测试点9答案错误616KB1MS测试点10答案错误616KB2MS

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

未通过

测试点结果内存时间测试点1答案正确624KB2MS测试点2答案正确636KB3MS测试点3答案正确680KB2MS测试点4答案正确688KB2MS测试点5答案正确684KB2MS测试点6答案错误644KB1MS测试点7答案错误676KB2MS测试点8答案错误688KB2MS测试点9答案错误692KB2MS测试点10答案错误696KB2MS

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答案正确652KB2MS测试点2答案正确684KB2MS测试点3答案正确748KB2MS测试点4答案正确740KB2MS测试点5答案正确772KB2MS测试点6答案正确692KB2MS测试点7答案正确744KB2MS测试点8答案正确780KB2MS测试点9答案正确788KB2MS测试点10答案正确780KB2MS
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答案正确652KB4MS测试点2答案正确672KB3MS测试点3答案正确744KB2MS测试点4答案正确736KB2MS测试点5答案正确776KB2MS测试点6答案正确680KB2MS测试点7答案正确744KB2MS测试点8答案正确776KB2MS测试点9答案正确776KB2MS测试点10答案正确780KB2MS
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.
 
 
 
 
 
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5703291.html