头像

奇点lzy




离线:8小时前


最近来访(10)
用户头像
RyanMoriarty
用户头像
InvolutionZ
用户头像
鮮笙
用户头像
catsayer_9
用户头像
五星市民欧某人
用户头像
咬不动鸡排吖

活动打卡代码 AcWing 841. 字符串哈希

include[HTML_REMOVED]

using namespace std;

typedef unsigned long long ULL;

const int N=1000010,base=131;//进制

char str[N];

ULL h[N],p[N]; //h数组是求前缀哈希值,p数组是求进制的i次幂

ULL get(int l,int r)
{ //求一段区间的哈希值
return h[r]-h[l-1]*p[r-l+1];
}

int main()
{
int m,n;
cin >> n >> m;
scanf(“%s”,str+1);

p[0]=1;
for(int i=1;i<=n;i++)
{
    h[i]=h[i-1]*base+str[i]-'a'+1;  //利用前缀和的思想求哈希值
    p[i]=p[i-1]*base;
}

while(m–)
{
int l,r,x,y;
scanf(“%d%d%d%d”,&l,&r,&x,&y);
if(get(l,r)==get(x,y))
cout<<”Yes”<<endl;
else
cout<<”No”<<endl;
}

return 0;

}



活动打卡代码 AcWing 840. 模拟散列表

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int N=100003;
int h[N];
int e[N],ne[N],idx; //为链表开的东西 数组模拟链表

void insert(int x)
{
int k=(x%N+N)%N; //一种哈希方式 由于x%N可能是负数,所以加上一个N(x%N+N)确保整体是正数

e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;

}

bool find(int x)
{
int k=(x%N+N)%N;
for(int i=h[k];i!=-1;i=ne[i])
if(e[i]==x)
return true;

return false;

}

int main()
{
int n;
scanf(“%d”,&n);

memset(h,-1,sizeof h);  //初始化h数组,空指针一般用-1来表示

while(n--)
{
    char op[2];
    int x;
    scanf("%s%d",op,&x);

    if(op[0]=='I') insert(x);
    else
    {
        if(find(x)) puts("Yes");
        else puts("No");
    }
}
return 0;

}



活动打卡代码 AcWing 842. 排列数字

include[HTML_REMOVED]

using namespace std;

const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u)
{
if(u == n)
{
for(int i=0;i[HTML_REMOVED]>n;
dfs(0);
}



活动打卡代码 AcWing 789. 数的范围

include[HTML_REMOVED]

using namespace std;

const int N = 1e6+10;
int n,m;
int q[N];
int main()
{
scanf(“%d %d”,&n,&m);
for(int i=0;i[HTML_REMOVED]> 1;
if(q[mid]>=x) r = mid;
else l = mid + 1;
}
if(q[l]!=x) cout << “-1 -1” << endl;
else
{
cout << l << ‘ ‘;
int l = 0,r = n - 1;
while(l[HTML_REMOVED]> 1;
if(q[mid]<=x) l = mid;
else r = mid - 1;
}
cout << l <<endl;
}
}
return 0;
}



活动打卡代码 AcWing 788. 逆序对的数量

include[HTML_REMOVED]

using namespace std;

typedef long long ll;

const int N = 1e5+10;
int n;
int q[N];
int temp[N];
ll merge_sort(int q[] , int l, int r)
{
if(l>=r) return 0;
int mid= l + r >> 1;
ll res=merge_sort(q, l , mid)+merge_sort(q, mid+1, r);
int k = 0 , i = l , j = mid + 1;
while(i <= mid && j <= r)
{
if(q[i]<=q[j]) temp[k] = q[i];
else
{
res += mid - i + 1;
temp[k] = q[j];
}
}
while(i<=mid) temp[k] = q[i];
while(j<=r) temp[k] = q[j];
for(i=l,k=0;i<=r;i,k) q[i] = temp[k];
return res;
}
int main()
{
scanf(“%d”,&n);
for(int i=0;i<n;i++) scanf(“%d”,&q[i]);
cout << merge_sort(q,0,n-1) << endl;
}



活动打卡代码 AcWing 787. 归并排序

include [HTML_REMOVED]

using namespace std;

const int N = 1e5 + 10;

int a[N], tmp[N];

void merge_sort(int q[], int l, int r)
{
if (l >= r) return;

int mid = l + r >> 1;

merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
    if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
    else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];

for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

}

int main()
{
int n;
scanf(“%d”, &n);
for (int i = 0; i < n; i ++ ) scanf(“%d”, &a[i]);

merge_sort(a, 0, n - 1);

for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);

return 0;

}



活动打卡代码 AcWing 786. 第k个数

include[HTML_REMOVED]

using namespace std;

const int N = 1e6+10;

int q[N];

int quick_sort(int q[],int l,int r,int k)
{
if(l>=r) return q[l];

int x=q[l + r >> 1],i=l-1,j=r+1;
while(i<j)
{
    do i++;while(q[i]<x);
    do j--;while(q[j]>x);
    if(i<j) swap(q[i],q[j]);
}

int s1=j-l+1;
if(k<=s1) return quick_sort(q,l,j,k);
else return quick_sort(q,j+1,r,k-s1);
}

int main()
{
int n,k;
scanf(“%d %d”,&n,&k);
for(int i=0;i<n;i++)
{
scanf(“%d”,&q[i]);
}
cout<<quick_sort(q,0 , n-1 , k)<<endl;
return 0;
}



活动打卡代码 AcWing 785. 快速排序

include[HTML_REMOVED]

using namespace std;

const int N = 1e6 + 10;
int n;
int a[N];

void quick_sort(int q[],int l,int r)
{
if(l>=r) return;

int x=q[l+r>>1],i=l-1,j=r+1;
while(i<j)
{
    do i++;while(q[i]<x);
    do j--;while(q[j]>x);
    if(i<j) swap(q[i],q[j]);
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);

}
int main()
{

scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
quick_sort(a,0,n-1);
for(int i=0;i<n;i++) printf("%d ",a[i]);
return 0;

}



活动打卡代码 AcWing 785. 快速排序

include[HTML_REMOVED]

using namespace std;

const int N = 1e6 + 10;
int n;
int a[N];

void quick_sort(int q[],int l,int r)
{
if(l>=r) return;

int x=q[l+r>>1],i=l-1,j=r+1;
while(i<j)
{
    do i++;while(q[i]<x);
    do j--;while(q[j]>x);
    if(i<j) swap(q[i],q[j]);
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);

}
int main()
{

scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
quick_sort(a,0,n-1);
for(int i=0;i<n;i++) printf("%d ",a[i]);
return 0;

}




include [HTML_REMOVED]

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int a[N], tmp[N];

LL merge_sort(int q[], int l, int r)
{
if (l >= r) return 0;

int mid = l + r >> 1;

LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);

int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
    if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
    else
    {
        res += mid - i + 1;
        tmp[k ++ ] = q[j ++ ];
    }
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];

for (i = l, k = 0; i <= r; i ++, k ++ ) q[i] = tmp[k];

return res;

}

int main()
{
int n;
scanf(“%d”, &n);
for (int i = 0; i < n; i ++ ) scanf(“%d”, &a[i]);

cout << merge_sort(a, 0, n - 1) << endl;

return 0;

}