A. Reverse a Substring
题意：
给你一串 s，让你判断能否通过反转区间[l,r]的元素，使得反转后的串的字典序小于 s；
如果能，输出 "YES"，并输出任意的 l,r，并不需要所输出的 l,r 是所有满足条件的 l',r' 中的字典序最小的；
反之，输出"NO"；
例如，如果串 s = "abaa"
你可以反转[2,3]得到 "aaba"
也可以反转[2,4]得到字典序更小的 "aaab"
输出其中一个答案即可；
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define INFull ~0ULL
#define ll long long
#define ull unsigned long long
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=3e5+; int n;
char s[maxn]; void Solve()
{
int len=strlen(s+);
int ans=len+;
for(int i=;i <= len;++i)
if(s[i] < s[i-])//求出第一个下降的位置
{
ans=i;
break;
}
if(ans == len+)//如果没找到下降的位置
printf("NO\n");
else
{
printf("YES\n");
printf("%d %d\n",ans-,ans);//反转区间[ans-1,ans]
}
}
int main()
{
// freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);
scanf("%d",&n);
scanf("%s",s+);
Solve();
return ;
}
思考：
如果题干改为求反转区间[l,r]使得得到的串的字典序最小呢？
该怎么求呢？
B. Game with Telephone Numbers
题意：
给出你一个包含 n 个数字的串 s（n为奇数）；
Vasya 和 Petya 个从中选取 (n-11)/2 个数字，删去，游戏从Vasya开始；
问 Vasya 能否必胜，必胜的条件是，删除后的串，s[0]='8'；
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define INFull ~0ULL
#define ll long long
#define ull unsigned long long
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=3e5+; int n;
char s[maxn]; char* Solve()
{
int len=strlen(s);
int need=(n-)/;//每人需要删除need元素
int tot8=;//s中'8'的总个数 for(int i=;i < len;++i)
if(s[i] == '')
tot8++;
if(tot8 <= need)//8的个数小于等于删除的个数
return "NO"; //最坏的情况是，Petya删除need个8
//那么，Vasya就需要将第need+1个8前的其他数字都删去
int tot=;//第need+1个8前的非'8'得个数
int cur=need+;
for(int i=;cur > && i < len;++i)
{
if(s[i] != '')
tot++;
else
cur--;
}
if(tot <= need)//可以删除这tot个非'8'数
return "YES";
else
return "NO";
}
int main()
{
// freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);
scanf("%d",&n);
scanf("%s",s);
printf("%s\n",Solve());
return ;
}
C. Alarm Clocks Everywhere
题意：
Ivan 在睡觉前定了闹铃；
闹铃在 a 时刻开始出声，每隔 b 时刻响一次；
Ivan 需要闹铃在 x,x,....,x 时刻提醒他；
给出你 x,x,....,x 和闹铃的间隔时刻 p,p,....,p；
假设闹钟在 a 开始出声，能否在给出的时间间隔内使闹钟响的时刻满足Ivan的需求；
如果能，输出开始出声的时刻a和时间间隔对应在在p中的下标；
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define INFull ~0ULL
#define ll long long
#define ull unsigned long long
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=3e5+; int n,m;
ll x[maxn];
ll p[maxn]; ll GCD(ll a,ll b)
{
return a == ? b:GCD(b%a,a);
} char* Solve()
{
ll gcd=x[]-x[];
for(int i=;i <= n;++i)
gcd=GCD(gcd,x[i]-x[i-]);//求所有时间间隔的GCD
int ans=;
for(int i=;i <= m;++i)
if(gcd%p[i] == )//如果找到gcd的因子
{
ans=i;
break;
}
if(ans == )
printf("NO\n");
else
{
printf("YES\n");
printf("%I64d %d\n",x[],ans);//从x[1]时刻开始，每隔p[ans]时刻提醒一次可以满足条件
}
}
int main()
{
// freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);
scanf("%d%d",&n,&m);
for(int i=;i <= n;++i)
scanf("%lld",x+i);
for(int i=;i <= m;++i)
scanf("%lld",p+i);
Solve();
return ;
}