牛客周赛 Round 2 A~D

A

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=1e5+10;
string s;
string p;
void solve(){
	cin>>s>>p;
	int n=s.length();
	s+=s;
	int num=0;
	for(int i=0;i<n;i++){
		if(s.substr(i,p.length())==p)
		num++;
	}
	cout<<num;
    
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

B:dp

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=1e5+10;
char s[N];
int n;
int a[N];
ll f[N];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>s+1;
	for(int i=2;i<=n;i++){
		if(s[i]==s[i-1]){
			f[i]=f[i-1];
			continue;
		}
		f[i]=max(f[i-1],f[i-2]+a[i-1]+a[i]);
	} 
	cout<<f[n];
    
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

C:模拟

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=18;
int a[N];
void solve(){
    int n;
    cin>>n;
    memset(a,0,sizeof a);
    while(n--){
    	int o,b;
    	cin>>o>>b;
    	if(o==0){
    		int x=max(a[b],a[b+1]);
    		a[b]=x+3;
    		a[b+1]=x+1;
		}
		else if(o==90){
			int x=max(a[b+1],a[b+2]);
			if(x>=a[b]+1){
				a[b]=x+1;
				a[b+1]=x+1;
				a[b+2]=x+1;
			}
			else{
				x=a[b];
				a[b]=x+2;
				a[b+1]=x+2;
				a[b+2]=x+2;
			}
		}
		else if(o==180){
			if(a[b]>=a[b+1]+3){
				int x=a[b];
				a[b]=x+1;
				a[b+1]=x+1;
			}
			else{
				int x=a[b+1];
				a[b]=x+3;
				a[b+1]=x+3;
			}
		}
		else{
			int x=max(a[b],a[b+1]);
			x=max(x,a[b+2]);
			a[b]=x+1;
			a[b+1]=x+1;
			a[b+2]=x+2;
		}
	}
	for(int i=1;i<=8;i++) cout<<a[i]<<" ";
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

D:前缀和+二分(注意这里会爆int全部换成long long，d题没过就是因为这个，一开始就把前缀和设为long long一直是58%qwq)

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,h,k,q;
typedef struct{
	ll h,v,sum;
}node;
node mos[N];
ll s[N];
bool cmp(node a,node b){
	return a.sum<b.sum;
}
ll get_sum(ll x,ll y){
	if(x%4==0){
		return (x/4*3-1)*y;
	}
	else if(x%4==3){
		return (x/4*3+1)*y;
	}
	else{
		return x/4*3*y;
	}
}
void solve(){
	cin>>n>>h>>k;
	for(int i=1;i<=n;i++){
		cin>>mos[i].h>>mos[i].v;
		mos[i].sum=get_sum(mos[i].h,mos[i].v);
	}
	sort(mos+1,mos+1+n,cmp);
	for(int i=1;i<=n;i++) s[i]=s[i-1]+mos[i].sum;
	cin>>q;
	while(q--){
		ll x;
		cin>>x;
		x=h+x*k;
		int l=0,r=n;
		while(l<r){
			int mid=l+r+1>>1;
			if(s[mid]>=x)  r=mid-1;
			else l=mid; 
		}
		cout<<l<<" ";
	}
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}