题解 | #牛客练习赛84#

牛客推荐系统开发之静态特征获取

https://ac.nowcoder.com/acm/contest/11174/A

A
A应该没啥难的吧直接map<string,map<string,int> >标记 机器ID和文章ID就行

map<string,map<string,int> > mp;
int main()
{
    tcase {
        string a,b;
        cin>>a>>b;
        if(mp[a][b]==0) {
            mp[a][b]=1;
            cout<<"YES"<<endl;
        }
        else {
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

B
直接bfs当前状态看能不能翻转成全是0就行
时间复杂度 O(16162^16)就行

int a[10][10];
void reverse(int x,int y) {
    a[x-1][y]=!a[x-1][y];
    a[x+1][y]=!a[x+1][y];
    a[x][y-1]=!a[x][y-1];
    a[x][y+1]=!a[x][y+1];
    a[x][y]=!a[x][y];
}
map<ll,int> mp;
int main()
{
    closeiostream;
    ll x=0,p=1;
    for(int i=1;i<=4;i++) {
        for(int j=1;j<=4;j++) {
            char ch;
            cin>>ch;
            a[i][j]=ch-'0';
            x+=a[i][j]*p;
            p*=2;
        }
    }
    queue<ll> que;
    mp[x]=1;
    que.push(x);
    while(!que.empty()) {
        if(mp[0]) break;
        ll t=que.front();
        que.pop();
        p=1;
        for(int i=1;i<=4;i++) {
            for(int j=1;j<=4;j++) {
                if(t&p) a[i][j]=1;
                else a[i][j]=0;
                p*=2;
            }
        }
        for(int i=1;i<=4;i++) {
            for(int j=1;j<=4;j++) {
                reverse(i,j);
                p=1,x=0;
                for(int i1=1;i1<=4;i1++) {
                    for(int j1=1;j1<=4;j1++) {
                        x+=a[i1][j1]*p;
                        p*=2;
                    }
                }
                reverse(i,j);
                if(mp[x]) continue;
                mp[x]=1;
                que.push(x);
            }
        }
    }
    if(mp[0]) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

C
从时间复杂度分析那必然是n方的,我们怎样才能n方实现呢? 先考虑不是两两不能重复的种数为ans="∏_1^4▒∑_1^n▒〖a[i]〗" 在减掉有两两重复的种数不就可以了? 那怎么实现呢??? 我们从四个里面选出来一对两个a,b有重复,另外两个c,d没有,有c(2,4)="6种情况" on枚举a,b的重复项在on枚举c,d的相同个数com,c有而d没有棋的个数cntc, d有而c没有棋的个数cntd, ans-="com这样就行" 减掉贡献就行。 另外还有两对有重复的情况要减掉,a="b,c=d" if(i="=1)" 再考虑有三个有重复而另一个不是的情况有四种情况减去贡献 再考虑有四个有重复的情况有四种情况去贡献即可。

int a[5][5005];
int main()
{
    closeiostream;
    int n;
    cin>>n;
    ll ans=1;
    for(int i=1;i<=4;i++) {
        ll res=0;
        for(int j=1;j<=n;j++) {
            char ch;
            cin>>ch;
            a[i][j]=ch-'0';
            res+=a[i][j];
        }
        ans*=res;
    }
    // 2
    for(int i=1;i<=4;i++) {
        for(int j=i+1;j<=4;j++) {
            for(int k=1;k<=n;k++) {
                if(a[i][k] && a[j][k]) {
                    int p=0,q=0;
                    for(int x=1;x<=4;x++) {
                        if(x!=i && x!=j) {
                            if(p==0) p=x;
                            else q=x;
                        }
                    }
                    ll cntq=0,cntp=0,com=0;
                    for(int y=1;y<=n;y++) {
                        if(y==k) continue;
                        if(a[q][y] && !a[p][y]) cntq++;
                        else if(!a[q][y] && a[p][y]) cntp++;
                        else if(a[q][y] && a[p][y]) com++;
                    }
                    ans-=cntq*cntp+(cntq+cntp+com-1)*com;
                    if(i==1) ans-=com;
                }
            }
        }
    }
    // 3
    for(int i=1;i<=4;i++) {
        for(int j=1;j<=n;j++) {
            if(!a[i][j]) continue;
            for(int k=1;k<=n;k++) {
                if(k==j) continue;
                int res=0;
                for(int x=1;x<=4;x++)
                    if(x!=i) res+=a[x][k];
                if(res==3) ans--;
            }
        }
    }
    // 4
    for(int i=1;i<=n;i++) {
        int res=0;
        for(int j=1;j<=4;j++) {
            res+=a[j][i];
        }
        if(res==4) ans--;
    }
    cout<<ans<<endl;
    return 0;
}

D我写崩了,

E
一看树的路径就知道必然是点分治题,用点分治维护路径 dis[v][0]="max(dis[u][0],w);维护路径最大值" dis[v][1]="min(dis[u][1],w);维护路径最小值" 我们得到路径之后不可能去n方计算答案 其实我们可以看到这是一个很清楚的二维偏序问题,我们首先对pair<max,min> a[N]这样的结构最大值升序排序
然后呢?
对于遍历到的a[i]我们知道前面的j<i的点a[j],最大值都是小于a[i]的,所以对于a[j]来说,如果a[j]的最小值小于a[i]的最小值,贡献等于 a[i].maxa[j].min, 如果a[j]的最小值大于等于a[i]的最小值,贡献等于 a[i].maxa[i].min,用树状数组维护所有的最小值就行,这样就可以logn地得到所有小于a[i].min的a[j],min的和sum了, 还有一点就是要离散化最小值,完毕。代码如下:

#include<bits/stdc++.h>
#define tcase int Case;cin>>Case;while(Case--)
#define closeiostream ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define bug3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define bug2(a,b) cout<<a<<" "<<b<<endl
#define bug1(a) cout<<a<<endl
#define ll long long
#define PI acos(-1)
#define N 100005
#define P pair<ll,ll>
#define fi first
#define se second
#define makep make_pair
#define ull unsigned long long
//#define endl '\n'
using namespace std;
const ll mod=998244353;
ll c[N][2];
vector<ll> b;
int n,rt,siz[N],maxx[N],dis[N][2];
bool vis[N];
ll a[N];
vector<int> e[N];
int sum;
int id(ll x) {
    return lower_bound(b.begin(),b.end(),x)-b.begin()+1;
}
int lowbit(int x) {
    return x&(-x);
}
void update(int x,int y,int s) {
    for(int i=x;i<=n;i+=lowbit(i))
    c[i][s]=(c[i][s]+mod+y)%mod;
}
ll getsum(int x,int s) {
    ll ans=0;
    for(int i=x;i;i-=lowbit(i))
    ans=(ans+c[i][s]+mod)%mod;
    return ans;
}
void getrt(int u, int fa) {
    siz[u]=1;
    maxx[u]=0;
    for(auto x:e[u]) {
        int v=x;
        if(v==fa || vis[v]) continue;
        getrt(v,u);
        maxx[u]=max(maxx[u],siz[v]);
        siz[u]+=siz[v];
    }
    maxx[u]=max(maxx[u],sum-siz[u]);
    if(maxx[u]<maxx[rt]) rt=u;
}
P dd[N],dx[N];
bool cmp(P x,P y) {
    return x.fi<y.fi;
}
int cnt,cntz;
void getdis(int u, int fa) {
    dd[++cntz].fi=dis[u][0];
    dd[cntz].se=dis[u][1];
    for(auto x:e[u]) {
        int v=x,w=a[x];
        if(v==fa || vis[v]) continue;
        dis[v][0]=max(dis[u][0],w);
        dis[v][1]=min(dis[u][1],w);
        getdis(v,u);
    }
}
ll ans=0;
void dfz(int u,int fa) {
    vis[u]=true;
    cnt=0;
    dis[u][0]=a[u];
    dis[u][1]=a[u];
    for(auto x:e[u]) {
        int v=x,w=a[x];
        if(v==fa || vis[v]) continue;
        dis[v][0]=max(dis[u][0],w);
        dis[v][1]=min(dis[u][1],w);
        cntz=0;
        getdis(v,u);
        sort(dd+1,dd+1+cntz,cmp);
        for(int i=1;i<=cntz;i++) {
            ans=(ans+(dd[i].fi*dd[i].se%mod))%mod;
            dx[++cnt]=dd[i];
            int idx=id(dd[i].se);
            ll res=getsum(idx,0),rs=i-getsum(idx,1)-1;
            rs=(rs+mod)%mod;
            res=(res+mod)%mod;
            ans=(ans-res*dd[i].fi%mod+mod)%mod;
            ans=(ans-rs*dd[i].se%mod*dd[i].fi%mod+mod)%mod;
            update(idx,dd[i].se,0);
            update(idx,1,1);
        }
        for(int i=1;i<=cntz;i++) {
            int idx=id(dd[i].se);
            update(idx,-dd[i].se,0);
            update(idx,-1,1);
        }
    }
    sort(dx+1,dx+1+cnt,cmp);
    for(int i=1;i<=cnt;i++) {
        int idx=id(dx[i].se);
        ll res=getsum(idx,0),rs=i-getsum(idx,1)-1;
        rs=(rs+mod)%mod;
        res=(res+mod)%mod;
        ans=(ans+res*dx[i].fi%mod)%mod;
        ans=(ans+rs*dx[i].se%mod*dx[i].fi%mod)%mod;
        update(idx,dx[i].se,0);
        update(idx,1,1);
    }
    for(int i=1;i<=cnt;i++) {
        int idx=id(dx[i].se);
        update(idx,-dx[i].se,0);
        update(idx,-1,1);
    }
    for(auto x:e[u]) { 
        int v=x;
        if(v==fa || vis[v]) continue;
        sum=siz[v];
        rt=0;
        maxx[rt]=INT_MAX;
        getrt(v,u);
        getrt(rt,-1);
        dfz(rt,u);
    }
}
void Init_Solve() {
    rt=0;
    maxx[rt]=INT_MAX;
    sum=n;
    getrt(1,-1);
    getrt(rt,-1);
    dfz(rt,-1);
}
int main()
{
    closeiostream;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        b.push_back(a[i]);
        ans=(ans+a[i]*a[i]%mod)%mod;
    }
    sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    Init_Solve();
    cout<<ans<<endl;
    return 0;
}
全部评论

相关推荐

有工作后先养猫:太好了,是超时空战警,我们有救了😋
点赞 评论 收藏
分享
dongsheng66:如果想进大厂的话,在校经历没必要占这么大篇幅,可以把专业技能单独放一个专栏写,可以加个项目经历
点赞 评论 收藏
分享
评论
5
收藏
分享
牛客网
牛客企业服务