T1

签到题没什么好讲的，我的做法是将所有的可能用数组存起来然后一个一个对比

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 15;
int ans[maxn];
int a[maxn];
int solve(int n) {
	for(int i=1;i<=3;i++) {
		ans[i]=a[i];
	}
	int cnt=3;
	for(int i=1;i<=3;i++) {
		for(int j=i+1;j<=3;j++) {
			ans[++cnt]=a[i]+a[j];
		}
	}
	ans[7]=a[1]+a[2]+a[3];
	int minn=INT_MAX;
	sort(ans+1,ans+1+7);
	for(int i=1;i<=7;i++) {
		if(n<ans[i]) {
			break;
		}
		minn=min(minn,n-ans[i]);
	}
	if(minn==INT_MAX) {
		minn=n;
	}
	return minn;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--) {
		int k;
		cin>>k;
		for(int i=1;i<=3;i++) {
			cin>>a[i];
		}
		sort(a+1,a+1+3);
		cout<<solve(k)<<"\n";
	}
	return 0;
}//100pts

T2

没注意要蛇型走位挂了35pts（）
其实这题50分超级好拿，对于n<=20,可以选择全部走边上的一，然后性质A的意思就是将从一到某一层全部拿满就行
正解思路是可以看到2^60大于1e18所以直接空出来，然后进行二进制分解去填前面的空，不够填空的说明可以用1来填

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
const int mod1 = 1e18+1;
const int mod = 99824353;
const int maxn = 505;
int dp[maxn][maxn];
struct point {
	int x,y;
};
vector<point>op;
int mul(int a,int b) {
	return ((a%mod)*(b%mod))%mod;
}
void init() {
	dp[1][1]=dp[2][1]=dp[2][2]=1;
	for(int i=1; i<=60; i++) {
		for(int j=1; j<=i; j++) {
			if(j==1||j==i) {
				dp[i][j]=1;
			} else {
				dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
			}
		}
	}
	return ;
}
int n;
signed main() {
	init();
	cin>>n;
	if(n<=60) {
		cout<<n<<'\n';
		for(int i=1; i<=n; i++) {
			cout<<i<<' '<<1<<"\n";
		}
		cout<<n<<' '<<1<<"\n";
		return 0;
	}
	int tmp=n-60;
	int cnt=1;
	int ans=1;
	int dir=0;
	int num=60;
	int sum=0;
	while(tmp) {
		if (tmp % 2 == 1) {
			if (dir == 1) {
				for (int i = 1; i <= cnt; i++) {
					op.push_back({cnt, i});
					ans = mul(ans, dp[cnt][i]);
					sum += dp[cnt][i];
				}
			} else {
				for (int i = cnt; i >= 1; i--) {
					op.push_back({cnt, i});
					ans = mul(ans, dp[cnt][i]);
					sum += dp[cnt][i];
				}
			}
			dir = !dir;
		} else {
			num--;
			if (dir == 0) {
				op.push_back({cnt, cnt});
			} else {
				op.push_back({cnt, 1});
			}
			sum += 1;
		}
		cnt++;
		tmp /= 2;
	}
	sum+=num;
	for(int i=1;i<=num;i++) {
		if(dir==0) {
			op.push_back({cnt,cnt});
		} else {
			op.push_back({cnt,1});
		}
		cnt++;
	}
	cout<<op.size()<<endl;
	for(int i=0;i<op.size();i++) {
		cout<<op[i].x<<' '<<op[i].y<<"\n";
	}
	cout<<sum<<' '<<ans<<'\n';
	return 0;
}

T3

dfs可以骗30pts（）
思路是既然w范围大价值范围小，我们反其道而行之，设能在j价值内获得最小容量来进行背包状态转移方程

CPP


dp[i][j] = dp[i - 1][j - v[i]] + w[i] // 装入
dp[i][j] = dp[i - 1][j]//不装入

CPP

#include<bits/stdc++.h>
using namespace std;
int dp[105][100005];
int v[105],w[105];
int main() {
	int n,W;
	cin>>n>>W;
	int sum=0;
	for(int i=1;i<=n;i++) {
		cin>>w[i]>>v[i];
		sum+=v[i];
	}
	for(int i=1;i<=sum;i++) {
		dp[0][i]=1e9;
	}
	int ans=0;
	dp[0][0]=0;
	for(int i=1;i<=n;i++) {
		for(int j=0;j<=sum;j++) {
			dp[i][j]=dp[i-1][j];
			if(j>=v[i]) {
				dp[i][j]=min(dp[i-1][j-v[i]]+w[i],dp[i][j]);
			}
		}
	}
	for(int i=0;i<=sum;i++) {
		if(dp[n][i]<=W) {
			ans=i;
		}
	}
	cout<<ans;
	return 0;
}

T4

首先要让一个一段亲密度最大，自然地我们就会想到使用二分答案，二分找出上限之后，我们使亲密度大于k的段数严格小于k，最后枚举就行
至于验证二分，将所有人分为两部分，1到n-x和n-x+1到n后面的部分让他们两两配对若亲密度小于k说明合法反之不合法

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
vector<int>num[maxn];
long long a[maxn],n,k;
long long calc(int x)
{
	long long sum = (n - x) * x + x * (x - 1) / 2;
	for (int i = 1; i <= n; i++)
	{
		int l = 0;
		for (int j = 0; j < num[i].size(); j++)
		{
			while (l < num[i].size() && num[i][j] - num[i][l] > x)
			{
				l++;
			}
			sum = sum - (j - l);
		}
	}
	return sum;
}
int main() {
	cin>>n>>k;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		num[a[i]].push_back(i);
	}
	if(calc(n)<k) {
		cout<<-1;
		return 0;
	}
	int l=0-1,r=n+1;
	while(l+1<r) {
		int mid=(l+r)/2;
		if(calc(mid)<k) {
			l=mid;
		} else {
			r=mid;
		}
	}
	int d=l+1;
	long long cnt=calc(l);
	for(int i=1; i<=n-d; i++) {
		if(a[i]!=a[i+d]) {
			cnt++;
		}
		if(cnt==k) {
			cout<<i<<' '<<i+d;
			return 0;
		}
	}
	return 0;
}

8.15test

文章操作

T1

T2

T3

T4

相关推荐

评论

8.15test