xiuzhiyuan

$$\href{https://www.acwing.com/blog/content/14845/}{\Huge\color{blue}{题解主页}}$$

10.6万

66大顺_帅气草履虫
hygge_
bobo0612

oneo

Zach_Tang

mouse-knight
xalbc2022

J_513

fangshi
Rainbow888

BT7274

#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int N=10010;
typedef pair<int,int> PII;
PII a[N];
int fa[N];
inline bool cmp(PII a,PII b){
return a.x>b.x;
}
inline int find(int x){
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
int main(){
int n;
while(~scanf("%d",&n)){
int ans=0,maxy=0;
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
maxy=max(maxy,a[i].y);
}
sort(a+1,a+1+n,cmp);
for(int i=0;i<=maxy;i++)
fa[i]=i;
for(int i=1;i<=n;i++){
int x=a[i].x,y=a[i].y;
int p=find(y);
if(p>0){
ans+=x;
fa[p]=p-1;
}
}
printf("%d\n",ans);
}
return 0;
}

Trie树

#include<iostream>
using namespace std;
const int N=100010,M=200010;
int to[M],ne[M],w[M],h[N],idxe=1;
int d[N];
int son[N*31][2],idx;
inline void add(int a,int b,int c){
to[idxe]=b,w[idxe]=c,ne[idxe]=h[a],h[a]=idxe++;
}
void dfs(int x,int from){
for(int i=h[x];i;i=ne[i]){
int j=to[i];
if(j==from)
continue;
d[j]=d[x]^w[i];
dfs(j,x);
}
}
inline void insert(int x){
int p=0;
for(int i=30;~i;i--){
int u=x>>i&1;
if(!son[p][u])
son[p][u]=++idx;
p=son[p][u];
}
}
inline int search(int x){
int p=0,res=0;
for(int i=30;~i;i--){
int u=x>>i&1;
res<<=1;
if(son[p][!u])
p=son[p][!u],res++;
else
p=son[p][u];
}
return res;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
}
dfs(0,-1);
int ans=0;
insert(d[0]);
for(int i=1;i<n;i++){
ans=max(ans,search(d[i]));
insert(d[i]);
}
printf("%d",ans);
return 0;
}

Trie树

#include<iostream>
using namespace std;
const int N=3100010;
int son[N][2],idx;
inline int search(int x){
int p=0,res=0;
for(int i=30;i>=0;i--){
int u=x>>i&1;
res<<=1;
if(son[p][!u])
p=son[p][!u],res++;
else
p=son[p][u];
}
return res;
}
inline void insert(int x){
int p=0;
for(int i=30;i>=0;i--){
int u=x>>i&1;
if(!son[p][u])
son[p][u]=++idx;
p=son[p][u];
}
}
int main(){
int n,ans=0;
scanf("%d",&n);
while(n--){
int x;
scanf("%d",&x);
ans=max(ans,search(x));
insert(x);
}
printf("%d",ans);
return 0;
}

Trie树

#include<iostream>
#include<cstring>
using namespace std;
const int N=1000010;
char s[N];
int son[N][30],cnt[N],idx;
inline void add(char *a){
int p=0,len=strlen(a);
for(int i=0;i<len;i++){
if(!son[p][a[i]-'a'])
son[p][a[i]-'a']=++idx;
p=son[p][a[i]-'a'];
}
cnt[p]++;
}
inline int count(char *a){
int p=0,len=strlen(a),res=0;
for(int i=0;i<len;i++){
if(!son[p][a[i]-'a'])
return res;
p=son[p][a[i]-'a'];
res+=cnt[p];
}
return res;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
while(n--){
scanf("%s",s);
}
while(m--){
scanf("%s",s);
printf("%d\n",count(s));
}
return 0;
}

kmp

#include<iostream>
using namespace std;
const int N=1000010;
int ne[N];
char a[N];
int main(){
int n,t=0;
while(scanf("%d",&n),n){
scanf("%s",a+1);
printf("Test case #%d\n",++t);
for(int i=2,j=0;i<=n;i++){
while(j&&a[i]!=a[j+1])
j=ne[j];
if(a[i]==a[j+1])
j++;
ne[i]=j;
}
for(int i=2;i<=n;i++)
if(i%(i-ne[i])==0&&ne[i])
printf("%d %d\n",i,i/(i-ne[i]));
puts("");
}
return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=300010,P=131;
char s[N];
int n;
LL h[N],p[N];
int sa[N];
inline LL get(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
inline int gmcp(int a,int b){
int l=0,r=min(n-a+1,n-b+1);
while(l<r){
int mid=l+r+1>>1;
if(get(a,a+mid-1)!=get(b,b+mid-1))
r=mid-1;
else
l=mid;
}
return l;
}
inline bool cmp(int a,int b){
int l=gmcp(a,b);
int av=a+l>n?-0x3f3f3f3f:s[a+l];
int bv=b+l>n?-0x3f3f3f3f:s[b+l];
return av<bv;
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
p[0]=1;
for(int i=1;i<=n;i++){
h[i]=h[i-1]*P+s[i]-'a'+1;
p[i]=p[i-1]*P;
sa[i]=i;
}
sort(sa+1,sa+1+n,cmp);
for(int i=1;i<=n;i++)
printf("%d ",sa[i]-1);
puts("");
printf("0 ");
for(int i=2;i<=n;i++)
printf("%d ",gmcp(sa[i-1],sa[i]));
return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=2000010,P=131;
char s[N];
LL h1[N],h2[N],p[N];
inline LL get(LL *h,LL l,LL r){
return h[r]-h[l-1]*p[r-l+1];
}
int main(){
int cnt=0;
while(scanf("%s",s+1),strcmp(s+1,"END")){
int n=strlen(s+1)<<1;
for(int i=n;i;i-=2){
s[i]=s[i>>1];
s[i-1]='z'+1;
}
s[++n]='z'+1;
p[0]=1;
for(int i=1,j=n;i<=n;i++,j--){
h1[i]=h1[i-1]*P+s[i]-'a'+1;
h2[i]=h2[i-1]*P+s[j]-'a'+1;
p[i]=p[i-1]*P;
}
LL ans=1;
for(int i=1;i<=n;i++){
LL r=min(i-1,n-i);
if(ans>=r||get(h1,i-ans,i-1)!=get(h2,n-i-ans+1,n-i))
continue;
while(ans<=r&&get(h1,i-ans,i-1)==get(h2,n-i-ans+1,n-i))
ans++;
ans--;
}
printf("Case %d: %d\n",++cnt,ans);
}
return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1000010,Hash=131;
LL sum[N],p[N];
char s[N];
int main(){
scanf("%s",s+1);
int len=strlen(s+1),n;
p[0]=1;
for(int i=1;i<=len;i++){
sum[i]=sum[i-1]*Hash+(s[i]-'a'+1);
p[i]=p[i-1]*Hash;
}
scanf("%d",&n);
while(n--){
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(sum[r1]-sum[l1-1]*p[r1-l1+1]==sum[r2]-sum[l2-1]*p[r2-l2+1])
puts("Yes");
else
puts("No");
}
return 0;
}

#include<iostream>
using namespace std;
typedef long long LL;
const int N=100010,mod=92083;
int tmp[10];
int h[N],ne[N];
int snow[N][10],idx;
inline int geth(int *a){
int res1=0,res2=1;
for(int i=0;i<6;i++){
res1=(res1+a[i])%mod;
res2=(LL)res2*a[i]%mod;
}
return (res1+res2)%mod;
}
inline bool check(int *a,int *b){
for(int i=0;i<6;i++){
bool flag=1;
for(int k=0;k<6;k++)
if(a[k]!=b[(i+k)%6])
flag=0;
if(flag)
return 1;
flag=1;
for(int k=0;k<6;k++)
if(a[k]!=b[((i-k)%6+6)%6])
flag=0;
if(flag)
return 1;
}
return 0;
}
inline bool insert(int *a){
int hash=geth(a);
for(int i=h[hash];i;i=ne[i])
if(check(a,snow[i]))
return 1;
idx++;
for(int i=0;i<6;i++)
snow[idx][i]=a[i];
ne[idx]=h[hash];
h[hash]=idx;
return 0;
}
int main(){
int n;
scanf("%d",&n);
while(n--){
for(int i=0;i<6;i++)
scanf("%d",&tmp[i]);
if(insert(tmp)){
puts("Twin snowflakes found.");
return 0;
}
}
puts("No two snowflakes are alike.");
return 0;
}

#include<iostream>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<LL,int> PLI;
const int N=100010;
PLI a[N],ans[N];
int p[N],l[N],r[N];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i].x);
a[i].y=i;
}
sort(a+1,a+1+n);
a[0].x=-4e9,a[n+1].x=4e9;
for(int i=1;i<=n;i++)
l[i]=i-1,r[i]=i+1,p[a[i].y]=i;
for(int i=n;i>=2;i--){
int j=p[i],left=l[j],right=r[j];
LL lv=a[j].x-a[left].x,rv=a[right].x-a[j].x;
if(lv<=rv)
ans[i]={lv,a[left].y};
else
ans[i]={rv,a[right].y};
l[right]=left,r[left]=right;
}
for(int i=2;i<=n;i++)
printf("%lld %d\n",ans[i].x,ans[i].y);
return 0;
}