测试原链接：TJU暑期训练 个人排位赛（二）

题目来源：Atcoder-abc297; Atcoder-abc298;

题目考点：广搜，概率与期望，博弈论，卷积，离散化（板子），和的用法

AT-6 chess960

Problem Statement

纯粹的就提一句，做这个题的时候纯粹的脑子有病……就非得拿数组存搁这儿秀智商下限……

虽然也是数字，但问题在于，这玩儿是一个字节的，数组是个字节，存储都不匹配,根本存不进去…………

AT-7 Kth Takoyaki Set

Problem Statement

题目大意：

有种商品，每一种商品可以买多个，每种商品价格,求购买的第小花费。

题目分析

买东西的时候先将所有单价一遍不用多说，当时上来就这么做了，买东西想要价格小必然先买便宜的。

一开始的时候我试图按照插件的思想来思考购买最小，因为第小的花费一定是只买一个物品并且买价格最低的那个，然后以这个为基准修正其他物品的价格为二者之差（类似于查分）来维护，结果很快就发现不对——在样例的第小的时候就产生了偏移不符。至于说为什么是按照这个想的，就是因为当时注意到可能会出现某个物品买3个是第小，但是某个物品买下来却是第小，我试图找出来怎样判断是买个的时候还是买的时候会有第小,然后不出所料的就寄了…………

其实这个题不应该纠结的是买什么玩意儿会第小，真正应该关心的是这些东西怎么买，至于说买的总价格先不关心，我知道怎么买得了价格不就好说了。

而买的情况无非就是每次购买都有十种可能，买个物品的总方案数是…………

等等，这个玩意儿不是无限的吗？

这个就是考场上扼杀我想法的第二个最为重要的关键，最后根本就没有往枚举的想法上靠拢。

这个玩意儿是无限的，但是，对于每一次购买，你都有且仅有十种可能，这就足够了。

那说这么多，你这第小，怎么解决？你买第个物品后再买其他的甚至可能比你买别的都便宜，并不符合严格的单调递增，你怎么确定第小？

很简单，当时只盯着第小不放，忽略了一个事情——找不到间谍，那就把所有可疑人员全杀了。

就是说，把前种可能全部算出来。

至于说前小顺序的维护，交给STL中容器。它会按照大小顺序将容器内数字从小到大排列。

那就好说了。我不关心每次购买之前都是怎么买的，我关心的只有当下方案可以怎么买。

当前状态最小的花费的方案上再去买肯定是相对最小的（这些的花费一定比在你的其他第二、第三小等花费方案上购买时要小，所以也会率先填满前K次的所有花费可能）那么每次从队列中取出当前的最小的花费总额作为全局的第小花费扔进集合，按照相对从小到大的十种购买可能枚举可能花费，逐一再扔回广搜队列，关于排序的问题让自己去操心就行了，这样我们就能将前小的所有可能全部都干穿（每次从队列取全局最小，保证小花费的连续性）。当有个元素的时候，就停下来。

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,k,a[11];
set<long long> s,q;
int main()
{
    #define int long long
    cin>>n;
    cin>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s.insert(a[i]);
    }
    while(q.size()<=k)
    {
        int top=*s.begin();
        s.erase(top);
        q.insert(top);
        for(int i=1;i<=n;i++)
        s.insert(top+a[i]);
    }
    for(int i=1;i<k;i++)
    {
        q.erase(*q.begin());
    }
    cout<<*q.begin()<<endl;
    system("pause");
    return 0;
}

AT-8 Minimum Bounding Box 2

Problem Statement

题目大意：

定义事件为在 的矩形中随机撒个点，定义能包围所有点的最小矩形面积为本次撒点的得分。求得分期望

题目分析

第一次接触概率学的数学题，上来啥都不会，听我儒哥一分析真的好简单…………

其实就是个纯粹的数学题。放到高考的试卷上都没准比比赛时想得明白。

得分期望就是每种得分可能乘上该得分情况出现的概率。

首先想，得分是矩形面积，那么得分为就是矩形面积为.对于每一个得分的矩形都有很多种可能(种，从到),累计计算过于麻烦。

所以，我们将情况按照矩形形状来分。

设函数为矩形能够满足要求的总概率，那么

讨论等于多少，发现如果要求恰好能够包住的前提是矩形的每一个边上都至少有一个点，否则必定会有更小的矩形能够满足条件。这部分就是容斥原理。

全部的可能是

存在某一条边上没有点的可能是

存在某两条边没有点的可能是

存在三条边没有的可能是

存在四条边没有的可能是

所以总的情况数就是

但是还是有个前提：想要加上或者减去某一项，必须保证组合数的底是两个正整数相乘（不能出现负负得正）以及组合数的底大于等于.否则该情况的可能就是为，不需要再参与运算。强行参与运算会导致错误（WA了无数发）

int f(int i,int j)
{
    int answ=c[i*j]%mod;
    if(i>1)if((i-1)*j>=k)(answ-=2*c[(i-1)*j])%=mod;
    if(j>1)if((j-1)*i>=k)(answ-=2*c[(j-1)*i])%=mod;
    if(j>2)if((j-2)*i>=k)(answ+=c[(j-2)*i])%=mod;
    if(i>2)if((i-2)*j>=k)(answ+=c[(i-2)*j])%=mod;
    if(i>1&&j>1)if((i-1)*(j-1)>=k)(answ+=4*c[(i-1)*(j-1)])%=mod;
    if(i>1&&j>2)if((i-1)*(j-2)>=k)(answ-=2*c[(i-1)*(j-2)])%=mod;
    if(i>2&&j>1)if((j-1)*(i-2)>=k)(answ-=2*c[(j-1)*(i-2)])%=mod;
    if(i>2&&j>2)if((i-2)*(j-2)>=k)(answ+=c[(j-2)*(i-2)])%=mod;
    //最后一错，组合数不能出现负负得正，(i-2)*(j-2)各项均必须为正
    if(answ<0)(answ+=mod)%=mod;
    return answ;
}

然后就是关于对概率求模的问题。分数求模通过的是逆元来实现。也就是将

同等的转化成了

称为的逆元,记作，一般的，有

逆元即可视为的等价代表，所以逆元可以相乘来表示：

所以阶乘的逆元和组合数的逆元就可以求出

int frac[1000001]={1},inv[1000001]={1},c[1000001];
int quickpow(int a,int n)
{
    int e=1;
    while(n)
    {
        if(n&1)(e*=a)%=mod;
        n>>=1;
        (a*=a)%=mod;
    }
    return e;
}
int C(int n,int m)
{
    if(n<m)return 0;
    return frac[n]*inv[n-m]%mod*inv[m]%mod;
}
void init()
{
    cin>>h>>w>>k;
    for(int i=1;i<=h*w;i++)frac[i]=frac[i-1]*i%mod,inv[i]=inv[i-1]*quickpow(i,mod-2)%mod;//阶乘逆元累乘计算
    for(int i=k;i<=h*w;i++)c[i]=C(i,k);
}

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353
int h,w,k;
int frac[1000001]={1},inv[1000001]={1},c[1000001];
int quickpow(int a,int n)
{
    int e=1;
    while(n)
    {
        if(n&1)(e*=a)%=mod;
        n>>=1;
        (a*=a)%=mod;
    }
    return e;
}
int C(int n,int m)
{
    if(n<m)return 0;
    return frac[n]*inv[n-m]%mod*inv[m]%mod;
}
void init()
{
    cin>>h>>w>>k;
    for(int i=1;i<=h*w;i++)frac[i]=frac[i-1]*i%mod,inv[i]=inv[i-1]*quickpow(i,mod-2)%mod;
    for(int i=k;i<=h*w;i++)c[i]=C(i,k);
}
int f(int i,int j)
{
    int answ=c[i*j]%mod;
    if(i>1)if((i-1)*j>=k)(answ-=2*c[(i-1)*j])%=mod;
    if(j>1)if((j-1)*i>=k)(answ-=2*c[(j-1)*i])%=mod;
    if(j>2)if((j-2)*i>=k)(answ+=c[(j-2)*i])%=mod;
    if(i>2)if((i-2)*j>=k)(answ+=c[(i-2)*j])%=mod;
    if(i>1&&j>1)if((i-1)*(j-1)>=k)(answ+=4*c[(i-1)*(j-1)])%=mod;
    if(i>1&&j>2)if((i-1)*(j-2)>=k)(answ-=2*c[(i-1)*(j-2)])%=mod;
    if(i>2&&j>1)if((j-1)*(i-2)>=k)(answ-=2*c[(j-1)*(i-2)])%=mod;
    if(i>2&&j>2)if((i-2)*(j-2)>=k)(answ+=c[(j-2)*(i-2)])%=mod;
    //最后一错，组合数不能出现负负得正，(i-2)*(j-2)各项均必须为正
    if(answ<0)(answ+=mod)%=mod;
    return answ;
}
signed main()
{
    init();
    int ans=0;
    for(int i=1;i<=h;i++)
    for(int j=1;j<=w;j++)
    {
        (ans+=f(i,j)*i%mod*j%mod*(h-i+1)%mod*(w-j+1)%mod)%=mod;
    }
    (ans*=quickpow(c[h*w],mod-2)%mod)%=mod;
    if(ans<0)(ans+=mod)%=mod;
    cout<<ans<<endl;
    system("pause");
    return 0;
}

AT-S-2 Constrained Nim 2

Problem Statement

博弈论，留空

AT-S-3 Diff Adjacent

Problem Statement

数学卷积，留空

AT-9 Unfair Sugoroku

Problem Statement

题目大意：两个人扔骰子过河，求某个人赢得概率

题目解析

赢得概率等于A抵达了终点时B未抵达的的概率

每一次扔骰子能到达的各个点的概率相同，每一次扔骰子相互独立。

所以在某一点扔骰子到达另一点的概率等于从起点到这一点的概率乘上扔的那的概率，且因为事件相互独立，概率具有可加性。

A的起点为的话最多扔次骰子（最坏的情况每次都扔一点）

所以

B同理。

A比B先扔，所以只要第次A到了，无论B到不到都是A嬴。

所以扔次就获胜的概率是

设表示

设表示

有如下计算

cin >> n >> a >> b >> p >> q;
    dp1[a][0] = dp2[b][0] = 1; // dp[i][j]表示走到i扔了j次筛子的概率
    int invp = quickpow(p, mod - 2) % mod;
    int invq = quickpow(q, mod - 2) % mod;
    for (int i = a; i < n; i++)
    {
        for (int j = 0; j <= i - a; j++)
        {
            for (int k = 1; k <= p; k++)
            {
                (dp1[i + k > n ? n : i + k][j + 1] += invp * dp1[i][j] % mod) %= mod;
            }
        }
    }
    for (int i = b; i < n; i++)
    {
        for (int j = 0; j <= i - b; j++)
        {
            for (int k = 1; k <= q; k++)
            {
                (dp2[i + k > n ? n : i + k][j + 1] += invq * dp2[i][j] % mod) %= mod;
            }
        }
    }

需要注意一个要命的问题，当到了终点的时候不论是谁都不允许再扔骰子了（要扔的话到达的概率就成了求和了，就把原来正确的数据给覆盖掉了。就比如，计算扔了次到的概率时,前面有一发扔了次到的概率，这个是不能加到扔了次到的概率里面的，因为你在不再扔骰子了），所以，第一层循环绝对不能加等号，歪了无数发。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, a, b, p, q;
int dp1[110][110], dp2[110][110];
int pa[110], pb[110];
#define mod 998244353
int quickpow(int a, int n)
{
    int e = 1;
    while (n)
    {
        if (n & 1)
            (e *= a) %= mod;
        (a *= a) %= mod;
        n >>= 1;
    }
    return e;
}
signed main()
{
    cin >> n >> a >> b >> p >> q;
    dp1[a][0] = dp2[b][0] = 1; // dp[i][j]表示走到i扔了j次筛子的概率
    int invp = quickpow(p, mod - 2) % mod;
    int invq = quickpow(q, mod - 2) % mod;
    for (int i = a; i < n; i++)
    {
        for (int j = 0; j <= i - a; j++)
        {
            for (int k = 1; k <= p; k++)
            {
                (dp1[i + k > n ? n : i + k][j + 1] += invp * dp1[i][j] % mod) %= mod;
            }
        }
    }
    for (int i = b; i < n; i++)
    {
        for (int j = 0; j <= i - b; j++)
        {
            for (int k = 1; k <= q; k++)
            {
                (dp2[i + k > n ? n : i + k][j + 1] += invq * dp2[i][j] % mod) %= mod;
            }
        }
    }

    /*for (int i = a; i <= n; i++)
    {
        for (int j = 0; j <= i - a; j++)
        {
            cout << "The popularity of A goes to ";
            cout << i;
            cout << " by throwing ";
            cout << j;
            cout << " times of the die is ";
            cout << dp1[i][j] << endl;
        }
    }
    for (int i = b; i <= n; i++)
    {
        for (int j = 0; j <= i - b; j++)
        {
            cout << "The popularity of B goes to ";
            cout << i;
            cout << " by throwing ";
            cout << j;
            cout << " times of the die is ";
            cout << dp2[i][j] << endl;
        }
    }*/
    int ans = 0;
    for (int j = 0; j <= n - a; j++)
    {
        for (int i = b; i <= n; i++)
        {
            ans = (ans + dp1[n][j] * dp2[i][j] % mod) % mod;
        }
    }
    cout << ans << endl;
    system("pause");
    return 0;
}

AT-10 Rook Score

Problem Statement

题目大意：

稀疏矩阵里有不超过个数，其余为，求最大的十字架和。

题目分析

首先考虑离散化。离散化完后矩阵变成了的，但是还是稀疏矩阵（只有个点）,暴力会超时。

所以只按照单行暴力来做。设每横行的和为,每一纵列的和为.纯暴力的话模拟每一个，但是首先有一堆的不需要减去，其次，每一次都需要对暴力寻找一次最大值。需要对此进行优化。

又是涉及到了有序的查询，想到了容器。

但是有一个问题，这里面可能会有两列的数之和大小一样，但是去重。

所以升级一下，使用维护的最大值。但是有个问题，鉴于所有的的不稳定，在定义时定义成单减序列;然后查询

对于每一行维护结束后，需要将复原为初始状态.

当时有个错点在于将一列的放入时放重复了（为了减少一个for循环），换成了set结果去重去多了（两列的数之和大小一样）

离散化板子：

#include <bits/stdc++.h>
using namespace sts;
int n,res,tot,a[MAXN],b[MAXN];
int main() {
    scanf("%d",&n);
    for(register int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        b[++tot]=a[i]; //b[]是a[]的副本 
    }
    sort(b+1,b+1+tot);  //第一步：排序 
    res=unique(b+1,b+1+tot)-(b+1);  //unique函数计算出去重后的元素个数，存在res中
    for(register int i=1;i<=n;i++) {
        a[i]=lower_bound(b+1,b+1+res,a[i])-b;  //lower_bound函数进行索引 
    }
    return 0;
} 

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
struct node
{
    int a, b, c;
};
bool cmpa(node a, node b)
{
    return a.a < b.a;
}
bool cmpb(node a, node b)
{
    return a.b < b.b;
}
vector<node> ns;
vector<ll> height, width;
vector<node> List[200005];//行邻接表优化矩阵
int n;
ll N[200005], M[200005]; // N行,M列
int t1,t2;//离散化后矩阵变为t1行t2列
multiset<ll,greater<ll>> U;//去重集合，自动排序
ll ans=0;
signed main()
{

    cin >> n;
    for (int i = 1, u, v, w; i <= n; i++)
    {
        cin >> u >> v >> w;
        ns.push_back((node){u, v, w});
        height.push_back(u);
        width.push_back(v);
    }
    sort(ns.begin(), ns.end(), cmpb);
    sort(width.begin(), width.end());
    t2 = unique(width.begin(), width.end()) - width.begin();
    for (int i = 0; i < n; i++)
    {
        ns[i].b = lower_bound(width.begin(), width.begin() + t2, ns[i].b) - width.begin() + 1;
        M[ns[i].b] += ns[i].c;//列和数组
    }
    sort(ns.begin(), ns.end(), cmpa);
    sort(height.begin(), height.end());
    t1 = unique(height.begin(), height.end()) - height.begin();
    for (int i = 0; i < n; i++)
    {
        ns[i].a = lower_bound(height.begin(), height.begin() + t1, ns[i].a) - height.begin() + 1;
        N[ns[i].a] += ns[i].c;//行和数组
        List[ns[i].a].push_back(ns[i]);//按行索引该行所有点的列序号以及权值
        //U.insert(M[ns[i].b]);//列和集合，降低访问复杂度，自动大小排序
    }
    for(int i=1;i<=t2;i++)
    U.insert(M[i]);//要命的问题，一开始是set可以直接向上面一样去重，但是如果不是set就要自己跑一边。
    //说白了，不需要老想着一个for把所有事情都干了，不嵌套的情况下基本数量级不会变化多少
    for(int i=1;i<=t1;i++)
    {
        int tmp=N[i];
        for(int j=0;j<List[i].size();j++)
        {
            int locationb=List[i][j].b;
            int w=List[i][j].c;
            U.erase(U.lower_bound(M[locationb]));//单纯erase会删掉所有的值，只需要删掉一个，用lower_bound
            //找到一个就行了
            U.insert(M[locationb]-w);
        }
        ans=max(ans,tmp+*U.begin());
        for(int j=0;j<List[i].size();j++)
        {
            int locationb=List[i][j].b;
            int w=List[i][j].c;
            U.erase(U.lower_bound(M[locationb]-w));
            //M[locationb]+=w;
            U.insert(M[locationb]);
        }
    }
    cout<<ans<<endl;
    system("pause");
    return 0;

}