分类目录归档:ACM

UVa 10755 Garbage Heap 三维前缀和 求最大子长方体和

题目给出一个长方体, 每个格子有一个值

现求一个子长方体, 使得其包含的方块的值的和最大.

采取枚举上下界, 配合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;
}

LA 3029 City Game 最大子矩阵

一个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;
}

POJ 1696 Space Ant 稍微修改的卷包裹法.

题目大意为,给定一些点,以最下且最左的那个点位起点,只能左拐,且路径不能交叉,求使得路径经过点数最多的走法.输出这条路径的长度和按顺序经过的点.

显然,只要沿着最外围走,所有点都可以被走到,使用求凸包的卷包裹法稍加更改,即可走出这样一条路径.

# include <iostream>
# include <algorithm>
# include <cmath>
# define rep(x, n) for (int x = 0; x < (n); ++x )
using namespace std;

int t, n;

class Point
{
    public:
    double x, y;
    int id;
    Point(){x = 0; y = 0;}

    Point(const double& x, const double& y, const int id = 0)
    { this->x = x; this->y = y; this->id = id; }

    inline bool operator <(const Point& a)const
    { return (y - a.y)? y < a.y : x < a.x; }

    inline Point operator +(const Point& a)
    { return Point(x + a.x, y + a.y); }

    inline Point operator -(const Point& a)
    { return Point(x - a.x, y - a.y); }

    inline double dot(const Point& a)
    { return x * a.x + y * a.y; }

    inline double Dis(const Point& a)
    { return sqrt( (*this - a).dot(*this - a)); }

    inline double cross(const Point& b, const Point& c)
    { return (b.x - x) * (c.y - y) - (b.y - y) * (c.x - x); }

}p[53];

bool v[53];
int res[53];

int main()
{
    int q;
    double x, y;
    cin >> t;
    while ( t-- )
    {
        cin >> n;
        rep(i, n)
        {
            cin >> q >> x >> y;
            p[i] = Point(x, y, q);
            v[i] = false;
        }
        sort(p, p+n);
        v[0] = true;
        res[0] = 0;
        rep(i, n-1)
        {
            rep(j, n)
                if ( !v[j] )
                    res[i+1] = j;
            rep(j, n)
            {
                if ( v[j] ) continue;
                double tmp = p[res[i]].cross(p[res[i+1]], p[j]);
                if ( tmp < 0 )
                    res[i+1] = j;
            }
            v[res[i+1]] = true;
        }
        cout << n;
        rep(i, n)
            cout << ' '<< p[res[i]].id;
        cout << endl;
    }
    return 0;
}

判断线段相交

刚刚开始接触计算几何.. 之前按自己的思路写了一个线段相交却怎么也过不了某题..

最后发现果然还是自己智商拙计= =..

线段a, b相交的充要条件是:  a 叉积 b 的两个端点之积为负, b 叉积 a 的两个端点之积为负数, 而且两线段不平行.

下面给出部分代码.

bool Parallel(Point a, Point b, Point c, Point d) {return !dcmp(a.cross(b, a + d - c));}

bool SegCross(Point& a, Point& b, Point& c, Point& d)
{
    //一定要判断是否平行!
    if( !Parallel(a, b, c, d) && a.cross(b, c) * a.cross(b, d) <= 0 && c.cross(d, a) * c.cross(d, b) <= 0)
        return true;
    return false;
}

某知识点列表=w=…

 一、动态规划
LCS
LIS
背包
单调性DP
环形DP
树形DP
状态压缩DP

二、搜索
枚举
搜索与剪枝
启发式搜索
DLX
双向搜索
折半搜索
记忆化搜索
模拟退火

三、计算几何
半平面交
凸包
几何图形的交与并
旋转卡壳
点定位
坐标变换
离散化与扫描
反演
voronoi图
平面图的对偶图
三角剖分
梯形剖分
几何知识

四、贪心

五、树结构
最近公共祖先
生成树
dfs序列
树上倍增
树的分治
树链剖分
link-cut-tree

六、图结构
平面图
二分图
二分图匹配
最短路
差分约束
拓扑排序
网络流
强连通分量
割点割边
欧拉回路
2-sat

七、数论
素数判定
欧几里得算法
不定方程
数位统计
解线性同余方程
baby-step-giant-step
pell方程
大整数质因数分解
勾股方程
积性函数
Fibonacci数列

八、模拟

九、数据结构

队列
链表
单调队列
并查集

平衡树
线段树
树状数组
树套树
四分树
划分树
归并树
kd树
块状链表
hashing
函数式编程

十、博弈论

十一、字符串
kmp
后缀数据结构
trie树
AC自动机
manacher
表达式处理

十二、组合数学
生成函数
容斥原理
康托展开
Catalan数列
Stirling数
polya定理

十三、线性代数
矩阵乘法
高斯消元
线性规划

十四、高精度
FFT

十五、递推

十六、概率论
随机化

十七、经典NPC问题

十八、其它
二分查找
三分查找
双指针扫描
分治
分块
RMQ
快速幂
数学
排序
构造