题意

给定一个平面\((n,m)\)，处理如下操作：

• OPT = 1：使点\((x,y)\)处使横纵行全部0/1取反。
• OPT = 2：矩形\((x_1,y_1,x_2,y_2)\)内的和。

Continue reading →

A – Binary & B – Chess

傻逼题，不分析。

C – Sum

这道题非常的有趣（精心调参之后随机化程序可以拿 90 分），正解非常的巧妙。我们可以把问题化为求\(min\{ S_{i,j} \mod P, K \leq S_{i,j} \mod P\}\)。我们先用\(O(n)\)的时间来进行前缀和的预处理，之后我们倒序处理前缀和，从后往前加入 set。在加入 set 的过程中二分查找\(s[i]+k\)和\(s[i]+k-p\)这两个目标最优解，之后记录答案即可，非常的巧妙。

// C.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 100010;
int n, k, p, ans = 0x7f7f7f7f, s[MAX_N];
set<int> st;
int main()
{
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 1; i <= n; i++)
        scanf("%d", &s[i]), (s[i] += s[i - 1]) %= p;
    set<int>::iterator it;
    st.insert(s[n]);
    for (int i = n - 1; i >= 1; i--)
    {
        it = st.lower_bound(s[i] + k);
        if (it != st.end())
            ans = min(*it - s[i], ans);
        it = st.lower_bound(s[i] + k - p);
        if (it != st.end() && *it < s[i])
            ans = min(*it - s[i] + p, ans);
        st.insert(s[i]);
    }
    printf("%d", ans);
    return 0;
}

D – Jail

哦，傻逼题。——crazydave

这道题算是套路吧，用状态压缩枚举每一维符号的状态，求出最大最小值，最大值减去最小值（最小值代表着状态相反的曼哈顿贡献）即可。

// D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000010;
int n, d, info[MAX_N][6], st[10], ans;
void calc(int stat)
{
    int mn = (1 << 29), mx = -mn;
    for (int i = 1; i <= d; i++, stat >>= 1)
        st[i] = stat & 1;
    for (int i = 1; i <= n; i++)
    {
        int acc = 0;
        for (int j = 1; j <= d; j++)
            acc += (st[j] == 1) ? info[i][j] : -info[i][j];
        if (acc != 0)
            mn = min(mn, acc), mx = max(mx, acc);
    }
    ans = max(mx - mn, ans);
}
int main()
{
    scanf("%d%d", &n, &d);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= d; j++)
            scanf("%d", &info[i][j]);
    for (int i = 0; i < (1 << d); i++)
        calc(i);
    printf("%d", ans);
    return 0;
}

思路

好神仙啊。

这道题思路非常的巧妙。答案很容易可以知道，为

\[ ans = \lfloor \sum_{i=1}^{n} \frac{L*C*speed[i]}{maxSpeed*C} \rfloor \]

化简得：

\[ ans = \lfloor \sum_{i=1}^{n} \frac{L*speed[i]}{maxSpeed} \rfloor \]

如果我们统计括号内的实数集和的话，会出现一些只有在计算机上才会出现的恶心误差，所以我们可以考虑分开取整再求和。这里有一个小技巧，对于两个数而言：

\[ \lfloor a – b \rfloor = \begin{cases} \lfloor a \rfloor – \lfloor b \rfloor, a的小数部分 \leq b的小数部分 \\ \lfloor a \rfloor – \lfloor b \rfloor – 1, a的小数部分>b的小数部分 \end{cases} \]

在判断小数部分的时候，我们可以把小数部分之间的大小关系转化为余数之间的大小关系进行判断，答案默认减掉那个取整的1，然后用树状数组补全那些被误删的取整项。

代码

// FOJ2930.cpp
#include <bits/stdc++.h>
#define ll long long
#define lowbit(p) (p & -p)
using namespace std;
const ll MAX_N = 1e5 + 200;
ll n, l, c, spd[MAX_N], mxspd, f[MAX_N], tree[1000100];
void update(int num)
{
    num++;
    while (num <= mxspd)
        tree[num] += 1, num += lowbit(num);
}
ll sum(int num)
{
    num++;
    ll ans = 0;
    while (num)
        ans += tree[num], num -= lowbit(num);
    return ans;
}
int main()
{
    scanf("%lld%lld%lld", &n, &l, &c);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &spd[i]);
    sort(spd + 1, spd + 1 + n), mxspd = spd[n];
    for (int i = 1; i <= n; i++)
        f[i] = (l * spd[i]) / mxspd;
    update((l * spd[1]) % mxspd);
    ll prefix = f[1], ans = 0;
    for (int i = 2; i <= n; i++)
    {
        prefix += f[i];
        ans += i * f[i] - prefix - i;
        update((l * spd[i]) % mxspd);
        ans += sum((l * spd[i]) % mxspd);
    }
    printf("%lld", ans);
    return 0;
}