about 2 years ago

嘟噜噜... 还有一个月就NOIP了,AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧

简单写点弱鸡题解, 第一是督促一下作业进度,第二呢也可以来熟悉一下输入法。岂不是很妙。


FoxAndMountainEasy

关键词:小学数学

算法简述

可以根据高度差来计算出U和D的数量,这里在计算的时候要处理一些非法的情况。由于还要满足这个条件,找到模式串中前缀最小的一个位置,计算它是否可行就行了。

一点点小代码

class FoxAndMountainEasy {
    public:
        string possible(int n, int h0, int hn, string history) {
            int num = 0; //history中U的个数
            for (int i = 0; i < history.size(); ++i) if (history[i] == 'U') ++num;
            int U, D; // U D 的个数

            if ((n + hn - h0) & 1) return "NO";
            U = (n + hn - h0) / 2;
            D = n - U;
            if (U < 0 || D < 0) return "NO"; //去掉不可到达的情况

            if (num > U || history.size() - num > D) return "NO"; //如果history中的U或D超过了实际的数量就不合法
            int lim = h0 + U - num;
            for (int i = 0; i < history.size(); ++i) { //还要满足h[i] >= 0 这个条件 计算最小的前缀是否可行
                if (history[i] == 'U') ++lim;
                else --lim;
                if (lim < 0) return "NO";
            }
            return "YES";
        }
};

Incubator

关键词:Dilworth定理,二分图匹配

算法简述

这个题目模型非常显然,就是要求一个最大的点集使得点集中任意两点在DAG中不可达。这是一个经典的问题,就是求这张DAG的最长反链。这个只要对DAG求传递闭包后计算最小链覆盖即可,求DAG最小链覆盖是个更加经典的问题,就不赘述了。

一点点小代码

int a[100][100];
int link[100];
bool vis[100];
int n;
int find(int x) { //匈牙利算法
    REP(i, 0, n - 1) if (vis[i] && a[x][i]){
        vis[i] = 0;
        if (link[i] == -1 || find(link[i])) {
            link[i] = x;
            return true;
        }
    }
    return false;
}
class Incubator {
    public:
        int maxMagicalGirls(vector<string> love) {
            CL(a, 0);
            n = love.size();
            REP(i, 0, n - 1) REP(j, 0, n - 1) a[i][j] = (love[i][j] == 'Y');
            REP(k, 0, n - 1) 
                REP(i, 0, n - 1)
                    REP(j, 0, n - 2) a[i][j] |= (a[i][k] & a[k][j]);//对DAG求传递闭包,这是应用Dilworth定理非常重要的一步

            CL(link, 0xff);
            int match = 0;
            REP(i, 0, n - 1) {
                CL(vis, 1);
                match += find(i);
            }
            return n - match; //DAG传递闭包的最小链覆盖等于点数 - 最大匹配 
     }
};

XorAndSum

关键词:异或方程组、贪心

题目简述

给你个数,你可以进行若干次操作,每次操作有如下两步:

  • 选择两个数
  • 保持不变,并将替换为

其中为异或运算。

你可以进行若干次操作,使得最终个数之和尽可能大。

算法简述

熟悉异或方程组的话,就能一眼看出来,这个题目就是给定了一组线性基,要你求个和最大数,且这些数组成的线性基等价于它。这个问题就分为两步,第一步就是把这个线性基求出来,第二步就是求这个线性基能生成的最大的个数(其中是这个线性基的秩)。这个在求线性基的时候只要把每个数的最高位当成主元来消就可以了。这样消出来的线性基就可以用贪心的方法来求出最大的个数了。当然还有个小问题,如果秩小于怎么办,这种情况只要把多出来的那些数都定为这组基能产生的最大的数就可以了。

一点小代码

vector<LL> base; //线性基
LL highbit(LL x) {
    for (int i = 60; i >= 0; --i) if (x & (1LL << i)) return (1LL << i); //计算最高位
}
void add(LL x) { //往线性基里加元素
    for (int i = 0; i < base.size(); ++i) {
        LL p = highbit(base[i]);
        if (x & p) x ^= base[i];
    }
    if (!x) return;
    LL p = highbit(x);
    for (int i = 0; i < base.size(); ++i) {
        if (base[i] & p) base[i] ^= x;
    }
    base.PB(x);
}
class XorAndSum {
    public:
        long long maxSum(vector<long long> number) {
            base.clear();
            int n = number.size();
            REP(i, 0, n - 1) add(number[i]);
            LL sum = 0, ans = 0;
            int m = base.size();
            REP(i, 0, m - 1) sum ^= base[i];

            ans = sum * (n - m + 1);  //对于超出线性基秩的部分 全都取最大的
            sort(base.begin(), base.end());
            REP(i, 0, m - 2) ans += (sum ^ base[i]); //贪心地选择最优的
         return ans;
        }
};
← SRM 561 弱鸡题解 SRM 593 弱鸡题解 →
 
comments powered by Disqus