补档

长期更新……这里是我做过并且感觉有收获的题

小仙女过生日啦

看了题解，是“区间dp经典例题——“凸多边形的三角剖分””……但是还没懂

知识点

1.叉积求三角形面积

之前自己只会个海伦公式……

找这个的时候我还看到了行列式，是线代里的，自己本来是打算寒假学的，结果净去过写题了……

double S(point a,point b,point c){
    //注意这里相减的顺序不能变
	return fabs((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x))/2;
}

2.判断一个点是否在三角形内

bool judge(point a,point b,point c){
	double s1=S(a,b,c);
	rep(i,1,n){
		int x=p[i].x,y=p[i].y;
		if(x==a.x&&y==a.y||x==b.x&&y==b.y||x==c.x&&y==c.y){
			continue;
		}
		double s2=S(a,b,p[i])+S(a,c,p[i])+S(b,c,p[i]);
        //因为是浮点数，所以不能直接相等
		if(fabs(s1-s2)<=1e-8) return false;
	}
	return true;
}

代码

蒟蒻只会dp的板子，这主函数部分就看不懂了……

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N=1e2+5;
double f[N][N];
int n;
struct point{
	double x,y;
}p[N];
double S(point a,point b,point c){
	return fabs((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x))/2;
}
bool judge(point a,point b,point c){
	double s1=S(a,b,c);
	rep(i,1,n){
		int x=p[i].x,y=p[i].y;
		if(x==a.x&&y==a.y||x==b.x&&y==b.y||x==c.x&&y==c.y){
			continue;
		}
		double s2=S(a,b,p[i])+S(a,c,p[i])+S(b,c,p[i]);
		if(fabs(s1-s2)<=1e-6) return false;
	}
	return true;
}
signed main()
{
//std::ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
	while(cin>>n){
		rep(i,1,n) cin>>p[i].x>>p[i].y;
		rep(i,1,n-2){
			f[i][i+2]=S(p[i],p[i+1],p[i+2]);
		}
		rep(len,4,n){
			rep(i,1,n-len+1){
				int j=i+len-1;
				f[i][j]=0x3f3f3f3f;
				rep(k,i+1,j-1){
					if(judge(p[i],p[k],p[j])){
						f[i][j]=min(f[i][j],max(S(p[i],p[k],p[j]),max(f[i][k],f[k][j])));
					}
				}
			}
		}
		cout<<fixed<<setprecision(1)<<f[1][n]<<endl;		
	}

	return 0;
}

Forsaken喜欢数论

求前n个数的最小质因子的和。

在从 1 到 n遍历整数时，使用筛法求素数。
如果本身是素数，那么它本身就是它的最小质因子，累加计入 ans。
遍历由该素数生成的合数，如果还没访问过，表示这个合数的最小质因子就是该素数，累加计入ans。——Forsaken喜欢数论_牛客博客

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
//const int N=1e2+5;
//int v[N];
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int n,ans=0;cin>>n;
	vector<bool>v(n+1,0);
	for(int i=2;i<=n;i++){
		if(!v[i]){
			ans+=i;
			for(int j=i*i;j<=n;j+=i){
				if(!v[j]){
					v[j]=1;
					ans+=i;
				}
			}
		}
	} 
	cout<<ans;
	return 0;
}