T1
Sort 一下与原数组比较 ，若有两个数或者没有数发生位置交换 ，则输出YES ，否则输出NO
#include <algorithm>
#include <cctype>
#include <cstdio>
#define N 1005000
int n, cnt1, cnt2, sum;
struct node
{
int num, pos;
bool operator < (node a)const
{
if (num != a.num) return num < a.num;
else return pos < a.pos;
}
}a[N];
int main(int argc, char *argv[])
{
freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout);
scanf("%d", &n);
for (int i = ; i <= n; ++i) scanf("%d", &a[i].num), a[i].pos=i;
std :: sort(a + , a + n + );
for (int i = ; i <= n; ++i)
{
if (a[i].pos > i) cnt1++;
if (a[i].pos < i) cnt2++;
}
if (cnt1 == || cnt2 == || (!cnt2 && !cnt1)) puts("YES");
else puts("NO");
return ;
fclose(stdin); fclose(stdout);
}
T2
同余方程组
前60%的数据可以用中国剩余定理
后面的数据 用数学构造
X%a1=b1
X%a2=b2
....
X+k1a1=b1
X+k2a2=b2
相减得到 k1a1-k2a2=b1-b2
解这个方程，用exgcd(a1,-a2,k1,k2)
Ax+by=gcd(a,b)
Ax+by=c;
把k1k2回带到原式中，求出x
X0=b1-k1a1
X%a1a2=x0
#include<iostream>
#include<cstdio>
typedef long long LL;
using namespace std; LL n,m[],a[];
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if (b == )
{
x = , y = ;
return a;
}
LL r = exgcd(b, a % b, x, y);
LL tmp = x;
x = y;
y = tmp - a / b * y;
return r;
}
inline LL crt()
{
LL a1 = a[], a2, m2, d, c, m1=m[];
for (LL i = ; i <= ; ++i)
{
a2 = a[i], m2 = m[i];
c = a2 - a1;
LL x, y;
d = exgcd(m1, m2, x, y);
x = x * c / d;
int mod = m2 / d;
x = (mod + x % mod) % mod;
a1 += m1 * x;
m1 *= mod;
}
return a1;
}
int main(int argc, char *argv[])
{
freopen("mod.in", "r", stdin);
freopen("mod.out", "w", stdout);
for(int i = ; i <= ; i++) cin >> m[i] >> a[i];
cout << crt() << endl;
return ;
fclose(stdin); fclose(stdout);
}
T3
可以发现回文串是可以二分的
比如：bbbabcbaabcba 我们以第1个c为中心，发现回文半径是3，大于3一定不是回文串。当回文串长度为偶数的时候，我们需要特殊处理一下。
现在有一个结论：本质不同的回文串个数只有O(N)个
本质不同：字符串本身是不同的。
每一次处理完回文串，我们要把他的hash值记录下来。
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map> using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
char s[];
ULL h[], rh[], pw[];
int L;
ULL hs(int l, int r)
{
return h[r] - h[l - ] * pw[r - l + ];
}
ULL rhs(int l, int r)
{
return rh[l] - rh[r + ] * pw[r - l + ];
}
struct N
{
int a[];
bool ok()
{
int b[];
for (int i = ; i < ; i++) b[i] = a[i];
sort(b,b + );
for (int i = ; i < ; i++)
{
if (b[i] > && b[i] == b[i + ]) return true;
}
return false;
}
void clear()
{
memset(a, , sizeof(a));
}
};
LL ans = ;
map<ULL, LL> num;
map<ULL, N> A;
void solve_odd()
{
for (int i = ; i <= L; i++)
{
int l = ,r = min(i,L - i + ) + ;
while (r - l > )
{
int mid = (l + r) >> ;
if (hs(i - mid + , i + mid - ) == rhs(i - mid + , i + mid - )) l = mid;
else r = mid;
}
int p = l;
int tmp = p;
while (tmp >= && num.find(hs(i - tmp + , i + tmp - )) == num.end()) tmp--;
LL sum = ;
N st;
st.clear();
if (tmp >= )
{
sum = num[hs(i - tmp + , i + tmp - )];
st = A[hs(i - tmp + ,i + tmp - )];
}
while (tmp < p)
{
st.a[s[i + tmp]-'a'] += (tmp == ? : );
if (st.ok()) sum++;
num[hs(i - tmp, i + tmp)] = sum;
A[hs(i - tmp, i + tmp)] = st;
tmp++;
}
ans += sum;
}
}
void solve_even()
{
A.clear();
num.clear();
for(int i = ; i < L; i++)
{
int l = ,r = min(i,L - i) + ;
while (r - l > )
{
int mid = (l + r) >> ;
if (hs(i - mid + , i + mid) == rhs(i - mid + , i + mid)) l = mid;
else r = mid;
}
int p = l,tmp = p;
while (tmp >= && num.find(hs(i - tmp + , i + tmp)) == num.end()) tmp--;
LL sum = ;
N st;
st.clear();
if (tmp >= )
{
sum = num[hs(i - tmp + , i + tmp)];
st = A[hs(i - tmp + , i + tmp)];
}
while (tmp < p)
{
st.a[s[i + tmp + ] - 'a'] += ;
if (st.ok()) sum++;
num[hs(i - tmp, i + tmp + )] = sum;
A[hs(i - tmp, i + tmp + )] = st;
tmp++;
}
ans += sum;
}
}
int main()
{
freopen("str.in", "r", stdin);
freopen("str.out", "w", stdout);
scanf("%s", s + );
L = strlen(s + );
s[] = '#';
pw[] = ;
for(int i = ; i <= L; i++) pw[i] = pw[i - ] * ;
for(int i = ; i <= L; i++) h[i] = h[i - ] * + s[i];
for (int i = L; i >= ; i--) rh[i] = rh[i + ] * + s[i];
solve_odd();
solve_even();
printf("%lld\n", ans);
fclose(stdout);
return ;
}