4.25字节跳动笔试

在这里写下每题的答案吧
1.纸牌均分问题的贪心
由于最左边只能由其右边填补，所以考虑从左边开始遍历，遇到不等于平均值的就从右边补就行了。
代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=1005;
int n;
int a[N];

int main() {
    cin>>n;
    ll sum=0;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        sum+=a[i];
    }
    ll k=sum/n;
    int ans=0;
    for(int i=1;i<=n;i++) {
        if (a[i]<k) {
            a[i+1]-=(k-a[i]);
            a[i]=k;
            ans++;
        }
        if (a[i]>k) {
            a[i+1]+=(a[i]-k);
            a[i]=k;
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

时间复杂度O(n)
2.这题直接dfs就好了，设置一个vis数组记录哪些点被遍历过了，如果遇到vis[x]==0的情况，把其子树中vis[x]==0的点全置1就好了。
代码：

#include<bits/stdc++.h>
#define pb push_back
#define SZ(x) (int)x.size()
using namespace std;

const int N=100005;
int n,x,q,num;
int vis[N];
vector<int> g[N];


void dfs(int x) {
    int len=SZ(g[x]);
    for(int i=0;i<len;i++) {
        int v=g[x][i];
        if (!vis[v]) {
            num++;
            vis[v]=1;
            dfs(v);
        }
    }
}

int main() {
    cin>>n;
    for(int i=1;i<n;i++) {
        cin>>x;
        g[x].pb(i);
    }
    cin>>q;
    int sum=n;
    while(q--) {
        scanf("%d",&x);
        if (!vis[x]) {
            num=1;
            vis[x]=1;
            dfs(x);
            sum-=num;
            printf("%d\n",sum);
        }
        else {
            printf("%d\n",sum);
        }
    }
    return 0;
}

时间复杂度O(n)
3.按照x.dy.c<y.cx.d排序，如果相等的话，id小的在前面。
代码：

#include<bits/stdc++.h>
#define FULL(x,y) memset(x,y,sizeof(x))
#define ll long long
#define SZ(x) (int)x.size()
#define pb push_back
using namespace std;

const int N=1005;

struct node {
    int c,d,id;
}no[N];

bool cmp(const node& x, const node& y) {
    if (x.d*y.c==y.d*x.c) return x.id < y.id;
    return x.d*y.c < y.d*x.c;
}

int n;

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>no[i].d>>no[i].c;
        no[i].id=i;
    }
    sort(no+1,no+1+n,cmp);
    for(int i=1;i<=n;i++) {
        cout<<no[i].id<<' ';
    }
    return 0;
}

时间复杂度O(nlogn)。
4.这题应该dp，令dp[i][j]表示以i为结尾且与前面的数相乘%2021==j的最长长度，则有状态转移方程：
dp[i][(a[i]*a[j])%2021]=max(dp[i][(a[i]*a[j])%2021], dp[j][a[i]]+1)，当dp[j][a[i]]!=0。且还需维护总数，令开一个cnt[i][j]数组维护。
代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1005;
int n;
int a[N],dp[N][2021],cnt[N][2021],f[N][2021];

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
//初始化
    for(int i=1;i<=n;i++) {
        for(int j=i-1;j>=1;j--) {
            dp[i][(a[i]*a[j])%2021]=2;
            f[i][(a[i]*a[j])%2021]++;
        }
    }
//dp
    for(int i=3;i<=n;i++) {
        for(int j=i-1;j>=2;j--) {
            if (dp[j][a[i]]) {
                dp[i][(a[i]*a[j])%2021]=max(dp[i][(a[i]*a[j])%2021],dp[j][a[i]]+1);
            }
        }
//维护数量
        for(int j=i-1;j>=2;j--) {
            if (dp[i][(a[i]*a[j])%2021]==dp[j][a[i]]+1) {
                if (dp[j][a[i]]==2)cnt[i][(a[i]*a[j])%2021]+=f[j][a[i]];
                else cnt[i][(a[i]*a[j])%2021]+=cnt[j][a[i]];
            }
        }
    }
    int ans=0,sum=0;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<2021;j++) {
            if (dp[i][j]>=3) ans=max(ans,dp[i][j]);
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=0;j<2021;j++) {
            if (dp[i][j]==ans) sum+=cnt[i][j];
        }
    }
    if (ans!=0)cout<<sum<<endl<<ans<<endl;
    else cout<<0<<endl<<0<<endl;
    return 0;
}

时间复杂度O(n^2)。