牛客挑战赛49 题解
非常抱歉G题本来是换一道题目的，本来想把题目出的更有好一些，结果同学说是找了一道内部校赛题目，结果撞了原题，抱歉给大家打来不好的体验，其实是不是可以删掉G题？但是声明一下D题不是原题，这题的数据范围和原题有一定的出入，导致可能算法有60%的不同
这题非常签到我们可以直接用的
或者
就可以了，然后您就签到成功
代码：
#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';
} 发现只需要算一下位的贡献就可以，大致都是9-0这位的，其他贡献都是1，然后大力分位统计一下即可
代码：
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
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(){
for(int i=1;i<=N;i++) p[i]=add(mul(p[i-1],10ll),ch[i]-'0');
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
inline LL read(){
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(){
n=read(),m=read();
for(int i=1;i<=n;i++) fa[i]=read(),F[i]=i;
for(int i=1,x;i<=m;i++) x=read(),sz[x]++;
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);
} 首先可以证明一个结论，
对于任意一个可行的权值，我们可以让它异或上任意两个点的权值，结果依然可行。
因为你可以从任意一个点出发，走到 再走回来，走到
再走回来，答案就会异或上
和
的权值。
由此，就可以继续证明，任意一次询问的答案，要么是任意选出奇数个点异或起来，要么是任意选出偶数个点异或起来。
考虑给所有权值加上2的30次方,那么选出奇数个数二进制下就一定有2的30次方这一位，偶数则一定没有。
于是，将所有权值加入线性基，询问时只要查询以0或2的30次方作为初始值的最大异或和即可。如果预处理两种大胆，
可以去掉 上的
。复杂度
。
#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
inline LL read(){
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 link(int x,int y){to[++tot]=y,nt[tot]=fs[x],fs[x]=tot;}
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(){
n=read(),m=read(),Q=read(),base=read(),xx=read(),yy=read();
int K=(1<<30);
for(int i=1,x;i<=n;i++) x=read(),BASE::ins(x^K);
for(int i=1,x,y;i<=m;i++) x=read(),y=read(),link(x,y),link(y,x);
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;
}
很容易证明其实对图的限制就是仙⼈掌，部分分只是⽤来骗⼈的。 那么考虑从S到T的最⼤流是什么呢，不难发现最小割要么割在⼀个环上，要么割在⼀条边上。
假如割在⼀个环上，那么必然会割两条边，并且这个环上的最小边会被割。 那么其实我们将所有的环上最小边加到环上其他边上去，最小割不会改变。
那么我们就可以将题⽬变成⼀棵树了，考虑从⼤到小加边，⽤并查集维护合并两个联通块，计算每⼀位 的贡献即可。
复杂度
//#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;}
inline int read()
{
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()
{
n=read();m=read();
REP(i,1,n)ed[i].clear(),ff[i]=i;
memset(vis,0,sizeof(int)*(m+1));
REP(i,1,m)
{
int u=read(),v=read(),w=read();
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
int t=read();
while(t--)
{
init();
doing();
}
return 0;
}
