暑假刷题第23天--8/6

3748. 递增子串 - AcWing题库

#include<iostream>
#include<string>
const int N=200005;
int a[N];
using namespace std;
int main(){int t;cin>>t;for(int q=1;q<=t;q++){int n;cin>>n;string s;cin>>s;int cnt=1;a[1]=1;for(int i=2;i<=n;i++){if(s[i-1]>s[i-2])cnt++,a[i]=cnt;else {cnt=1;a[i]=cnt;}}printf("Case #%d: ",q);for(int i=1;i<=n;i++){cout<<a[i]<<' ';}cout<<endl;}return 0;
} 

3325. Kick_Start - AcWing题库

#include<iostream>
#include<string>
const int N=200005;
int a[N];
using namespace std;
int main(){int t;cin>>t;for(int q=1;q<=t;q++){string s;cin>>s;int cnt=0;a[s.size()]=0;for(int i=s.size()-1;i>=0;i--){if(i>=4&&s[i]=='T'&&s[i-1]=='R'&&s[i-2]=='A'&&s[i-3]=='T'&&s[i-4]=='S'){cnt++;a[i]=cnt;}else {a[i]=a[i+1];}}int ans=0;for(int i=0;i<s.size()-3;i++){if(s[i]=='K'&&s[i+1]=='I'&&s[i+2]=='C'&&s[i+3]=='K'){ans+=a[i];}}printf("Case #%d: ",q);cout<<ans<<endl;}return 0;
} 

Problem - 1817A - Codeforces（需要学习）

#include<iostream>
#include<string>
const int N=200005;
int a[N];
int p[N];
using namespace std;
void solve(){int n,q;cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];for(int i=2;i<=n-1;i++){int cnt=0;if(a[i]>=a[i+1]&&a[i-1]>=a[i])cnt=1;p[i]=p[i-1]+cnt;}while(q--){int l,r;cin>>l>>r;if(l==r){cout<<1<<endl;}else {cout<<(r-l+1)-(p[r-1]-p[l])<<"\n";}}
}
int main(){int t=1;while(t--){solve();}
} 

Problem - 1811E - Codeforces（进制转换--需要学习）

#include<iostream>
#include<string>
#include<vector>
const int N=200005;
int a[N];
int p[N];
using namespace std;
void solve(){long long n;cin>>n;vector<long long>ans;while(n>0){ans.push_back(n%9);n/=9;}for(int i=ans.size()-1;i>=0;i--){if(ans[i]<4)cout<<ans[i];else cout<<ans[i]+1;}cout<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}
} 

Problem - C - Codeforces（构造）

#include<iostream>
#include<string>
#include<vector>
const int N=200005;
int a[N];
int b[N];
using namespace std;
void solve(){int n;cin>>n;for(int i=1;i<=n-1;i++){cin>>a[i];b[i]=-1;}for(int i=1;i<=n-1;i++){if(b[i]!=-1){if(a[i]<a[i+1]){b[i+1]=a[i];}else {b[i+1]=a[i+1];}continue;}if(a[i]<a[i+1]){b[i]=a[i];b[i+1]=a[i];}else {b[i]=a[i];}}b[n]=a[n-1];for(int i=1;i<=n;i++){cout<<b[i]<<' ';}cout<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}
} 

Problem - D - Codeforces（需要学习）

#include<iostream>
#include<string>
#include<vector>
#define ll long long
const int N=200005;
int a[N];
int b[N];
long long f[46];
using namespace std;
void solve(){ll n,x,y;cin>>n>>x>>y;ll left =y-1,right =f[n+1]-y;ll up=x-1,down=f[n]-x;bool ok=true;ll now=0;for(ll i=n;i>=1;i--){if(~now){if(left>=f[i])left-=f[i];else if(right>=f[i])right-=f[i];else{ok=false;break;}}else{if(up>=f[i])up-=f[i];else if(down>=f[i])down-=f[i];else{ok = false;break;}}now=~now;}if(ok==false)cout<<"NO"<<endl;else cout<<"YES"<<endl;
}
int main(){f[0]=1,f[1]=1;for(int i=2;i<=45;i++){f[i]=f[i-1]+f[i-2];}int t;cin>>t;while(t--){solve();}
} 

Problem - D - Codeforces

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
#define ll long long
const int N=200005;
int a[N];
int b[N];
int d[27],x[27];
using namespace std;
void solve(){int n;cin>>n;string s;cin>>s;int ans=0;string cnt;int f=1;for(int i=0;i<n-1;i++){if(i>=1&&s[i-1]==s[i+1]){f=1;continue;}string p;p+=s[i];p+=s[i+1];if(i==0||cnt!=p||f==1){f=0;ans++;cnt=p;}}cout<<ans<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}
} 

Problem - C2 - Codeforces

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
#define ll long long
const int N=200005;
int a[N];
int b[N];
int d[27],x[27];
using namespace std;
void solve(){priority_queue<int,vector<int>,less<int> >q;int n;cin>>n;long long ans=0;for(int i=0;i<n;i++){int x;cin>>x;if(x==0){if(!q.empty()){ans+=q.top();q.pop();}}else {q.push(x);}}cout<<ans<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}
} 

C-游游的数值距离_牛客周赛 Round 6 (nowcoder.com)

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
#define ll long long
const int N=200005;
ll a[N];using namespace std;
void solve(){ll n;cin>>n;ll ans1,ans2,p=1e16+6;a[1]=1;for(int i=2;i<=20;i++){a[i]=a[i-1]*i;}for(int x=1;x<=20;x++){if(a[x]==1&&x!=2){if(p>abs((-n))){ans1=x,ans2=3;p=n;}continue;}ll y=n/(a[x]-1);if(y==0)y++;if(p>abs((a[x]-1)*y-n)&&x!=2&&y!=2){ans1=x,ans2=y;p=abs((a[x]-1)*y-n);}y++;if(p>abs((a[x]-1)*y-n)&&x!=2&&y!=2){ans1=x,ans2=y;p=abs((a[x]-1)*y-n);}}cout<<ans1<<' '<<ans2<<endl;
}
int main(){int t=1;//cin>>t;while(t--){solve();}
}