NOIP提高组—— 问题求解 与 完善程序

问题求解1：

甲乙丙丁四人在考虑周末要不要外出郊游。
已知①如果周末下雨，并且乙不去，则甲一定不去；②如果乙去，则丁一定去；③如果丙去，则丁一定不去；④如果丁不去，而且甲不去，则丙一定不去。如果周末丙去了，则甲___去了___（去了/没去）(1 分)，乙___没去___（去
了/没去）(1 分)，丁____没去__（去了/没去）(1 分)，周末___没下雨___（下雨/没下雨）(2 分)。

分析：大水题，送分。只要别写错字就好了。

证明：

丙去了，联系③，丁不会去，一分 get

丁没去，联系②，乙不会去，一分 get

丁没去，丙去了，联系④，甲会去，一分 get

乙不去，甲去了，联系①，不会下雨，一分 get

问题求解2：

方程 a*b = (a or b) * (a and b)，在 a,b 都取 [0, 31] 中的整数时，共有   454   组解。（* 表示乘法；or 表示按位或运算；and 表示按位与运算）

分析：考场上蒙了蒙，感觉等式成立的条件应该是 a 是 b 二进制下的子集或者 b 是 a 的子集。 然鹅并没有证明出来，于是就组合数搞了一下 A 掉了

（我同桌其实也 A 掉了，而且他还证出来了只不过他算错了2333）。

于是先证明一下：

不妨设 t = a- (a & b) 。(一开始我是设 t = a&b 的，所以死活证不出来)， 于是 (x | y) = (y+t)

然后我们将 t 带入式子，得到： $a * b = ( a - t ) * ( b + t )$ 。

然后展开

=>  $a * b = a*b + a*t - b*t - t*t$

=>  $a*t - b*t - t*t = 0$ 

=>  $t * (a - b - t) = 0$ 

=> 1. t=0   ;   2. a=b+t

考虑 t=0 的情况，t 等于零 意味着 a = a&b ，那么也就说明二进制下的 a 被包含于 b 中。

再考虑 a=b+t 的情况，这意味着 b=a&b，那么也就说明二进制下的 b 被包含于 a 中。

于是我们得出结论： 若原式成立，则在二进制下，a 是 b 的子集，或者 b 是 a 的子集。

然后我们考虑到如果 a=b ，那么原式必然成立，所以我们先将答案加上 32 (0~31每个数都与自己匹配)，然后我们去讨论 b 是 a 的 真 子集情况，然后把讨论出来的答案 * 2 累加上去就好了。

那么我们先考虑 a 的数值。如果说这时候我们枚举 32 次，答案也是能出来的，但是这样做不仅低效率而且容易出错，那么我们考虑在用二进制的方法枚举 a 。

其实既然说了 b 是 a 的二进制真子集了，那么其实 我们只需要枚举在 log32 位空格（也就是 5 个空格）里面，放 k(k=0~5) 个 1 的方案就好了，因为这些数对答案的贡献是相同的，都是 k 个 1 里面计算真子集数。

那么方案数也就是组合数 C(5，k) 了。然后我们考虑在这 k 个位置里面安排 b 。 那么 b 的数值方案数也还是组合数，就是 $sigma_{s=1}^{k} C（k，s）$ 了。

然后我们将 $sigma_{s=1}^{k} C（k，s）$ 乘上 C（5，k），再乘以二，累加进答案就好了。

最近我听说这道题是吉老师出的啊？而且原数据范围是 [ 0~1023 ] 啊？不过后来谁验题后改成 [ 0~32 ] 了？ 反正不是杜雨皓【逃】

于是我们得出结论：吉老师是铁了心要给 zjoi 选手盖上棺材板了 （但愿复赛...咳咳）

emmm...其实1024的范围用上面的方法是可以做初步的运算的（唔，别打脸），只不过应该是要用到更高深的组合数学理论了吧？（反正我不会，组合数没好好学哈~）

完善程序1:

对于一个1到 𝑛 的排列 𝑃 （即1到𝑛中每一个数在𝑃中出现了恰好一次），令 𝑞𝑖 为第 𝑖 个位置之后第一个比 𝑃𝑖 值更大的位置，如果不存在这样的位置，则 𝑞𝑖 = 𝑛 +1 。举例来说，如果 𝑛 = 5且 𝑃 为1 5 4 2 3，则 𝑞 为2 6 6 5 6。
下列程序读入了排列 𝑃，使用双向链表求解了答案。试补全程序。（第二空2 分，其余3 分）
数据范围 1 ≤ 𝑛 ≤ 105。

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int L[N], R[N], a[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        (1)a[x]=i ;
    }
    for (int i = 1; i <= n; ++i) {
        R[i] = (2)i+1 ;
        L[i] = i - 1;
    }
    for (int i = 1; i <= n; ++i) {
        L[ (3)R[a[i]] ] = L[a[i]];
        R[L[a[i]]] = R[ (4)a[i] ];
    }
    for (int i = 1; i <= n; ++i) {
        cout << (5)R[i] << " ";
    }
    cout << endl;
    return 0;
}

不是很想说，因为我挂了。

这个其实就是双向链表，我们看第一个空，a[i] 就是指数字 i 所在的位置。

然后后面的三个空其实都是上下文对照着填就对了。 最后一个空的话，可以看出来是输出 R[i] ：位置 i 右边比它大的最近的数。

这个我没什么技巧了，毕竟都做错了。就是猜着填什么，模拟一遍对了就过吧。

完善程序2：

一只小猪要买N 件物品（N 不超过1000）。它要买的所有物品在两家商店里都有卖。第i 件物品在第一家商店的价格是a[i]，在第二家商店的价格是b[i]，两个价格都不小于0 且不超过10000。如
果在第一家商店买的物品的总额不少于50000，那么在第一家店买的物品都可以打95 折(价格变为原来的0.95 倍)。
求小猪买齐所有物品所需最少的总额。

输入：第一行一个数N。接下来N 行，每行两个数。第i 行的两个数分别代
表a[i]，b[i]。
输出：输出一行一个数，表示最少需要的总额，保留两位小数。
试补全程序。（第一空2 分，其余3 分）

于是不做分析，代码里面解释。

#include <cstdio>
#include <algorithm>
using namespace std;
const int Inf = 1000000000;
const int threshold = 50000;
const int maxn = 1000;
int n, a[maxn], b[maxn]; //表示价格
bool put_a[maxn]; //put_a[i]表示第 i 个物品是不是在 a 商场买的
int total_a, total_b;  //表示在 a 商场和 b 商场耗费的金钱
double ans;
int f[threshold];  //这个是重点： f[i] 表示从 当前前缀状态下， 买总价格为 i 的物品，所需要去 b 商场的最小花费
int main() {
    scanf("%d", &n);
    total_a = total_b = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", a + i, b + i);
        if (a[i] <= b[i]) total_a += a[i];
        else total_b += b[i];
    }
    ans = total_a + total_b; //不考虑优惠，直接算一遍答案
    total_a = total_b = 0;
    for (int i = 0; i < n; ++i) {
        if ( (1)a[i]*0.95<=b[i] ) {//考虑优惠且必须优惠（因为不优惠的状况考虑过了），只要 a[i] 在优惠状态下 <= b[i] 就选 a
            put_a[i] = true;
            total_a += a[i];
        } else {
            put_a[i] = false;
            total_b += b[i];
        }
    }
    if ( (2)total_a>=50000 ) { //如果说total_a 已经达到优惠所需最小花费，那么直接输出答案（这时把任何 b 商场里的东西换到 a 商场买不会更优）
        printf("%.2f", total_a * 0.95 + total_b);
        return 0;
    }
    f[0] = 0;
    for (int i = 1; i < threshold; ++i)
        f[i] = Inf;
    int total_b_prefix = 0;
    for (int i = 0; i < n; ++i)
        if (!put_a[i]) { //如果是去 b 商场买的就考虑背包转移
            total_b_prefix += b[i]; //当前去 b 商场买的物品所花费总代价
            for (int j = threshold - 1; j >= 0; --j) {
                if ( (3)total_a + j + a[i] >= threshold && f[j] != Inf)  //如果说可以转移
                    ans = min(ans, (total_a + j + a[i]) * 0.95 + (4)total_b + f[j] - total_b_prefix ); //判断是否更优
　　　　　　　　　　　　//当前去 a 商场的总花费加上背包体积以及当前物品，乘以折扣，在加上去 b 商场购买的总价值，是否小于 ans
                f[j] = min(f[j] + b[i], j >= a[i] ? (5)f[j-a[i]] : Inf); //背包转移
　　　　　　　　　　//考虑当前的 j 大小的背包是加上b[i] 更优还是直接靠 f[j-a[i]] 转移更优（就是考虑当前的背包是加上代价还是状态转移）
            }
        }
    printf("%.2f", ans);
    return 0;
}