头像

纳兰晚宁




在线 


活动打卡代码 AcWing 142. 前缀统计

纳兰晚宁
14小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;
int n,m;
char str[N];
int son[N][26],cnt[N],idx;

void insert(char *str)
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u])  son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}

int query(char *str)
{
    int p=0,res=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u])  return res;
        p=son[p][u];
        res+=cnt[p];
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    while (n -- ){
        scanf("%s",str);
        insert(str);
    }
    while (m -- )
    {
        scanf("%s",str);
        printf("%d\n",query(str));
    }
    return 0;
}


活动打卡代码 AcWing 71. 二叉树的深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int treeDepth(TreeNode* root) {
        if(!root)  return  0;
        return max(treeDepth(root->left),treeDepth(root->right))+1;
    }
};



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


#define v first
#define w second

using namespace std;

typedef pair<int,int> PII;

const int N =60,M=32010;
int n,m;
PII master[N];
vector<PII> servent[N];
int f[M];

int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        int v,p,q;
        cin>>v>>p>>q;
        p*=v;
        if(!q)  master[i]={v,p};
        else servent[q].push_back({v,p});
    }

    for(int i=1;i<=n;i++)
       for(int u=m;u>=0;u--)
       {
           for(int j=0;j<1<<servent[i].size();j++)
           {
               int v=master[i].v,w=master[i].w;
               for(int k=0;k<servent[i].size();k++)
                  if(j>>k&1)
                  {
                      v+=servent[i][k].v;
                      w+=servent[i][k].w;
                  }
                  if(u>=v)  f[u]=max(f[u],f[u-v]+w);
           }
       }
       cout<<f[m]<<endl;
       return 0;
}


活动打卡代码 AcWing 491. 字符串的展开

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

using namespace std;

int p1,p2,p3;
char str[100];

int main()
{
    cin>>p1>>p2>>p3>>str;
    for(int i=0;i<strlen(str);i++){
        if(str[i]=='-'&&str[i-1]<str[i+1]&&(((str[i-1]>='a'&&str[i-1]<='z')&&(str[i+1]>='a'&&str[i+1]<='z'))||((str[i-1]>='0'&&str[i-1]<='9')&&(str[i+1]>='0'&&str[i+1]<='9')))){
            if(str[i-1]+1!=str[i+1])
                for(int j=(p3==2?str[i+1]-1:str[i-1]+1);(p3==2?j>str[i-1]:j<str[i+1]);(p3==2?j--:j++))
                    for(int k=0;k<p2;k++)
                        cout << (char(p1==3?'*':(p1==2?(j>='a'?j-32:j):(j))));
        }else{
            cout << str[i]; 
        }

    }
  return 0;
}


活动打卡代码 AcWing 490. 统计数字

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

using namespace std;

const int N = 200005;
int n,a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )  scanf("%d",a+i);
    sort(a+1,a+1+n);
    for (int i = 1; i <= n; i ++ )
    {
        int s=1;
        while(i<n&&a[i+1]==a[i])  i++,s++;
        printf("%d %d\n",a[i],s);
    }
    return 0;
}


活动打卡代码 AcWing 320. 能量项链

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

using namespace std;

const int N=210,INF=0x3f3f3f3f;
int n;
int w[N];
int f[N][N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        w[i+n]=w[i];
    }
    for(int len=3;len<=n+1;len++)
       for(int l=1;l+len-1<=n*2;l++)
       {
           int r=len+l-1;
           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<<endl;
    return 0;
}


活动打卡代码 AcWing 1453. 移掉K位数字

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

using namespace std;

int main()
{
    string num;
    int k;

    cin>>num>>k;
    string res="0";
    for(auto c:num)
    {
        while(k&&c<res.back())   res.pop_back(),k--;
        res+=c;
    }
    while(k--)  res.pop_back();
    k=0;
    while(k+1<res.size()&&res[k]=='0') k++;
    cout<<res.substr(k)<<endl;
    return 0;
}


活动打卡代码 AcWing 62. 丑数

class Solution {
public:
    int getUglyNumber(int n) {
        vector<int> q(1,1);
        int i=0,j=0,k=0;
        while (--n)
        {
            int t=min(q[i]*2,min(q[j]*3,q[k]*5));
            q.push_back(t);
            if(t==q[i]*2) i++;
            if(t==q[j]*3) j++;
            if(t==q[k]*5) k++;
        }
        return q.back();
    }
};



class Solution {
public:
    int getNumberSameAsIndex(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(nums[mid]>=mid)  r=mid;
            else l=mid+1;
        }
        if(nums[r]==r)  return r;
        return -1;
    }
};



代码解释

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

using namespace std;

const int N=1510;
int n;
int h[N],e[N],ne[N],idx;
int f[N][2];
bool st[N];

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

//状态表示为:以u为根节点的子树,1代表选这个点的方案,0代表不选这个点的方案
//类似于上司的舞会
void dfs(int u)
{
    f[u][0]=0,f[u][1]=1;//不选   选
    for(int i=h[u];~i;i=ne[i])//遍历整个根节点
    {
        int j=e[i];
        dfs(j);//找到了这个点,搜索下一个
        f[u][0]+=f[j][1];   //这个点不选,子结点一定选
        f[u][1]+=min(f[j][0],f[j][1]);//选这个点,则子结点可选或可不选
    }
}

int main()
{
        cin>>n;
        memset(h,-1,sizeof h);//初始化表头
        idx=0;
        memset(st,0,sizeof st);//初始化数组

        for(int i=0;i<n;i++)
        {
            int id,cnt;
            scanf("%d:(%d)",&id,&cnt);
            while(cnt--)
            {
                int ver;
                cin>>ver;
                add(id,ver);  //在id这个城市和另外的cnt的城市之间建图
                st[ver]=true;//标记孩子节点
            }
        }
        int root=0;
        while(st[root])   root++;   //寻找根节点
        dfs(root);

        printf("%d\n",min(f[root][0],f[root][1]));  //最少的士兵数

    return 0;
}