一、数学

1.AcWing 1205. 买不到的数目

如果a,b均是正整数且互质，那么由ax+by,x>=0,y>=0不能凑出的最大整数是 ab - a - b
证明：
首先证明 ab−a−bab−a−b 不能被 ax+bx,x≥0,y≥0ax+bx,x≥0,y≥0表示出。
反正法，假设 ab−a−b=ax+byab−a−b=ax+by，那么 ab=a(x+1)+b(y+1)ab=a(x+1)+b(y+1)，由于 a|ab,a|a(x+1)a|ab,a|a(x+1)，所以 a|b(y+1)a|b(y+1)，由于 a,ba,b 互质，所以 a|(y+1)a|(y+1)，由于 y≥0y≥0，所以 a<=y+1a<=y+1，所以 b(y+1)≥abb(y+1)≥ab。同理可得 a(x+1)≥aba(x+1)≥ab，所以 a(x+1)+b(y+1)≥2ab>aba(x+1)+b(y+1)≥2ab>ab，矛盾。
证明 ab−a−b+d,d>0ab−a−b+d,d>0 一定可以表示成 ax+by,x,y≥0ax+by,x,y≥0 的形式.

2.AcWing 1211. 蚂蚁感冒

理解：蚂蚁碰面时相当于他们不会掉头，而是继续朝各自的方向走

#include<iostream>
using namespace std;

const int N = 55;
int Left,Right;//分别表示左边向右走的，和右边向左走的
int n,x[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x[i];   
    }
    for(int i=1;i<n;i++)
    {
        if(abs(x[i]) > abs(x[0]) && x[i] < 0) Right++; 
        else if(abs(x[i]) < abs(x[0]) && x[i] > 0) Left++;
    }
    int ans = 1;
    if(x[0] > 0)
    {
        if(Right > 0) ans += Right + Left;
        else ans += Right; 
    }
    else
    {
        if(Left > 0) ans += Left + Right;
        else ans += Left;
    }
    cout<<ans<<endl;
    return 0;
}

1216. 饮料换购

#include<iostream>
using namespace std;

int n,res;

int main()
{
    cin>>n;
    int res = n;
    while(n>=3)
    {
        res += n/3;
        n = n/3 + n%3;
    }
    cout<<res<<endl;
    return 0;
}

上取整的方法

1.ceil函数

C 库函数 double ceil(double x)
返回大于或等于 x 的最小的整数值。

2.公式计算法

[a/b] = [(a+b-1)/b]

二、动态规划,简单DP

01背包问题

#include<iostream>
using namespace std;

const int M = 1005;
int n,m;//物品数量和背包体积
int v[M],w[M];//表示某件物品的体积和价值
int f[M][M];//状态表示：包含所有选法的集合

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>v[i]>>w[i];
    //f[0][0~M]全部初始化为0
    for(int i=1;i<=n;i++) //枚举前i件物品
    {
        for(int j=1;j<=m;j++)//枚举不超过j的体积
        {
            if(v[i] > j) f[i][j] = f[i-1][j];//当前背包容量装不进第i个物品，则价值等于前i-1个物品
            else f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]);//能装，需进行决策是否选择第i个物品
        }
    }
    cout<<f[n][m]<<endl;
}

1015. 摘花生

#include<iostream>
using namespace std;

const int N = 105;
int f[N][N],g[N][N]; //f[i][j]：状态表示第i行第j列取得花生数最大值
int T,m,n,x;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);//n行m列
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&g[i][j]);
            }
        }

        //f[1][1] = g[1][1];//区域外方案数为0，无需初始化
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                f[i][j] = max(f[i-1][j] + g[i][j],f[i][j-1] + g[i][j]);//来自上方和左边的方案数加上当前花生数，求较大者
            }
        }
        cout<<f[n][m]<<endl;
    }
    return 0;
}

895. 最长上升子序列

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int N = 1005;
int n,a[N],ans;
int f[N];//状态表示：所有以i结尾的严格单调上升子序列的集合
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f[i] = 1;//初始化，最短子序列为1
    }
   for(int i=2;i<=n;i++)//右端点
   {
       for(int j = 1;j<=i;j++)
       {
           if(a[j] < a[i]) f[i] = max(f[i],f[j] + 1);//如果a[i]左边有比它小的数，选取个数较多的集合
           ans = max(ans,f[i]);//结果方案不一定包含最后一个数,因此需要取最大值
       }
   }
   cout<<ans<<endl;
   return 0;
}

1212. 地宫取宝

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 55,MOD = 1000000007;

int n,m,k;
int w[N][N];
int f[N][N][13][14];//状态表示：横坐标，纵坐标，已经取了多少件，当前价值

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&w[i][j]);
            ++w[i][j];//由于起初要遍历(1,1)，C++数组下标不支持-1,故映射价值到[1,13]
        }
    }
    f[1][1][0][0] = 1;
    f[1][1][1][w[1][1]] = 1;
    for(int i=1;i<=n;i++)//枚举横坐标
    {
        for(int j=1;j<=m;j++)//枚举纵坐标
        {
            if(i==1 && j==1) continue;//(1,1)处已经处理过了
            for(int u=0;u<=k;u++)//枚举已经取的个数，不大于k
            {
                for(int v=0;v<=13;v++)//枚举当前价值
                {
                    int &val = f[i][j][u][v];
                    val = (val + f[i-1][j][u][v]) % MOD;//价值小于当前宝物价值，不选
                    val = (val + f[i][j-1][u][v]) % MOD;//出于范围的考虑，最多加2数就取模
                    if(u > 0 && v == w[i][j])
                    {
                        for(int c=0;c<v;c++)
                        {
                            val = (val + f[i-1][j][u-1][c]) % MOD;//价值等于当前宝物价值，选
                            val = (val + f[i][j-1][u-1][c]) % MOD;
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0;i<=13;i++) ans = (ans + f[n][m][k][i]) % MOD;
    cout<<ans<<endl;
    return 0;
}

1214. 波动数列

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1005,MOD = 100000007;

int f[N][N];//f[i][j] 前i个数中，总和取余n为j的方案个数
int n,s,a,b;

inline int get_mod(int a,int b)//余数转为正数
{
    return (a % b + b) % b;
}
int main()
{
    cin>>n>>s>>a>>b;
    f[0][0] = 1;
    for(int i = 1;i < n;i++) //枚举前n-1项中
    {
        for(int j = 0;j < n;j++)//枚举总和取余n为j的方案
        {
            f[i][j] = ( f[i-1][get_mod(j - a*i,n)] + f[i-1][get_mod(j + b*i,n)] ) % MOD;//由前i-1项推得
        }
    }
    cout<<f[n-1][get_mod(s,n)] % MOD<<endl;//注意s可能为负数，因此此处s%n仍需转正处理
    return 0;
}