签到题.
输入输出读完应该就懂了:
从y1枚举到y2,若枚举的年份不在停办年份里则答案加一
void solve() {
int n,m;
cin >> n;
vector<int> a(N),year(N);
cin >> m;
for(int i = 0;i < m;i++){
int y;
cin >> y;
year[y] = 1;
}
int y;
cin >> y;
int ans = 0;
for(int i = n;i <= y;i ++)
if(!year[i])
ans++;
cout << ans << endl;
}每次应该从价格最便宜的商店购买货物，并卖给价格最贵的商店。用双指针模拟这一贪心策略即可.
#include<bits/stdc++.h>
using namespace std;
#define LL long long
void solve(){
LL n;
cin >> n;
vector<pair<LL,LL>> a;
for(LL i = 0;i < n;i ++){
LL x,y;
cin >> x >> y;
a.push_back({x,y});
}
LL sum = 0;
sort(a.begin(), a.end());
for(LL i = 0, j = n - 1; i < j; ){
LL x = min(a[i].second, a[j].second);
sum += (a[j].first - a[i].first) * x;
a[i].second -= x;
a[j].second -= x;
if(a[i].second == 0)
i++;
if(a[j].second == 0)
j--;
}
cout << sum << endl;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
LL T;
cin>>T;
while(T--){
solve();
}
return 0;
}如果已知 2 个人有邻居，剩下的人没有邻居，怎样选择有邻居的人才能使总满意度最大化？
这是一个经典问题。先假设所有人都是没邻居的，得到总满意度 。当第 个人从没邻居变成有邻居时，总满意度将增加 ai bi。因此选择 最大的 个人变成有邻居的即可。排序后可以在 的复杂度内一次性算出 的最大总满意度。
如果 个人有邻居，剩下的人没有邻居，这样的布局至少需要 栋房子（即有邻居的人都住在最左边，然后每隔一栋房子住一个没邻居的人）。因此只有满足 才能考虑。
最后，别忘了考虑所有人都没有邻居的情况。这要求 。
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e6+10, M = 998244353;
typedef unsigned long long ll;
typedef pair<int,int> PII;
int n,m,t,k;
map<int,int> mp;
void solve() {
cin >> n >> m;
vector<int> A(n + 1), B(n + 1),ve;
for(int i = 1;i <= n;i ++){
cin >> A[i] >> B[i];
ve.push_back(A[i] - B[i]);
}
sort(ve.begin(), ve.end());
int ans = 0, now = 0;
for(int i = 1;i <= n;i ++)
now += B[i];
if(m >= 2 * n - 1)
ans = now;
now += ve[n - 1];
for(int i =2;i <= n;i ++){
now += ve[n - i];
if(2 * n - i <= m)
ans = max(ans, now);
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int Ke_scholar = 1;
cin >> Ke_scholar;
while(Ke_scholar--)
solve();
return 0;
}
/*
*/
假设答案为 ，那么存在一条路径，使得从 到 的每个整数都在路径上。这一条件满足二分性，因此我们可以二分答案 ，并检查是否存在这样的路径。
由于每一步只能往右或者往下走，因此将路径上每个格子的坐标按行为第一关键字，列为第二关键字排序后，排在前面的坐标的列编号，一定小于等于排在后面的坐标的列编号。
因此，将从 0 到 的每个整数所在的格子的坐标排序，并检查列编号是否满足以上条件，即可判断是否存在一条路径，使得这些整数都在路径上。实际实现时，不需要使用排序函数。只要依此枚举每个格子，若格子里的整数小于 则把格子加入 vector，这样得到的 vector 就已经按枚举的顺序排序了。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e6+10, M = 998244353;
typedef unsigned long long ll;
typedef pair<int,int> PII;
int n,m,t,k,a[N];
// 将从 0 到 x - 1 所在的格子坐标“排序”，检查前面的列坐标是否小于等于后面的列坐标
bool check(int x){
// 实际实现时，不需要使用排序函数，
// 直接按顺序枚举每个格子，若格子里的整数小于 x 则把格子加入 vector，
// 这样得到的 vector 就已经按枚举的顺序排序了
// 而且甚至连 vector 也不用真的维护，
// 因为我们只关心 vector 最后一个元素的列坐标，和当前列坐标的大小关系，
// 直接用变量 last 维护最后一个元素的列坐标即可
int last = 0;
for(int i = 0;i <n;i ++){
for(int j = 0;j < m;j ++){
if(a[i * m + j] < x){
if(last > j)
return false;
last = j;
}
}
}
return true;
}
void solve() {
cin >> n >> m;
for(int i = 0;i < n;i ++)
for(int j = 0;j <m ;j++)
cin >> a[i * m + j];
int l = 0, r = n * m;
while(l < r){
int mid = (l + r + 1) >> 1;
if(check(mid)) l = mid ;
else r = mid - 1;
}
cout << l << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int Ke_scholar = 1;
cin >> Ke_scholar;
while(Ke_scholar--)
solve();
return 0;
}
/*
*/
因为数据范围很小,直接模拟暴力就能过
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
#define int long long
int ans = 100;
int u[] = {0,2,0,-2};
int v[] = {2,0,-2,0};
int uu[] = {0,1,0,-1};
int vv[] = {1,0,-1,0};
int n,m,k;
void dfs(int x,int y, vector<vector<int>>& gg ){
for(int i = 0;i < 4;i ++){
int dx = u[i] + x;
int dy = v[i] + y;
int d1 = uu[i] + x;
int d2 = vv[i] + y;
if(dx > 0 && dy > 0 && dx <= n && dy <= m && gg[d1][d2] && !gg[dx][dy]){
gg[dx][dy] = 1;
gg[x][y] = gg[d1][d2] = 0;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
if(gg[i][j]){
auto ggg = gg;
dfs(i,j,ggg);
}
}
}
gg[dx][dy] = 0;
gg[x][y] = gg[d1][d2] = 1;
}
}
int sum = 0;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
if(gg[i][j])
sum++;
ans = min(ans, sum);
return ;
}
void solve(){
ans = 100;
cin >> n >> m >> k;
vector<vector<int> > g(n + 1, vector<int> (m + 1, 0));
for(int i = 0;i < k; i++){
int x,y;
cin >> x >> y;
g[x][y] = 1;
}
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
if(g[i][j]){
auto gg = g;
dfs(i,j,gg);
}
}
}
cout << ans << endl;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
其余题解参考
因为咱很懒,所以有的题解直接拿来用了?