2023年广东工业大学腾讯杯新生程序设计竞赛

E.不知道叫什么名字

题意：找一段连续的区间，使得区间和为0且区间长度最大，输出区间长度。
思路：考虑前缀和，然后使用map去记录每个前缀和第一次出现的位置，然后对数组进行扫描即可。原理：若$s[i]=x$,则，$map[x]=i$,当后续出现$s[j]=x$时，$s[j]?s[i]=0$,则合法的区间长度为$j?i$。
将此题一般化为，找一段连续的区间，使得区间和为 k 且长度最大，输出区间长度，我们同样使用这个方法，去记录前缀和，然后对数组进行扫码即可，对于前缀和$s[j]$而言，因为$s[j]?(s[j]?k)=k$,所以需要定位到$s[j]?k$第一次出现的位置即可。

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
// const int maxv = 4e6 + 5;
// #define endl "\n"



void solve()
{
	int n;
	cin>>n;
	vector<int> a(n+5),s(n+5);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		s[i]=s[i-1]+((a[i]==1)?1:-1);
	}
	map<int,int> mp;
    mp[0]=0;
	for(int i=1;i<=n;i++){
		if(!mp.count(s[i])) mp[s[i]]=i;
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		int x=s[i];
		ans=max(ans,i-mp[x]);
	}
	cout<<ans<<endl;


}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
// 	cin>>t;
	while(t--){
		solve();
	}
   	system("pause");
    return 0;
}

G.闪闪发光心动不已！

题意：找到包含kira…doki的最长子序列。
思路：运用前后缀的思想，对字符串正向扫描一遍，然后逆向扫描一遍，对于位置i而言，其最大长度为其前面的kira子序列+其后面doki的子序列。

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> ar;
int mod = 1e9+7;
// const int maxv = 4e6 + 5;
#define endl "\n"

void solve()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    s=" "+s;
    vector<int> pre(n+5),suf(n+5);
    int tot=0;
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1];
        if(tot==0&&s[i]=='k') tot++;
        else if(tot==1&&s[i]=='i') tot++;
        else if(tot==2&&s[i]=='r') tot++;
        else if(tot==3&&s[i]=='a') tot++;
        if(tot==4) pre[i]+=4,tot=0;
    }
//     for(int i=1;i<=n;i++) cout<<pre[i]<<" ";
    tot=0;
    for(int i=n;i>=1;i--){
        suf[i]=suf[i+1];
        if(tot==0&&s[i]=='i') tot++;
        else if(tot==1&&s[i]=='k') tot++;
        else if(tot==2&&s[i]=='o') tot++;
        else if(tot==3&&s[i]=='d') tot++;
        if(tot==4) suf[i]+=4,tot=0;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(pre[i]&&suf[i+1]) ans=max(ans,pre[i]+suf[i+1]);
    }
    cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
// 	cin>>t;
	while(t--){
		solve();
	}
   	system("pause");
    return 0;
}

I.uu爱玩飞行棋

题意：距离终点m米，然后给定n个操作，每次可以走x步，若不能直接到达终点则需返回多余的步数，问走到终点的最小操作。
思路：考虑背包，设计状态$dp[i][j]$，表示对于前$i$个操作，还剩$j$步的最小操作数量。

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
// const int maxv = 4e6 + 5;
// #define endl "\n"

int dp[2010][2010];

void solve()
{
	int n,m;
	cin>>n>>m;
	vector<int> a(m+5);
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	memset(dp,0x3f,sizeof dp);
	dp[0][n]=0;
	for(int i=1;i<=m;i++){
		for(int j=0;j<=n+5;j++){
                dp[i][j]=min(dp[i-1][j],dp[i-1][j+a[i]]+1);//当前状态由j+a[i]转移而来
                if(j<a[i])dp[i][j]=min(dp[i-1][j],dp[i-1][a[i]-j]+1);//表示反弹的状态
            }
	}
	if(dp[m][0]>1e9/2) cout<<-1<<endl;
	else cout<<dp[m][0]<<endl;


}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
// 	cin>>t;
	while(t--){
		solve();
	}
   	system("pause");
    return 0;
}

J.火柴人小游戏

思路：很容易想到二分，需要思考如何进行check，我们同样容易发现，我们可以贪心去选择战斗力较小的且能到达的点，所以我们无论我们初始的战斗力如何，我们的战斗顺序都是固定的，显然，普通的队列并不能满足我们的贪心需求，我们使用优先队列去生成我们的路径即可，然后每次就可以在线性时间复杂度内check完成。

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> ar;
int mod = 1e9+7;
// const int maxv = 4e6 + 5;
// #define endl "\n"

int n,m,x,y;
ll a[1005][1005];

vector<ll> p;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int st[1005][1005];
void bfs()
{
	priority_queue<ar,vector<ar>,greater<ar> > q;
	int eg=a[x][y];
	q.push({eg,x,y});
	st[x][y]=1;
	//p.push_back(a[x][y]);
	while(!q.empty()){
		auto [z,nx,ny]=q.top();
        //cout<<z<<" "<<nx<<" "<<ny<<endl;
        p.push_back(z);
		q.pop();
		for(int i=0;i<4;i++){
			int zx=dx[i]+nx,zy=dy[i]+ny;
			if(zx<1||zx>n||zy<1||zy>m) continue;
			if(st[zx][zy]) continue;
			//p.push_back(z);
            st[zx][zy]=1;
			q.push({a[zx][zy],zx,zy});
		}
	}
}

bool check(ll x)
{
	ll now=x;
//     if(x<p[0]) return false;
	for(int i=1;i<p.size();i++){
		if(p[i]>now) return false;
		now+=p[i];
	}
	return true;
}

void solve()
{
	cin>>n>>m>>x>>y;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	bfs();
	ll l=a[x][y],r=1e18,ans=-1;
	while(l<=r){
		ll mid=(l+r)/2;
		if(check(mid)){
			r=mid-1;
			ans=mid;
		}
		else{
			l=mid+1;
		}
	}
//     for(auto x: p) cout<<x<<" ";
    
	if(ans==a[x][y]) cout<<"No cheating need."<<endl;
	else cout<<ans<<endl;


}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
// 	cin>>t;
	while(t--){
		solve();
	}
   	system("pause");
    return 0;
}