头像

NikolaTesla




离线:2天前



acwing 上报 Internal Error
给的样例也是对的
过不了
编译器报了什么错误?
Internal Error
但是相同的代码在poj 上能过(水过, 几乎压的时间)
poj 3565 ants




NikolaTesla
3个月前

这题直接贪心就能过
让 i 从 F 开始 到 N 结束 表示 我选择的区间的末尾位置
而 开头位置 不过 就是 从 1 到 i - p + 1选一个最优的
看过程
就让 j 从 1 到 i - p + 1 每次看一下(j, i - p + 1这一段的均值是否 小于 我总共的均值 如果小于
就让 j++ 并且当i增加的时候j继续看就行
证明一下为什么贪心对
假设 当 i = x 的时候 我已经抛弃了 角标为 1 和 角标 为 2
那么 当 i = x+1 的时候 我一定不会选择 角标为 1 或者 2
因为 如果 当 i 等于 x + 1的时候 均值变小 一定不是最优解 而均值比原来的大那么一定也不选 1 和 2 因为均值比这个小的时候都不选 那么大了肯定也不选

C++ 代码

#include <iostream>
#include <algorithm>
#define rep(i, a, b) for (int i = a; i <= b; ++i)
using namespace std;
const int maxn = 1e5 + 5;
double a[maxn];
int main() {
    int n, p;
    cin >> n >> p;
    rep(i, 1, n) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    double max_ = -9999.999;
    int j = 1;
    double jun;
    rep(i, p, n) {
        jun = (a[i] - a[j - 1]) / (i - j + 1);// 这是目前的均值加上可以抛弃的长度
        double cha = (a[i - p] - a[j - 1]) / (i - p - j + 1);//可以抛弃的部分的均值 
       while (i - j + 1 > p && cha <= jun) { // 开始抛弃
           j++;
           cha = (a[i - p] - a[j - 1]) / (i - p - j + 1); // 每次抛弃的时候均值会改变
       }
        jun = (a[i] - a[j - 1]) / (i - j + 1);//抛弃完毕 这里就是 以i为结尾的最大均值
        max_ = max(max_, jun);
    }
    cout << int(max_ * 1000);

    return 0;
}



NikolaTesla
3个月前

该想法无链接 匈牙利算法

某年某月某天(早以前..) 看dinic的时候看到了当前弧优化
突然想到匈牙利算法 好像也可以当前弧优化一下 而且应该会快很多

然后自己尝试了一下 wrong了
不过偶然间的稍微改动了一点点 就可以AC题目了
而且有些不能用匈牙利算法的题目(会tle的)也能用我优化的匈牙利过了

然后当时就问了很多人 都没有人解释一下原因 1 是为什么之前的会wrong 2 是为什么偶然改的能ac
当然也可能想法本身还是有漏洞,数据凑巧了 不过在那之后我也试了好多题都能过 求大佬解…
(“优化”)后的匈牙利:(加括号是因为我还是不知道正确性 而且 优化了到底多少我也搞不清)


   bool find(int x) {
    for (int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].to;
        if (used[y]) continue;
        used[y] = true;
        if (!fa[y] || find(fa[y])) {
        // temp[x] 记录 初始状态下的 head[x] 的值 
        // 也就是最开始的 head[x] 的值
            if (edge[i].nex) head[x] = edge[i].nex;
            else head[x] = temp[x]; 
            fa[y] = x;
            return true;
        } 
    }
    head[x] = false;
    return false;
}

可以试试这么写哪种数据过不了… 目前我没找到..(- -)
嗯 .. 可以找些二分图匹配的题这么写试试..
Orz 。。。求大佬解开我心中的疑惑/…

确实有过不去的数据但是我还是不知道原因 自己改进了一下应该是没问题了

int head[maxn], nex[maxn], to[maxn], cnt, tmp[maxn];
inline void add(int a, int b) { // 创建链表的时候采用循环链表
    to[++cnt] = b;
    nex[cnt] = head[a];
    if (head[a] == 0) {
        tmp[a] = nex[cnt] = cnt;
    } else {
        nex[tmp[a]] = cnt;
    }
    head[a] = cnt;
}
bool find(int x) {
int i = head[x];
if (i == 0) return false;
    do {
        int z = to[i];
        i = nex[i];
        if (used[z]) continue;
        used[z] = true;
        if (!f[z] || find(f[z])) {
            head[x] = i;
            f[z] = x;
            return true;
        }   
    } while (i != head[x]);
    return false;
}

为什么第一种有问题? 想不通啊…

附上一张 从tle 变成 ac的图 这两张图都用的匈牙利算法

只不过ac的用的是我这个改进之后的匈牙利
tle.png.png
ac.png.png




NikolaTesla
3个月前

题目描述

样例

3 
1 1 2 
2 16 1 
3 4 33 

算法1

很明显能看出来前一个图和 下一个图的关系
下一个图是这个图分为四部分拼起来的 左上和左下进行了以对角线为中心的翻转 而右上和右下就是上一个图

参考文献

要求点的坐标 就可以先求上一个图中的坐标 在加上一个特定的值(例如 x轴 加值 或者 y轴加值 或者都加)
只需要知道这个点在当前图的那个位置就好 (左上、左下、右上右下)
对于右上右下 的点 非常好求 因为只需要减去整数倍的上一个图就行 (具体原因自己思考)
但是对于左上左下怎么办呢? 因为有翻转 这个时候可以考虑用dfs中的晦朔来解决
完事了

参考文献

C++ 代码

pair<ll, ll> dfs(ll n, ll num) {// n表示 当前是第几级  num就是第几个房子
//  cout << "n : " << n << "   num : " << num << endl;   
    if(n == 1) {
        switch(num) {
            case 1: return pair <ll, ll> (1, 1);
            case 2: return pair <ll, ll> (2, 1);
            case 3: return pair <ll, ll> (2, 2);
            case 4: return pair <ll, ll> (1, 2);
        }
    } 
    ll ans = quick(2, 2 * (n - 1));//ans表示上一个图中点的数量 一边确定当前值的位置
    ll bian_x = quick(2, n - 1);// bian_x 表示上一个图的变长 用来所谓的加特定值
//  cout << ans << "  -  " << bian_x <<endl;
//  system("pause");
    int cnt = 0;
    pair <ll, ll> xx;
    switch ((num - 1)/ ans) {
        case 0: { // 如果 在 左上角 就得到上一个图的坐标后(晦朔) 以坐上到右下为轴翻转一下 
            xx = dfs(n - 1, num);
            pair <ll, ll> yy;
            yy.first = xx.second, yy.second = xx.first;
            return yy;
            break;
        }
        case 1: {
            xx = dfs(n - 1, num - ans);
            xx.first += bian_x;
            return xx;
            break;
        }
        case 2: {
            xx =  dfs(n - 1, num - 2 * ans);
            xx.first += bian_x;
            xx.second += bian_x;
            return xx;
            break;
        }
        case 3: {// 如果在 左下角 与在左上角同理
            xx = dfs(n - 1, num - 3 * ans);
            pair <ll, ll> yy;
            yy.first = bian_x - xx.second + 1, yy.second = bian_x - xx.first + 1;
            yy.second += bian_x;
            return yy;
            break;
        }
    }
}