10.29考试题

· · 个人记录

T1

题目描述

这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！

输入格式：

一行包含两个整数N，M，之间由一个空格隔开。

输出格式：

总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果

Input
1 3
Output
7

题意分析

我们对于当前这一行的话 有六种情况

1.老子不放

2.在已有一个棋子的列上放一个

3.在没有棋子的列上放一个

4.在没有棋子的两列上放两个

5.在有一个棋子的两列上放两个

6.在没有棋子的一列以及有一个棋子的一列上各放一个

CODE:

/*-------------OI使我快乐-------------*/
int n,m;
int dp[110][110][110];
IL int C(int x)
{
    return (((x)*(x-1))>>1);
}
signed main()
{
//    freopen("cannon.in","r",stdin);
//    freopen("cannon.out","w",stdout);
    read(n);read(m);
    dp[0][0][0]=1;
    for(R int i=0;i<=n;++i)
     for(R int j=0;j<=m;++j)
      for(R int k=0;(j+k)<=m;++k)
       if(dp[i][j][k])
       {
        dp[i+1][j][k]=(dp[i][j][k]+dp[i+1][j][k])%mod;       
        if(j>=1) dp[i+1][j-1][k+1]=(dp[i+1][j-1][k+1]+dp[i][j][k]*j)%mod;
        if((m-k-j)>=1) dp[i+1][j+1][k]=(dp[i+1][j+1][k]+dp[i][j][k]*(m-k-j))%mod;
        if(j>=2) dp[i+1][j-2][k+2]=(dp[i+1][j-2][k+2]+dp[i][j][k]*C(j))%mod;
        if((m-k-j)>=2) dp[i+1][j+2][k]=(dp[i+1][j+2][k]+dp[i][j][k]*C(m-k-j))%mod;
        if((m-k-j)>=1 && j>=1) dp[i+1][j][k+1]=(dp[i+1][j][k+1]+dp[i][j][k]*j*(m-k-j))%mod;
       }
    int ans=0;
    for(R int i=0;i<=m;++i)
     for(R int j=0;(i+j)<=m;++j)
      ans=(ans+dp[n][i][j])%mod;
    printf("%lld\n",ans);     
    return 0;    
}

T2

题目描述

著名的N皇后问题。

输入格式：

第一行有一个N。接下来有N行N列描述一个棋盘，“* ”表示可放“.”表示不可放。

输出格式：

输出方案总数

Input
4
**.*
****
****
****
Output
1

题意分析

一般的八皇后问题可以使用暴搜

但是面对本题的数据范围 只好使用状压

1.行

顺序递推即可

2.列

我们使用一个累加的二进状态来判重

3.对角线

思考一下

左对角线

1001010 当前行

0000100 下一行

>>

右对角线

1001010

0010000 下一行

<<

所以我们就是用位运算累加来判断

4.当前计算方案

我们得到当前的状态是 10100101

那么我们按位取反之后就是 01011010

然后再使用一个lowbit来计算状态

CODE:

/*-------------OI使我快乐-------------*/
char Map[21][21];
int n,ans,all;
int key[21];
IL void dfs(R int now,R int led,R int rid,R int dep)
{
    if(dep==n+1) {++ans;return;}
    R int pos=all&(~(now|led|rid|key[dep]));
    while(pos)
    {
        R int p=(pos)&(-pos);
        pos-=p;
        dfs(now+p,(led+p)<<1,(rid+p)>>1,dep+1); 
    }
}
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(n);all=(1<<n)-1;
    for(R int i=1;i<=n;++i)
    {
        scanf("%s",Map[i]+1);
        for(R int j=1;j<=n;++j)
        if(Map[i][j]=='.')key[i]+=(1<<(n-j));
    }
    dfs(0,0,0,1);
    printf("%d\n",ans);
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

T3

【题目描述】

小林来到商店中进行购物。商店里一共有 n 件物品，第 i 件物品的价格为 a[i]元。

小林总共需要购买 m 件物品，他希望他所花费的钱最少，请你计算出最小花费。

由于输入的数据数量过大，我们采用一种加密的方式进行输入。给出两个密 钥 x 和 y。则 a[1] = x, a[i] = (y* a[i-1] + x)\% 10^9。

【输入格式】

一行两个整数 n 和 m。 第二行共两个整数 x 和 y，表示密钥。

【输出格式】

输出只有一个整数，表示最小花费。

【样例输入】

5 3

2 9

【样例输出】

204

【数据规模】

对于 50%的数据，n <= 1000； 对于 100%的数据，1 <= n <= 10^7, 1 <= m <= 100, 1 <= x,y < 10^9。 对于 100%的数据，保证 m <= n

【题意分析】

一般思路是模拟存储 然后sort

尽管作为STL最快的函数没有之一加上数据水直接过了

但是sort的复杂度是O(nlog_n)面对n<=10^7有那么些许吃力

所以我们可以考虑维护一个大小只有m的容器

我们把每一次计算来的值桶当前容器最优解内的最大值进行一个比较

然后比起小的话 就进入容器中

至于维护最优解的容器

你可以使用 二分查找维护一个数组 但是

我想没有什么是比堆再好不过的数据结构了                              
                                                                 ---------沃兹基硕德

CODE:

/*-------------OI使我快乐-------------*/
priority_queue<ll> Q;
ll n,m,x,y,now,ans;
int main()
{
    freopen("shop.in","r",stdin);
    freopen("shop.out","w",stdout);
    read(n);read(m);read(x);read(y);
    now=x;Q.push(x);
    for(R ll i=2;i<=n;++i)
    {
        now=(now*y+x)%mod;
        if(Q.size()<m)
        {
            Q.push(now);
        }
        else
        {
            if(now<Q.top())
            {
                Q.pop();
                Q.push(now);
            }
        }
    }
    while(!Q.empty())
    {
        ans+=Q.top();Q.pop();
    }
    printf("%lld\n",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

T4

【题目描述】

我们知道，若一个随机变量 X，在 p_i 的概率下，它的值等于 x_i，则它的数学期望 \sum x_i* p_i

现在有如下一个表达式：

0\ a_1\ b_1\ a_2\ b_2\ .\ .\ .\ a_n\ b_n

其中 a_i 为一个位运算符，是“和”“或”“异或”三者中的一种，b_i 是一个整数。

求这一表达式的值是一件容易的事，然而刚学完数学期望的小林在思考，如果每一对 a_i\ b_i 有 c_i 的概率会消失，那么这一表达式的结果的数学期望是多少。

【输入格式】

第一行只有一个正整数 n。

第二行为 n 个整数表示 n 个运算符 ai，0 表示 and，1 表示 or，2 表示 xor。

第三行为 n 个非负整数 bi。

第四行为 n 个实数 ci（不超过三位小数）。

【输出格式】

只有一个实数，表示表达式的数学期望，保留一位小数。

【样例输入】

2

1 2

5 7

0.5 0.5

【样例输出】

3.5

【数据规模】

对于 30%的数据，1 <= n <= 10,0 <= bi <= 20；

对于 70%的数据，1 <= n <= 100,0 <= bi <= 1000；

对于 100%的数据，1 <= n <= 100000,0 <= ai <= 2,0 <= bi < 2^31。

对于 100%的数据，0 <= ci <= 0.999