ACM周报Ⅱ

完成题目：

洛谷：

$\color{green}{P1631}$
$\color{green}{[ABC123D] Cake 123}$
$\color{green}{[ABC137D] Summer Vacation}$
$\color{green}{P4053}$
$\color{orange}{P8754}$
$\color{blue}{P1139}$
$\color{#FFD700}{P1754}$

CF：

$Round 988 (div.3)$：赛时$solved 4$，赛后$solved 6$，$rank 3856$

sort和priority自定义比较器分析与比较

sort自定义比较器

$sort$有三个参数，$sort(x,y,cmp)$
前两个参数为需要排序的数组或者容器的初始指针位置，后一个为尾指针位置$+1$
$cmp$为自定义比较器，需要额外添加一个函数

code:

struct node{
    int a,b;
};
bool cmp(node x,node y){return x.a>y.a;}

通过以上$cmp$函数可以把$sort$排序方式变为按照$node.a$从大到小排序

priority_queue自定义比较器

$priority_queue$也有三个参数，$priority_queue(type,container,cmp)$
第一个参数为储存的数据类型，可以为结构体
第二个参数为容器类型，一般是vecctor
第三个是比较器，自带的有$less<int>$和$greater<int>$
前一个是大根堆比较器，后一个是小根堆比较器，默认是大根堆

code:

struct node{
  int a,b;  
};
struct cmp{
    bool operator()(node x,node y){
        return x.a>y.a;
    }
};
priority_queue(node,vector<node>,cmp)

以上函数即是按照$node$中的$a$从小到大排序，为小根堆
或者在结构体内重载运算符：

struct node{
    int a,b;
    bool operator <(const node &R) const{//把运算符<换一种运算方式
        return a > R.a;//比较当前R中的a和其他所有a
    }
};//因为原priority中是按照<来排序所以要把<换一种方式

注意事项

注意，sort自定义比较器$>$代表从大到小排序
而priority里$>$代表从小到大排序，priority的$>$代表若大于则返回真，需要交换对顶和堆尾

容斥原理具体写法

假设需要求以下式子：
$f[p_1]+f[p_2]+...+f[p_n]-f[p_1*p_2]-f[p_1*p_3]-...+f[p_1*p_2*p_3]+...$
假设一共有$p_1...p_n$，$n$个数

Code:

for(int i=1;i<(1<<n);i++){
    int t=1,s=0;
    for(int j=1;j<=n;j++){
        if((i>>(j-1))&1){//需要取用当前位
        	if(t*p[j]>n){t=-1;break;}//超过范围作废
			t*=p[j];
            s++;//计数
        }
	}
    if(t!=-1){
        if(s&1)ans+=f[t];//奇数个
        else ans-=f[t];//偶数个
    }
}
cout<<ans;

矩阵乘法速度提升方法

RT，众所周知矩阵乘法时间复杂度是$O(n*m*k)，但常数是多少就不知道了$
代码如下：

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        for (int k = 1; k <= R; k++)
            ans[i][j] += a[i][k] * b[k][i];

但是调换一下顺序将会提升2~5倍速度
代码如下：

for (int i = 1; i <= n; i++)
    for (int k = 1; k <= R; k++) {
        int x = a[i][k];//为了避免重复调用可以先储存，可以加快速度
        for (int j = 1; j <= m; j++)
            ans[i][j] += x * b[k][i];
    }

具体原因和$cpu$运行方式有关，我没看懂。有兴趣自己搜

加速cin与cout

输入以下代码即可：

std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);