#EDU 137

A：

题目：

已知手机密码由四位数字组成，且密码有恰好两个不同的数组组成，且每个密码都出现了两次。

并且给出一些用不到的数字

问你可能是手机密码的不同序列的数量。

思路：

找出可能用到数字的次数，然后组合数，从几个中任意选2个的所有可能性的次数

代码

void init()
{
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
            if(!j) c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1]);
}

void solved()
{
    memset(st, 0, sizeof st);

    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        st[x] = true;
    }

    int cnt = 0;

    for(int i = 0; i < 10; i++)
    {
        if(st[i] == false) cnt++;
    }

    cout << 6 * c[cnt][2] << endl;


}

B

题目：

给出一个由 1- n 的不同数组组成的排列。

定义一个排列的值为，他的所有连续子序列中符合 1-长度不同数字组成的序列的个数

问你构造一个长度为 n 的排列，并且他的值最小。

思路：
观察样例不难发现，最小为2，分别为 只要 1的单独子序列，和含有全部数字的子序列。

首先除了 1，单个能组成外，其他都要从 2开始，所以不妨把 2 和 1 只要不在连续的位置即可。

那么把 1放开头，2放结尾，这样不会出现只要 1 和 2 存在的子序列，也就没有其他的连续子序列。

代码

void solved()
{
    int n;
    cin >> n;

    a[1] = 1, a[n] = 2;

    cout << 1 << " ";

    for(int i = 2; i <= n - 1; i++) cout << i + 1 << " ";
    cout << 2 << " ";

    cout << endl;

}

C：

题目：

已知存在 n 个盒子，每个盒子中都有一些杂志。现在下雨了，现在只有一些盒子有盖子。

我们在同一时间可以进行多次操作。但每个盖子只能被操作一次。

操作 ：如果 i - 1 个盒子存在的话，将盖子放到 i - 1个盒子上。

问你在操作后能保存的最大杂志个数是多少。

思路：

因为每个盖子只能向左一个转移。所以每个盖子移动的区间就是他的前一个，如果考虑连续的1，那么区间会增长。

所以不妨对每个连续的1，加上左边的0，为一个区间。例如 0111 就是一个区间。

那么双指针，每次找到这样的区间，然后取区间内前 1 的个数大的数字即可。这样就是区间的最优选取。

代码

void solved()
{
    memset(st, 0, sizeof st);

    int n;
    cin >> n;
    cin >> s + 1;
    for(int i = 1; i <= n; i++)
        cin >> a[i];

    int ans = 0;

    for(int i = 1; i <= n; i++)
    {
        if(s[i] == '1')
        {
            int j = i + 1;

            while(s[j] == '1') j++;
            j--;

            vector<int>tem;

            for(int k = i - 1; k <= j; k++)
            {
                tem.push_back(a[k]);
            }

            sort(tem.begin(), tem.end());
            reverse(tem.begin(), tem.end());

            for(int k = 0; k < j - i + 1; k++)
            {
                ans += tem[k];
            }

            i = j;
        }
    }

    cout << ans << endl;

}