CF262A

题意：

罗马(一个流行的俄罗斯名字，意思是“罗马”)喜欢小利沃夫大象的幸运数字。
让我们提醒您，幸运数字是正整数，其十进制表示只包含幸运数字 4 和 7 。例如，数字 47 、 744 、 4 是幸运数字，而 5 、 17 、 467 是不吉利数字。
罗马有 _n_ 个正整数。他想知道，这些整数中有多少的幸运数字不超过 $k$ ？帮他写解决问题的程序。

题解：

每个数字检测数位有几个4和7，如果个数大于等于k了就答案+1.

CF262B

题意：

罗玛在一家卖电视的公司工作。现在他要准备一份去年的报告。
罗玛有一份公司的收入清单。列表是一个由 $n$ 个整数组成的序列。公司的总收入是按顺序排列的所有整数的总和。罗马决定对数列中几个数字的符号进行精确的 $k$ 更改。他还可以改变数字的符号一次，两次或更多次。
改变一个数的符号的操作将这个数乘以- 1 。
帮助Roma执行更改，以使公司的总收入(结果序列中的数字总和)最大化。注意，Roma应该执行完全 $k$ 更改。

题解：

贪大心，先挑好的，然后最后看看有没有剩的，有的话是偶数就不管是奇数就挑个最小的变成负数

R1T3

题面

给出若干个打折优惠：买 $q_i$ 送 $2$，送的物品最大值不能高于买的物品最小值。问买完所有东西的最小价格是多少。

题解

很显然送的物品是固定的，所以买的越少越赚。所以就是纯模拟了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
sort(q + 1, q + m + 1);
sort(a + 1, a + n + 1);
int i = n; ll ans = 0;
// 注意不能写成 i >= q[1] + 2，因为我们不仅可以送两个，在物品不够的情况下也可以直送一个或者一个不送
while(i >= q[1]) { 
    for(int k = 1; k <= q[1]; k++, i--) {
        ans += a[i];
        // cout << i << ' ';
    }
    i -= 2;
}
for( ; i >= 1; i--) ans += a[i];
printf("%lld\n", ans);

R1T4

题面

$n$ 个客人排成一队去吃饭。每个客人有一个宽度 $a_i$ ，但是饭桌的大小有限，只能容纳下 $p$ 的宽度。所以客人们依次进入直到进不去为止。

现在 $n$ 个客人以所有可能的形式排列去吃饭(即全排列)，求每次吃饭人数的数学期望。

题意

考虑每一次到了哪一个客人就会导致桌子坐满。

考虑背包记录前 $i$ 个人选 $j$ 个并且体积恰好为 $k$ 的方案数。那么每一次的答案可以表示为：

简单理解为 $i$ 是权重，$1/n$ 是导致桌子坐满的客人。再由期望线性性可以直接相加。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
if(sum <= P) {
    printf("%.4lf\n", 1.0 * n);
    return ;
}
Init();
double ans = 0;
for(int ne = 1; ne <= n; ne++) {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        if(i == ne) continue;
        for(int j = n - 1; j >= 1; j--) {
            for(int v = P; v >= a[i]; v--) {
                dp[j][v] += dp[j - 1][v - a[i]];
            }
        }
    }
    for(int i = 0; i < n; i++) {
        for(int v = 0; v <= P; v++) {
            if(v + a[ne] > P) {
                ans += i * (1.0 * dp[i][v] / C[n-1][i]) / n;
            }
        }
    }
}
printf("%.4lf\n", ans);

R1T5：

题意：

​ 给你一份伪代码如下：

​

​ 根据这份代码生成一个 $(m+1)*(m+1)(m \le n)$ 的矩阵，问你第 $m+1$ 行的 1 的个数总和为 $t$ 的方案数有多少个。

题解：

​ 观察到数据范围异常的大，所以我们肯定要小数据打表找规律。通过找规律我们找到了个很神奇的答案序列：$1 2 1 2 2 4 ……2 4 4 8……$。不难发现 1 的个数都为 2 的整数次幂，所以如果输入的 t 不是 2 的整数次幂，那肯定答案是 0。然后发现数跟二进制有关，所以我们不妨手摸一下，发现 $n+1$ 的二进制的 1 的个数就是对应答案。所以原问题就变成了在 $1-n$ 中找到所有二进制 1 的个数为 t 的数。需要注意，如果 $t=1$，那么答案显然要少一。所以我们用数位 $dp$ 求解。我们设 $dp_{i,j}$ 表示，共有 $i$ 位，1 的个数为 $j$ 的方案数。容易推出来 $dp_{i,j}+=dp_{i,j-1}+dp_{i-1,j-1}$。求答案的时候我们枚举每一位，如果当前位置为 1，那么后面可以随便取，计算答案即可，否则直接跳过，非常简单。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t,flag,a[550],tot,dp[555][555],ans;
 
signed main()
{
    cin>>n>>t;
    if(n==1||t==1)ans--;
    n++;
    while(t)
    {
        flag+=t%2;
        a[++tot]=t%2;
        t/=2;
    }
    if(flag>1)
    {
        cout<<0<<endl;
        return 0;
    }
    dp[0][0]=1;
    for(int i=1;i<=55;i++)dp[i][0]=1;
    for(int i=1;i<=55;i++)
        for(int j=1;j<=i;j++)
            dp[i][j]+=dp[i-1][j]+dp[i-1][j-1];
    for(int i=55;i>=0;i--)
        if((n>>i)&1&&tot>=0)
            ans+=dp[i][tot--];
    if(tot==0)ans++;
    cout<<ans<<endl;
    return 0;
}