一、第四周学习总结表

本周学习完成情况
Contest 完成情况
LCS和LIS 6/9
动态规划基础 13/22
高精度计算 10/10
简单递推练习 13/13
树和二叉树 6/6
牛客 3/10
Atcoder 4/8
总计 55/78
个人感悟
本周开始，明显感觉到了难度的提升，每天的题目开始做不完了。而第二天又有新的题目，也没来的及去补题。难点主要在动态规划的思想难以真正的掌握，每道题目如果没有预先学习过相应的模型，具体算法分类。如没有学习区间DP之前，自己完全想不出来怎么写石子合并问题。如果在比赛过程中，遇到此类问题，将毫无下手空间。希望下周开始能把本周没有补完的动态规划补完，并学习更多的动态规划模型。

Contest	完成情况
LCS和LIS	6/9
动态规划基础	13/22
高精度计算	10/10
简单递推练习	13/13
树和二叉树	6/6
牛客	3/10
Atcoder	4/8
总计	55/78

二、本周学习新内容

1.inline函数

inline定义类的内联函数，函数的代码被放入符号表中，在使用时直接进行替换（像宏一样展开）没有了调用的开销，效率也高了

如果需要多次调用，如快读的时候可以加上inline

2.位运算技巧

判断一个整数x是否为2的n次方

x & (x-1) == 0

3.算位数

一个数如果能表示为10^n^那么，他的位数，很显然就是int(n+1)

如：$10^1=10$位数为2.
$10^{log_{10}20}=20$,$log_{10}20=1.3$ .位数为2

所以一个数为x^k^次方

则这个数的位数即为log~10~

4.nullptr和NULL

NULL是一个宏定义，在c和c++中的定义不同，c中NULL为（void*)0,而c++中NULL为整数0

所以在c++中int *p=NULL; 实际表示将指针P的值赋为0，而c++中当一个指针的值为0时，认为指针为空指针

nullptr是一个字面值常量，类型为std::nullptr_t,空指针常数可以转换为任意类型的指针类型

5.快速求组合数

预处理阶乘逆元求组合数

有取模条件，根据取模条件，如果模数是质数用费马小定理，用快速幂就可求逆元，否则用扩展欧几里得求逆元

typedef long long ll;
const ll N = 3e6+5;
const ll MOD = 1e9 + 7;
ll fac[N], ifac[N];
ll dp[1000010];
// a 为求逆元的数，b 为模数，运算完成后 x 就是在模 a 下的逆元
int exgcd(int a, int b, int &x, int &y)
{
	if (!b)
	{
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
ll qpow(ll a, ll b, ll MOD) {
    ll res = 1;
    while (b) {
        if (b & 1)
            res = 1ll * res * a % MOD;
        a = 1ll * a * a % MOD;
        b >>= 1;
    }
    return res;
}
void init(ll n) {
	fac[0] = ifac[0] = 1;
    for (int i = 1; i <= n; i++) {
		fac[i] = 1ll * fac[i - 1] * i % MOD;
		ifac[i] = 1ll * ifac[i - 1] * qpow(i, MOD - 2, MOD) % MOD;
	}
}
ll C(ll a,ll b){
	if(a<0 || b<0 || a<b) return 0;
	return (1ll * fac[a] * ifac[b] % MOD * ifac[a - b] % MOD);
}

卢卡斯定理求组合数

求大组合数 $C_{a}^b$ ，a、b > 1e10, and 模数 p 较小的情况下。求逆元根据p的情况来定，为质数可用费马小定理，否则用扩展欧几里得求逆元

typedef long long ll;
const ll MOD = 1e9 + 7;
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1)
            res = 1ll * res * a % MOD;
        a = 1ll * a * a % MOD;
        b >>= 1;
    }
    return res;
}
 
int C(int a, int b)
{
	int res = 1;
	for (int i = 1, j = a; i <= b; i++, j--)
	{
		res = (ll)res * j % MOD;
		res = (ll)res * qpow(i, MOD - 2) % MOD;
	}
	return res;
}
 
int lucas(ll a, ll b)
{
	if (a < MOD && b < MOD) return C(a, b);
	return (ll)C(a % MOD, b % MOD) * lucas(a / MOD, b / MOD) % MOD;
}

三、题解一览

1.AtCoder Beginner Contest 261 - D - Flipping and Bonus

题目标签

题目描述

高桥君可以扔n次硬币，第i枚硬币面朝上加相应的得分a[i]，硬币面朝下则不加分

此外还有一个奖励机制，即高桥君连续正面朝上j次可以得到c[j]的得分，但是一旦正面朝下，i就会清零

请你算出高桥君最多能得到几分

题目解析`

本题使用动态规划的思想

定义DP数组dp[i][j]，i代表第i次扔硬币，j代表这是第j次连胜，转移过程中取最大值

当硬币面朝上时，$dp[i][j]=max(dp[i-1][j-1]+a[i]+c[j],dp[i][j])$

当硬币面朝下时，$dp[i][0]=max(dp[i][0],dp[i-1][j])$

硬币朝下的时候，取的就是前一次连胜为j时的得分的最大值，所以不会出现重复的情况

通过代码

int dp[N][N];  
int a[N];  
int w[N];  
void solve(){  
    cin>>n>>m;  
    for(int i=1;i<=n;i++) cin>>a[i];  
    for(int i=1;i<=m;i++){  
        int a,b;  
        cin>>a>>b;  
        w[a]=b;  
    }  
    for(int i=1;i<=n;i++){  
        for(int j=1;j<=i;j++){  
            //这回合赢了  
            dp[i][j]=max(dp[i-1][j-1]+w[j]+a[i],dp[i][j]);  
            //这回合输了  
            dp[i][0]=max(dp[i-1][j],dp[i][0]);  
        }  
    }  
    int ans=0;  
    for(int j=1;j<=n;j++){  
        ans=max(ans,dp[n][j]);  
    }  
    cout<<ans<<endl;  
}

2.AtCoder Beginner Contest 261 - E - Many Operations

题目标签

位运算

题目描述

一共有i次操作，每一次操作用一个ti和一个ai来改变x

如果 ti=1, x=x&a
如果 ti=2, x=x|a
如果 ti=3, x=x^a
现在进行n轮操作，
第i轮操作，将进行1,2,3…i−1,i次操作
询问每一轮操作后的x值，x是一直更新的

题目解析

如果直接暴力方法，毫无意义问会超时

问题的关键在于如何优化，让每一轮的操作，都能被保留下来，并进行下一次运算，这样就可以减少时间复杂度

这里考虑二进制拆位，对每一轮的操作都记录并记录

通过前缀和记录，可以求得

通过代码

#include<bits/stdc++.h>
#define N 2e5+10
int a[N];  
int oper[N];  
int pre[2][30][N];  
int ans[N];
int main(){
    for(int i=1;i<=n;i++) cin>>oper[i]>>a[i];  
    for(int i=0;i<30;i++) pre[1][i][0]=1;  
    for(int i=0;i<30;i++) pre[0][i][0]=0;  
    for(int j=0;j<30;j++){  
        for(int i=1;i<=n;i++){  
            int x=(a[i]>>j)&1;  
            if(oper[i]==1){  
                pre[1][j][i]=pre[1][j][i-1]&x;  
                pre[0][j][i]=pre[0][j][i-1]&x;  
            }  
            else if(oper[i]==2){  
                pre[1][j][i]=pre[1][j][i-1]|x;  
                pre[0][j][i]=pre[0][j][i-1]|x;  
            }  
            else {  
                pre[1][j][i]=pre[1][j][i-1]^x;  
                pre[0][j][i]=pre[0][j][i-1]^x;  
            }  
        }  
    }
    ans[0]=c;  
    for(int i=1;i<=n;i++){  
        int pres=ans[i-1];  
        int now=0;  
        for(int j=0;j<30;j++){  
            int x=(pres>>j)&1;  
                if(pre[x][j][i]) now+=(1<<(j));  
        }  
        ans[i]=now;  
        cout<<ans[i]<<"\n"; 
    }
}

3.AtCoder Beginner Contest 263 - D - Left Right Operation

题目标签

前缀和

题目描述

给你一个序列，以及数字LR

你可以把任意前i个数字变成L

也可以把任意后i个数字变成R

求变完之后的最小值

题目解析

可以将问题转换：

改变数字再求最小值，也就是先找出所有改变的数字与原数字之差的和最小值，最后输出这个最小值+原数组的sum即可

所以我们可以先开两个数组lnum和rnum，记录原数字分别和L，R的差

然后对这些数字求前缀和/后缀和，并开一个数组dp，记录前/后i个前缀和的最小值

最后取ldp[i]+rdp[i+1]的最小值即可

注意点：

数组的初始化ldp[0]和rdp[n+1]要初始化为0，表示一个数也不改变的情况，就是将原sum+0
minn的初始化取0，这样可以保证如果改变完数字，比原来还大了。说明不用改变任何一个，也就是让minn=0

通过代码

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define N 200000+10
#define inf 0x3f3f3f
using namespace std;
const double PI = acos(-1.0);
//前缀和和后缀和+dp
ll num[N];
ll lnum[N];
ll rnum[N];
ll lsum[N];
ll rsum[N];
ll ldp[N];
ll rdp[N];
int main()
{
    // freopen("3output.out","w",stdout);
    // freopen("1input.in","r",stdin);
    ll n, l, r;
    scanf("%lld %lld %lld", &n, &l, &r);
    ll allsum = 0;
    for (ll i = 1; i <= n; i++)
    {
        scanf("%lld", &num[i]);
        allsum += num[i];

        lnum[i] = l - num[i];
        rnum[i] = r - num[i];
    }
    ldp[0] = 0;
    rdp[n + 1] = 0;
    for (ll i = 1; i <= n; i++)
    {
        lsum[i] = lsum[i - 1] + lnum[i];
        ldp[i] = min(ldp[i - 1], lsum[i]);
    }
    for (ll i = n; i >= 0; i--)
    {
        rsum[i] = rsum[i + 1] + rnum[i];
        rdp[i] = min(rdp[i + 1], rsum[i]);
    }
    ll minn = 0;
    for (ll i = 0; i <= n; i++)
    {
        minn = min(minn, rdp[i+1] + ldp[i]);
    }
    cout << allsum + minn;
}

4.哈理工暑假训练赛 - F - 奇怪的魔法

题目标签

数论；求组合数

题目描述

创造长度为n的单调非递减数组，每个数组需要消耗的魔力为数组的最大值，数组的最大值不超过K

求所有不同数组的魔力值之和，对答案1e9+7取模

题目解析

很可惜的一道题，因为不了解详细的原理，逆元和阶乘数组设太小了，最终没有AC

拿到题先用BFS跑了一遍，并打印每轮每个数作为最大数出现在数组中的次数，并很快找到了规律，

可以发现这是一个组合数的表，$c[i][j]=c[i-1][j]+c[i][j-1]$

并且最终答案的状态转移方程为$dp[i]=dp[i-1]+c[i][j]*i$

每次转移取模即可

但是问题出现在了复杂度上，如果打二维表空间不够，并且会超时

仔细观察，又可以发现$c[i][j]=C_{i+j-1}^{i}$

那么放弃递推打表，只需要找到一种快速求出组合数的方法即可

于是我们可以通过预处理逆元和阶乘的方式，求出组合数

通过代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e6+5;
const ll MOD = 1e9 + 7;
ll fac[N], ifac[N];
ll dp[1000010];
ll qpow(ll a, ll b, ll MOD) {
    ll res = 1;
    while (b) {
        if (b & 1)
            res = 1ll * res * a % MOD;
        a = 1ll * a * a % MOD;
        b >>= 1;
    }
    return res;
}
void init(ll n) {
	fac[0] = ifac[0] = 1;
    for (int i = 1; i <= n; i++) {
		fac[i] = 1ll * fac[i - 1] * i % MOD;
		ifac[i] = 1ll * ifac[i - 1] * qpow(i, MOD - 2, MOD) % MOD;
	}
}
ll C(ll a,ll b){
	if(a<0 || b<0 || a<b) return 0;
	return (1ll * fac[a] * ifac[b] % MOD * ifac[a - b] % MOD);
}
int main() {
    ll row,col;
    cin>>col>>row;
    ll j=col;
	init(N);
    for (ll i = 0; i <= row ; i++)
    {
        ll num=C(i+j-1,i);
		dp[i]=(dp[i-1]%MOD+(num*i)%MOD)%MOD;
    }
	cout<<dp[row];
}

5.哈理工暑假训练赛 - A - 寂寞如雪

题目标签

DP；最大子序列和

题目描述

给你一段0和1组成的串，每一段由连续n个1的组成的段，都代表一个数：

也就是$n^2$

比如111011001111100111代表的是3^2^,2^2^,5^2^,3^2^

你可以任意截取一段，并且求和。

但是题目规定，当某一段被截下来后是第奇数段，那他就是正的，偶数段就是负的

注意：截取不能把一段1截断，必须完整的截下来，比如11110011不能被截取为1100必须是111100或者0011

比如截取1110110011111，也就是截取前三个数，3^2^,2^2^,5^2^

那么求和就是3^2^+（-2^2^）+5^2^

比如截取11001111100111也就是截取后三个数，2^2^,5^2^,3^2^

那么求和就是2^2^+（-5^2^）+3^2^

题目解析

由于题目规定，不能拦腰截断，必须截完整（后面广播给出的）

问题就变得非常简单了。（也就是为什么一开始没做，看到广播的提示才做的原因）

对于给出的字符串，可以直接将其压缩成一个数组

比如：

110011111001100111

其实可以压缩成数组[3^2^,2^2^,5^2^,3^2^]

由于不能拦腰截断1——不会改变压缩后的数组的大小，所以只要对压缩成的数组进行截取。使得这个区间求和最大就可以了

那么这题就转化成了对一个数组，求最大的连续子段和。刚好本周的训练里就有这道题

而问题难就难在题目给出的限制：规定截取后的数，是第偶数个就得变成负数

看似每次截取后的正负都不同，都要判断，每次判断都会很麻烦

其实仔细推导会发现，不管怎么截取，每个数总共就只有两种状态

要么这个数的序号是奇数（正），下一个数是偶数（负），再下一个数是奇数（正）

要么这个数的序号是偶数（负），下一个数是偶数（正），再下一个数是奇数（负）

即对：

[3^2^,-2^2^,5^2^,-3^2^]，进行任意截取求和，也就是求最大字段和
[-3^2^,2^2^,-5^2^,3^2^]，进行任意截取求和，也就是求最大字段和

最后两个最大字段和，取最大的输出即可

通过代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    vector<int> vz,vf;
    vz.push_back(0);//占位，下标从1开始
    vf.push_back(0);
    int flag = 1;
    int cnt = 0;

    //输入并预处理
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '1')
            cnt++;
        if (cnt > 0 && s[i]=='0' || i==s.length()-1 && s[i]=='1')
        {
            vz.push_back(cnt * cnt * -flag);//负正负正负正
            vf.push_back(cnt * cnt * flag);//正负正负正负
            flag = -flag;
            cnt = 0;
        }
    }

    //两个数组分别求最大子段和
    int maxn=vz[1];
    for (int i = 1; i <= vz.size(); i++)
    {
        if (vz[i - 1] >= 0)
        {
            vz[i] = vz[i - 1] + vz[i];
            //如果是负数，就说明前一个数对和没有贡献，不算进去，重新从i开始求子段和找最大值。初始化vi[i]=0，不需要清零操作
        }
        maxn=max(vz[i],maxn);
    }
    for (int i = 1; i <= vf.size(); i++)
    {
        if (vf[i - 1] >= 0)
        {
            vf[i] = vf[i - 1] + vf[i];
        }
        maxn=max(vf[i],maxn);
    }

    //输出
    cout<<maxn;
    return 0;
}

6.MaxSum

题目标签

题目描述

求最大字段和，并输出子段的下标

题目解析

从第一个数开始动态规划

dp[i]代表了从当前起始点到i的所有数之和

起始点会随着dp[i]进行动态更新

那么动态更新的依据是什么呢？

即：状态转移的过程中，dp[i]每次都加上他的前一个数dp[i-1]

但是如果dp[i-1]<0。说明dp[i-1]这个数在转移之前是一个很大的负数

dp[i-1]+dp[i-2]的时候他一加上去，把之前加在一起的全都变成负数了

说明这个数对求最大的和起不了贡献。

这个数就放弃加上去，那么前一个起点开始求的子段和就到此为止了

再加就不礼貌了

然后开一个新的起点，从新的起点开始加，求连续的最大字段和。

每次转移的时候更新max，这样再求了所有的子段和之后，就能找到最大的字段和。

通过代码

#include <bits/stdc++.h>
#define ll long long
#define N 100000 + 5
using namespace std;
int main()
{
    ll dp[N] = {0};
    ll t;
    cin >> t;
    ll cnt = 1;
    while (t--)//duo'zu'shu
    {
        if (cnt != 1)
            cout << endl;
        ll n;
        cin >> n;
        for (ll i = 1; i <= n; i++)
        {
            cin >> dp[i];
        }
        
        ll maxn = -9999999;
        ll st = 1, ed = 1;
        int tempst=1;
        for (ll i = 1; i <= n; i++)
        {
            if (dp[i - 1] >= 0)
            {
                dp[i] = dp[i - 1] + dp[i];
            }
            else
            {
                tempst = i;//一旦小于0,然后另起一个新的下去。新的dp从当前i开始,st记录为i
            }                 
            if (dp[i] > maxn) //每次都判断，并更新最大值
            {
                maxn = dp[i];
                st=tempst;
                ed = i;
            }
        }
        //输出
        cout << "Case " << cnt++ << ":" << endl
             << maxn << " " << st << " " << ed << endl;
        
    }
}

22暑期ACM集训周记04

一、第四周学习总结表

本周学习完成情况

个人感悟

二、本周学习新内容

1.inline函数

2.位运算技巧

3.算位数

4.nullptr和NULL

5.快速求组合数

预处理阶乘逆元求组合数

卢卡斯定理求组合数

三、题解一览

1.AtCoder Beginner Contest 261 - D - Flipping and Bonus

题目标签

题目描述

题目解析`

通过代码

2.AtCoder Beginner Contest 261 - E - Many Operations

题目标签

题目描述

题目解析

通过代码

3.AtCoder Beginner Contest 263 - D - Left Right Operation

题目标签

题目描述

题目解析

通过代码

4.哈理工暑假训练赛 - F - 奇怪的魔法

题目标签

题目描述

题目解析

通过代码

5.哈理工暑假训练赛 - A - 寂寞如雪

题目标签

题目描述

题目解析

通过代码

6.MaxSum

题目标签

题目描述

题目解析

通过代码