C.Constructive Problems Never Die

题意：
给出一个长度为n的序列A,Ai<=n。
请找出一个排列P使得对于所有得i，Pi!=Ai。
如果可以，就输出YES并输出这个排列。
否则，就输出NO。

思路：
输入的是a数组，先预处理出b排列,b[i]=i。
当i<n时，如果a[i]=b[i],就交换b[i]和b[i+1]。
前面的都已经处理成满足要求的啦，
接下来考虑b[n]。
如果b[n]==a[n]，
就找前面的b[i]和b[n]交换，
如果能实现b[n]!=a[n]&&交换的那个a[i]!=b[i],
就表示能行，退出循环。
如果不行，就恢复到原来的样子。
如果遍历完前面的都不能找到可行的，
就输出NO。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,a[N],b[N];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) {
			scanf("%d",&a[i]);
			b[i]=i;
		}
		for(int i=1;i<n;i++){
			if(a[i]==b[i]){
				swap(b[i],b[i+1]);
			}
		}
		bool f=0;
		if(a[n]==b[n]){
			f=1;
			for(int i=1;i<n;i++){
				swap(b[i],b[n]);//先交换
				//如果能行，直接break 
				if(a[i]!=b[i]&&a[n]!=b[n]){
					f=0;
					break;
				}
				//如果不行，那就恢复到原来的，这样就不会破坏原有的已经满足条件的。 
				else swap(b[i],b[n]);
			}
		}
		if(f) puts("NO");
		else{
			puts("YES");
			for(int i=1;i<=n;i++) printf("%d ",b[i]);
			puts("");
		}
	}
	return 0;
}

F.Candies

题意：
给出一串环形数字，每次可以选择相邻相等数字或者相加=x的数字
并将它们消除并得到一个糖果，问最多得到多少个糖果。

思路：
双指针。
首先，边输入边处理输入时就满足消除的糖果，
每次消除之后ans++,j–。
不满足就j++,当j==0时因为不能实现j-1，
所以只能j++。
因为是环形的，因此最后面输入的可能会和最前面
输入的消除，因此最后用双指针，
处理最前面和最后面的。
最前面i=0,最后面j–。
因为每次输入之后都会到已有的最后一个数字
的下一个数字，因此需要j–先回退到最后一个数字。

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
int n,x,ans,i,j;

int main(){
	scanf("%d%d",&n,&x);
	for(i=0;i<n;i++){
		scanf("%d",&a[j]);
		if(j>0){
			if(a[j]==a[j-1]||a[j]+a[j-1]==x){
				ans++;
				j--;
			}
			else j++;
		}
		else j++; 
	} 
	i=0;
	j--;
	while(j>i&&(a[j]==a[i]||a[j]+a[i]==x)){
		j--;
		i++;
		ans++;
	}
	printf("%d\n",ans);
	return 0;
}

G.Regular Expression

题意：
给出q次询问，每次询问给出一个由小写字母组成的字符串。
请输出此字符串匹配的最短正则表达式的长度以及个数。

思路：
分析了给出的例子和用测试网站测之后，
了解到只有用 . * +才能缩短字符串长度。
.可以用在任意位置，表示一个任意字母，*和+都不能用在第一个位置，
*表示复制前面的一个字母任意多次（可为0次），+表示在后面添加任意长度（>1）的任意字符串。
那么可以每个正则表达式只能以字母或者.开头。

（1）当字符串长度为1时，
匹配的是它本身和 .
（2）当字符串长度为2时，
1>字符串所有字符相同，比如aa
那么匹配的情况有：
以字母a开头的：
aa
a+
a*
a.
以.开头的：
…
.+
.*
.a
共8种。
2>不是所有字符相同：如ab
ab
a+
a.
…
.+
.b
（3）长度>=3时
我们发现.+一定可以匹配任意字符串。
因此长度>=3时最短长度一定为2。
1>当所有字母相同时，如aaa
以字母开头：
a+
a*
以点开头：
.+
.*
共四种。

2>不是所有字母相同：
那么就不能用到 表示复制的*
因此只有
a+
.+
共两种情况

至于题目所说的取模，纯纯吓唬人的！

代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
	int q;
	string s;
	scanf("%d",&q);
	while(q--){
		cin>>s;
		
		if(s.size()==1) puts("1 2");
		else{
			bool f=1;
			for(int i=1;i<s.size();i++){
				if(s[i]!=s[i-1]){
					f=0;
					break;
				}
			}
			if(f){
				if(s.size()==2) puts("2 8");
				else puts("2 4");
			}
			else {
				if(s.size()==2) puts("2 6");
				else puts("2 2");
			}
		}
	}
	return 0;
}