之前构造排列都是自己写…真是麻烦啊..
结果今天围观刘汝佳神犇的白书发现了一个好用的函数:
next_permutation();
可以用于可重, 或者不可重集, 寻找下一个排列.
时间复杂度尚不明.
//适用于不可重和可重集的排列.
# include <iostream>
# include <algorithm>
using namespace std;
int a[1003], n;
int main()
{
cin >> n;
for (int i = 0; i < n; ++i )
cin >> a[i];
sort(a, a+n);
do
{
for(int i = 0; i < n; ++i)
cout << a[i] << ' ';
cout << endl;
} while( next_permutation(a, a+n) );
return 0;
}
本次使用铅笔画初稿.
然后用钢笔描线一次.
铅笔稿:
用铅笔绘制的少女头部草稿
钢笔稿
用钢笔描线的少女头部
给定N < 25个大写字母组成的字符串, 选择最多的传, 使得每个大写字母都能出现偶数次.
显然字母出现偶数次可以转换为: 每次异或, 最后为零. 由于只有26个英文字母, 故一个字符串可用一个int类型来表示.
直接枚举显然会超时, 故使用 中途相遇法 (Meet-in-the-Middle)
又知, 异或值为零的两个数必然完全相等.故可以使用map来维护xor值及对应使用的句子
# include <iostream>
# include <algorithm>
# include <string>
# include <map>
# define rep(x, n) for(int x = 0; x < (n); ++x)
using namespace std;
int n;
int a[30];
string s;
map <int, int> table;
int bitcount(int x)
{
return x == 0 ? 0 : bitcount(x>>1) + (x&1);
}
int main()
{
while ( cin >> n)
{
rep(i, n)
{
cin >> s;
a[i] = 0;
rep(j, s.size())
a[i] ^= (1<<(s[j]-'A'));
}
table.clear();
int n1 = n / 2;
int n2 = n - n1;
//枚举前n1个元素的所有子集的xor值
//table保存xor值为x, 包含元素最多的子集s
rep(i, 1<<n1)
{
int x = 0;
rep(j, n1) if (i & (1<<j)) x ^= a[j];
if ( !table.count(x) || bitcount(table[x]) < bitcount(i) )
table[x] = i;
}
int ans = 0;
rep(i, 1<<n2)
{
int x = 0;
rep(j, n2) if (i & (1<<j)) x ^= a[n1+j];
if ( table.count(x) && bitcount(ans) < bitcount(table[x]) + bitcount(i) )
ans = (i<<n1) | table[x];
}
cout << bitcount(ans) << endl;
rep(i, n)
if (ans & (1<<i))
cout <<i+1<<" ";
cout << endl;
}
return 0;
}
题目给出一个长方体, 每个格子有一个值
现求一个子长方体, 使得其包含的方块的值的和最大.
采取枚举上下界, 配合3维前缀和即可在O(n ^ 5)的时间内求解.
枚举x1, x2(x的上下界), 枚举y1, y2(y的上下界), 之后O(n)对该段z的前缀和处理, 找出最大的子段.
# include <iostream>
# include <cstring>
# include <algorithm>
# define rep(x, s, t) for (int x = (s); x <= (t); ++x )
using namespace std;
const int maxn = 30;
const long long INF = 1LL<<60;
int a, b, c;
long long S[maxn][maxn][maxn];
inline void expand(int i, int&b0, int& b1, int &b2)
{
b0 = i&1; i >>= 1;
b1 = i&1; i >>= 1;
b2 = i&1;
}
inline int sign(int b0, int b1, int b2)
{
return (b0 + b1 + b2) % 2 == 1 ? 1 : -1;
}
long long sum(int x1, int x2, int y1, int y2, int z1, int z2)
{
int dx = x2-x1+1, dy = y2-y1+1, dz = z2-z1+1;
long long s = 0;
rep(i, 0, 7)
{
int b0, b1, b2;
expand(i, b0, b1, b2);
s -= S[x2 - b0*dx][y2 - b1*dy][z2 - b2*dz] * sign(b0, b1, b2);
}
return s;
}
int main()
{
int T;
cin >> T;
while (T--)
{
int b0, b1, b2;
cin >> a >> b >> c;
memset(S, 0, sizeof S);
rep(x, 1, a) rep(y, 1, b) rep(z, 1, c) cin >> S[x][y][z];
rep(x, 1, a) rep(y, 1, b) rep(z, 1, c)
rep(i, 1, 7)
{
expand(i, b0, b1, b2);
S[x][y][z] += S[x-b0][y-b1][z-b2] * sign(b0, b1, b2);
}
long long ans = -INF;
rep(x1, 1, a) rep(x2, x1, a) rep(y1, 1, b) rep(y2, y1, b)
{
long long M = 0;
rep(z, 1, c)
{
long long s = sum(x1, x2, y1, y2, 1, z);
ans = max(ans, s - M);
M = min(M, s);
}
}
cout << ans << endl;
if (T) cout << endl;
}
return 0;
}
一个n x m的矩阵中有很多障碍物.
现求一个最大的且不包含障碍物的子矩阵.
把每个格子向上延伸到障碍或者边界的连续的空格看做一条线段, 则对于该格来说, 它对应的一个子矩阵子矩阵即为这条线段左右可移动到的边界.
又知任何一个矩阵均可以由它最下层的某个对应线段长度恰好为矩形高度的格子表示.
故对于每一个格子, 求出其对应矩阵即可(即其对应线段左右移动的最远地点)
可推得:
up[i][j] = up[i-1][j] + 1, 当格子为障碍物或者边界时, up为0
left[i][j] = max(left[i-1][j], lo+1) 其中lo为当前格子所在行左侧最靠近的障碍坐标.
同理有
right[i][j] = min(right[i-1][j], ro-1)
# include <cstdio>
# include <algorithm>
# define rep(x, n) for (int x = 0; x < n; ++x)
using namespace std;
const int maxn = 1003;
int t;
int n, m;
int a[maxn][maxn];
int up[maxn][maxn], left[maxn][maxn], right[maxn][maxn];
int main()
{
scanf("%d", &t);
while ( t-- )
{
scanf("%d%d", &n, &m);
rep(i, n)
rep(j, m)
{
char ch = getchar();
while ( ch != 'R' && ch != 'F' ) ch = getchar();
a[i][j] = ch == 'R' ? 1 : 0;
}
int ans = 0;
rep(i, n)
{
int lo = -1, ro = m;
rep(j, m)
if ( a[i][j] )
{
up[i][j] = left[i][j] = 0;
lo = j;
}
else
{
up[i][j] = i == 0 ? 1 : up[i-1][j] + 1;
left[i][j] = i == 0 ? lo+1 : max(left[i-1][j], lo+1);
}
for (int j = m-1; j >= 0; --j )
if ( a[i][j] == 1 )
{
right[i][j] = m;
ro = j;
}
else
{
right[i][j] = i == 0 ? ro-1 : min(right[i-1][j], ro-1);
ans = max(ans, (right[i][j] - left[i][j] + 1) * up[i][j]);
}
}
printf("%d\n", ans*3);
}
return 0;
}