2023-5-17.md

Note

• 202209-2 背包问题，将求（超过限制的最少）转化为（小于限制的最多）
• 202212-2 暴力搜索
• 202303-2 二分或优化cost数组（结构体排序，iterator用法）
• 202206-1 sqrt，pow返回的是double，memset使用0,-1,0x3f,double不能用==
• 202206-2 vector<pair,pair>a;a.push_back({x,y});a.first;a.second

Code

20220601

#include<bits/stdc++.h>

using namespace std;

double a[1010];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	double sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	double t=sum/n;
	double d=0;
	for(int i=1;i<=n;i++){
		d+=(a[i]-t)*(a[i]-t);
	}
	d/=n;
	for(int i=1;i<=n;i++){
		cout<<(a[i]-t)/sqrt(d)<<endl;
	}
	return 0;
}

20220602

#include<bits/stdc++.h>

using namespace std;

vector<pair<int,int>>a;
int mp[55][55];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	memset(mp,0,sizeof(mp));
	int n,l,s;
	cin>>n>>l>>s;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		a.push_back({x,y});
	}
	int tcnt=0;
	for(int i=s;i>=0;i--){
		for(int j=0;j<=s;j++){
			cin>>mp[i][j];
			if(mp[i][j])tcnt++;
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		if(a[i].first+s>l||a[i].second+s>l)
			continue;
		int flag=1;
		int xx=a[i].first;
		int yy=a[i].second;
		int cnt=0;
		for(int j=0;j<n;j++){
			if(a[j].first>=xx&&a[j].first<=xx+s&&a[j].second>=yy&&a[j].second<=yy+s){
				if(mp[a[j].first-xx][a[j].second-yy]==0){
					flag=0;
					break;
				}
				else cnt++;
			}	
			else continue;
		}
		if(flag==1&&cnt==tcnt)ans++;
	}
	cout<<ans<<endl;
	return 0;
}

20220902

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=3e5+10;
int a[40];
int dp[40][N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n,x;
	cin>>n>>x;
	memset(dp,0,sizeof(dp));
	int sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	int v=sum-x;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=v;j++){
			if(j-a[i]>=0){
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+a[i]);
			}
			else dp[i][j]=dp[i-1][j];
		}
	}
	cout<<sum-dp[n][v]<<endl;
	return 0;
}