2024牛客寒假算法基础集训营5
赛时出了五题,被自己不严谨的思维害惨了,之后的题晚几天再补，要开学了
A.mutsumi的质数合数
思路
既不是质数也不是合数恐怕非1莫属了吧
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin()+1,x.end()
void solve(){
int n; cin>>n;
std::vector<int> a(n+1);
int ans=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]!=1){
ans++;
}
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
C.anon的私货
思路
感觉这题没多少需要特别注意的地方,一定要记住在两个数中间插入0两边的数都会受到影响的
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin()+1,x.end()
void solve(){
int n; cin>>n;
int ans=0;
std::vector<int> a(n+2,0);
std::vector<int> s(n+2,0);
for(int i=1;i<=n;i++){
cin>>a[i];
// s[i]=s[i-1]+a[i];
}
int res=0;
int l=0;
a[n+1]=1e18;
a[0]=1e18;
for(int i=1;i<=n+1;i++){
int minn=min(a[i],a[i-1])-1;
ans+=minn;
a[i]-=minn;
a[i-1]-=minn;
}
// for(int i=1;i<=n;i++){
// cout<<s[i]<<" ";
// }
cout<<ans<<endl;
// cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t=1;
while(t--){
solve();
}
return 0;
}
I.rikki的最短路
思路
就是一个简单的模拟,这题还是比较简单的,但是我写的比较复杂,应该是有更好的解决办法
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int t,a,k; cin>>t>>a>>k;
if(t>=0&&a>=0){
if(a<=t){
cout<<t<<endl;
return ;
}
else{
cout<<(t+(a-t)*2)<<endl;
return ;
}
}
else if(t>=0&&a<=0){
if(abs(a)<=k){
cout<<(abs(a)*2+t)<<endl;
return ;
}
else{
cout<<(t+(t+abs(a))*2)<<endl;
return ;
}
}
else if(t<=0&&a>=0){
if(a<=k){
cout<<(abs(t)+abs(a)*2)<<endl;
return ;
}
else{
cout<<(abs(t)+(a-t)*2)<<endl;
return ;
}
}
else if(t<=0&&a<=0){
if(t<a){
cout<<abs(t)<<endl;
return ;
}
else{
cout<<(t-a)*2+abs(t)<<endl;
return ;
}
}
}
signed main(){
// int t1=1; cin>>t;
int t1=1;
while(t1--) solve();
return 0;
}
L.anon的星星
思路
判断局数,当我们减去星星数的绝对值之后,我们就会发现剩下的机场一定是一胜一负抵消掉的,所以只需要判断(n-x)%2是不是零就行,这里一开始我是直接模拟,想的巨麻烦,也wa了一次
Code
#include <bits/stdc++.h>
using namespace std;
// using i64 = long long;
#define int long long
void solve(){
int n,x;
cin>>n>>x;
int ans=n-abs(x);
if(ans%2){
cout<<-1<<endl;
return ;
}
else{
if(x<=0){
cout<<ans/2<<" "<<ans/2+abs(x)<<endl;
return ;
}
else{
cout<<ans/2+x<<" "<<ans/2<<endl;
return ;
}
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
// std::cin >> t;
t=1;
while (t--) {
solve();
}
return 0;
}
M.mutsumi的排列连通
思路
这个不难想要么是没办法分成两个连通块,要么一定可以在两次删除中出现至少两个连通块,(可惜我用map时候不小心把其中一个判断写错了,我醉了,自己搞反了可恶),我们可以用map存储下标,然后判断两个相同数字的位置,如果差小于等于1且不在两边(不在两边是位置相同的情况)是可以一次切成的
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N],b[N];
void solve(){
int n;
cin>>n;
std::map<int, int> mp1,mp2;
for(int i=1;i<=n;i++){
cin>>a[i];
mp1[a[i]]=i;
}
bool f=false;
for(int i=1;i<=n;i++){
cin>>b[i];
mp2[b[i]]=i;
if(abs(mp2[b[i]]-mp1[b[i]])<=1){
if(mp1[b[i]]==mp2[b[i]]&&i==1) continue;
if(mp1[b[i]]==mp2[b[i]]&&i==n) continue;
f=true;
}
}
if(n==1){
cout<<-1<<endl;
return ;
}
if(n==2){
if(mp1[a[1]]==mp2[a[1]]){
cout<<-1<<endl;
return ;
}
}
if(f){
cout<<1<<endl;
return ;
}
else{
cout<<2<<endl;
}
// std::map<int, int> mp1,mp2;
}
signed main(){
int t=1;
cin>>t;
while(t--) solve();
return 0;
}