个人技术分享

1.卓儿是外星人 - 蓝桥云课 (lanqiao.c)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int a[N];//求满足子串和小于m的最长子串
void solve()
{
	int n,m;cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
    a[i]+=a[i-1];
  }
  if(a[n]<=m)
  {
    cout<<a[n]<<" "<<n;
    return ;
  }
  int l=0;int nct=0;int min1=inf;
  for(int r=1;r<=n;r++)
  {
    if(a[r]-a[l]>m)
    {
      r--;
      if(nct<=r-l)
      {
        if(nct==r-l)
        {
          min1=min(min1,a[r]-a[l]);
        }
        else
        {
          nct=r-l;
          min1=a[r]-a[l];
        }
      }
      l++;
    }
  }
  cout<<min1<<" "<<nct;
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

2.分巧克力 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int h[N],w[N];int n,k;
bool check(int x)
{
  int nct=0;
  for(int i=1;i<=n;i++)
  {
    nct+=(h[i]/x)*(w[i]/x);
  }
  if(nct>=k)return true;
  else return false;
}
void solve()
{
	cin>>n>>k;
  for(int i=1;i<=n;i++)
  {
    cin>>h[i]>>w[i];
  }
  int l=1,r=100000;int fk;
  while(l<=r)
  {
    int mid=(l+r)>>1;
    if(check(mid)){l=mid+1;fk=mid;}
    else r=mid-1;
  }
  cout<<fk;
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

3.[USACO 2009 Dec S]Music Notes (nowcoder.com)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int a[N];
void solve()
{
	int n,m;cin>>n>>m;int nct=0;
    for(int i=0;i<n;i++)
    {
        int x;cin>>x;a[i]=nct;
        nct+=x;
    }
    while(m--)
    {
        int x;cin>>x;
        cout<<upper_bound(a,a+n,x)-a<<endl;
    }
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

2.小朋友崇拜圈 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,t,f[N],a[N],max1=0;
void dfs(int x,int y)
{
  if(f[x])
  {
    if(a[x]==a[t])
    {
      if(max1<y){max1=y;}
    }
    return ;
  }
  else
  {
    f[x]=1;
    dfs(a[x],y+1);
    f[x]=0;
  }
}
void solve()
{
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<=n;i++)
  {
    t=i;
    dfs(i,0);
  }
  cout<<max1;
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

6.玩具蛇 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int fk[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int fl[5][5];int nct=0;
void dfs(int x,int y,int len)
{
  if(x<1||y<1||x>4||y>4){return ;}
  if(fl[x][y]){return ;}
  if(len==16){nct++;return ;}
  fl[x][y]=1;
  for(int xx=0;xx<4;xx++)
  {
    dfs(x+fk[xx][0],y+fk[xx][1],len+1);
  }
  fl[x][y]=0;
}
void solve()
{
	for(int i=1;i<=4;i++)
  {
    for(int j=1;j<=4;j++)
    {
      dfs(i,j,1);
    }
  }
  cout<<nct;
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

7.最大数字 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf=0x3f3f3f3f3f3f3f3f;
string s;int a,b;int nct=0;
void dfs(int x,int y)
{
	int fk=s[x]-'0';
	if(s[x])
	{
		int c=min(a,9-fk);
		a-=c;
		dfs(x+1,y*10+fk+c);
		a+=c;
		if(b>fk)
		{
			b=b-fk-1;
			dfs(x+1,y*10+9);
      b=b+fk+1;
		}
	}
	else
	{
		nct=max(nct,y);
	}
}
void solve()
{
	cin>>s>>a>>b;
	dfs(0,0);
	cout<<nct;
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}