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

首先可以得知，十次多项式得知十一组 $i,j$ 就一定可以确定，所以和交互库进行十一次询问，再用高斯消元法求出多项式，最后暴力代入即可。

结果在 $mod(10^6+3)$ 下，除法就可以改成逆元。

——来自 $\color{red}{Fido\_Puppy}$ 巨佬的题解

如果某次交互给出的答案是 $0$，就可以直接输出。

Code：

#include<bits/stdc++.h>

#define ll long long

#define mod 1000003

using namespace std;

int y;

ll qpow(ll x,int p){

	ll ans=1;

	while(p) {

		if(p&1) ans=ans*x%mod;

		x=x*x%mod;

		p>>=1;

	}

	return ans;

};

int main() {

	vector< vector <ll> > a(20,vector <ll> (20));

	for(int i=1;i<=11;i++){

		cout<<"? "<<i-1<<endl;

		cin>>y;

		if(y==0){

			cout<<"! "<<i-1<<endl;

			return 0;

		}

		ll P=1ll;

		for(int j=1;j<=11;j++){

			a[i][j]=P;

			P=P*1ll*(i-1)%mod;

		}

		a[i][12]=y;

	}

	for(int i=1;i<=11;i++){

		for(int j=i+1;j<=12;j++){

			a[i][j]=a[i][j]*qpow(a[i][i],mod-2)%mod;

		}

		a[i][i]=1ll;

		for(int j=1;j<=11;j++){

			if(i!=j){

				for(int k=i+1;k<=12;k++){

					a[j][k]=(a[j][k]-a[j][i]*a[i][k]%mod+mod)%mod;

				}

				a[j][i]=0;

			}

		}

	}

	for(int i=0;i<mod;i++){

		ll sum=0,P=1ll;

		for(int j=1;j<=11;j++){

			sum=(sum+P*a[j][12])%mod;

			P=P*1ll*i%mod;

		}

		if(sum==0){

			cout<<"! "<<i<<endl;

			return 0;

		}

	}

	cout<<"! -1";

	return 0;

}

T6：Delivery Oligopoly

黑题，告辞 $qwq$

巴特西

【Virt.Contest】CF1155(div.2)

CF 传送门

T1：Reverse a Substring

T2：Game with Telephone Numbers

T3：Alarm Clocks Everywhere

T4：Beautiful Array

T5：Guess the Root

T6：Delivery Oligopoly

最新文章

热门文章