小石的签到题

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int n; cin>>n;
	if(n==1) puts("Yang");
	else puts("Shi");
	return 0;
}
//n=1 yang
//n=2 shi
//n=3 shi
//n=4 shi

小雨的三角形【前缀和】

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int mod=1e9+7;
const int N=1e3*2+10;
int f[N][N],s[N],n,m;
int main(void)
{
	cin>>n>>m;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++) f[i][j]=1;
	for(int i=2;i<=n;i++)
		for(int j=1;j<=i;j++) 
			f[i][j]=(1ll*f[i-1][j-1]+f[i-1][j])%mod;
	for(int i=1;i<=n;i++)
	{
		LL temp=0;
		for(int j=1;j<=i;j++) temp=(temp+f[i][j])%mod;
		s[i]=(s[i-1]+temp)%mod;
	}
	while(m--)
	{
		int l,r; cin>>l>>r;
		cout<<(s[r]-s[l-1]+mod)%mod<<'\n'; 
	}
	return 0;
}

小石的海岛之旅【双指针】

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N],n,m;
int main(void)
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	while(m--)
	{
		int x; cin>>x;
		int cnt=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i]>x)
			{
				int j=i;
				while(j<=n&&a[j]>x) j++;
				i=j;cnt++;
			}
		}
		cout<<cnt<<endl;
	}
	return 0;
}

小阳买水果【思维】

在这里插入图片描述
线段树做法：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6*2+10;
typedef long long int LL;
LL n,w[N];
struct node
{
	LL l,r,v;//结尾在区间[l,r] 内中的最大值
}tr[N*4];
void build(int u,int l,int r)
{
	tr[u].l=l,tr[u].r=r;
	if(tr[u].l==tr[u].r)
	{
		tr[u].v=w[l];
		return;
	}
	int mid=(l+r)/2;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	tr[u].v=max(tr[u*2].v,tr[u*2+1].v);
}
int query(int u,LL sum)
{
	if(tr[u].l==tr[u].r) return tr[u].l;
	if(tr[u*2+1].v>sum) return query(u*2+1,sum);//贪心的思路先去右边找，找的更长
	if(tr[u*2].v>sum)   return query(u*2,sum);
    return 0;
}
int main(void)
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i],w[i]+=w[i-1];
	build(1,1,n);
	int ans=0;
	for(int i=0;i<=n;i++)
	{
		int res=query(1,w[i]);
		if(res) ans=max(ans,res-i);
	}
	cout<<ans; 
	return 0; 
}

排序：

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=1e6*5+10;
int n,a[N];
struct node{int sum,pos;};
vector<node>ve;
bool cmp(node a,node b)
{
	if(a.sum==b.sum) return a.pos>b.pos;
	return a.sum<b.sum;
}
int main(void)
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		a[i]+=a[i-1];
		ve.push_back({a[i],i});
	} 
	ve.push_back({0,0});
	sort(ve.begin(),ve.end(),cmp);
	int pos=n,ans=0;
	for(int i=0;i<ve.size();i++)
	{
		pos=min(pos,ve[i].pos);//保存最小的下标
		if(pos<ve[i].pos) ans=max(ans,ve[i].pos-pos);
	}
	cout<<ans;
}

小雨的矩阵【DP】

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const int N=15;
const int M=1e4+10;
int f[N][N][M],w[N][N],n;
int main(void)
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) cin>>w[i][j];
	f[1][1][w[1][1]]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=0;k<M;k++) 
			{
				int temp=k-w[i][j];
				if(temp>=0&&f[i-1][j][temp]) f[i][j][k]=1;
				if(temp>=0&&f[i][j-1][temp]) f[i][j][k]=1;
			}
		}
	}
	int ans=0;
	for(int i=0;i<M;i++) 
		if(f[n][n][i]) ans++;
	cout<<ans;
	return 0;
}

小石的图形

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
int main(void)
{
	double n; cin>>n;
	double r=n/pi;
	printf("%.3lf",pi*r*r/2);
	return 0;
}