ya.h
5分钟前
思路:
创建一个存储删除重复元素后的新链表,遍历源链表元素,并将非重复元素接到r指针后面,最后返回操作后的链表即可

要点:
1.内层循环:若下一结点不为空,且当前结点数值域值等于下一结点数值域值,则跳过该节点
2.由于重复的结点一个都不保留,故用一个bool变量flag记录是否为重复的结点元素,内层while循环跳出后,flag为假则说明该元素是重复结点元素的最后一个,无需添加;否则创建一个数值域相等的无指向的新结点q接到新链表后面
3.头结点可能被删掉时,创建一个虚拟头结点指向头结点,返回时返回虚拟节点的下一结点即可

代码:
ListNode* deleteDuplication(ListNode* head) {
    //虚拟头结点
    ListNode* p=new ListNode(-1);
    ListNode* r=p;
    for(;head;)
    {
        bool flag=true;
        while(head->next&&head->val==head->next->val)
        {
            flag=false;
            head=head->next;
        }
        if(flag)
        {
            ListNode* q=new ListNode(head->val);
            r->next=q;
            r=r->next;
        }
        head=head->next;
    }
    return p->next;
}



阿凡_1
13分钟前

题目描述

blablabla

样例

include[HTML_REMOVED]

using namespace std;
const int N = 1e6+10;
long long q[N];
long long temp[N];
int n;
long long merge_sort(int l,int r) {
if(l >= r) {
return 0;
}
int mid = (l+r)/2;
long long res = merge_sort(l,mid) + merge_sort(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 {
temp[k] = q[j];
res += mid-i+1;
}
}
while(i<=mid) {
temp[k] = q[i];
}
while(j<=r) {
temp[k] = q[j];
}
for(i=l,j=0;i<=r;i,j) {
q[i] = temp[j];
}
return res;
}
int main() {
cin>>n;
for(int i=0;i[HTML_REMOVED]>q[i];
}
cout<<merge_sort(0,n-1);
return 0;
}

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



藕丝泥霸
15分钟前

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
stack<int> st;

int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int x;
        scanf("%d",&x);
        while(!st.empty()&&st.top()>=x) st.pop();
        if(st.empty()) printf("%d ",-1);
        else printf("%d ",st.top());
        st.push(x);
    }
    return 0;
}

静态数组模拟

#include<iostream>
#include<cstdio>

using namespace std;
const int N=1e5+10;

int st[N];
int idx=-1;

int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int x;
        scanf("%d",&x);
        while(idx!=-1&&st[idx]>=x) idx--;
        if(idx==-1) printf("%d ",-1);
        else printf("%d ",st[idx]);
        st[++idx]=x;
    }
    return 0;
}



ya.h
25分钟前

$\it{***快慢指针***}$


思路:
创建两个指针变量分别指向两个链表的头结点,遍历到头后立即指向另一个结点的头结点,若两链表存在公共结点,则公共点处相遇,否则交换初始位置后同时遍历到尾结点

要点:
1.如果两个链表有公共结点,则各自走到头后交换起始位置走到公共结点一定会相遇,因为走的总长度相同。假设两链表有公共点,公共点前的长度分别为a与b,公共点及其后的公共长度为c(题意表面公共点后面不会再分叉),交换起始位置可以看作是a+c+b=b+c+a的意思
2.暴力枚举,两个结点分别指向两个链表的头结点,然后实行双重遍历找有无公共结点,但是这么做会TLE

代码:

暴力枚举(最后一个数据TLE)
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
    for(;headA;headA=headA->next)
    {
        for(ListNode* q=headB;q;q=q->next)
        {
            if(headA==q) return headA;
        }
    }
    if(headA==NULL) return NULL;
}
快慢指针
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
    auto p=headA,q=headB;
    while(p!=q)
    {
        if(p) p=p->next;
        else p=headB;
        if(q) q=q->next;
        else q=headA;
    }
    return p;//退出循环说明两者相等,要么是走到公共结点,要么是不存在公共结点且都走到空
}



刘_0
30分钟前

发射站

某地有 N 个能量发射站排成一行,每个发射站 i 都有不相同的高度 Hi,并能向两边(当然两端的只能向一边)同时发射能量值为 V~i~ 的能量,并且发出的能量只被两边最近的且比它高的发射站接收。

显然,每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受,出于安全考虑,每个发射站接收到的能量总和是我们很关心的问题。

由于数据很多,现在只需要你帮忙计算出接收最多能量的发射站接收的能量是多少。

输入格式

第一行包含整数 N。

接下来 N 行,每行包含两个整数 H~i~ 和 V~i~,其中第 i 行的数据为第 i 个发射站的高度和能量值。

输出格式

输出仅一行,表示接收最多能量的发射站接收到的能量值。

数据保证答案不超过 2^31^−1。

数据范围

$$ 1≤N≤10^6\\ 1≤Hi≤2×10^9\\ 1≤Vi≤10000 $$

输入样例:

3
4 2 
3 5 
6 10

输出样例:

7

思路

​ 看代码

代码

// 代码1
#include<iostream>
#include<algorithm>
#include <cstring>

using namespace std;

const int N=1e6+10;
typedef pair<int,int> PII;
int n,res;
PII q[N];   //存放各个塔的高度和能量
int qq[N];   //存放进栈塔对应的q数组下标
int s[N];   //各个塔的能量值,一个从左往右看,一个从右往左看

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int h,v;
        cin>>h>>v;
        q[i]={h,v};
    }
    //计算塔向左侧发出能量各个塔的接受情况
    int tt=0;
    for(int i=1;i<=n;i++)
    {
        while(tt&&q[i].first>q[qq[tt]].first)   //确保栈不空,且新元素更优
            tt--;   //出栈,栈单调减
        if(tt)
            s[qq[tt]] += q[i].second;       //i塔左边最近比它高的塔为此时栈顶
        qq[++tt]=i;     //进栈
    }

    //计算来塔向右测发射能量各个塔的接受情况

    tt=0;
    memset(qq, 0, sizeof qq);
    for(int i=n;i;i--)      //逆序遍历
    {
        while(tt&&q[i].first>q[qq[tt]].first)
            tt--;   //出栈
        if(tt)
            s[qq[tt]] += q[i].second;
        qq[++tt] = i;       //进栈
    }

    int mmax = 0;
    for(int i=1;i<=n;i++) {
        mmax=max(mmax,s[i]);
    }

    cout<<mmax;
    return 0;
}

// 代码2
#include < iostream>
#include < algorithm>
using namespace std;
const int N = 1e6 + 10;
typedef pair< int, int> PII;
int n, res;
PII q[N]; // 存放各个塔的高度和能量
int qq[N]; // 相当于之前讲的单调栈里的st数组
int s[N]; // 各个塔的能力值
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++){
        int h, v;
        cin >> h >> v;
        q[i] = {h, v};
    }   
    int tt = 0;
    for (int i = 1; i <= n; i++) {
        while (tt && q[i].first > q[qq[tt]].first) s[i] += q[qq[tt--]].second;
        if (tt) s[qq[tt]] += q[i].second;
        qq[++tt] = i;
    }
    int mmax = 0;
    for(int i = 1;i <= n;i ++) mmax = max(mmax,s[i]);
    cout << mmax;
    return 0;
}



shady1972
32分钟前

题目描述

一共有 n 个数,编号是 1∼n,最开始每个数各自在一个集合中。

现在要进行 m 个操作,操作共有两种:

  1. M a b,将编号为 a 和 b 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
  2. Q a b,询问编号为 a 和 b 的两个数是否在同一个集合中;

输入格式

第一行输入整数 n 和 m。

接下来 m 行,每行包含一个操作指令,指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b,都要输出一个结果,如果 a 和 b 在同一集合内,则输出 Yes,否则输出 No。

每个结果占一行。

数据范围

$1≤n,m≤105$

输入样例:

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例:

Yes
No
Yes

分析

屏幕截图 2024-02-22 112814.png

屏幕截图 2024-02-22 112831.png

图解

屏幕截图 2024-02-22 112903.png

屏幕截图 2024-02-22 112915.png

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    while (m -- )
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'M') p[find(a)] = find(b);
        else
        {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}



Baitlo
33分钟前

容斥原理

如果给了三个素数:2,3,5
求1~10内能被这个素数集整除的元素个数。

👇👇👇

例子:如下图是三个集合相交融,S1里面元素个数为x,S2里面元素个数为y,S3里面元素个数为z,求S1^S2^S3的元素总个数。

S1可以对应1~10内2的倍数的集合,S2可以对应1~10内3的倍数的集合,S3可以对应1~10内5的倍数的集合,S1^S2^S3的元素总个数即为最上面样例的解。

截屏2024-02-22 10.13.35.png

$$|S_{1} \cup S_{2} \cup S_{3}| = |S_{1}|+|S_{2}|+|S_{3}|-|S_{1} \cup S_{2}|-|S_{1} \cup S_{3}|-|S_{2} \cup S_{3}|+|S_{1} \cap S_{2} \cap S_{3} |$$

由此可见,当素数集合的元素个数为k时,我们上面这个式子的项数(我们需要运算的次数)为
$$C_{k}^{1}+C_{k}^{2}+…C_{k}^{k}=(1+1)^k$$(Newton二次项定理)

在k个元素中只能选1个的方案数+只能选两个+…
实际上就是在k个元素中可以任意选择的方案数
那么根据排列组合,第一个元素 选or不选 第二个元素 选or 不选…
乘起来正好就是 $2^k$

我们如何算两个集合相与呢?在这个题中我们可以采用简单的乘法。比如我们求“能同时整除2、3的数字个数”时,我们直接用n/(2*3)向下取整即是我们要的结果。那么当求最后一项k个集合相与的时候,我们就要先做k次乘法运算。

所以总的时间复杂度为$O(k2^k)$

暴力代码

#include<iostream>
using namespace std;
#include<algorithm>
#include<set>
int main(void){
    int n;
    int k;
    cin>>n>>k;
    int p[k+1];
    for(int i=1;i<=k;i++) cin>>p[i];
    set<int> s;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            if(i%p[j]==0){
                s.emplace(i);
                break;
            }
        }
    }
    cout<<s.size();
}

时间复杂度

O(nm)–n为给的1~n的数字范围,m为给的素数集合的元素个数

容斥代码

#include<iostream>
using namespace std;
#include<algorithm>
int main(void){
    long long n,k,sum=0;
    cin>>n>>k;
    long long p[k];
    for(long long i=0;i<k;i++) cin>>p[i];
    long long maxv=1<<k;
    for(long long i=1;i<maxv;i++){
        long long num_1=0,product=1;
        long long j=0;
        while(product<=n&&j<k){//如果乘积>n,那么这一项为0,不予考虑,防止出现不断累乘溢出
            if((i>>j)&1){
                num_1++;
                product*=p[j];
            }
            j++;
        }
        if(j!=k) continue;
        if(num_1%2==1) sum+=n/product;
        else sum-=n/product;
    }
    cout<<sum;
}

注意

while(product<=n&&j<k){//如果乘积>n,那么这一项为0,不予考虑,防止出现不断累乘溢出
    if((i>>j)&1){
        num_1++;
        product*=p[j];
    }
    j++;
}
if(j!=k) continue;

这段代码很重要,比如在以下样例中:

输入样例

1000000000 6
2 5 191 421 90679 252986611

单单90679*252986611就达到了23847099912258 超出了longlong的范围
本来应该是n/23847099912258=0,然而溢出后product实际=1152570933,这就导致了错误。




acwing_60326
49分钟前
#include <stdio.h>
#include <math.h>
int max(int a,int b){
    return (a+b+abs(a-b))/2;
}
int main(){

    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    int m;
    m=max(a,b);
    m=max(m,c);
    printf("%d eh o maior",m);

    return 0;
}



MeowRain
50分钟前

bash内置命令

echo

image-20240222111258461

image-20240222111435056

image-20240222111629081

printf

image-20240222111805828

eval

image-20240222112025562

image-20240222111953540

exec

image-20240222112035530

image-20240222112124467




阿凡_1
51分钟前

题目描述

blablabla

样例

include[HTML_REMOVED]

using namespace std;
const int N = 1e6+10;
int n;
int q[N];
int k;
void quick_sort(int q[],int l,int r) {
if(l >= r) {
return ;
}
int x = q[(l+r)/2];
int i = l-1;
int 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() {
cin>>n>>k;
for(int i=0;i[HTML_REMOVED]>q[i];
}
quick_sort(q,0,n-1);
cout<<q[k-1];
}

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla