2012 Multi-University Training Contest 7
A.As long as Binbin loves Sangsang
题意:在连续的n秒中，每秒会出现m个龙珠。已知初始位置，每从一个位置i,移动到另一个位置j的时候，消耗的代价为abs(i-j), 知道了每次出现的龙珠的位置及取它的代价，每一秒必须取一颗龙珠。问 n 秒之后花费的最小代价是多少。
SOL:用dp[i][j]表示i秒之后，留在第j个龙珠所在位置的最小花费，这样就有了一个$O(n*m^2)$的做法，之后很容易想到用单调队列优化，复杂度$O(n*m)$。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int oo = 1e9;
int i, j, k, n, m, s, t, ans, x;
struct node {
int pos, cost;
} a[][];
int dp[][];
bool cmp(const node &x, const node &y) {
return x.pos < y.pos;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d %d %d", &n, &m, &x);
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
scanf("%d", &a[i][j].pos);
}
}
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
scanf("%d", &a[i][j].cost);
}
}
for (int i = ; i <= n; i++) {
sort(a[i] + , a[i] + + m, cmp);
}
for (int j = ; j <= m; j++) {
dp[][j] = a[][j].cost + abs(a[][j].pos - x);
}
for (int i = ; i <= n; i++) {
int k = , t = oo;
for (int j = ; j <= m; j++) {
while (k + <= m && a[i][j].pos >= a[i - ][k + ].pos) {
k++;
t = min(t, dp[i - ][k] - a[i - ][k].pos);
}
dp[i][j] = t + a[i][j].cost + a[i][j].pos;
}
k = m + , t = oo;
for (int j = m; j >= ; j--) {
while (k - >= && a[i][j].pos <= a[i - ][k - ].pos) {
k--;
t = min(t, dp[i - ][k] + a[i - ][k].pos);
}
dp[i][j] = min(dp[i][j], t + a[i][j].cost - a[i][j].pos);
}
}
ans = oo;
for (int j = ; j <= m; j++) {
ans = min(ans, dp[n][j]);
}
printf("%d\n", ans);
}
return ;
}
题意:给你n*n的方格纸，在格子里填颜色,要满足任意水平、垂直翻转，转任意个90度后看到的图形都一样；现在你有k种颜色，有m个格子已经图了颜色，求方案数。
SOL:直接搞出等价类再用快速幂做一做就好了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod = ;
const int LEN = 1e5 + ;
int i, j, k, n, m, s, t, ans, tot;
int a[LEN];
int pow_mod(const int &x, int y) {
if (y == ) {
return ;
}
int ans = pow_mod(x, y >> );
ans = (ll)ans * ans % mod;
if (y & ) {
ans = (ll)ans * x % mod;
}
return ans;
}
int trans(int x, int y) {
if (x > n / ) {
x = n + - x;
}
if (y > n / ) {
y = n + - y;
}
if (x > y) {
swap(x, y);
}
return x * + y;
}
int getnum(int n) {
int L = (n + ) / ;
return (L + ) * L / ;
}
int main() {
while (scanf("%d %d %d", &n, &m, &k) != EOF) {
tot = ;
for (int i = ; i <= m; i++) {
int x, y;
scanf("%d %d", &x, &y);
x++, y++;
a[++tot] = trans(x, y);
}
if (tot > ) {
sort(a + , a + + tot);
tot = unique(a + , a + + tot) - a - ;
}
printf("%d\n", pow_mod(k, getnum(n) - tot));
}
return ;
}
题意:给你一棵树，每个结点有两个属性值，1.能力值,2.忠诚度。然后m个询问，每次询问一个整数u，求u的子树中能力值大于u的且忠诚度最大的点的编号。
SOL:先按能力值排序，这样从大到小考虑就满足了条件１,然后从大到小依次在线段树里查询子树中忠诚度最大的点的编号，复杂度O(nlogn)。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define tl (p << 1)
#define tr (p << 1 | 1)
using namespace std;
const int LEN = 1e5 + ;
int i, j, k, n, m, s, t, tot, Time;
struct edge {
int vet, next;
} E[LEN * ];
struct node {
int x, y, id;
} a[LEN];
bool cmp(const node &x, const node &y) {
return x.x > y.x;
};
int head[LEN], size[LEN], tid[LEN], ans[LEN], pre[LEN], b[LEN];
int to[];
int tmax[LEN * ];
void add(int u, int v) {
E[++tot] = (edge){v, head[u]};
head[u] = tot;
}
void dfs(int u) {
size[u] = ;
tid[u] = ++Time;
pre[Time] = u;
for (int e = head[u]; e != -; e = E[e].next) {
int v = E[e].vet;
dfs(v);
size[u] += size[v];
}
}
int ask(int l, int r, int x, int y, int p) {
if (l == x && y == r) {
return tmax[p];
}
int mid = (l + r) >> ;
if (mid >= y) {
return ask(l, mid, x, y, tl);
} else if (mid + <= x) {
return ask(mid + , r, x, y, tr);
} else {
return max(ask(l, mid, x, mid, tl), ask(mid + , r, mid + , y, tr));
}
}
void update(int p) {
tmax[p] = max(tmax[tl], tmax[tr]);
}
void modify(int l, int r, const int &x, int p, const int &c) {
if (l == r) {
tmax[p] = c;
return;
}
int mid = (l + r) >> ;
if (mid >= x) {
modify(l, mid, x, tl, c);
} else {
modify(mid + , r, x, tr, c);
}
update(p);
}
void build(int l, int r, int p) {
if (l == r) {
tmax[p] = -;
return;
}
int mid = (l + r) >> ;
build(l, mid, tl);
build(mid + , r, tr);
update(p);
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
tot = Time = ;
scanf("%d %d", &n, &m);
for (int i = ; i <= n; i++) {
head[i] = -;
size[i] = ;
tid[i] = ;
}
a[] = (node){1e9, , };
for (int i = ; i <= n; i++) {
int fa, x, y;
scanf("%d %d %d", &fa, &x, &y);
x++,y++,fa++;
swap(x, y);
add(fa, i);
a[i] = (node){x, y, i};
to[y] = i;
}
dfs();
build(, n, );
sort(a + , a + + n, cmp);
int j = ;
for (int i = ; i <= n; i++) {
int x = a[i].id, t = ask(, n, tid[x], tid[x] + size[x] - , );
if (t == -) {
ans[x] = ;
} else {
ans[x] = to[t];
}
while (j + <= i && a[j + ].x > a[i + ].x) {
modify(, n, tid[a[j + ].id], , a[j + ].y);
j++;
}
}
while (m--) {
int x;
scanf("%d", &x);
printf("%d\n", ans[x + ] - );
}
}
return ;
}