C++小白训练第六天
以下为牛客挑战
今日收获
了解了map<int,int>m;，map可以去重共，因为键值对key是唯一的，for (auto it = m.begin(); it != m.end(); ++it) {int key = it->first; // 键int& val = it->second; // 值
}
for (auto& [k, v] : m) { /* k 是键，v 是值 */ }
所以一般使用时候都是先转换为vector<pair<int,int>>m;
for(auto &z: m){v.emplace_back(z);}
小红出千
G-小红出千_牛客周赛 Round 123
5
1 2 3 4 6
1
5 5
这个顺子一定是长度为n的，所以当我门固定一个左端，那右端就可以确定了，我们可以用双指针去维护
我们去维护一个区间，我们发现在区间中，只要我们的数够多就可以，我们就可以更少的从区间外去变换到区间里面，所以我就去遍历一下找到合适的区间，
最后找到一个区间满足且有较多的数，再把这些里面的数进行标记一下，标记为使用
一个是数有没有用，一个是位置
for(int i=l;i<=r;i++){vis[v[i].second]=1;//位置used.emplace(v[i].first);//用过了}
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;map<int,int>m;vector<int>s(n+1);for(int i=1;i<=n;i++){cin>>s[i];m[s[i]]=i;}vector<pair<int,int>>v;for(auto &z: m){v.emplace_back(z);}
// for(int i=0;i<v.size();i++){
// cout<<v[i].first<<" "<<v[i].second<<endl;
// }int l=-1,r=-1;int mx=0;for(int i=0,j=0;i<v.size();i++){while(j<i&&v[i].first-v[j].first>=n){j++;}if(i-j+1>mx){mx=i-j+1;l=j;r=i;}}set<int>used;vector<int>vis(n+1);for(int i=l;i<=r;i++){vis[v[i].second]=1;used.emplace(v[i].first);}vector<pair<int,int>>ans;int dow=v[l].first;for(int i=1;i<=n;i++){while(used.count(dow)){dow++;}if(vis[i])continue;ans.emplace_back(i,dow);dow++;}cout<<ans.size()<<endl;for(auto & [x,y]:ans){cout<<x<<" "<<y<<endl;}return 0;
}
牛客周赛 Round 122
CPC Problems
12
A B C D E F G H I J K L
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;for(int i=0;i<n;i++){char m='A'+i;cout<<m<<" ";}return 0;
}
Chess
输入和输出
2
1 1
3 3
1
2
这个是规律题，如果不知道规律很难做出来
直接上结论
先写一下不要算的情况，第一点行数或者列数小于等于2没办法跳，直接输出1；然后结论是 n/2向上取整*m/2向上取整得到的结果继续向上取整
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];
void solve(){int n,m;cin>>n>>m;if(n<=2||m<=2){cout<<"1"<<endl;}else{n=(n+1)/2;m=(m+1)/2;cout<<(n*m+1)/2<<endl;}
};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}
Sequence Cost
C-Sequence Cost_牛客周赛 Round 122
2
4
1 3 1 1
2
1 1
6
2
这题其实就两种情况
要么不改，直接sum就完事了，
要么全部改为最小加一个最大的就可以了。
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];
void solve(){int n;cin>>n;vector<int>m(n);int m1=1e10,m2=0,sum=0;for(int i=0;i<n;i++){cin>>m[i];if(m[i]>m2){m2=m[i];}if(m1>m[i]){m1=m[i];}sum+=m[i];}if(sum>(m2+m1*n)){cout<<m2+m1*n<<endl;}else{cout<<sum<<endl;}};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}
Digital Deletion
2
4
2 3 4 6
3
1 1 1
4
0
对于一个给定的非负整数集合 S，mex(S) 是最小的不在 S 中的非负整数。
思路就我们可以先排序，然后从前面向后遍历，我们会发现存在这个数的和存在一个范围，【0，前面数的和】，如果下一个数大于这个和+1的话就相当于要取合并的了，中间会存在一个空缺。我们所以之后的都不可以取了
特别判定一下0的
这个范围
2
5
0 0 0 0 0
3
0 0 1
//可以直接把0全部删除。
全零的分开讨论
就行了
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];
void solve(){int n;cin>>n;vector<int>v(n+1);int s=0;for(int i=1;i<=n;i++){cin>>v[i];if(v[i]==0){s++;}}if(s==n){cout<<n<<endl;return;}sort(v.begin()+1,v.end());int sum=0;for(int i=1;i<=n;i++){if(v[i]>sum+1){if(s>=2){cout<<n-i+1+s-1<<endl;}else{cout<<n-i+1<<endl;}return;}sum+=v[i];}cout<<0+s-1<<endl;
};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}