HDU 4622 Reincarnation
枚举字符串的起点，构造后缀自动机，每次插入一个字符，就能统计得到当前不同字串的个数，预处理出所有的询问。
#include<cstdio>
#include<cstring>
#define MAXN 2010
#define MAXM 26
int res[MAXN][MAXN];
char str[MAXN];
struct node {
node *next[MAXM];
node *pre;
int step;
int tot;
} sam[MAXN << ];
node *root = &sam[];
int cnt, last;
int ans;
node &newNode() {
sam[++cnt].tot = ;
memset(sam[cnt].next, , sizeof(sam[cnt].next));
return sam[cnt];
}
void add(int idx, int step) {
node &p = newNode();
p.step = step;
p.pre = &p;
node *u = &sam[last];
last = cnt;
while (u && u->next[idx] == ) {
u->next[idx] = &p;
p.tot += u->tot;
u = u->pre;
}
if (!u) {
p.pre = root;
} else {
node *q = u->next[idx];
if (q->step == u->step + ) {
p.pre = q;
} else {
node &nq = newNode();
memcpy(nq.next, q->next, sizeof(q->next));
nq.step = u->step + ;
nq.pre = q->pre;
q->pre = &nq;
p.pre = &nq;
for (; u && u->next[idx] == q; u = u->pre) {
u->next[idx] = &nq;
q->tot -= u->tot;
nq.tot += u->tot;
}
}
}
ans += p.tot;
}
int main() {
int T;
int i, j;
int len;
int q;
scanf("%d", &T);
while (T--) {
scanf(" %s", str);
len = strlen(str);
for (i = ; i < len; i++) {
sam[].pre = ;
sam[].tot = ;
cnt = last = ;
ans = ;
memset(sam[cnt].next, , sizeof(sam[cnt].next));
for (j = i; j < len; j++) {
add(str[j] - 'a', j - i + );
res[i][j] = ans;
}
}
scanf("%d", &q);
while (q--) {
scanf("%d%d", &i, &j);
printf("%d\n", res[i - ][j - ]);
}
}
return ;
}
HDU 4623 Crime
dp[28][228]表示最后取的数，当前状态，可以得到的方案数。显然不可行。
由于相邻的两个数必须互素，所以这两个数不会有相同的素因子。
将1～n的数划分等价类，具有相同素因子的数属于同一个等价类。
通过打表可以发现，最后取的数减少到15，状态数减少到1728000。
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#define MAXL 15
#define MAXN 30
#define MAXM 1728000
using namespace std;
vector<int> prime;
vector<int> factor;
map<int, int> mymap;
vector<int> g[MAXL];
bool vis[MAXN];
int dp[MAXM][MAXL];
int base[MAXN];
int stand[MAXN];
int arr[MAXN];
int tot;
bool isPrime(int n) {
for (int i = ; i < n; i++) {
if (n % i == ) {
return false;
}
}
return true;
}
int GCD(int x, int y) {
return y ? GCD(y, x % y) : x;
}
int encrypt() {
int res = ;
for (int i = ; i < tot; i++) {
res = res * base[i] + arr[i];
}
return res;
}
void decrypt(int val) {
for (int i = tot - ; i >= ; i--) {
arr[i] = val % base[i];
val /= base[i];
}
}
int main() {
int T;
int n, m;
int i, j, k, l;
int tmp;
int ans;
pair<int, int> head, cur;
map<int, int>::iterator it;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
mymap.clear();
memset(vis, false, sizeof(vis));
for (i = ; i <= n; i++) {
for (j = ; j <= n; j++) {
if (i == j) {
continue;
}
if (GCD(i, j) != ) {
break;
}
}
if (j > n) {
vis[i] = true;
mymap[]++;
}
}
prime.clear();
for (i = ; i <= n; i++) {
if (isPrime(i)) {
prime.push_back(i);
}
}
for (i = ; i < ( << prime.size()); i++) {
tmp = ;
factor.clear();
for (k = i, j = ; k; k >>= , j++) {
if (k & ) {
tmp *= prime[j];
factor.push_back(prime[j]);
}
}
if (tmp <= n && !vis[tmp]) {
for (j = ; j <= n; j++) {
for (k = ; k < (int) factor.size(); k++) {
if (j % factor[k] != ) {
break;
}
}
if (k >= (int) factor.size()) {
l = j;
for (k = ; k < (int) factor.size(); k++) {
while (l % factor[k] == ) {
l /= factor[k];
}
}
if (l == ) {
vis[l] = true;
mymap[tmp]++;
}
}
}
}
}
memset(dp, , sizeof(dp));
tot = ;
for (it = mymap.begin(); it != mymap.end(); it++) {
stand[tot] = (*it).first;
arr[tot] = (*it).second;
base[tot++] = (*it).second + ;
}
l = encrypt();
dp[l][] = ;
for (i = ; i < tot; i++) {
g[i].clear();
for (j = ; j < tot; j++) {
if (GCD(stand[i], stand[j]) == ) {
g[i].push_back(j);
}
}
}
for (i = l; i > ; i--) {
decrypt(i);
for (j = ; j < tot; j++) {
for (k = ; k < (int) g[j].size(); k++) {
if (arr[g[j][k]] == ) {
continue;
}
arr[g[j][k]]--;
l = encrypt();
dp[l][g[j][k]] += dp[i][j];
if (dp[l][g[j][k]] >= m) {
dp[l][g[j][k]] -= m;
}
arr[g[j][k]]++;
}
}
}
ans = ;
for (i = ; i < tot; i++) {
ans += dp[][i];
}
ans %= m;
for (i = ; i < tot; i++) {
for (j = ; j < base[i]; j++) {
ans *= j;
ans %= m;
}
}
printf("%d\n", ans);
}
return ;
}
HDU 4627 The Unsolvable Problem
a+b=n，当a与b越接近，a*b越大。
寻找最接近的两个互素的数，答案最大。
#include<iostream>
typedef long long LL;
using namespace std;
LL GCD(LL x, LL y) {
return y ? GCD(y, x % y) : x;
}
int main() {
int T;
int n;
int tmp;
cin >> T;
while (T--) {
cin >> n;
for (int i = n >> ; i <= n; i++) {
tmp = GCD(i, n - i);
if (tmp == ) {
cout << (LL) i * (n - i) / tmp << endl;
break;
}
}
}
return ;
}
HDU 4628 Pieces
dp[i]表示状态为i的最少步数。对i枚举子集，dp[i]=min(dp[j]+dp[i^j])。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 16
#define oo 123456789
using namespace std;
char str[MAXN];
int dp[ << MAXN];
bool isOK(int val) {
char tmp[MAXN];
int len = ;
for (int i = ; val; val >>= , i++) {
if (val & ) {
tmp[len++] = str[i];
}
}
for (int i = , j = len - ; i <= j; i++, j--) {
if (tmp[i] != tmp[j]) {
return false;
}
}
return true;
}
int dfs(int x) {
if (dp[x] != -) {
return dp[x];
}
int ans = oo;
for (int i = (x - ) & x; i; i = (i - ) & x) {
ans = min(ans, dfs(i) + dfs(x ^ i));
}
dp[x] = ans;
return ans;
}
int main() {
int T;
int len;
scanf("%d", &T);
while (T--) {
memset(dp, -, sizeof(dp));
scanf(" %s", str);
len = strlen(str);
dp[] = ;
for (int i = ; i < ( << len); i++) {
if (isOK(i)) {
dp[i] = ;
}
}
printf("%d\n", dfs(( << len) - ));
}
return ;
}
HDU 4630 No Pain No Game
枚举i，对于任意两个i的倍数，他们一定有约数i，有的等于它们的GCD，有的小于它们的GCD。
对i的倍数，在数列出现的位置排序，相邻的两个看成一个线段，线段有一个权值i。
问题转化为询问一个区间，能覆盖到的线段中，权值最大是多少。
离线处理，对询问右端点排序从小到大排序，对所有线段右端点从小到大排序。
每个询问[l,r]，若线段[x,y]权值为val，对所有满足y<=r的线段插入线段树，插入的位置为x，权值为val。
回答询问即求询问区间的最大值。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define MAXN 50010
#define MAXM 550000
using namespace std;
int arr[MAXN];
int pos[MAXN];
struct Query {
int x, y;
int index;
friend bool operator<(Query a, Query b) {
return a.y < b.y;
}
} ask[MAXN];
struct node {
int x, y;
int val;
friend bool operator<(node a, node b) {
return a.y < b.y;
}
} p[MAXM];
int tree[MAXN << ];
int ans[MAXN];
void build(int L, int R, int rt) {
tree[rt] = ;
if (L != R) {
int mid = (L + R) >> ;
build(L, mid, rt << );
build(mid + , R, rt << | );
}
}
inline void pushUp(int rt) {
tree[rt] = max(tree[rt << ], tree[rt << | ]);
}
void update(int x, int val, int L, int R, int rt) {
if (L == R) {
tree[rt] = max(tree[rt], val);
} else {
int mid = (L + R) >> ;
if (x <= mid) {
update(x, val, L, mid, rt << );
} else {
update(x, val, mid + , R, rt << | );
}
pushUp(rt);
}
}
int query(int x, int y, int L, int R, int rt) {
if (x <= L && R <= y) {
return tree[rt];
} else {
int mid = (L + R) >> ;
int ans = ;
if (x <= mid) {
ans = max(ans, query(x, y, L, mid, rt << ));
}
if (y > mid) {
ans = max(ans, query(x, y, mid + , R, rt << | ));
}
return ans;
}
}
int main() {
int T;
int n, q;
int i, j;
int cnt;
vector<int> tmp;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (i = ; i <= n; i++) {
scanf("%d", &arr[i]);
pos[arr[i]] = i;
}
scanf("%d", &q);
for (i = ; i < q; i++) {
scanf("%d%d", &ask[i].x, &ask[i].y);
ask[i].index = i;
}
sort(ask, ask + q);
cnt = ;
for (i = ; i <= n; i++) {
tmp.clear();
for (j = i; j <= n; j += i) {
tmp.push_back(pos[j]);
}
sort(tmp.begin(), tmp.end());
for (j = ; j < (int) tmp.size(); j++) {
p[cnt].x = tmp[j - ];
p[cnt].y = tmp[j];
p[cnt++].val = i;
}
}
sort(p, p + cnt);
build(, n, );
for (i = j = ; i < q; i++) {
for (; j < cnt && p[j].y <= ask[i].y; j++) {
update(p[j].x, p[j].val, , n, );
}
ans[ask[i].index] = query(ask[i].x, ask[i].y, , n, );
}
for (i = ; i < q; i++) {
printf("%d\n", ans[i]);
}
}
return ;
}
HDU 4631 Sad Love Story
由于数据是随机的……
用set保存点集，按x坐标排序。
每次插入一个点后，从该位置沿x方向递增更新结果，当横坐标之差大于等于最近点对的时候，就跳出循环。
#include<cstdio>
#include<set>
#include<iostream>
typedef long long LL;
#define MAXN 500010
#define oo 123456789123456789LL
using namespace std;
struct Point {
int x, y;
Point(int _x = , int _y = ) {
x = _x;
y = _y;
}
friend bool operator<(Point a, Point b) {
if (a.x != b.x) {
return a.x < b.x;
} else {
return a.y < b.y;
}
}
};
set<Point> myset;
Point p[MAXN];
inline LL dis2(Point a, Point b) {
LL x = a.x - b.x;
LL y = a.y - b.y;
return x * x + y * y;
}
inline LL dis1(Point a, Point b) {
LL x = a.x - b.x;
return x * x;
}
int main() {
int T;
int n;
int ax, bx, cx;
int ay, by, cy;
LL ans, res;
set<Point>::iterator it, tmp;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d%d%d%d%d", &n, &ax, &bx, &cx, &ay, &by, &cy);
p[] = Point(bx % cx, by % cy);
for (int i = ; i < n; i++) {
p[i] = Point((p[i - ].x * (LL) ax + bx) % cx,
(p[i - ].y * (LL) ay + by) % cy);
}
res = oo;
ans = ;
myset.clear();
myset.insert(p[]);
for (int i = ; i < n; i++) {
if (myset.count(p[i])) {
break;
}
myset.insert(p[i]);
it = myset.find(p[i]);
for (tmp = it, ++tmp; tmp != myset.end(); ++tmp) {
if (dis1(*it, *tmp) >= res) {
break;
} else {
res = min(res, dis2(*it, *tmp));
}
}
if (it != myset.begin()) {
for (tmp = it, --tmp;; --tmp) {
if (dis1(*it, *tmp) >= res) {
break;
} else {
res = min(res, dis2(*it, *tmp));
}
if (tmp == myset.begin()) {
break;
}
}
}
ans += res;
}
cout << ans << endl;
}
return ;
}