# 牛客挑战赛49 题解 精

```#include<bits/stdc++.h>
using namespace std;
int a[1000005],n;
map<int,int> mp;
long long ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
mp[a[i]]++;
}
for(int i=1;i<=n;i++) ans=max(ans,1LL*mp[a[i]]*a[i]);
cout<<ans<<'\n';
}```

```#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 100020
char ch[M]; int N;
namespace btf{
int sum[M*100];
inline void solve(){
int n=0; LL ans=0;
for(int i=1;i<=N;i++) n=n*10ll+(ch[i]-'0');
for(int i=1;i<=n;i++){
int x=i;
while(x) sum[i]+=x%10,x/=10;
}
for(int i=2;i<=n;i++) ans+=(LL)abs(sum[i]-sum[i-1]);
printf("%lld\n",ans);
}
}
#define mod 1000000007
namespace  CALC{
inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
inline int mns(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
inline int mul(LL x,LL y){return x*y%mod;}
inline void upd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
inline void dec(int &x,int y){x=(x-y<0)?(x-y+mod):(x-y);}
inline int qpow(int x,int sq){int res=1;for(;sq;sq>>=1,x=mul(x,x))if(sq&1)res=mul(res,x);return res;}
}using namespace CALC;
namespace sub1{
int p[M],dat[M],ans;
inline void solve(){
dec(p[N],1);
for(int i=N;i;i--){
int tmp=(i==N)?1:((N-i)*9-1);
dat[i]=mns(p[i],p[i-1]),upd(ans,mul(dat[i],tmp));
}
printf("%d\n",ans);
}
}

int main(){
scanf("%s",ch+1),N=strlen(ch+1);
if(N<=7) btf::solve(); else sub1::solve();
return 0;
}
```

100% 的数据

```#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ---------------------- "<<endl
#define LL long long
#define DB double
LL nm=0; bool fh=true; char cw=getchar();
for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-');
for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
return fh?nm:-nm;
}
#define M 3000200
int n,m,F[M],fa[M],sz[M]; LL ans;
inline int Fd(int x){return (F[x]==x)?x:(F[x]=Fd(F[x]));}

int main(){
for(int i=1;i<=n;i++) if(!sz[i]) F[i]=fa[i];
for(int i=n,x;i;--i){
x=Fd(i);
if(sz[x]){
ans+=(LL)i,--sz[x];
if(!sz[x]) F[x]=fa[x];
}
} printf("%lld\n",ans);
return 0;
}

```

```#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
int n,m,nxt[N][26],pre[N][26],pret[N][26],nxtt[N][26],cnt[N][26],lst[26];
int pos,mid,lim,ans;char str[N],t[N];
void dfs(int dep,int x,int y,int z,int now){
if(dep>lim){
if(~mid){if(x<y&&cnt[y-1][mid]-cnt[x][mid]>0&&z>pos)ans=max(ans,now<<1|1);}
else{if(x<y&&z>=pos)ans=max(ans,now<<1);}
return;
}
int c=t[dep]-'a';
if(nxt[x][c]&&pre[y][c]&&pret[z][c])dfs(dep+1,nxt[x][c],pre[y][c],pret[z][c],now+1);
dfs(dep+1,x,y,z,now);
}
void dfs2(int dep,int x,int y,int z,int now){
if(dep<lim){
if(~mid){if(x>y&&cnt[x-1][mid]-cnt[y][mid]>0&&z<pos)ans=max(ans,now<<1|1);}
else{if(x>y&&z<=pos)ans=max(ans,now<<1);}
return;
}
int c=t[dep]-'a';
if(nxt[x][c]&&pre[y][c]&&nxtt[z][c])dfs2(dep-1,nxt[x][c],pre[y][c],nxtt[z][c],now+1);
dfs2(dep-1,x,y,z,now);
}
int main(){
scanf("%s",str+1);n=strlen(str+1);
scanf("%s",t+1);m=strlen(t+1);
for(int i=n;~i;i--){
for(int j=0;j<26;j++)nxt[i][j]=lst[j];
lst[str[i]-'a']=i;
}
memset(lst,0,sizeof(lst));
for(int i=1;i<=n+1;i++){
for(int j=0;j<26;j++)pre[i][j]=lst[j];
lst[str[i]-'a']=i;
}
for(int i=1;i<=n;i++)memcpy(cnt[i],cnt[i-1],sizeof(cnt[i])),cnt[i][str[i]-'a']++;
memset(lst,0,sizeof(lst));
for(int i=m;~i;i--){
for(int j=0;j<26;j++)nxtt[i][j]=lst[j];
lst[t[i]-'a']=i;
}
memset(lst,0,sizeof(lst));
for(int i=1;i<=m+1;i++){
for(int j=0;j<26;j++)pret[i][j]=lst[j];
lst[t[i]-'a']=i;
}
for(int i=1;i<=m;i++){
pos=i;mid=t[i]-'a';
if(i-1<m-i)lim=i-1,dfs(1,0,n+1,m+1,0);
else lim=i+1,dfs2(m,n+1,0,0,0);
}
mid=-1;
for(int i=1;i<=m;i++){
if(i<=m-i)lim=i,pos=i+1,dfs(1,0,n+1,m+1,0);
else lim=i+1,pos=i,dfs2(m,n+1,0,0,0);
}
printf("%d\n",ans);
return 0;
}
```

```#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
int d[maxn];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n - 1; i++)
{
int u, v;
scanf("%d%d", &u, &v);
d[u]++; d[v]++;
}
sort(d + 1, d + n + 1);
int res = 0;
for (int i = 1; i <= n; i++)
if (i % 2) res += 2 - d[i];
else res += -2 + d[i];
printf("%d\n", res / 2);
}```

```#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ---------------------- "<<endl
#define LL long long
#define DB double
LL nm=0; bool fh=true; char cw=getchar();
for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-');
for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
return fh?nm:-nm;
}
#define M 500200
namespace BASE{
int p[32];
inline void ins(int x){
for(int k=30;~k;--k) if(x&(1<<k)){
if(!p[k]){p[k]=x;return;}
x^=p[k];
}
}
inline int qry(int x){
for(int k=30;~k;--k) if((x^p[k])>x) x^=p[k];
return x;
}
}
int to[M<<1],nt[M<<1],fs[M],tot;
int n,m,Q,a[M],Col[M],base,xx,yy;
inline void dfs(int x,int c){Col[x]=c; for(int i=fs[x];i;i=nt[i]) if(Col[to[i]]==-1) dfs(to[i],c^1);}

int main(){
int K=(1<<30);
memset(Col,-1,sizeof(Col)),dfs(1,1);
LL Ev=BASE::qry(0)^K,Od=BASE::qry(K)^K,ans=0ll;
int lastans=0;
while(Q--){
xx=((LL)xx*base+lastans)%n+1;
yy=((LL)yy*base+lastans)%n+1;
lastans=(Col[xx]==Col[yy])?Od:Ev;
ans+=(LL)lastans;
} printf("%lld\n",ans);
return 0;
}```

```//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
{
int s=0,f=1; char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')ch=getchar(),f=-1;
while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
return ~f?s:-s;
}

const int maxn=2e5+20;
#define size sssss
struct Edge {
int u,v,w;
Edge(int _u=0,int _v=0,int _w=0){ u=_u; v=_v; w=_w;}
};
Edge E[maxn];
int vis[maxn];

vector<int>ed[maxn];

int ff[maxn];
int fin(int x){ return x==ff[x]?x:ff[x]=fin(ff[x]);}
inline void merge(int x,int y){ x=fin(x); y=fin(y); ff[y]=x;}

int n,m;
int fa[maxn],deep[maxn],fai[maxn];

void dfs(int u)
{
for(int i:ed[u])
if(i!=fai[u])
{
int v=u^E[i].u^E[i].v;
fai[v]=i;
fa[v]=u;
deep[v]=deep[u]+1;
dfs(v);
}
}

int sz[maxn][32][2],size[maxn];

inline void init()
{
REP(i,1,n)ed[i].clear(),ff[i]=i;
memset(vis,0,sizeof(int)*(m+1));
REP(i,1,m)
{
E[i]=Edge(u,v,w);
}
sort(E+1,E+m+1,[](Edge a,Edge b){ return a.w>b.w;});
REP(i,1,m)
{
int u=E[i].u,v=E[i].v;
if(fin(u)==fin(v))continue;
vis[i]=1;
merge(u,v);
ed[u].push_back(i);
ed[v].push_back(i);
}
fai[1]=0; deep[1]=1; dfs(1);
REP(i,1,m)if(!vis[i])
{
int u=E[i].u,v=E[i].v,w=E[i].w;
while(u!=v)
{
if(deep[u]>deep[v])swap(u,v);
E[fai[v]].w+=w;
v=fa[v];
}
}
}

unsigned ll ans=0;

inline void Merge(int u,int v,int w)
{
u=fin(u); v=fin(v);
REP(j,0,20)
{
unsigned ll num=0;
int val=w>>j&1;
REP(op,0,1)num+=(unsigned ll)sz[u][j][op]*sz[v][j][op^val^1];
ans+=(1<<j)*num;
REP(op,0,1)sz[u][j][op]+=sz[v][j][op];
}
w&=~((1<<21)-1);
ans+=(unsigned ll)size[u]*size[v]*w;

ff[v]=u; size[u]+=size[v];
}

inline void doing()
{
ans=0;
REP(i,1,n)
{
size[i]=1;
memset(sz[i],0,sizeof(sz[i]));
ff[i]=i;
REP(j,0,20)sz[i][j][i>>j&1]++;
}
int num=0;
REP(i,1,m)if(vis[i])E[++num]=E[i];
sort(E+1,E+num+1,[](Edge a,Edge b){ return a.w>b.w;});
REP(i,1,num)
{
int u=E[i].u,v=E[i].v,w=E[i].w;
Merge(u,v,w);
}
printf("%llu\n",ans);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("okfly.in","r",stdin);
freopen("okfly.out","w",stdout);
#endif
while(t--)
{
init();
doing();
}
return 0;
}```

# 近期热帖

• 回复(2) 发表于 2021-05-11 10:48:26
• 回复(0) 发表于 2021-05-11 15:17:22
• 回复(0) 发表于 2021-05-11 20:07:37
• 回复(0) 发表于 2021-05-11 17:09:22
• 回复(0) 发表于 2021-05-11 17:58:36

# 等你来战

• 报名截止时间：2021-05-20 16:00
• 报名截止时间：2021-05-14 22:00
• 报名截止时间：2021-05-14 22:00
• 报名截止时间：2021-05-21 22:00
• 报名截止时间：2021-05-28 22:00
• 报名截止时间：2021-07-17 17:00
• 报名截止时间：2021-07-19 17:00

# 热门推荐

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题