传送门
题意
A.询问改变一个字符是否能使字符串变成回文串
B.将字符串首字符放到尾部称为一次操作
给出n个字符串，询问使n个字符串变成相同字符串的 最少操作次数
C.给出A序列，(a_i,a_{i+1}->a_i-a_{i+1}，a_i+a_{i+1})称为一次操作
询问使得序列gcd>1的最少操作次数，不能输出-1
D.给出序列a,b，选出最多n/2+1个数，满足选出的数的2倍大于等于原序列数之和
分析
A.(O(n/2))扫一遍统计不同字符数，注意a,abcba都满足A题意
B.直接$O(len^3n)暴力，注意细节
C.我们发现对于x,y
x,y都为奇，一次操作后x,y为偶
x,y其中一个为奇，两次操作后x,y为偶
那么我们先扫一遍判断是否有gcd>1，没有扫一遍处理相邻数都为奇的，再扫一遍处理相邻数为一奇一偶，证明见此
D.构造方法如下：
1.将A数组排序
2.记录第一个坐标，再每次看b[a[2i].loc],b[a[2i+1].loc]，如果b[a[2i].loc]>b[a[2i+1].loc],p[i+1]=a[2i].loc;否则p[i+1]=a[2i+1].loc
3.如果n为偶，再把最后一个添加进去
我们只证奇个数情况，b数组肯定满足性质，我们看a数组
除去第一个，我们选了n/2个数，可能选择的数都比未选的数都小，不妨记dex=a[2i]-a[2*i+1]，因为数都是正的，故n/2个dex之和必定小于a[1]，请读者好好想一想，所以我们能保证a数组满足性质
trick
代码
只给出C和D的代码
C
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define F(i,a,b) for(int i=a;i<=b;++i)
#define mem(a,b) memset(a,b,sizeof(a))
#pragma comment(linker, "/STACK:102400000,102400000")
int n;
ll a[100100],ret,cnt;
inline ll gcd(ll x,ll y) { return y==0?x:gcd(y,x%y); }
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lld",a+i);
ret=gcd(abs(a[1]),abs(a[2]));
for(int i=3;i<=n;++i) ret=gcd(ret,abs(a[i]));
if(ret>1) { puts("YES");puts("0");return 0; }
for(int i=1;i<n;++i)
{
ll x=abs(a[i]),y=abs(a[i+1]);
if((x&1)&&(y&1)) {cnt++;a[i]=a[i+1]=2;}
}
for(int i=1;i<n;++i)
{
ll x=abs(a[i]),y=abs(a[i+1]);
if(((x&1)&&(y%2==0))||((x%2==0)&&(y&1))) { cnt+=2;a[i]=a[i+1]=2; }
}
puts("YES");printf("%lld
",cnt);
return 0;
}
D
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,b[100100];
struct node
{
int loc,value;
bool operator<(const node &p)const
{
return value>p.value;
}
}a[100100];
int p[100100];
int cnt=0;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i) {scanf("%d",&a[i].value);a[i].loc=i;}
sort(a,a+n);
for(int i=0;i<n;++i) scanf("%d",b+i);
if(n%2==0)
{
p[cnt++]=a[0].loc;
for(int i=1;i<n-1;i+=2)
if(b[a[i].loc]>b[a[i+1].loc]) p[cnt++]=a[i].loc;else p[cnt++]=a[i+1].loc;
p[cnt++]=a[n-1].loc;
}
else
{
p[cnt++]=a[0].loc;
for(int i=1;i<n;i+=2)
if(b[a[i].loc]>b[a[i+1].loc]) p[cnt++]=a[i].loc;else p[cnt++]=a[i+1].loc;
//printf("p[i]=%d
",p[cnt-1]);
}
//for(int i=0;i<n;++i) printf("a[%d].loc=%d
",i,a[i].loc);
printf("%d
",cnt);
for(int i=0;i<cnt;++i) printf("%d%c",p[i]+1,i==(cnt-1)?'
':' ');
}