HDU 4911 Inversion
题意：n个数字 通过k次相邻交换 使得逆序对数最少
思路：如果序列为 XXXABYYY 假设A和B位置互换 易知X和AB、Y和AB的逆序对数不变 换句话说一次交换最多使逆序对减少1 那么只需要求原逆序对数和k进行比较即可
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100100
typedef __int64 ll;
int n;
ll k, ans;
int a[N], b[N], c[N];
int lowbit(int x) {
return x & (-x);
}
void add(int x) {
for (; x <= n; x += lowbit(x)) {
c[x]++;
}
}
int sum(int x) {
int res = 0;
for (; x > 0; x -= lowbit(x)) {
res += c[x];
}
return res;
}
int main() {
int i, j;
while (~scanf("%d%I64d", &n, &k)) {
for (i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = a[i];
}
memset(c, 0, sizeof(c));
sort(b + 1, b + n + 1);
ans = 0;
for (i = 1; i <= n; i++) {
j = lower_bound(b + 1, b + n + 1, a[i]) - b;
ans += sum(n) - sum(j);
add(j);
}
if (ans > k)
printf("%I64d\n", ans - k);
else
printf("0\n");
}
return 0;
}HDU 4915 Parenthese sequence
题意：？可以代表（或） 那么输入的字符串能构造出几种合法的括号序列呢 输出无解、唯一解、多解
思路：这题是我YY的… 首先我们可以计算出（和）应该填几个 如果计算出？不满足我们要填的东西 那么必然无解 接着有一种最简单的解 那就是把靠左边的问号全变成‘（’（注意个数）剩下的变成‘）’ 如果这样构造完的字符串都不是合法的 那么一定没有合法的解 然后开始YY… 发现我们填上的最中间的（和）通过交换可以影响最小 而且两边的括号很可能可以满足它们 所以我们将构造出的序列中我们填上的最中间的两个括号交换 最后验证一下新串是否合法 合法就是多解 否则唯一解 注意！！ 有可能我们根本不能交换！！ 因为我们全填的是（或）
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1000010
char str[N], f[N];
int n, num, g1, g2;
int ff(int x) {
if (x < 0)
return -x;
return x;
}
int main() {
int i, j, tmp;
while (~scanf("%s", str)) {
n = strlen(str);
for (i = num = g1 = g2 = 0; i < n; i++) {
if (str[i] == '?')
num++;
else if (str[i] == '(')
g1++;
else
g2++;
}
tmp = ff(g1 - g2);
if (num < tmp || (num - tmp) % 2 != 0) {
puts("None");
continue;
}
if (g1 < g2)
tmp = tmp + (num - tmp) / 2;
else
tmp = (num - tmp) / 2;
for (i = j = 0; i < n; i++) {
if (str[i] == '?') {
j++;
if (j <= tmp)
str[i] = '(';
else
str[i] = ')';
if (j < tmp || j == tmp + 1)
f[i] = '(';
else
f[i] = ')';
} else
f[i] = str[i];
}
for (i = j = 0; i < n; i++) {
if (str[i] == '(')
j++;
else
j--;
if (j < 0)
break;
}
if (i < n) {
puts("None");
continue;
}
if (tmp == 0 || tmp == num) {
puts("Unique");
continue;
}
for (i = j = 0; i < n; i++) {
if (f[i] == '(')
j++;
else
j--;
if (j < 0)
break;
}
if (i < n)
puts("Unique");
else
puts("Many");
}
return 0;
}HDU 4920 Matrix multiplication
题意：求矩阵乘法 最后所有数字%3
思路：分块！ 如果n3我们会T的话 那么我们可以把任务分成两次去做 类似于前缀和或分治的优化思想！
首先分块7个数字一组 然后矩阵相乘就变成了块相乘 既然块相乘的复杂度我们可以接受 那么剩下的就是——如果给你两个块 如何快速计算他们的积 打表！ 我们利用3进制数表示状态dp打出任何两个块相乘的积 最后利用dp的结果计算即可
代码：
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define M 810
int n, N;
int f[2200][2200];
int a[M][M], b[M][M], c[M][M];
int A[M][M], B[M][M];
int read() {
char ch;
bool ok = 0;
int res = 0;
for (;;) {
ch = getchar();
if (ch >= '0' && ch <= '9')
res = res * 10 + ch - '0', ok = 1;
else if (ok)
return res % 3;
}
}
int solve(int a, int b) {
int i = 7, res = 0;
while (i--) {
res += (a % 3) * (b % 3);
a /= 3;
b /= 3;
}
return res % 3;
}
int main() {
int i, j, k;
for (i = 0; i < 2187; i++)
for (j = 0; j < 2187; j++)
f[i][j] = solve(i, j);
while (~scanf("%d", &n)) {
N = (n - 1) / 7 + 1;
for (i = 0; i < n; i++) {
int cnt = 0;
int tmp = 0;
for (j = 0; j < n; j++) {
cnt++;
a[i][j] = read();
tmp = tmp * 3 + a[i][j];
if (cnt == 7) {
A[i][j / 7] = tmp;
tmp = 0;
cnt = 0;
}
}
if (cnt > 0)
A[i][N - 1] = tmp;
}
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
b[i][j] = read();
c[i][j] = 0;
}
for (j = 0; j < n; j++) {
int cnt = 0;
int tmp = 0;
for (i = 0; i < n; i++) {
cnt++;
tmp = tmp * 3 + b[i][j];
if (cnt == 7) {
B[i / 7][j] = tmp;
tmp = 0;
cnt = 0;
}
}
if (cnt > 0)
B[N - 1][j] = tmp;
}
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
for (k = 0; k < N; k++)
c[i][j] += f[A[i][k]][B[k][j]];
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
printf("%d", c[i][j] % 3);
if (j == n - 1) {
putchar('\n');
} else
putchar(' ');
}
}
return 0;
}2014多校联合五（HDU 4911 HDU 4915 HDU 4920）,布布扣,bubuko.com
2014多校联合五（HDU 4911 HDU 4915 HDU 4920）
原文：http://blog.csdn.net/houserabbit/article/details/38389505