目录

A - Omkar and Password

B - Omkar and Infinity Clock

C - Omkar and Waterslide

D - Omkar and Bed Wars

A - Omkar and Password

 给一个序列，每次操作可以合并两个相邻但不相等的数，问最终能把序列的长度合并到最短是多少；

如果存在两个相邻的数不相等，那么就能把序列合并为长度为1，否则就是n

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int a[N];
int main()
{int t;cin >>t;while(t--){int n;cin >>n;int f=0;for(int i=1;i<=n;i++) cin >>a[i];for(int i=1;i<=n;i++) if(i>1&&a[i]!=a[i-1]){f=1;break;}if(f) puts("1");else printf("%d\n",n);}
}

B - Omkar and Infinity Clock

 规律题，看到k那么大，肯定有规律，模拟一组数据就能看出来了，循环周期为2，判断k的奇偶负即可；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+7;
int a[N];
int main()
{int t;cin >>t;while(t--){ll n ,k;cin >>n>>k;int maxx=-0x3f3f3f3f;for(int i=0;i<n;i++) cin >>a[i],maxx=max(a[i],maxx);int temp=-0x3f3f3f3f;for(int i=0;i<n;i++) a[i]=maxx-a[i],temp=max(a[i],temp);if(k&1) for(int i=0;i<n;i++) printf("%d%c",a[i],i==n-1?'\n':' ');else for(int i=0;i<n;i++) a[i]=temp-a[i],printf("%d%c",a[i],i==n-1?'\n':' ');}
}

C - Omkar and Waterslide

 思路就是 序列中的每一个凹点都要变成和他距离最近的凸点一样高，并且凹点要在凸点的右侧，相当于存在  a[i] <a[i-1] 的话，加上两者的差即可；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+7;
int a[N];
int main()
{int t;cin >>t;while(t--){int n;cin >>n;ll sum=0;for(int i=0;i<n;i++) cin >>a[i],sum+=i>0&&a[i]<a[i-1]?a[i-1]-a[i]:0;cout <<sum<<endl;}
}

D - Omkar and Bed Wars

是个假DP（当然网上有大佬用五维DP，也有可能正解就是DP，极其复杂。。） 

 想了一个思路，假设以下几种情况：

• ......RRR......   需要操作1次
• ......RRRR.....    1次
• .....RRRRR.....   1次
• ......RRRRRR.....    2次

也就是连续的片段需要操作的次数就是：    长度 / 3 

 所以，现预处理字符串的所有连续片段的长度并且记录，对于首部和尾部片段如果相同，可以叠加到尾部；然后计算即可；

（对于字符串全是一种字符的情况： RRRRRRRRRR或者LLLLLLLLL，那么答案是   1 + (len-1) / 3 ）;

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+7;int a[N];
int main()
{int t;cin >>t;while(t--){string s;int n;cin >>n;cin >>s;//cout <<s<<endl;int res=0,cnt=1;for(int i=1;i<n;i++){if(s[i]==s[i-1]) cnt++;else{a[++res]=cnt;cnt=1;}}a[++res]=cnt;ll ans=0;if(res>1) {if(s[0]==s[n-1]) a[res]+=a[1],a[1]=0;for(int j=1;j<=res;j++) ans+=a[j]/3;}
//		else ans+=a[1]>=3&&a[1]%3==2? a[1]/3+1:a[1]/3;else ans+=1+(a[1]-1)/3;cout <<ans<<endl;}
}