NKweek-Round-106(赛时ABCDE，补F)
#单调栈 #构造 #贪心
- 单调栈过于久远，忘了
A
题意
- 用1*2和2*1的砖块填充3*n的矩形，判断能不能填充满
思路
- 签到，偶数可以，奇数不行
代码
void solve(){
int n;
cin >> n;
if(n%2) cout << "NO" << endl;
else cout << "YES" << endl;
}
B
题意
- 给定x，最多进行k次操作，判断能不能使得操作后变为回文串
- 记y为x翻转并去除前导0，每次操作x=x+y
思路
- 直接模拟
代码
bool check(string s){
for(int i=0,j=s.size()-1;i<=j;i++,j--){
if(s[i]!=s[j]) return false;
}
return true;
}
long long deal(long long n){
long long ans=0;
while(n%10==0) n/=10;
while(n){
ans*=10;
ans+=n%10;
n/=10;
}
return ans;
}
void solve(){
long long n,k;
cin >> n >> k;
bool ok=false;
if(check(to_string(n))){
cout << n << ' ' << 0 << endl;
return ;
}
for(int i=1;i<=k;i++){
n+=deal(n);
if(check(to_string(n))){
ok=true;
cout << n << ' ' << i << endl;
return ;
}
}
if(!ok) cout << n << ' ' << -1 << endl;
}
C
- 这题读题的时候发病了，从[l,r]选一个数看成了从序列的[l,r]选一个，难绷
题意
- 给定一个序列，序列的每一位是前两位乘积的个位，给定前两个数的取值范围，和从第三位开始的n-2个数字，求解前两位，如果没有答案输出-1
思路
- 从第三位开始只有个位，暴力枚举前两位，枚举范围最大为10
- 要开long long
代码
void solve(){
int n,l1,l2,r1,r2;
cin >> n >> l1 >> r1 >> l2 >> r2;
vector<int> a(n+10);
for(int i=3;i<=n;i++){
cin >> a[i];
}
bool ok=false;
for(int a1=l1;a1<=min(l1+100,r1);a1++){
for(int a2=l2;a2<=min(l2+100,r2);a2++){
if(a1*a2%10!=a[3]||a2*a[3]%10!=a[4]) continue;
ok=true;
cout << a1 << ' ' << a2 << endl;
return ;
}
}
if(!ok) cout << -1 << ' ' << -1 << endl;
}
D
题意
- 长为n的序列，你可以将任何数
变为
- 输出将这个序列变为回文序列的最少操作数，如果无法变成，输出-1
思路
- 显然，对一个数的操作不会改变最高位的位置，所以对应位置如果最高位不同直接寄
- 可以证明，对于任何一个数，经过这个变换最多32次就会循环
。对于int范围的数，当
大于32，就一定会读到高位0，然后不发生变化
代码
int hibit(int x){
int ans=0;
while(x){
x>>=1;
ans++;
}
return ans;
}
void solve(){
int n;
bool ok=true;
cin >> n;
vector<int> a(n+10);
vector<int> b(n+10);
for(int i=1;i<=n;i++){
cin >> a[i];
b[i]=hibit(a[i]);
}
int ans=0;
for(int i=1,j=n;i<=j;i++,j--){
if(a[i]==a[j]) continue;
if(b[i]!=b[j]){
ok=false;
break;
}
unordered_map<int,int> mi,mj;
int cnti=0,cntj=0;
while(mi.find(a[i])==mi.end()){
mi[a[i]]=cnti++;
a[i]^=(a[i]>>1);
}
while(mj.find(a[j])==mj.end()){
mj[a[j]]=cntj++;
a[j]^=(a[j]>>1);
}
int mn=INT_MAX;
for(auto [x1,x2]:mi){
for(auto [y1,y2]:mj){
if(x1==y1) mn=min(x2+y2,mn);
}
}
ans+=mn;
}
if(!ok) cout << -1 << endl;
else cout << ans << endl;
}
E
题意
- 对于一个数他的洞数值指的是：每一个数位上的数字所含的闭合空间个数
- 给定n和sum，构造长为n，元素和不超过sum，洞数和最大的数组
思路
- 观察到能产生贡献的只有4和8
- 数的范围不超过1e10，每次确定一个数的一个数位，最多
的复杂度就能构造完
代码
void solve(){
int n;
ll sum;
cin>>n>>sum;
if(sum<n){
cout<<-1<<"\n";
return;
}
vector<ll>ans(n,1);
ll rst=sum-n;
for(int i=0;i<=9;i++){
ll base=qpow(10,i);
if(i==0){
for(int j=0;j<n&&rst>=3;j++){
ans[j]+=3;
rst-=3;
}
for(int j=0;j<n&&rst>=4;j++){
ans[j]+=4;
rst-=4;
}
}else{
ll c=4*base;
for(int j=0;j<n&&rst>=c;j++){
ans[j]+=c;
rst-=c;
}
for(int j=0;j<n&&rst>=c;j++){
ans[j]+=c;
rst-=c;
}
}
}
for(int i=0;i<n;i++)cout<<ans[i]<< ' ';
cout << endl;
}
F
题意
- 对于一个长为n的序列，计算其满足如下要求的连续片段个数
- 片段长度大于等于3
- 片段首尾不相等
- 片段中所有元素需要小于片段两端元素
思路
- 假设片段尾小于片段首，可以证明满足条件的答案至多有一个
- 如果有第二个，则片段中间的元素(上一个)就存在大于段尾的情况，而这个唯一合法的答案其实就是左侧第一个大于当前元素的元素，所以维护一个单调递减栈，同时判断长度够不够
- 对于另一种情况，只需要反向扫一遍序列即可
代码
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
vector<int> a(n+10);
for(int i=1;i<=n;i++)cin >> a[i];
long long cnt=0;
stack<int> st;
for(int i=1;i<=n;i++){
bool ok=false;
while(!st.empty()&&a[i]>a[st.top()]) st.pop();
if(!st.empty()&&a[st.top()]==a[i]) ok=true;
if(!ok&&!st.empty()&&st.top()!=i-1) cnt++;
st.push(i);
}
while(!st.empty()) st.pop();
for(int i=n;i>=1;i--){
bool ok=false;
while(!st.empty()&&a[i]>a[st.top()]) st.pop();
if(!st.empty()&&a[st.top()]==a[i]) ok=true;
if(!ok&&!st.empty()&&st.top()!=i+1) cnt++;
st.push(i);
}
cout << cnt << endl;
}
return 0;
}
查看11道真题和解析
投递三维家等公司10个岗位