CF 传送门

T1：Reverse a Substring

只有本身单调不减的字符串不能转换为字典序更小的字符串。否则肯定会出现 \(s_i>s_{i+1}\) 的情况。

所以只要从头到尾扫一遍，找到 \(s_i>s_{i+1}\) 的位置，输出 \(i+1\) 与 \(i+2\) 即可（从 \(0\) 开始）。

Code：

#include<bits/stdc++.h>
using namespace std;
string s;
int n;
int main(){
	scanf("%d",&n);
	cin>>s;
	for(int i=0;i<s.size()-1;i++){
		if(s[i]>s[i+1]){
			printf("YES\n");
			printf("%d %d",i+1,i+2);
			return 0;
		}
	}
	printf("NO");
    return 0;
}

\(3min\) 速切

T2：Game with Telephone Numbers

洛谷上是蓝题，感觉虚高

首先得知 Vasya 应该删掉靠前的 \(8\)，而 Petya应该删掉靠前的但不是 \(8\) 的数字（比如样例1中的 \(3\)），这样才能让剩余的 \(8\) 往前靠。

所以只需要处理前面的 \(s.size()-11+1\) 位即可（虽然只删到 \(s.size()-11\) 为止，但如果剩下第一位刚好是 \(8\) 也可以，如样例1，所以多判一位）。若 \(8\) 比非 \(8\) 多，则 Petya 必胜。

Code：

#include<bits/stdc++.h>
using namespace std;
string s;
int n,cnt;
int main(){
	scanf("%d",&n);
	cin>>s;
	for(int i=0;i<s.size()-10;i++){
		if(s[i]=='8') cnt++;
		else cnt--;
	}
	if(cnt>0) printf("YES");
	else printf("NO");
    return 0;
}

\(12min\) \(AC\)

T3：Alarm Clocks Everywhere

首先容易想到，要使闹钟在 \(x_1,x_2,x_3...x_n\) 分钟都响一次，其时间间隔必须是所有 \(x_i-x_{i-1}\) $(1<i \le n) $ 的公因数。开始时间设为 \(x_1\) 即可。

所以只要先求出所有 \(x_i-x_{i-1}\) $(1<i \le n) $ 的最大公因数，再判断其是否能整除 \(p_i\) 即可。若可以整除，则答案就是 \(x_1\)，\(i\)。

注意要开 \(long long\)

Code：

#include<bits/stdc++.h>
using namespace std;
long long n,m,jg,a[300005],p;
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		if(i>1){
			jg=__gcd(jg,a[i]-a[i-1]);
		}
	}
	for(int i=1;i<=m;i++){
		scanf("%lld",&p);
		if(jg%p==0){
			printf("YES\n");
			printf("%lld %d",a[1],i);
			return 0;
		}
	}
	printf("NO");
    return 0;
}

\(20min\) \(AC\)

T4：Beautiful Array

定义 \(f[0/1/2][i]\) 表示当前在第 \(i\) 位，\(0\) 代表还没用过 \(\times x\)，\(1\) 代表正在用 \(\times x\)，\(2\) 代表 \(\times x\) 已经用过了。

得出三个转移方程：

• \(f[0][i]=\max(f[0][i-1]+a[i],\max(a[i],0))\)
• \(f[1][i]=\max(\max(f[0][i-1],f[1][i-1])+a[i]*x,\max(a[i]*x,0))\)
• \(f[2][i]=\max(\max(f[0][i-1],\max(f[1][i-1],f[2][i-1]))+a[i],\max(a[i],0))\)

因为每次产生的都可能是最优答案，所以每次处理完 \(ans\) 取 \(\max\) 即可。

注意要开 \(long long\)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,x,f[3][300005],a[300005],tmp,ans;
int main(){
	scanf("%lld%lld",&n,&x);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		
		tmp=f[0][i-1]+a[i];
		f[0][i]=max(tmp,max(a[i],0ll));
		ans=max(ans,f[0][i]);
		
		tmp=max(f[0][i-1],f[1][i-1])+a[i]*x;
		f[1][i]=max(tmp,max(a[i]*x,0ll));
		ans=max(ans,f[1][i]);
		
		tmp=max(f[0][i-1],max(f[1][i-1],f[2][i-1]))+a[i];
		f[2][i]=max(tmp,max(a[i],0ll));
		ans=max(ans,f[2][i]);
	}
	printf("%lld",ans);
    return 0;
}

\(1h\) \(03min\) \(AC\) \(qwq\)

T5：Guess the Root

施工中 \(qwq\)

下午学了拉格朗日插值，或者求多项式的高斯消元再来写。

T6：Delivery Oligopoly

黑题，告辞 \(qwq\)