找平均值问题一般都是二分法

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

using namespace std;

const int N = 100010;

int n, F;
double a[N], s[N];

bool check(double avg)
{
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i] - avg;

    double mins = 0;
    for (int k = F; k <= n; k ++ )
    {
        mins = min(mins, s[k - F]);
        if (s[k] >= mins) return true;
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &F);

    double l = 0, r = 0;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lf", &a[i]);
        r = max(r, a[i]);
    }

    while (r - l > 1e-5)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%d\n", (int)(r * 1000));

    return 0;
}

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

using namespace std;

const int N=110,M=N*2;

int n,w[M],f[M][M];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        w[n+i]=w[i];
    }
    memset(f,-0x3f,sizeof f);//本题可以不初始化，因为不存在负数的状态

    for(int len=2;len<=n+1;len++){
        for(int l=1,r;(r=l+len-1)<=n*2;l++){
            if(len==2) f[l][r]=0;
            else for(int k=l+1;k<r;k++){
                f[l][r]=max(f[l][r],f[l][k]+f[k][r]+w[l]*w[k]*w[r]);
            }
        }
    }
    int res=0;
    for(int l=1;l<=n;l++)
    res=max(res,f[l][l+n]);
    cout<<res;

}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210, M = N*2, INF = 0x3f3f3f3f;
//小细节，因为是环形，所以 我们可以把链延长两倍，变成 2n 个点
//其中 i 和 i+n 是相同的两个点，然后直接套 区间 dp 模板
int n;
int w[M], s[M];
int f[M][M], g[M][M];//f求最大，g求最小

int main()
{
    //读入
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) cin >> w[i], w[i + n] = w[i];

    //预处理前缀和（DP状态转移中会频繁的用到区间和）
    for (int i = 1; i <= n*2; ++ i) s[i] = s[i - 1] + w[i];//n*2等价于n<<1

    memset(f, -0x3f, sizeof f);//求最大值预处理成最小值（可以省掉，这题不会有负数状态所以0就是最小）
    memset(g, +0x3f, sizeof g);//求最小值预处理成最大值（不可省掉）

    for (int len = 1; len <= n; ++ len)//阶段
    {
        for (int l = 1, r; r = l + len - 1, r < n*2; ++ l)//左右区间参数
        {
            if (len == 1) f[l][l] = g[l][l] = 0;//预处理初始状态
            else
            {
                for (int k = l; k + 1 <= r; ++ k)//枚举分开点
                {
                    f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]),
                    g[l][r] = min(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
                }
            }
        }
    }
    //目标状态中找出方案
    int minv = INF, maxv = -INF;
    for (int l = 1; l <= n; ++ l)
    {
        minv = min(minv, g[l][l + n - 1]);
        maxv = max(maxv, f[l][l + n - 1]);
    }

    //输出
    printf("%d\n%d\n", minv, maxv);

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

const int N = 110, M = 1 << 10;
int n, m;
int g[N], cnt[M];
int f[2][M][M];
vector<int> state;
vector<int> head[M];

bool check(int st)
{
    return !(st & st >> 1 || st & st >> 2);
}
int count(int st)
{
    int res = 0;
    while (st) res += st & 1, st >>= 1;
    return res;
}
int main()
{
    //input
    cin >> n >> m;
    for (int i = 1, j = 0; i <= n; ++ i, j = 0)
        for (char c; j < m && cin >> c; ++ j)   //纯属为了压行,没有其他意思w
            g[i] += (c == 'H') << j;
    //找出所有合法状态
    for (int st = 0; st < 1 << m; ++ st)
        if (check(st))
            state.push_back(st), cnt[st] = count(st);
    //找出所有合法状态的合法转移
    for (int cur_st: state)
        for (int pre_st: state)
            if (!(cur_st & pre_st))
                head[cur_st].push_back(pre_st);
    //dp
    for (int i = 1; i <= n; ++ i)
        for (int st: state)
            if (!(g[i] & st))
                for (int p1: head[st])
                    for (int p2: head[p1])
                        if (!(st & p2))
                            f[i&1][st][p1] = max(f[i&1][st][p1], f[i-1&1][p1][p2] + cnt[st]);//&1为目标状态优化
    //枚举最终状态
    int res = 0;
    for (int st: state)
        for (int pre: head[st])
            res = max(res, f[n&1][st][pre]);
    //output
    cout << res << endl;
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

const int N = 14, M = 1 << N, mod = 1e8;

int n, m, k;
int g[N];
int f[N][M];
vector<int> state;
vector<int> head[M];

bool check(int state)
{
    return  !(state & state << 1);
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
        for (int j = 0; j < m; ++ j)
            cin >> k, g[i] |= !k << j;
    for (int st = 0; st < 1 << m; ++ st)
        if (check(st))
            state.push_back(st);    //预处理合法状态
    for (auto st: state)//auto型变量可自动分配
        for (auto ne_st: state)
            if (!(st & ne_st))
                head[st].push_back(ne_st);  //预处理合法状态的合法转移
    f[0][0] = 1;//与上一题一样，初始化很重要
    for (int i = 1; i <= n + 1; ++ i)
        for (auto st: state)
            if (!(st & g[i]))
                for (auto pre_st: head[st])
                    f[i][st] = (f[i][st] + f[i - 1][pre_st]) % mod;
    cout << f[n + 1][0] << endl;
    return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;//应该是溢出了对吧，所以我们要把所有的f改成long long 

const int N=12;//待会儿我会给大家解释一下为什么要开到12

const int M=1<<10,K=110;//K是我们的国王数量

int n,m;//这里用m来表示国王数量，因为我习惯用n来表示一个数然后m来表示另外一个值

vector<int> state; //state 用来表示所有的合法的状态

int id[M];//id的话是存这个每一个状态和这个它的下标之间的映射关系 id有用到吗？好像没有用到
//应该是我之前写的时候思路不太一样，想的时候可能，就是前面设计的思路和实际用到的思路可能会有一点区别
//所以这里其实是不要加id i 的

vector<int> head[M];//这个是每一状态所有可以转移到的其他状态

int cnt[M];/*然后cnt的话存的是每个状态里面 1 的个数，因为我们刚才我们的状态转移方程里面，
其实有一个需要求这个每一个状态里面1的个数的一个过程对吧*/

LL f[N][K][M];//这就是我们刚才说的那个状态表示

bool check(int state)
{
    for(int i=0;i<n;i++)
     if((state >> i & 1)&&(state >> i + 1 & 1))
       return false;//如果存在连续两个1的话就不合法

    return true;//否则的话就是合法的
}

int count(int state)//这里y总没具体解释，我补充一下，这里就是计算某个数二进制里面1的个数
{
    int res=0;

    for(int i=0;i<n;i++)res+=state>>i&1;

    return res;
}

int main()
{
    cin>>n>>m;

    //首先我们需要把所有合法状态处理出来对吧，把它预处理一下
    for(int i=0;i<1<<n;i++)
       if(check(i))
    /*check函数是检查一下我们当前状态是不是合法，也就是检查一下我们这个状态里面是不是存在连续的两个1，
    如果不存在的话就表示它是合法的*/
       {
           state.push_back(i);
           id[i]=state.size()-1;//id存的是我们这个合法状态对应的下标是多少
           cnt[i]=count(i);//cnt的话存的是这个i里面 1 的个数是多少
       }

    //然后我们来看一下这个不同状态之间的一个这个边的关系
    for(int i = 0;i< state.size();i ++ )
      for(int j=0;j<state.size();j++)
      {
          //用a来表示第一个状态，用b来表示第二个状态
          int a=state[i],b=state[j];
          //这里是建立一个不同状态之间的转移关系
          //先预处理一下哪些状态和哪些状态之间可以转移
          //首先转移的话是要满足两个条件对吧
          //一个是这个 a 和 b 的交集必须要是空集，它必须是空集才可以，否则的话同一列的两个国王会攻击到
          //并且的话它们的这个这个并集的话也是需要去满足我们不能包含两个相邻的1的
          if((a&b)==0&&check(a|b))
             // head[a].push_back(b);
             //然后只要这个 b 是合法的，那么我们就把 b 添加到 a 可以转移到的状态集合里面去
             //这里y总第一次写错了，debug了
             head[i].push_back(j);

             //这里是debug过程
             //这里写错了，这里应该是head[i].push_back(j);
             //因为咱么这里去做的时候用的是下标，不是一个状态的值
      }

      //好，那剩下的就是 DP 了对吧

      f[0][0][0]=1;
      //最开始的时候，我们f[0][0][0]=1
      /*什么意思呢，就是说，前0行对吧，我们前0行已经摆完了，其实也就是一行也没有摆的情况下，
      那么此时由于我们这个是在棋盘外面，
      所以肯定每个国王都不能摆对吧，所以我们就只有0这个状态时合法的，那么这个状态的方案数是1*/

      //好，然后从前往后枚举每一种状态

      for(int i=1;i<=n+1;i++)
         for(int j=0;j<=m;j++)//j的话是从0到m对吧，m表示的是国王数量
           for(int a=0;a<state.size();a++)//然后我们来枚举一下所有的状态，a表示第i行的状态
             for(int b : head[a])//然后来枚举所有a能到的状态（这个是C++ 11的语法 for(int a:b) 从数组b依次取出元素赋值给整形变量a，循环执行for中语句）
             {
                 //这里要判断一下
                 //首先要判断的是
                 //求一下我们a里面的一个1的个数对吧
                 int c=cnt[state[a]];
                 //好，然后如果说，呃，就我们的j必须要大于等于c对吧，j是必须要大于等于c的
                 //为什么呢,因为我们这个表示我们当前这行摆放的国王数量一定要小于等于我们整个的上限对吧
                 if(j>=c)//如果数说满足要求的话，那么我们就可以转移了
                 {
                     f[i][j][a]+=f[i-1][j-c][b];
                     //转移的话就是f[i][j][a]+=f[i-1][j-c][b]，然后从b转移过来
                 }
             }

    //好，那我们最终的答案是什么呢？
    //我们的最终的答案应该是这个f[n][m][ ]，然后最后一维可以直接去枚举对不对
    //去枚举一下最后一维是从，就是所有合法状态都是可以的，就最后一行它所有合法状态都是可以的对不对
    //那这里的话我们可以偷个懒，不是偷个懒，我们可以有个小技巧，就是我们在枚举i的时候,枚举到n+1就可以了
    //就是我们去算到第i+1行，假设我们的棋盘是一个n+1 * n的一个棋盘，多了一行
    /*那么我们最终算的时候 就需要输出一个 f[n+1]，就是第n+1行，
    一共摆到了第n+1行，然后m，然后0，因为第n+1行一个都没摆，对吧*/

    cout<<f[n+1][m][0]<<endl;
    /*就是我们假设存在第n+1行，但是第n+1行完全没有摆，
    那这种情况里面的所有方案其实就是等于这个这个我们只有n行的一个所有方案，对吧*/
    /*那这样枚举n+1的一个好处是我们最后不需要再循环枚举最后一行的状态了，
    就是我们这个f[n+1][m][0]已经在这个循环里面被循环算出来了*/
    //所以可以少一层循环
    /*这里的话就是为什么我们一开始N要从12开始，对吧，首先我们要用到11这个下标对吧，
    那其实11这个下标是需要开长度是12才可以*/
    return 0;
}

质因数分解，约数和公式，分治递归

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

using namespace std;

const int mod=9901;

int qmi(int a,int k)//快速幂（高效求一个数的几次方）
{
    int res=1;
    a%=mod;
    while(k)
    {
        if(k&1) res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res;
}

int sum(int p,int k)
{
    if(k==1) return 1;
    if(k%2==0) return (1+qmi(p,k/2))*sum(p,k/2)%mod;
    return (sum(p,k-1)+qmi(p,k-1))%mod;
}

int main(){
    int a,b;
    cin>>a>>b;

    int res=1;
    //对a分解质因数
    for(int i=2;i*i<=a;i++){
        if(a%i==0){
            int s=0;
            while(a%i==0){
                a/=i,s++;
            }
            res=res*sum(i,b*s+1)%mod;
        }

    }
    if(a>1) res=res*sum(a,b+1)%mod;
    if(a==0) res=0;
    cout<<res<<endl;
}

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

using namespace std;

const int dx[5]={-1,0,0,0,1};
const int dy[5]={0,-1,0,1,0};

int T,M,N;//本题用不到，但可以自定义矩阵长宽
int tile[10][10];
int x[10];

int flip[10][10];//保存中间结果

//查询（x,y）的颜色
int get(int x,int y){
    int c=tile[x][y];
    for(int d=0;d<5;d++){
        int x2=x+dx[d],y2=y+dy[d];
        if(0<=x2&&x2<M&&0<=y2&&y2<N){
            c+=flip[x2][y2];
        }
    }
    return c%2;
}

//求出第1行确定的情况下的最小操作次数
//不存在解的话返回-1
int calc(){
    //求出从第2行开始的翻转方式
    for(int i=1;i<M;i++){
        for(int j=0;j<N;j++){
            if(get(i-1,j)==0)
            //(i-1,j)不亮的话，则必须翻转这个格子
            flip[i][j]=1;
        }
    }
    //判断最后一行是否全亮
    for(int j=0;j<N;j++){
        if(get(4,j)==0){
        //无解
        return -1;
        }
    }
    //统计翻转的次数
    int res=0;
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            res+=flip[i][j];
        }
    }
    return res;
}


int solve(){
    int res=-1;
    //按照字典序尝试第一行的所有可能性
    for(int i=0;i<1<<N;i++){
        memset(flip,0,sizeof(flip));
        for(int j=0;j<N;j++){
            flip[0][N-j-1]=i>>j&1;
        }
        int num=calc();
        if(num>=0&&(res<0||res>num))
        res=num;
    }
    return res;
}


int main(){
    cin>>T;
    while(T--){
    M=N=5;
    for(int i=0;i<5;i++){
        cin>>x[i];
    }

    for(int i=0;i<5;i++)
       for(int j=4;j>=0;j--){
           tile[i][j]=x[i]%10;
           x[i]/=10;
        }

    int a=solve();
    if(a>6) cout<<-1<<endl;
    else cout<<a<<endl;

    }
}

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

using namespace std;

long long a,b,p,res=0;

int main(){
    cin>>a>>b>>p;
    while(b){
        if(b&1)
           res=(res+a)%p;
        b>>=1;
        a=2*a%p;
    }
    cout<<res;
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 55, M = 1010, K = 25;
const int INF = 0x3f3f3f3f;

int n;
char s[M];
int tr[N * K][4], cnt[N * K], idx;
int fail[N * K], q[N * K];
int f[M][N * K];

int get(char c)
{
    if (c == 'A') return 0;
    if (c == 'G') return 1;
    if (c == 'C') return 2;
    return 3;
}
void insert(char s[])
{
    int p = 0;
    for (int i = 0; s[i]; ++ i)
    {
        int u = get(s[i]);
        if (!tr[p][u]) tr[p][u] = ++ idx;
        p = tr[p][u];
    }
    cnt[p] = 1;
}
void build()
{
    int tt = -1, hh = 0;
    for (int i = 0; i < 4; ++ i)
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];
    while (hh <= tt)
    {
        int u = q[hh ++ ];
        for (int i = 0; i < 4; ++ i)
        {
            if (tr[u][i])
                fail[tr[u][i]] = tr[fail[u]][i],
                cnt[tr[u][i]] |= cnt[fail[tr[u][i]]],//看他跳转的状态是否是匹配成功状态
                q[ ++ tt] = tr[u][i];
            else
                tr[u][i] = tr[fail[u]][i];
        }
    }
}
void solve()
{
    //初始化
    memset(fail, 0, sizeof fail);
    memset(cnt, 0, sizeof cnt);
    memset(f, 0x3f, sizeof f);
    memset(tr, 0, sizeof tr);
    f[0][0] = 0;
    idx = 0;
    //输入建立 AC 自动机
    for (int i = 1; i <= n; ++ i) cin >> s, insert(s);
    cin >> s + 1; build();
    int n = strlen(s + 1);
    //dp
    for (int i = 0; i < n; ++ i)
    {
        for (int j = 0; j <= idx; ++ j)
        {
            //枚举下一个字符
            for (int k = 0; k < 4; ++ k)
            {
                int cost = get(s[i + 1]) != k;  //修复下一个字符的费用
                int p = tr[j][k];               //下一个字符的自动机状态
                if (!cnt[p]) f[i + 1][p] = min(f[i + 1][p], f[i][j] + cost);
            }
        }
    }
    int res = INF;
    for (int j = 0; j <= idx; ++ j) res = min(res, f[n][j]);
    if (res == INF) res = -1;
    cout << res << endl;
}
int main()
{
    int T = 1;
    while (cin >> n, n)
    {
        cout << "Case " << T ++ << ": ";
        solve();
    }
    return 0;
}