2015年3月

数学#1又砸了……
没做完啊……而且前面不保证正确率……
完了这学期看来是回不去了只能AFMO啊……

算了给自己定一个目标吧:#2的时候做完整张卷。

被虐了不解释……只求个三等……
选择填空居然错了两题……二试第一题脑残其实只要把负根舍去就只有一个根了……第二题相似漏了写等角……第三题发现不可做然后推翻过程咱还没写完呢(哭……
果然小学没学好MO初中只靠自己看书就是等价于有先天缺陷啊……
有空再补上总结……?

Segment tree.
祝卡cin/cout的出题者全·家·爆·炸!

#include <cstdio>
#include <cstring>
#include <limits> 
#include <algorithm>
using namespace std;
namespace DEL
{
    int n;
    template<int maxn, class T>
    class SegmentTree
    {
    private:
        T maxv[maxn*3], minv[maxn*3];
        T left, right, v;
        T _max, _min;
    public:
        void init()
        {
            memset(maxv, 0, sizeof maxv);
            memset(minv, 0, sizeof minv);
            _max = 0;
            _min = numeric_limits<T>::max(); 
        }
        void set(int l, int r, int _v)
        {
            left = l, right = r, v = _v;
        }
        void update(T o = 1, T L = 1, T R = n)
        {
            if(L == R)
            {
                maxv[o] += v;
                minv[o] += v;
            }
            else
            {
                T lc = o << 1, rc = lc + 1, M = (L + R) / 2;
                if(left <= M)
                    update(lc, L, M);
                else
                    update(rc, M + 1, R);
                maxv[o] = max(maxv[lc], maxv[rc]);
                minv[o] = min(minv[lc], minv[rc]);
            }
        }
        void query(T o = 1, T L = 1, T R = n)
        {
            if(left <= L && R <= right)
            {
                _max = max(_max, maxv[o]);
                _min = min(_min, minv[o]);
            }
            else
            {
                T lc = o << 1, rc = lc + 1, M = (L + R) / 2;
                if(left <= M)
                    query(lc, L, M);
                if(M < right)
                    query(rc, M + 1, R);
            }
        }
        T get()
        {
            int ans = _max - _min;
            _max = 0;
            _min = numeric_limits<T>::max(); 
            return ans;
        }
    };
}
using namespace DEL;
SegmentTree<(int)5e4 + 10, int> st;
int q;
int main()
{
    st.init();
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++)
    {
        int tmp;
        scanf("%d", &tmp);
        st.set(i, 0, tmp);
        st.update();
    }
    while(q--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        st.set(a, b, 0);
        st.query();
        printf("%d\n", st.get());
    }
    return 0;
}

一道很有趣的题。代码也很短。
第一反应是gcd,事实证明我对了。只要略微变动一下gcd即可。
下面贴出只有16行的代码,顺便说一句咱是1次AC。

#include <iostream>
using namespace std;
long long gcd(long long a, long long b)
{
    if(a == 0 || b == 0)
        return 0;
    return a / b + gcd(b, a % b);

}
int main()
{
    long long a, b;
    cin>>a>>b;
    cout<<gcd(a, b)<<endl;
    return 0;
}