nowcoder-挑战赛14
#include"stdio.h" long long a,b,c; void pan(){ long long i=0,j=0; if (a%2==0&&i==0) a=a/2,i=1; if (a%3==0&&j==0) a=a/3,j=1; if (b%2==0&&i==0) b=b/2,i=1; if (b%3==0&&j==0) b=b/3,j=1; if (c%2==0&&i==0) c=c/2,i=1; if (c%3==0&&j==0) c=c/3,j=1; } int main() { long long i,j,k,n,t; scanf("%lld",&t); for (i=1;i<=t;i++) { scanf("%lld %lld",&n,&k); a=n+1;b=n+2;c=n+3; pan(); long long ans=a%k*b%k*c%k; printf("%lld\n",ans); } }
1.插入新人名 si,声望为 ai
2.给定名字前缀 pi 的所有人的声望值变化 di
3.查询名字为 sj 村民们的声望值的和(因为会有重名的)
4.查询名字前缀为 pj 的声望值的和
/* 指针占内存大 所以要用数组字典树 trie[maxn][27];表示下一个字母的位置 sign[maxn]表示是否重复,val[maxn]表示前缀和 */ #include"stdio.h" #include"string.h" #define maxn 1050005 long long trie[maxn][27]; long long number[maxn];//人数 long long all[maxn];//声望和 long long name[maxn];//当前人的声望和 long long numname[maxn]; long long lazy[maxn];//标记 long long sum; char s[1000005]; void pushdown(long long p){ long long j; if (lazy[p]==0) return; for (j=1;j<=26;j++) if (trie[p][j]!=0){ long long son=trie[p][j]; lazy[son]+=lazy[p]; all[son]+=number[son]*lazy[p]; name[son]+=numname[son]*lazy[p]; } lazy[p]=0; } void createtrie(char s[],long long x){ long long i,l,j; long long p=0; long long id; for (i=0;i
4 4
2 1
2 3
3 4
4 2
#include"stdio.h" #include"memory.h" struct node { int u,v,next; }edge[100050]; int dfn[100050],low[100050],belong[100050]; int stack[100050],head[100050],visit[100050],bcnt,cnt,tot,inde; int a[100050]; int in[100050]; void add(int x,int y){ cnt++; edge[cnt].u=x; edge[cnt].next=head[x]; edge[cnt].v=y; head[x]=cnt; } int min(int a,int b){if (a>b) return b;else return a;} void tarjan(int x){ int i; tot++; dfn[x]=tot; low[x]=tot; inde++; stack[inde]=x; visit[x]=1; for (i=head[x];i!=-1;i=edge[i].next){ if (dfn[edge[i].v]==0){ tarjan(edge[i].v); low[x]=min(low[x],low[edge[i].v]); } else if (visit[edge[i].v]!=0){ low[x]=min(low[x],dfn[edge[i].v]); } } if (low[x]==dfn[x]){ bcnt++; do { // printf("%d",stack[inde]); visit[stack[inde]]=0; belong[stack[inde]]=bcnt; inde--; } while (x!=stack[inde+1]); } // printf("\n"); return; } int main(){ int n,m; int x,y; int i; int sum=0; scanf("%d %d",&n,&m); memset(head,-1,sizeof(head)); memset(visit,0,sizeof(visit)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); cnt=0;tot=0;inde=0;bcnt=0;sum=0; for(i=1;i<=m;i++) { scanf("%d %d",&x,&y); add(x,y); } for(i=1;i<=n;i++) if(dfn[i]==0) tarjan(i); memset(in,0,sizeof(in)); for (i=1;i<=cnt;i++) if (belong[edge[i].v]!=belong[edge[i].u]) in[belong[edge[i].v]]=1; int l; l=0; for (i=1;i<=n;i++) if (in[belong[i]]==0) { l++; a[l]=i; in[belong[i]]=1; } printf("%d\n",l); for (i=1;i
sum[k]-sum[son]<=m
中的sum[k]已经知道,我们需要求得最小的son,使得sum[k]-m<=sum[son]
。在这里,我们可以应用一下划分树。也就是说,我们先用dfs序构造出来,然后放到划分树里。每次枚举结点的时候,可以找到对应的子树区间。然后对于子树区间,二分枚举第k大,然后划分树log找到值,去判断合不合法。复杂度约为O(n*log(n)^2)。#include"stdio.h" #include"string.h" #define maxn 105000 struct node{ long long v,dis,next; }edge[2*maxn]; long long head[maxn]; long long sum[maxn]; long long number[maxn]; long long sign[maxn][30]; long long cnt; long long m; long long ans; long long max(long long a,long long b){ if (a>b) return a;return b; } void add(long long u,long long v,long long dis){ cnt++; edge[cnt].v=v; edge[cnt].dis=dis; edge[cnt].next=head[u]; head[u]=cnt; } void dfs(long long k,long long father){ long long i,v; number[k]=1; sum[k]=0; for (i=head[k];i!=-1;i=edge[i].next){ v=edge[i].v; if (v!=father){ dfs(v,k); number[k]+=number[v]; sum[k]+=sum[v]+number[v]*edge[i].dis; } } } void find(long long k,long long father){ long long i,v; long long now,ff; for (i=head[k];i!=-1;i=edge[i].next){ v=edge[i].v; if (v!=father) { sign[v][0]=v; now=0;ff=k; while(ff!=-1) { now++; sign[v][now]=sign[ff][now-1]; ff=sign[ff][now-1]; } find(v,k); } } } void query(long long k,long long father) { long long i,v; for (i=head[k];i!=-1;i=edge[i].next) { v=edge[i].v; if (v!=father){ query(v,k); } } long long now=0; long long ff=k; int j=1; while(sign[ff][j]!=-1) { now=sign[ff][j]; if (sum[now]-sum[k]<=m) ans=max(ans,sum[now]-sum[k]); j++; now=sign[ff][j]; if (sum[now]-sum[k]>m) { ff=sign[ff][j-1]; j=1; now=sign[ff][j]; if (now==-1||sum[now]-sum[k]>m) break; } } } int main(){ long long e,t,n,x,y,dis; long long i,j; scanf("%lld",&t); for (e=1;e<=t;e++) { cnt=0; memset(head,-1,sizeof(head)); scanf("%lld %lld",&n,&m); for (i=1;i
线性基大概就是,像网络流类比水流一样,可以把异或中的线性基类比为n维向量空间的一组基。n维向量空间中,可以找到一族基向量,比如单位基,可以去表示空间中的所有向量。我们可以发现,如果我们在异或基中,取2进制的1,10,100,1000,10000......这样子取,空间中的任何数字都能被这组基所表示出来。当然,n为向量空间中的一组基不一定要是单位基,只要n个向量线性无关即可。所以,我们在取线性基的时候,同样保证线性无关即可,即基中的任意一个数不能通过其他的数异或得到。
#include"stdio.h" #include"string.h" #include"algorithm" using namespace std; long long sign[105000][40]; long long b[105000]; long long vis[105000]; long long a[105000]; long long wei[105000]; long long father[105000]; void insert(long long k,long long wei){ long long i; for (i=40;i>=1;i--) if ((k&(1LL<<(i-1)))>0){ if (sign[wei][i]>0) k=k^sign[wei][i]; else { sign[wei][i]=k; return; } } } long long getfather(long long k){ if (father[k]==k) return k; else father[k]=getfather(father[k]); return father[k]; } long long find(long long wei){ long long i; long long ans=0; for (i=40;i>=1;i--)if (sign[wei][i]>0) if ((ans^sign[wei][i])>ans) ans=(ans^sign[wei][i]); return ans; } int main(){ long long ans,n,i,j,x,y; long long l=0; scanf("%lld",&n); for (i=1;i<=n;i++) {scanf("%lld",&a[i]);insert(a[i],i);} for (i=1;i<=n;i++) scanf("%lld",&wei[i]); for (i=1;i<=n;i++) father[i]=i; memset(vis,0,sizeof(vis)); ans=0; for (i=n;i>=1;i--){ if (vis[wei[i]-1]==1) { x=getfather(wei[i]-1); y=getfather(wei[i]); father[y]=x; for (j=1;j<=40;j++) if (sign[y][j]>0){ insert(sign[y][j],x); } } if (vis[wei[i]+1]==1) { x=getfather(wei[i]); y=getfather(wei[i]+1); father[y]=x; for (j=1;j<=40;j++) if (sign[y][j]>0){ insert(sign[y][j],x); } } x=getfather(wei[i]); ans=max(find(x),ans); l++; b[l]=ans; vis[wei[i]]=1; } for (i=l;i>=1;i--) printf("%lld\n",b[i]); }优质内容筛选与推荐>>