By

算法+牙痛

没有记单词，又堕落了一天。

下午看了看中科大的校赛，只做得出一题。

P12035 Hackergame

题意：在一个字符串中找到合法字符串并输出。

题解：用数组存储下左括号和右括号的位置，便于等会二分迅速找到最近的右括号和左括号。然后使用 find()函数一直查找就行。我开始还担心二分能不能过，感觉双指针也可以。

#include<bits/stdc++.h>
using namespace std;
int n,x,ans,xl,xr;
vector<int> l,r;
string s,str;
int main(){
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='}') r.push_back(i);
		if(s[i]=='{') l.push_back(i);
	}
	if(r.size()==0||l.size()==0) goto L;
	x=s.find("flag{");
	while(x!=-1){
		int m=upper_bound(r.begin(),r.end(),x)-r.begin();
		if(m!=r.size()){
			int tmp=upper_bound(l.begin(),l.end(),x+4)-l.begin();
			if(l[tmp]>r[m]||tmp==l.size()){
				str=s.substr(x,r[m]-x+1);
				cout<<str;
				return 0;
			}
		}
		x=s.find("flag{",x+1);
	}
	L:
	cout<<"NOT FOUND";
	return 0;
}

P12037 数学分析

这第四题题就是算一个积分，但我数学没学好……题解说是个大学生都能做出来

image-20250406173810305

P12036 摩拉

这第三题就是一个斐波那契数列变种，下面是题解的两种方法。

晚上水了水蓝桥杯的第28场 蓝桥入门赛

第三题蓝桥速算

题意：给定一个长度为 $N$ 的数组 $A$ ，其中第 $i$ 个数字为 $A_i$。然后进行Q次操作，每次操作给两个数字 $L,R$ ，表示对 $A_i(L<=i<=R)$中 的数字进行操作。

  • $A_L$ 增加 $L$
  • $A_{L+1}$ 减少 $L+1$
  • $A_{L+2}$ 增加 $L+2$
  • 以此类推，直到 $R$

问最终数组之和。

题解：只需要看$L$和$R$的值就行，然后可以发现是个数学加减法。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read();
int n,q;
ll sum,x;
int main(){
    cin>>n>>q;
    while(n--){
        x=read();
        sum+=x;
    } 
    while(q--){
        ll l,r,x;
        l=read(),r=read();
        x=r-l;
        if(x%2==0){
            sum+=l;
            if(x) sum+=x/2;
        }else sum-=(x+1)/2;
    }
    cout<<sum;
    return 0;
}

第四题浓缩咖啡液

题意：有N种饮料，有各自的浓度，每种饮料无限，能否混合出浓度为 $M\%$的饮料。

题解：我们首先知道混合后怎样变化，$a$浓度和$b$浓度各取一杯混合后为$(a+b)/2$的浓度，杯数不一样混合后浓度也不一样。又是数学题，所有饮料不论怎么混合，混合后浓度都会大于等于最小浓度，且小于等于最大值，因为饮料无限，中间任何浓度都可以到达。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read();
int n,m,a[1010];
void solve(){
	int mi=100,mm=0;
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		mi=min(mi,a[i]),mm=max(mm,a[i]);
	}
	if(m>=mi&&m<=mm) cout<<"YES\n";
	else cout<<"NO\n";
}
int main(){
	int t;t=read();
	while(t--) solve();
	return 0;
}

第五题破译密码

题意：N个任务，每个任务都有完成时间和发送时间，两人一人负责完成一人负责发送，互不影响，但同一任务必须完成后才能发送。问所有任务完成且发送的最短时间。

题解：贪心，按照min(a1.完成, a2.发送) < min(a2.完成, a1.发送)排序即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct t{
	ll l,r;
}a[1010];
bool cmp(t a1,t a2){
  return min(a1.l, a2.r) < min(a2.l, a1.r);
}
ll n,ans,sum;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].l;
	for(int i=1;i<=n;i++) cin>>a[i].r;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		sum+=a[i].l;
		if(sum>=ans) ans=sum+a[i].r;
		else ans=ans+a[i].r;
	}
	cout<<ans<<"\n";
	return 0;
}

第六题插入数字

题意：给定一个正整数 N，如果在 N 的开头、结尾，或者任意两个相邻数字之间插入一个数字（0∼9），可以得到多少种不同的新数字？插入后的数字不能以 0 开头。

题解：直接循环插入，然后放入map。

#include <bits/stdc++.h>
using namespace std;
string s, str;
map<string,bool> mp;
int solve() {
	int l = s.size();
	for (int d = 1; d <= 9; ++d) {
		str = (char)(d + '0') + s;
		mp[str]=1;
	}
	for (int pos = 1; pos < l; ++pos) {
		for (int d = 0; d <= 9; ++d) {
			str = s.substr(0, pos) + (char)(d + '0') + s.substr(pos);
			mp[str]=1;
		}
	}
	for (int d = 0; d <= 9; ++d) {
		str = s + (char)(d + '0');
		mp[str]=1;
	}
	return mp.size();
}
int main() {
	cin >> s;
	cout << solve() << endl;
	return 0;
}