题解 | #牛客练习赛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; }