【Gym 100971K】Palindromization
Mihahim has a string s. He wants to delete exactly one character from it so that the resulting string would be a palindrome. Determine if he can do it, and if he can, what character should be deleted.
The input contains a string s of length (2 ≤ |s| ≤ 200000), consisting of lowercase Latin letters.
If the solution exists, output «YES» (without quotes) in the first line. Then in the second line output a single integer x — the number of the character that should be removed from s so that the resulting string would be a palindrome. The characters in the string are numbered from 1. If there are several possible solutions, output any of them.
If the solution doesn't exist, output «NO» (without quotes).
evertree
YES
2
emerald
NO
aa
YES
2
从左右两边往中间移动,如果相同,l++,r--,如果不同,第一次循环i==0时,则让l++,第二次循环则让r--,最后判断不同的出现了几次。如果dif是0,l>=r代表本身就是回文,则去掉l位置的字符。
#include <cstring> #include <cstdio> #define N 100005 char s[N<<1]; int len,l,r,dif,at; int main() { scanf("%s",s); len=strlen(s); for(int i=0;i<2;i++){ dif=0; l=0,r=len-1; while(l<r){ if(s[l]!=s[r]){ dif++; if(i){ at=r; r--; }else { at=l; l++; } } if(s[l]==s[r]){ l++; r--; } } if(l>=r&&dif==0)at=l; if(dif<2){ printf("YES\n%d\n",at+1); break; } } if(dif>1)puts("NO"); }
相关文章
- Gym 101201J Shopping (线段树+取模)
- Gym 100512F Funny Game (博弈+数论)
- UVaLive 6950 && Gym 100299K Digraphs (DFS找环或者是找最长链)
- Gym 100299C && UVaLive 6582 Magical GCD (暴力+数论)
- CodeForces Gym 100685J Just Another Disney Problem (STL,排序)
- Gym 100851A Adjustment Office (思维)
- CodeForces Gym 100685I Innovative Business (贪心)
- gym.ObservationWrapper使用时的注意点——reset和step函数可以覆盖observation函数
- openAI的仿真环境Gym Retro的Python API接口(续1)—— 游戏过程记录及回放
- NVIDIA公司推出的GPU运行环境下的机器人仿真环境(NVIDIA Isaac Gym)的安装——强化学习的仿真训练环境 (续2)
- NVIDIA公司推出的GPU运行环境下的机器人仿真环境(NVIDIA Isaac Gym)的安装——强化学习的仿真训练环境
- 【Gym - 100947G】Square Spiral Search
- 【Gym - 100812G 】Short Path (SPFA)
- 【 Gym 101116K 】Mixing Bowls(dfs)