头像

huangsitaozc




离线:17小时前


最近来访(17)
用户头像
xiami_ya
用户头像
earth-moon
用户头像
yxc
用户头像
Black_Panda
用户头像
贾淏文
用户头像
no_one
用户头像
ZSLF
用户头像
DogSeven
用户头像
reclusive
用户头像
lofty
用户头像
Phigros
用户头像
WisNourx_

活动打卡代码 AcWing 154. 滑动窗口

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define maxn 1000100
using namespace std;
int q[maxn], a[maxn];
int n, k;

void getmin() {  
  int head = 0, tail = 0;
  for (int i = 1; i < k; i++) {
    while (head <= tail && a[q[tail]] >= a[i]) tail--;
    q[++tail] = i;
  }
  for (int i = k; i <= n; i++) {
    while (head <= tail && a[q[tail]] >= a[i]) tail--;
    q[++tail] = i;
    while (q[head] <= i - k) head++;
    printf("%d ", a[q[head]]);
  }
}

void getmax() {  
  int head = 0, tail = 0;
  for (int i = 1; i < k; i++) {
    while (head <= tail && a[q[tail]] <= a[i]) tail--;
    q[++tail] = i;
  }
  for (int i = k; i <= n; i++) {
    while (head <= tail && a[q[tail]] <= a[i]) tail--;
    q[++tail] = i;
    while (q[head] <= i - k) head++;
    printf("%d ", a[q[head]]);
  }
}

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


活动打卡代码 AcWing 312. 乌龟棋

#include<bits/stdc++.h>
using namespace std;
const int M=41;
int n,m;
int a[360];
int f[M][M][M][M];
int main(){
    int b[5]={0};
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<m;i++){
        int t;scanf("%d",&t);
        b[t]++; 
    }
    for(int A=0;A<=b[1];A++){
        for(int B=0;B<=b[2];B++){
            for(int c=0;c<=b[3];c++){
                for(int d=0;d<=b[4];d++){
                    int t=a[A+B*2+c*3+d*4];
                    int &v=f[A][B][c][d];
                    v=t;
                    if(A) v=max(v,f[A-1][B][c][d]+t);
                    if(B) v=max(v,f[A][B-1][c][d]+t);
                    if(c) v=max(v,f[A][B][c-1][d]+t);
                    if(d) v=max(v,f[A][B][c][d-1]+t);
                }
            }
        }
    }
    printf("%d\n",f[b[1]][b[2]][b[3]][b[4]]);
    return 0;
} 



#include<bits/stdc++.h>
using namespace std;
struct edge{int x,y,pre;}a[6100]; int alen,last[6100];
void ins(int x,int y){alen++;a[alen]=edge{x,y,last[x]};last[x]=alen;}
int f[6100][2],w[6100];
void treedp(int x){
    f[x][1]=w[x];f[x][0]=0;
    for(int k=last[x];k;k=a[k].pre){
        int y=a[k].y;
        treedp(y);
        f[x][1]+=f[y][0];
        f[x][0]+=max(f[y][1],f[y][0]);
    }
}
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    alen=0;memset(last,0,sizeof(last));
    int root=(n+1)*n/2;
    for(int i=1;i<=n-1;i++){
        int x,y;scanf("%d%d",&y,&x);
        ins(x,y);
        root=root-y;
    }
    treedp(root);
    printf("%d",max(f[root][1],f[root][0]));
    return 0;
} 


活动打卡代码 AcWing 203. 同余方程

#include <bits/stdc++.h>
#define ll long long
using namespace std;
void gcd(ll a,ll b,ll &x,ll &y)
{
  if(!b) x=1,y=0;
  else
  {
    gcd(b,a%b,y,x);
    y-=(a/b)*x;
  }
}
int main()
{
  ll a,b,x,y;
  cin>>a>>b;
  gcd(a,b,x,y);
  cout<<(x+b)%b;
  return 0;
}


活动打卡代码 AcWing 190. 字串变换

#include<bits/stdc++.h>
using namespace std;
const int N=6;
int n;
string a,b,s1[N],s2[N];
int etd(queue<string>&q,unordered_map<string,int>&da,unordered_map<string,int>&db,string s1[N],string s2[N]){
    int d=da[q.front()];
    while(q.size()&&da[q.front()]==d){
        auto t=q.front();
        q.pop();
        for(int i=0;i<n;i++){
            for(int j=0;j<t.size();j++){
                if(t.substr(j,s1[i].size())==s1[i]){
                    string r=t.substr(0,j)+s2[i]+t.substr(j+s1[i].size());
                    if(db.count(r)) return da[t]+db[r]+1;
                    if(da.count(r)) continue;
                    da[r]=da[t]+1;
                    q.push(r);
                }
            }
        }
    }
    return 11;
}
int bfs(){
    if(a==b) return 0;
    queue<string> qa,qb;
    unordered_map<string,int> da,db;
    qa.push(a),qb.push(b);
    da[a]=db[b]=0;
    int step=0;
    while(qa.size()&&qb.size()){
        int t;
        if(qa.size()<qb.size()) t=etd(qa,da,db,s1,s2);
        else t=etd(qb,db,da,s2,s1);
        if(t<=10) return t;
        if(++step==10) return -1;
    }
    return -1;
}
int main(){
    cin>>a>>b;
    while(cin>>s1[n]>>s2[n]) n++;
    int t=bfs();
    if(t==-1) puts("NO ANSWER!");
    else printf("%d\n",t);
    return 0;
} 


活动打卡代码 AcWing 286. 选课

#include<bits/stdc++.h>
using namespace std;
struct trnode{
    int lc,rc,c,lastc;
    trnode(){
        lc=rc=lastc=0;
    }
}t[1100];
int f[1100][1100];
void treedp(int x,int k){
    if(f[x][k]!=-1)return;
    int mx=0;
    for(int rs=0;rs<=k;rs++){
        int ls=k-rs,lc=t[x].lc,rc=t[x].rc,fls,frs;
        if(ls>=1){
            treedp(lc,ls-1);
            fls=f[lc][ls-1]+t[x].c;
        }
        else fls=0;
        treedp(rc,rs);frs=f[rc][rs];
        mx=max(mx,fls+frs);
    }
    f[x][k]=mx;
}
int main(){
    int n,k;scanf("%d%d",&n,&k);k++;
    for(int i=1;i<=n;i++){
        int x;scanf("%d%d",&x,&t[i].c);
        if(x==0)x=n+1;
        if(t[x].lastc==0)t[x].lc=i;
        else t[t[x].lastc].rc=i;
        t[x].lastc=i;
    }
    memset(f,-1,sizeof(f));
    for(int i=0;i<=n+1;i++)f[i][0]=f[0][i]=0;
    treedp(n+1,k);
    printf("%d",f[n+1][k]);
    return 0;
} 


活动打卡代码 AcWing 240. 食物链

#include<bits/stdc++.h>
using namespace std;
int fa[160000];
int findfa(int x){return fa[x]=(fa[x]==x)?fa[x]:findfa(fa[x]);}
int main(){
    int n,k;scanf("%d%d",&n,&k);
    for(int i=1;i<=3*n;i++) fa[i]=i;
    int ans=0,tx0,ty0,tx1,ty1,tx2,ty2,x,c,y;
    for(int i=1;i<=k;i++){
        scanf("%d%d%d",&c,&x,&y);
        if(x>n||y>n){ans++;continue;}
        if(c==2&&x==y){ans++;continue;}
        tx0=findfa(x);ty0=findfa(y);
        tx1=findfa(x+n);ty1=findfa(y+n);
        tx2=findfa(x+2*n);ty2=findfa(y+2*n);
        if(c==1){
            if(tx0==ty1||tx0==ty2) ans++;
            else{
                fa[tx0]=ty0;
                fa[tx1]=ty1;
                fa[tx2]=ty2;
            }
        }
        else{
            if(tx0==ty0||tx0==ty1) ans++;
            else{
                fa[tx0]=ty2;
                fa[tx1]=ty0;
                fa[tx2]=ty1;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}


活动打卡代码 AcWing 313. 花店橱窗

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 282. 石子合并

#include<bits/stdc++.h>
using namespace std;
long long f[450][450];
long long s[450];
int n,i,j,k,x;
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&x);
        s[i]=s[i-1]+x;
    }
    memset(f,127,sizeof(f));
    for(i=1;i<=n;i++)f[i][i]=0;
    for(i=n-1;i>=1;i--){
        for(j=i+1;j<=n;j++){
            for(k=i;k<=j-1;k++){
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    printf("%lld\n",f[1][n]);
    return 0;
}


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

#include<bits/stdc++.h>
using namespace std;
struct node{int l,r;}a[201];
int f[201][201];
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i].l);
    for(int i=1;i<=n-1;i++) a[i].r=a[i+1].l;
    a[n].r=a[1].l;
    for(int i=1;i<=n;i++) a[i+n]=a[i];
    for(int i=1;i<=2*n;i++) f[i][i]=0;
    for(int L=2;L<=n;L++){
        for(int st=1;st<=2*n-L+1;st++){
            int ed=st+L-1;
            f[st][ed]=0;
            for(int k=st;k<ed;k++) f[st][ed]=max(f[st][ed],f[st][k]+f[k+1][ed]+a[st].l*a[k].r*a[ed].r);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,f[i][i+n-1]);
    printf("%d\n",ans);
    return 0;
}