D6题解

题解

T1

考虑相邻元素的大小关系，是递增的。
如果相邻的两个不对判一下。
比较糟的是一个大的后面连上一个递增的，特判一下即可。
也可以直接判断删除一个元素之后是否有序

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int a[1000005];
bool check(int pos){//判断删除一个后是否有序
    for(int i=1;i<n;i++){
        if(i == pos || i+1 == pos) continue;
        if(a[i]>a[i+1]) return 0;
    }
    if(pos >=2 && pos<n&& a[pos-1] > a[pos+1]) return 0;
    return 1;
}
int main(){
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    bool no = 0;
    for(int i=1;i<n;i++){
        if(a[i]>a[i+1]){
            if( check(i) || check(i+1) ){
                break;
            }else{
                no = 1;
                break;
            }
        }
    }
    if(no) puts("NO");
    else puts("YES");
    return 0;
}

T2

解同余方程组
30%
用昨天的公式，
60%
用昨天的公式，exgcd求逆元
100%
需要合并
$x+k_1a_1=b_1,x+k_2a_2=b_2$
联立，$k_1a_1-k_2a_2=b_1-b_2$
然后exgcd(a1,-a2,k1,k2)
解出来x,y后解出k1k2使之成立
而这个x就是同时满足上面两个式子的东西
合并之后可以得到 x%(a1a2)=x0
标程：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <cmath>
using namespace std;
typedef long long LL;
int a[4],b[4];
LL A,B;
LL gcd(LL a,LL b){
    return b==0?a:gcd(b,a%b);
}
LL lcm(LL a,LL b){
    return a/gcd(a,b)*b;
}
LL exgcd(LL a,LL b,LL &x,LL &y){
    LL t;
    if(!b) {x=1;y=0;return a;}
    t=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return t;
}
LL mulmod(LL a,LL b,LL p){
    LL ret = 0;
    while(b){
        if(b&1) ret=(ret+a)%p;
        b>>=1;
        a=(a+a)%p;
    }
    return ret;
}
void merge(LL a,LL b){
    LL k1,k2;
    LL g = exgcd(A,-a,k1,k2);
    LL M = lcm(A,a);
    // assert(abs((B-b)/g*1.*k1)<=1e18);
    k1 = mulmod((B-b)/g,k1,M);
    // assert(abs(k1*1.*A)<=1e18);
    LL x = B-mulmod(k1,A,M);
    // printf("# %.3f\n",k1*1.*A);
    // assert(x+k1*A == B);
    // assert(x+(B-b)/g*k2*a == b);
    // printf("# %lld %lld %lld %lld\n",x,k1,A,B);
    assert(((x%A)+A)%A == B);
    x = ((x%M)+M)%M;
    assert(x%A == B);
    assert(x%a == b);
    A=M;
    B=x;
}
int main(){
    freopen("mod.in","r",stdin);
    freopen("mod.out","w",stdout);
    for(int i=0;i<4;i++) scanf("%d%d",&a[i],&b[i]);
    A=1,B=0;
    for(int i=0;i<4;i++){
        merge(a[i],b[i]);
    }
    // printf("# %lld\n",A);
    printf("%lld\n",B);
    return 0;
}

顺便推销一波神奇的大数翻倍法

T3

回文串长度是可以二分的。
首先预处理，奇数以某一个字符为中心，偶数以某一个空隙为中心。
本质不同的回文串最多有O(n)个，通过hash记下答案可以求出来包含多少回文串。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
char s[10005];
ULL h[10005],rh[10005],pw[10005];
int L;
ULL hs(int l,int r){
    return h[r]-h[l-1]*pw[r-l+1];
}
ULL rhs(int l,int r){
    return rh[l] - rh[r+1]*pw[r-l+1];
}
struct N{
    int a[26];
    bool ok(){
        int b[26];
        for(int i=0;i<26;i++) b[i]=a[i];
        sort(b,b+26);
        for(int i=0;i<25;i++){
            if(b[i]>0&& b[i] == b[i+1]) return true;
        }
        return false;
    }
    void clear(){
        memset(a,0,sizeof a);
    }
};
LL ans=0;
map<ULL,LL> num;
map<ULL,N> A;
//奇数 
void solve_odd(){//二分判断是否出便捷，判断标准为正反读是否一样 
    for(int i=1;i<=L;i++){
        int l = 1,r = min(i,L-i+1)+1;
        while(r-l>1){
            int mid = (l+r)/2;
            if(hs(i-mid+1,i+mid-1)== rhs(i-mid+1,i+mid-1)) l=mid;
            else r=mid;
        }
        int p=l;
        int tmp = p;
        while(tmp>=1&&num.find(hs(i-tmp+1,i+tmp-1))==num.end()) tmp--;
        //两边删直到取出算过的东西为止 ，hash判断 
        LL sum = 0;
        N st;
        st.clear();
        if(tmp>=1){
            sum=num[hs(i-tmp+1,i+tmp-1)];
            st = A[hs(i-tmp+1,i+tmp-1)];
        }
        while(tmp<p){
            st.a[s[i+tmp]-'a']+= (tmp == 0?1:2);
            if(st.ok()) sum++;
            num[hs(i-tmp,i+tmp)] = sum;
            A[hs(i-tmp,i+tmp)] = st;
            tmp++;
        }
        ans+=sum;
        // printf("# %d %lld\n",i,sum);
    }
}
//偶数 
void solve_even(){
    A.clear();
    num.clear();
    for(int i=1;i<L;i++){
        // printf("### %d\n",i);
        int l = 1,r = min(i,L-i)+1;
        while(r-l>1){
            int mid = (l+r)/2;
            if(hs(i-mid+1,i+mid)== rhs(i-mid+1,i+mid)) l=mid;
            else r=mid;
        }
        int p=l;
        int tmp = p;
        while(tmp>=1&&num.find(hs(i-tmp+1,i+tmp))==num.end()) tmp--;
        LL sum = 0;
        N st;
        st.clear();
        // printf("## %d\n",p);
        if(tmp>=1){
            sum=num[hs(i-tmp+1,i+tmp)];
            st = A[hs(i-tmp+1,i+tmp)];
        }
        while(tmp<p){
            // printf("# %d %lld\n",tmp,sum);
            st.a[s[i+tmp+1]-'a']+= 2;
            if(st.ok()) sum++;
            num[hs(i-tmp,i+tmp+1)] = sum;
            A[hs(i-tmp,i+tmp+1)] = st;
            tmp++;
        }
        ans+=sum;
        // printf("# %d %lld\n",i,sum);
    }
}
int main(){
    freopen("str.in","r",stdin);
    freopen("str.out","w",stdout);
    scanf("%s",s+1);
    L=strlen(s+1);
    s[0]='#';
    pw[0]=1;
    for(int i=1;i<=L;i++) pw[i] = pw[i-1]*13131 ;
    for(int i=1;i<=L;i++) h[i] = h[i-1]*13131 + s[i];//正着求hash
    for(int i=L;i>=1;i--) rh[i] = rh[i+1]*13131 + s[i];//反着求 
    solve_odd();
    solve_even();
    printf("%lld\n",ans);
    fclose(stdout);
    return 0;
}

```