头像

AI弱鸡




离线:1天前


活动打卡代码 AcWing 2065. 整除序列

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    long long int n;
    cin>>n;
    cout<<n<<' ';
    while(n)
    {
        n = n/2;
        if(n > 1)
        cout<<n<<' ';
        else if(n == 1)
        {
            cout<<n<<endl;
            break;
        }
        else break;
    }
    return 0;
}



AI弱鸡
11天前

字符串的相关操作

初始化

char str1[] = {"Le Chapon Dodu"};
string str2 = {"Le Chapon Dodu"};
char str3[20] = "jinan";

赋值,拼接和附加


char charr1[20];
char charr2[20] = "jinan";
//赋值操作
charr1 = charr2;

string str2 = {"Le Chapon Dodu"};
string str3 = {"Le Dodu"};
str3 = str3 + str2;

结构体

//申请结构体
stuct tree
{
    int l;
    int r;
    double k;
}

//申请结构体数组
struct tree a[50];

//初始化结构体
tree b = {1,2,1.0};
a[0] = b;

vector

#include<vector>

vector<int> v;

//把1压入堆栈
v.push_back(1);

//返回首尾元素
int a = v.begain();
int b = v.end();

//返回v的大小
v.size(); 

//判断是否为空
v.empty();


活动打卡代码 AcWing 1220. 生命之树

AI弱鸡
13天前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10,M = N*2;
typedef long long LL;
int n;
int w[N];
int h[N],e[M],ne[M],idx;
LL f[N];

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;  
}

void dfs(int u,int father)
{
    f[u] = w[u];
    for(int i = h[u];i != -1;i = ne[i])
    {
        int j = e[i];
        if(j != father)
        {
            dfs(j,u);
            LL zero = 0;
            f[u] += max(zero,f[j]);
        }
    }
}
int main()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i = 1;i<=n;i++) scanf("%d",&w[i]);
    int a,b;
    for(int i = 0;i<n-1;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    dfs(1, -1);
    LL res = f[1];
    for(int i = 2;i<=n;i++)res = max(res,f[i]);
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1248. 灵能传输

AI弱鸡
13天前
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 300010;
typedef long long LL;

LL a[N],s[N];
bool st[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        s[0]=0;
        for(int i = 1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            s[i] = s[i - 1] + a[i];
        }
        LL s0 = s[0],sn = s[n];
        if(s0 >sn)swap(s0,sn);
        sort(s,s + n + 1);

        for(int i = 0;i<=n;i++)
        {
            if(s[i] == s0)
            {
                s0 = i;
                break;
            }

        }
         for(int i = n;i>=0;i--)
        {
            if(s[i] == sn)
            {
                sn = i;
                break;
            }

        }   
         memset(st, 0, sizeof st);
         int l = 0,r = n;
         for(int i = s0;i>=0;i -= 2)
         {
             a[l++] = s[i];
             st[i] = true;
         }
         for(int i = sn;i<=n;i += 2)
         {
             a[r--] = s[i];
             st[i] = true;
         }

        for(int i = 0;i<=n;i++)
        {
            if(st[i] == false)
               {
                   a[l++] = s[i];
                   st[i] = true;
               }
        }
        LL res = 0;

        for(int i = 1;i<=n;i++)res = max(res,abs(a[i] - a[i - 1]));

        printf("%lld\n", res);
    }
    return 0;
}



活动打卡代码 AcWing 1239. 乘积最大

AI弱鸡
14天前
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010,MOD = 1000000009;
int a[N],b[N];
long long int res = 1;
int n,k;

//a存整数,b存负数

int main()
{
    int w = 0,e = 0,z = 0,num;
    cin>>n>>k;
    //w表示正数个数,e表示负数个数
    if(n == k)
    {
         for(int i = 0;i<n;i++)
       {
        scanf("%d",&num);
        res = (res*num)%MOD;
       }
       cout<<res<<endl;
       return 0;
    }
    for(int i = 0;i<n;i++)
    {
        scanf("%d",&num);
        if(num>0) a[++w]=num;
        else if(num<0) b[++e]=num;
        else  z = 1; 

    }    
    sort(a+1,a+w+1);
    sort(b+1,b+e+1);
    if(k%2 == 1&& w == 0)
    {
        if(z == 0)
        {
            for(int i = 0;i<k;i++)res = 0 - (0 - res*b[e - i])%MOD;
        }
        else res = 0;
        cout<<res<<endl;
        return 0;
    }
    else
    {
        int flag = 1;
        if(k%2 == 1)
        {
            res = a[w--];
            k--;
        }
        while(flag<= e - 1 && w>1 && k)
       {
          long long int num1 = (long long int) a[w]*a[w - 1];
          long long int num2 =  (long long int) b[flag]*b[flag + 1];
          if(num1> num2)
          {
              res = (((res* a[w])%MOD)*a[w - 1])%MOD;
              w = w - 2;
          }
          else
          {
          res = 0 - (0 - res*b[flag])%MOD;
          res = 0 - (0 - res*b[flag + 1])%MOD;
          flag = flag + 2;
          }
        k = k - 2;
       }
       if(k)
       {
           if(flag>e - 1)
           {
               for(int i = k;i>=1;i--)
               {
                   res = (res* a[w])%MOD;
                   w --;
               }
           }
           else
           for(int i = k;i>=1;i--)
            {
                   res = 0 - (0 - res*b[flag])%MOD;
                   flag++;
            }
       }
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1247. 后缀表达式

AI弱鸡
14天前
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 2*1e5 + 10;
int s[N];
long long int res = 0;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 0;i<n+m+1;i++)scanf("%d",&s[i]);
    sort(s,s+n+m+1);
    if(!m)
     for(int i = 0;i<n+m+1;i++)res += s[i];   
    else 
    {
        res = s[n+m] - s[0];
        for(int i = 1;i<n+m;i++)res += abs(s[i]);
    }
    printf("%lld",res);
    return 0;
}



AI弱鸡
15天前

枚举

递归实现指数型枚举

从 1~n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。

const int N=15;
int n;
int st[N]; 
void dfs(int u)
{
    if(u>=n)
    {
        for(int i=0;i<=n;i++)
        {
            if(st[i]==1)printf("%d ",(i+1));
        }
       printf("\n");
       return;
    }
    st[u]=1;
    dfs(u+1);

    st[u]=2;
    dfs(u+1);
    st[u]=0;
}

递归实现排列型枚举

把 1~n 这 n 个整数排成一行后随机打乱顺序,输出所有可能的次序。

const int N=10;
int n;
int state[N];//表示没用过,1~N表示数字
bool used[N];//true表示用过,false表示没用过

void dfs(int num)
{
     if(num>n)
     {
         for(int i=1;i<=n;i++) printf("%d ",state[i]);
         puts(" ");

         return;
     }
     for(int i=1;i<=n;i++)
     {
         if(!used[i])
         {
             used[i]=true;
             state[num]=i;
             dfs(num+1);

             state[num]=0;
             used[i]=false;
         }
     } 
}

递归实现组合型枚举

从 1~n 这 n 个整数中随机选出 m 个,输出所有可能的选择方案。

const int N=30;
int n,m;
int way[N];
void dfs(int u,int start)
{
    if(u==m+1)
    {
        for(int i=1;i<=m;i++)printf("%d ",way[i]);
        puts("");
        return;
    }
    for(int i=start;i<=n;i++)
    {
        way[u]=i;
        dfs(u+1,i+1);
    }
}

二分法

整数的二分法

样题链接
https://www.acwing.com/problem/content/submission/code_detail/1524544/

算法模板
```
// n 是数组的中元素的个数
// k为要查找的数
//输出为该元素的起始位置与终止位置
int l = 0, r = n -1;
int k;
scanf(“%d”,&k);
while(l < r)
{
int mid = l + r >> 1;
if(m[mid] >= k)r = mid;
else l = mid + 1;
}

    if(m[l] != k) printf("-1 -1\n");
    else
    {
        cout << l << ' ';

        int l = 0, r = n - 1;
        while(l < r)
        {
        int mid = l + r + 1 >> 1;
        if(m[mid] <= k)l = mid;
        else r = mid - 1;
        }
        cout<<l<<endl;
    }

```

double类型的二分法

 while(r-l>1e-8)
    {
        mid = (l + r)/2;
        if(mid*mid*mid > n)r = mid;
        else l = mid;
    }

前缀和

一维前缀和

1,初始化数组

    for(int i = 1;i <= n;i++)
    {
        s[i] +=s[i-1];
    }

2, 求和

    while(m--)
    {
        res = s[r]-s[l-1];
    }

二维数组前缀和

1,初始化数组

    for(int i = 1;i <=n;i++)
    for(int j = 1;j <=m;j++)
    {
    s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
    }

2, 求和

   for(int i =0;i<q;i++)
    {
        res = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
        cout<<res<<endl;
    }

闫式DP

总的来说,我感觉DP方法主要还是靠经验。我是菜鸡就不过多总结了。只是把y总的模板放在这里。
DP.png

双指针算法

算法思想: 利用问题本身与序列的特性(序列递增性质),使用两个下标i、j对序列进行扫描 (可以同向扫描,也可以反向扫描) ,以较低的复杂度解决问题。

for(int i = 0,j = 0;i < n;i++)
   {
      while()
       {
           j++;
       }
   }

DFS

dfs()
{  
    if(到达终点状态)  
    {  
        ...//根据题意添加  
        return;  
    }  
    if(越界或者是不合法状态)  
        return;  
    if(特殊状态)//剪枝
        return ;
    for(扩展方式)  
    {  
        if(扩展方式所达到状态合法)  
        {  
            修改操作;//根据题意来添加  
            标记;  
            dfs();  
            (还原标记);  
            //是否还原标记根据题意  
            //如果加上(还原标记)就是 回溯法  
        }  

    }  
}

BFS

void bfs ()
{
    queue 初始化

    while(hh <= tt)  //队列非空
    {
        t = q[hh ++ ];  //更新队头

        // 扩展队头 + 放入队列
    }
}

欧几里得算法

int gcd(int a,int b)
{
    return b ? gcd(b,a%b) : a;
}

预处理质数

void get_primes(int n)  //预处理质数
{
    for(int i = 2;i<=n;i++)
    {
        if(!st[i])
        {
            minp[i] = i;
            primes[cnt++] = i;
        }

        for(int j = 0;primes[j]*i<= n;j++)
        {
            int t =primes[j]*i;
            st[t] =true;
            minp[t] = primes[j];
            if(i%primes[j]==0)break;
        }
    }
}



AI弱鸡
15天前

静态链表

int head,e[N],ne[N],idx;
//head为记录头结点
//e[N]记录每个单链表的值
//ne[N]记录每个链表next指针
//idx 记录总共值的个数

//初始化单链表
void init()
{
    head = -1;
}

//在头结点加入一个值
void add_head(int x)
{
    e[idx] = x,ne[idx] = head,head = idx++;
}


//表示在第k个输入的数后面插入一个数x
void add_k(int k,int x)
{
    e[idx] = x,ne[idx]=ne[k],ne[k]=idx++;
}


//表示删除第k个输入的数后面的数
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

//遍历链表的方法
for(int i = head;i!= - 1;i = ne[i])cout <<e[i]<<' ';
cout<<endl;

静态链表记录树和图

主要思想是用把树或者是图用临界链表的方式存储,之后把临界链表改写成静态链表的方式。其中h[N]中记录这每一个头结点的位置

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

int n;
int h[N], e[M], ne[M], idx;
int ans = N;
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}


//主函数初始化过程
//其中a和b表示两点之间有一条边
memset(h, -1, sizeof h);

for (int i = 0; i < n - 1; i ++ )
{
     int a, b;
     scanf("%d%d", &a, &b);
     add(a, b), add(b, a);
}

线段树和树状数组

应用背景:给定 n 个数组成的一个数列,规定有两种操作,一是修改某个元素,二是求子数列 [a,b] 的连续和。
线段树和树状数组与前缀和都是求一个区间上的的和。如果不进行修改元素的操作,前缀和可以把复杂度降低到O(1)。
但是如果存在修改元素的操作,前缀和算法复杂度就会升到O(n)。而线段树和树状数组允许修改操作,时间复杂度为O(logn)。

树状数组

模板题目链接https://www.acwing.com/problem/content/description/1266/
树状数组.png

图片来自小呆呆同学的题解。
原题解的链接如下
https://www.acwing.com/solution/content/7526/
1、lowbit(x):返回x的最后一位1

int lowbit(int x)
{
    return x&-x;
}

2、add(x,v):在x位置加上v,并将后面相关联的位置也加上v

void add(int x,int v)
{
    for(int i = x;i<=n;i +=lowbit(i)) tr[i] +=v;
}

3、query(x):询问x的前缀和`

int query(int x)
{
    int res = 0;
    for(int i = x;i;i-=lowbit(i)) res += tr[i];
    return res;
}

线段树

线段树.png
1、pushup(u):用子节点信息来更新当前节点信息(把信息往上传递)

void pushup(int u)
{
    tr[u].maxv = max(tr[u<<1].maxv , tr[u<<1|1].maxv);
}

2、build(u,l,r):在一段区间上初始化线段树,其中u表示根结点,l表示左边界,r表示右边界

void build(int u ,int l,int r)
{
    if(l == r)tr[u]={l,r,w[r]};
    else
    {
    tr[u] = {l,r};
    int mid = l + r >> 1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
    }
}

3、query(u,l,r):查询某段区间的和,其中u表示根结点,l表示左边界,r表示右边界

int query(int u,int l,int r)
{
    if(tr[u].l>=l && tr[u].r<=r)return tr[u].maxv;
    int res = INT_MIN;
    int mid = tr[u].l + tr[u].r >> 1;
    if(mid>=l)res = query(u<<1,l,r);
    if(mid<r)res = max(res,query(u<<1|1,l,r));
    return res;
}

4、modify(u,x,v):修改操作,在u结点中,x位置加上v

   void modify(int u,int x,int v)
    {
        if(tr[u].l == tr[u].r) tr[u].sum += v;
        else
        {
            int mid = tr[u].l + tr[u].r >> 1;
            if(x <= mid) modify(u << 1,x,v);
            else modify(u << 1 | 1,x,v);
            pushup(u);
        }
    }

堆(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:
1. 堆中某个节点的值总是不大于或不小于其父节点的值;
2.堆总是一棵完全二叉树。
3.将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的up和down操作

down

void down(int u)
{

    int t = u ;
    if(2*u <= cnt && h[2*u]<h[t]) t = 2*u;
    if(2*u + 1 <=cnt && h[2*u+1]<h[t]) t =2*u + 1;

    if(t != u)
    {
        swap(h[t],h[u]);
        down(t);
    }
}

up

void up(int u)
{
    while(u/2 && h[u/2] > h[u])
    {
        swap(h[u/2],h[u]);
        u /= 2;
    }
}

堆的五个基本操作

1.插入一个数

heap[++size] = x;up(size);

2.求集合当中的最小(大)值

heap[1]; 

3.删除最小值

heap[1] = heap[size];size--;down(1);

4.删除任意一个元素

heap[k] = heap[size];size--;down(k);up(k);

5.修改任意一个操作

heap[k] = x;down(k);up[k];


活动打卡代码 AcWing 826. 单链表

AI弱鸡
16天前
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int head,e[N],ne[N],idx;

void init()
{
    head = -1;
}

void add_head(int x)
{
    e[idx] = x,ne[idx] = head,head = idx++;
}

void add_k(int k,int x)
{
    e[idx] = x,ne[idx]=ne[k],ne[k]=idx++;
}

void remove(int k)
{
    ne[k] = ne[ne[k]];
}
int main()
{
    init();
    int m;
    cin>>m;
    while(m--)
    {
        char op;
        int k,x;
        cin>>op;
        if(op == 'H')
        {
            cin>>x;
            add_head(x);
        }
        else if(op == 'I')
        {
            cin>>k>>x;
            add_k(k - 1,x);
        }
        else
        {
            cin>>k;
            if(!k)head = ne[head];
            else remove(k - 1);
        }
    }

    for(int i = head;i!= - 1;i = ne[i])cout <<e[i]<<' ';
    cout<<endl;

    return 0;

}


活动打卡代码 AcWing 1096. 地牢大师

AI弱鸡
16天前
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 110;
char m[N][N][N];

struct Point
{
    int x, y, z;
};

int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
Point q[N*N*N];
int dist[N][N][N];
int l,r,c;
int bfs(Point start,Point end)
{
    memset(dist, -1, sizeof dist);   
    int head = 0,tail = 0;
    q[head] = start;
    dist[start.x][start.y][start.z] = 0;
    while(head <= tail)
    {
        Point sit = q[head];
        for(int i = 0;i<6;i++)
        {
            int X = sit.x + dx[i];
            int Y = sit.y + dy[i];
            int Z = sit.z + dz[i];
            if(X<0||X>=l||Y<0||Y>=r||Z<0||Z>=c)continue;
            if(m[X][Y][Z] == '.' && dist[X][Y][Z] == -1)
            {
                tail++;
                q[tail].x = X;
                q[tail].y = Y;
                q[tail].z = Z;
                dist[X][Y][Z] = dist[sit.x][sit.y][sit.z] + 1;
            }
            if(m[X][Y][Z] == 'E')
            return dist[sit.x][sit.y][sit.z] + 1;
        }
        head ++;
    }
    return -1;
}
int main()
{
    Point start,end;
    while(scanf("%d%d%d", &l, &r, &c),l||r||c)
    {
      for (int i = 0; i < l; i ++ )
            for (int j = 0; j < r; j ++ )
            { 
                scanf("%s", m[i][j]);
                for (int k = 0; k < c; k ++ )
                {
                    char C = m[i][j][k];
                    if (C == 'S') start = {i, j, k};
                    else if (C == 'E') end = {i, j, k};
                }
            }

        int res = bfs(start,end);

        if(res != -1) printf("Escaped in %d minute(s).\n",res);
        else printf("Trapped!\n");
    }

    return 0;
}