头像

纳兰晚宁




在线 



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

using namespace std;

const int N = 1000010;
int n;
int id[N],q[N];

int main()
{
    scanf("%d", &n);
    memset(id,-1,sizeof id);
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        id[x]=i;
    }
    int tt=0;
    q[0]=-1;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        int k=id[x];
        if(k==-1)  continue;
        int l=0,r=tt;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(q[mid]<k)  l=mid;
            else r=mid-1;
        }
        q[r+1]=k;
        tt=max(tt,r+1);
    }
    cout<<tt<<endl;
    return 0;
}


活动打卡代码 AcWing 3502. 不同路径数

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

using namespace std;

const int N = 10;
int n,m,k;
int w[N][N];
unordered_set<int> S;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x,int y,int u,int num)
{
    if(u>k)  S.insert(num);
    else 
    {
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<n&&b>=0&&b<m)
            dfs(a,b,u+1,num*10+w[a][b]);
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
      scanf("%d",&w[i][j]);

    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
      dfs(i,j,1,w[i][j]);

    cout<<S.size()<<endl;
    return 0;
}


活动打卡代码 AcWing 3499. 序列最大收益

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

using namespace std;

const int N = 210;
int n,k,m;
int a[N],w[N][N];
int f[N][N];

int main()
{
    scanf("%d%d%d",&n,&k,&m);
    for(int i=1;i<=m;i++)  scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
       scanf("%d",&w[i][j]);

    memset(f,-0x3f,sizeof f);
    f[1][0]=0;
    for(int i=2;i<=m;i++)
      for(int j=0;j<=k;j++)
        for(int u=1;u<i;u++)
        if(j>=i-u-1)
        f[i][j]=max(f[i][j],f[u][j-(i-u-1)]+w[a[u]][a[i]]);

    int res=0;
    for(int i=0;i<=k;i++)
      res=max(res,f[m][i]);
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 3493. 最大的和

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

using namespace std;

typedef long long LL;

const int N = 100010;
int n,m;
int a[N],b[N];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++)  scanf("%d",&a[i]);
    for(int i=0;i<n;i++)  scanf("%d",&b[i]);

    LL sum=0;
    for(int i=0;i<n;i++)
      if(b[i])
      sum+=a[i];

    LL v=0,s=0;
    for(int i=0;i<n;i++)
    {
        if(!b[i])  s+=a[i];
        if(i>=m&&!b[i-m]) s-=a[i-m];
        v=max(v,s);
    }
    cout<<sum+v<<endl;
    return 0;
}


活动打卡代码 AcWing 3466. 清点代码库

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

#define x first
#define y second

using namespace std;

const int N = 10010;
int n,m;
map<vector<int>,int> cnt;
vector<pair<int,vector<int>>> ans;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        vector<int> line;
        for (int j = 0; j < m; j ++ )
        {
            int x;
            scanf("%d",&x);
            line.push_back(x);
        }
        cnt[line]++;
    }

    for(auto& p: cnt) ans.push_back({-p.y,p.x});
    sort(ans.begin(),ans.end());

    cout<<cnt.size()<<endl;
    for(auto& p:ans)
    {
        printf("%d",-p.x);
        for(auto x: p.y)
          printf(" %d",x);
        cout<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 3465. 病毒溯源

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

using namespace std;

const int N = 10010,M=10010;
int n;
int h[N], e[M], ne[M], idx;
int son[N];
bool st[N];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs(int u)
{
  int res=0;
  son[u]=-1;
  for(int i=h[u];~i;i=ne[i])
  {
      int j=e[i];
      int d=dfs(j);
      if(res<d)  res=d,son[u]=j;
      else if(res==d)  son[u]=min(son[u],j);
  }
  return res+1;
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int cnt;
        scanf("%d",&cnt);
        while(cnt--)
        {
            int x;
            scanf("%d",&x);
            add(i,x);
            st[x]=true;
        }
    }

    int root=0;
    while(st[root])   root++;

    cout<<dfs(root)<<endl;
    cout<<root;
    while(son[root]!=-1)
    {
        root=son[root];
        printf(" %d",root);
    }
    return 0;
}


活动打卡代码 AcWing 3485. 最大异或和

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

using namespace std;

const int N = 100010*31,M=100010;
int n,m;
int s[M];
int son[N][2],cnt[N],idx;

void insert(int x,int v)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;
        if(!son[p][u])  son[p][u]=++idx;
        p=son[p][u];
        cnt[p]+=v;
    }
}

int query(int x)
{
    int res=0,p=0;
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;
        if(cnt[son[p][!u]])  p=son[p][!u],res=res*2+1;
        else p=son[p][u],res=res*2;
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        s[i]=s[i-1]^x;
    }
    int res=0;
    insert(s[0],1);
    for(int i=1;i<=n;i++)
    {
        if(i>m)  insert(s[i-m-1],-1);
        res=max(res,query(s[i]));
        insert(s[i],1);
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 3463. 乘法口诀数列

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

using namespace std;

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

    string s = a + b;
    int i = 0;
    while (s.size() < n)
    {
        s += to_string((s[i] - '0') * (s[i + 1] - '0'));
        i ++ ;
    }

    for (int i = 0; i < n; i ++ )
    {
        printf("%c", s[i]);
        if (i != n - 1) printf(" ");
    }

    return 0;
}



活动打卡代码 AcWing 3462. 天梯赛的善良

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

using namespace std;

const int N = 20010;
int a[N];
int res;
int cnt;

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    scanf("%d", &a[i]);
    sort(a+1,a+1+n);
    for(int i=2;i<=n;i++)
    if(a[i]==a[1])
    res++;
    else break;
    for(int i=n-1;i>=1;i--)
    if(a[i]==a[n]) cnt++;
    else break;
    cout<<a[1]<<' '<<res+1<<endl;
    cout<<a[n]<<' '<<cnt+1<<endl;
    return 0;
}


活动打卡代码 AcWing 3461. 吉老师的回归

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

using namespace std;

int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    getchar();
    string str;
    while (n -- ){
        getline(cin,str);
        if(str.find("qiandao")!=-1||str.find("easy")!=-1)
        continue;
        if(!m)
        {
            cout<<str<<endl;
            return 0;
        }
        m--;
    }
    cout<<"Wo AK le"<<endl;
    return 0;
}