头像

我呼吸了

$$\href{/blog/content/23943/}{\color{DarkTurquoise}{【考研AND保研】机试题}}$$




离线:2小时前


最近来访(492)
用户头像
skkdw
用户头像
济带阿孙
用户头像
Say永
用户头像
flexible
用户头像
牛.
用户头像
可乐土豆
用户头像
TOKYOMI
用户头像
Sakia
用户头像
tyjz_yynb
用户头像
题再简单我也会
用户头像
zxmcoder
用户头像
JesseChan
用户头像
巷港
用户头像
laidui
用户头像
爱抠鼻屎的
用户头像
BT7274
用户头像
daybreak
用户头像
一个莫得感情的独行侠
用户头像
江湖小虾
用户头像
富贵


我呼吸了
13小时前

欢迎访问==> 【考研OR保研】机试题


n(id, value) 对,其中 id1n 之间的一个整数,value 是一个字符串。不存在 id 相同的两个 (id, value) 对。

设计一个流,以 任意 顺序获取 n 个 (id, value) 对,并在多次调用时 id 递增的顺序 返回一些值。

实现 OrderedStream 类:

  • OrderedStream(int n) 构造一个能接收 n 个值的流,并将当前指针 ptr 设为 1
  • String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后:
    • 如果流存储有 id = ptr(id, value) 对,则找出从 id = ptr 开始的 最长 id 连续递增序列 ,并 按顺序 返回与这些 id 关联的值的列表。然后,将 ptr 更新为最后那个  id + 1 。
    • 否则,返回一个空列表。

示例:

输入
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
输出
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]

解释
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // 插入 (3, "ccccc"),返回 []
os.insert(1, "aaaaa"); // 插入 (1, "aaaaa"),返回 ["aaaaa"]
os.insert(2, "bbbbb"); // 插入 (2, "bbbbb"),返回 ["bbbbb", "ccccc"]
os.insert(5, "eeeee"); // 插入 (5, "eeeee"),返回 []
os.insert(4, "ddddd"); // 插入 (4, "ddddd"),返回 ["ddddd", "eeeee"]

提示:

  • 1 <= n <= 1000
  • 1 <= id <= n
  • value.length == 5
  • value 仅由小写字母组成
  • 每次调用 insert 都会使用一个唯一的 id
  • 恰好调用 ninsert

C++代码

/*
难在理解题意,多读几遍理解题意后,模拟即可
*/
class OrderedStream {
public:
    int ptr, ed;
    unordered_map<int, string> h;

    OrderedStream(int n) {
        ptr = 1, ed = n;
    }

    vector<string> insert(int idKey, string value) {
        h[idKey] = value;
        vector<string> res;

        for(int i = ptr; i <= ed; i ++)
        {
            if(h[i] == "")
            {
                ptr = i;
                break;
            } 

            res.push_back(h[i]);
        }
        return res;
    }
};

/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream* obj = new OrderedStream(n);
 * vector<string> param_1 = obj->insert(idKey,value);
 */


活动打卡代码 LeetCode 1656. 设计有序流

我呼吸了
13小时前

欢迎访问==> 【考研OR保研】机试题


n(id, value) 对,其中 id1n 之间的一个整数,value 是一个字符串。不存在 id 相同的两个 (id, value) 对。

设计一个流,以 任意 顺序获取 n 个 (id, value) 对,并在多次调用时 id 递增的顺序 返回一些值。

实现 OrderedStream 类:

  • OrderedStream(int n) 构造一个能接收 n 个值的流,并将当前指针 ptr 设为 1
  • String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后:
    • 如果流存储有 id = ptr(id, value) 对,则找出从 id = ptr 开始的 最长 id 连续递增序列 ,并 按顺序 返回与这些 id 关联的值的列表。然后,将 ptr 更新为最后那个  id + 1 。
    • 否则,返回一个空列表。

示例:

输入
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
输出
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]

解释
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // 插入 (3, "ccccc"),返回 []
os.insert(1, "aaaaa"); // 插入 (1, "aaaaa"),返回 ["aaaaa"]
os.insert(2, "bbbbb"); // 插入 (2, "bbbbb"),返回 ["bbbbb", "ccccc"]
os.insert(5, "eeeee"); // 插入 (5, "eeeee"),返回 []
os.insert(4, "ddddd"); // 插入 (4, "ddddd"),返回 ["ddddd", "eeeee"]

提示:

  • 1 <= n <= 1000
  • 1 <= id <= n
  • value.length == 5
  • value 仅由小写字母组成
  • 每次调用 insert 都会使用一个唯一的 id
  • 恰好调用 ninsert

C++代码

/*
难在理解题意,多读几遍理解题意后,模拟即可
*/
class OrderedStream {
public:
    int ptr, ed;
    unordered_map<int, string> h;

    OrderedStream(int n) {
        ptr = 1, ed = n;
    }

    vector<string> insert(int idKey, string value) {
        h[idKey] = value;
        vector<string> res;

        for(int i = ptr; i <= ed; i ++)
        {
            if(h[i] == "")
            {
                ptr = i;
                break;
            } 

            res.push_back(h[i]);
        }
        return res;
    }
};

/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream* obj = new OrderedStream(n);
 * vector<string> param_1 = obj->insert(idKey,value);
 */



欢迎访问==> 【考研OR保研】机试题


题目描述

砝码是一种作为质量标准的物体,通常为金属块或金属片,可以用作称量较精准的质量。

给定一个整数 $n$,我们需要选取一些砝码用于称量,砝码只能放在一边,要求:

  1. 所有选取砝码的总重量恰好为 $n$。
  2. 每个选取砝码的重量 $x$ 都是满足 $1 \le x \le n$ 的正整数。
  3. 可以选取多个重量相同的砝码,例如选取两个重量为 $1$ 的砝码。
  4. 利用选取的砝码(部分或全部),可以组成 $1 \sim n$ 之间的任意整数重量。
  5. 选取砝码的数量应尽可能少。

请你计算并输出选取砝码的最少可能数量。

输入格式

共一行,一个整数 $n$。

输出格式

一个整数,表示选取砝码的最少可能数量。

数据范围

前三个测试点满足 $1 \le n \le 10$。
所有测试点满足 $1 \le n \le 10^9$。

输入样例1:

6

输出样例1:

3

样例1解释

在此样例中,我们只需要选取重量为 $1,2,3$ 的砝码各一个,即可组成 $1 \sim 6$ 之间的任意整数重量:

  • $1 = 1$
  • $2 = 2$
  • $3 = 3$
  • $4 = 1 + 3$
  • $5 = 2 + 3$
  • $6 = 1 + 2 + 3$

所以最少需要 $3$ 个砝码。

输入样例2:

2

输出样例2:

2

样例2解释

在此样例中,我们可以选取两个重量为 $1$ 的砝码,即可组成 $1$ 和 $2$ 两种重量。


C++ 代码

/*
知识积累:【1 ~ 2 ^ k】,k + 1个数可以凑出来【1 ~ 2 ^ (k + 1) - 1】中的任意一个数
*/
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int res = 0;

    while((1 << res) - 1 < n) res ++;

    cout << res << endl;

    return 0;
}



欢迎访问==> 【考研OR保研】机试题


设计实现双端队列。

实现 MyCircularDeque 类:

  • MyCircularDeque(int k) :构造函数,双端队列最大为 k
  • boolean insertFront():将一个元素添加到双端队列头部。 如果操作成功返回 true ,否则返回 false
  • boolean insertLast() :将一个元素添加到双端队列尾部。如果操作成功返回 true ,否则返回 false
  • boolean deleteFront() :从双端队列头部删除一个元素。 如果操作成功返回 true ,否则返回 false
  • boolean deleteLast() :从双端队列尾部删除一个元素。如果操作成功返回 true ,否则返回 false
  • int getFront() ):从双端队列头部获得一个元素。如果双端队列为空,返回 -1 。
  • int getRear() :获得双端队列的最后一个元素。 如果双端队列为空,返回 -1
  • boolean isEmpty() :若双端队列为空,则返回 true ,否则返回 false  。
  • boolean isFull() :若双端队列满了,则返回 true ,否则返回 false

示例 1:

输入
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]

解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);                    // 返回 true
circularDeque.insertLast(2);                    // 返回 true
circularDeque.insertFront(3);                   // 返回 true
circularDeque.insertFront(4);                   // 已经满了,返回 false
circularDeque.getRear();                // 返回 2
circularDeque.isFull();                     // 返回 true
circularDeque.deleteLast();                 // 返回 true
circularDeque.insertFront(4);                   // 返回 true
circularDeque.getFront();               // 返回 4

提示:

  • 1 <= k <= 1000
  • 0 <= value <= 1000
  • insertFrontinsertLastdeleteFrontdeleteLastgetFrontgetRearisEmptyisFull  调用次数不大于 2000 次

C++代码

/*
我们规定:
tt代表队尾指针,hh代表队头指针
hh == tt时说明队列为空,hh == tt + 1,说明队列已满
其他情况下[hh, tt)为队列中的元素
注意:
因为我们实现的是循环队列,所以所有的计算和比较都是在取模意义下进行的
*/
class MyCircularDeque {
public:

    vector<int> q;
    int tt = 0, hh = 0;

    MyCircularDeque(int k) {
        q.resize(k + 1);
    }

    int get(int x)
    {
        return (x + q.size()) % q.size();
    }

    bool insertFront(int value) {
        if(isFull()) return false;

        hh = get(hh - 1);
        q[hh] = value;
        return true;
    }

    bool insertLast(int value) {
        if(isFull()) return false;
        q[tt] = value;
        tt = get(tt + 1);
        return true;
    }

    bool deleteFront() {
        if(isEmpty()) return false;
        hh = get(hh + 1);
        return true;
    }

    bool deleteLast() {
        if(isEmpty()) return false;
        tt = get(tt - 1);
        return true;
    }

    int getFront() {

        if(isEmpty()) return -1;

        return q[hh];
    }

    int getRear() {
        if(isEmpty()) return -1;
        return q[get(tt - 1)];
    }

    bool isEmpty() {
        return hh == tt;
    }

    bool isFull() {
        return get(tt + 1) == hh;
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */



欢迎访问==> 【考研OR保研】机试题


设计实现双端队列。

实现 MyCircularDeque 类:

  • MyCircularDeque(int k) :构造函数,双端队列最大为 k
  • boolean insertFront():将一个元素添加到双端队列头部。 如果操作成功返回 true ,否则返回 false
  • boolean insertLast() :将一个元素添加到双端队列尾部。如果操作成功返回 true ,否则返回 false
  • boolean deleteFront() :从双端队列头部删除一个元素。 如果操作成功返回 true ,否则返回 false
  • boolean deleteLast() :从双端队列尾部删除一个元素。如果操作成功返回 true ,否则返回 false
  • int getFront() ):从双端队列头部获得一个元素。如果双端队列为空,返回 -1 。
  • int getRear() :获得双端队列的最后一个元素。 如果双端队列为空,返回 -1
  • boolean isEmpty() :若双端队列为空,则返回 true ,否则返回 false  。
  • boolean isFull() :若双端队列满了,则返回 true ,否则返回 false

示例 1:

输入
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]

解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);                    // 返回 true
circularDeque.insertLast(2);                    // 返回 true
circularDeque.insertFront(3);                   // 返回 true
circularDeque.insertFront(4);                   // 已经满了,返回 false
circularDeque.getRear();                // 返回 2
circularDeque.isFull();                     // 返回 true
circularDeque.deleteLast();                 // 返回 true
circularDeque.insertFront(4);                   // 返回 true
circularDeque.getFront();               // 返回 4

提示:

  • 1 <= k <= 1000
  • 0 <= value <= 1000
  • insertFrontinsertLastdeleteFrontdeleteLastgetFrontgetRearisEmptyisFull  调用次数不大于 2000 次

C++代码

/*
我们规定:
tt代表队尾指针,hh代表队头指针
hh == tt时说明队列为空,hh == tt + 1,说明队列已满
其他情况下[hh, tt)为队列中的元素
注意:
因为我们实现的是循环队列,所以所有的计算和比较都是在取模意义下进行的
*/
class MyCircularDeque {
public:

    vector<int> q;
    int tt = 0, hh = 0;

    MyCircularDeque(int k) {
        q.resize(k + 1);
    }

    int get(int x)
    {
        return (x + q.size()) % q.size();
    }

    bool insertFront(int value) {
        if(isFull()) return false;

        hh = get(hh - 1);
        q[hh] = value;
        return true;
    }

    bool insertLast(int value) {
        if(isFull()) return false;
        q[tt] = value;
        tt = get(tt + 1);
        return true;
    }

    bool deleteFront() {
        if(isEmpty()) return false;
        hh = get(hh + 1);
        return true;
    }

    bool deleteLast() {
        if(isEmpty()) return false;
        tt = get(tt - 1);
        return true;
    }

    int getFront() {

        if(isEmpty()) return -1;

        return q[hh];
    }

    int getRear() {
        if(isEmpty()) return -1;
        return q[get(tt - 1)];
    }

    bool isEmpty() {
        return hh == tt;
    }

    bool isFull() {
        return get(tt + 1) == hh;
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */



欢迎访问==> 【考研OR保研】机试题


题目描述

给定一个 $n$ 个点 $m$ 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你判断图中是否存在负权回路。

输入格式

第一行包含整数 $n$ 和 $m$。

接下来 $m$ 行每行包含三个整数 $x,y,z$,表示存在一条从点 $x$ 到点 $y$ 的有向边,边长为 $z$。

输出格式

如果图中存在负权回路,则输出 Yes,否则输出 No

数据范围

$1 \le n \le 2000$,
$1 \le m \le 10000$,
图中涉及边长绝对值均不超过 $10000$。

输入样例:

3 3
1 2 -1
2 3 4
3 1 -4

输出样例:

Yes

C++ 代码

本题基于spfa求最短路算法,具体请参考spfa求最短路

/*
spfa判负环
只需要在spfa求最短路的同时维护一个cnt数组表示经过的边数
当cnt[i] >= n时,说明出现了负环
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 2010, M = 10010;

int n, m, d[N], cnt[N];
int h[N], e[M], nxt[M], w[M], idx;
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, nxt[idx] = h[a], h[a] = idx ++;
}

bool spfa()
{
    queue<int> q;
    memset(d, 0x3f, sizeof d);
    memset(st, 0, sizeof st);
    d[1] = 0;

     /*遍历每一个点去更新其他点的情况
      因为有可能只让1号点作为起点时,图中的负环可能与1号点是不连通的
      所以需要遍历每一个点去更新其他点的情况
    */
    for(int i = 1; i <= n; i ++)
    {
        q.push(i);
        st[i] = true;
    }

    while(q.size())
    {
        int t = q.front();
        q.pop(), st[t] = false;

        for(int i = h[t]; i != -1; i = nxt[i])
        {
            int j = e[i];

            if(d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                cnt[j] = cnt[t] + 1;     //更新cnt数组

                if(cnt[j] >= n) return true;

                if(!st[j]) q.push(j), st[j] = true;

            }
        }
    }
    return false;
}

int main()
{
    memset(h, -1, sizeof h);

    cin >> n >> m;

    while(m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    if(spfa()) puts("Yes");
    else puts("No");

    return 0;
}



欢迎访问==> 【考研OR保研】机试题


题目描述

给定一个 $n$ 个点 $m$ 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出 $1$ 号点到 $n$ 号点的最短距离,如果无法从 $1$ 号点走到 $n$ 号点,则输出 impossible

数据保证不存在负权回路。

输入格式

第一行包含整数 $n$ 和 $m$。

接下来 $m$ 行每行包含三个整数 $x,y,z$,表示存在一条从点 $x$ 到点 $y$ 的有向边,边长为 $z$。

输出格式

输出一个整数,表示 $1$ 号点到 $n$ 号点的最短距离。

如果路径不存在,则输出 impossible

数据范围

$1 \le n,m \le 10^5$,
图中涉及边长绝对值均不超过 $10000$。

输入样例:

3 3
1 2 5
2 3 -3
1 3 4

输出样例:

2

C++ 代码

/*
spfa算法是对Bellman_ford算法的优化
只有被更新了距离的点才去更新其他点
用一个队列存储可以去更新其他点的集合
每次取出队列中的一个点去更新其他点即可
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

int h[N], e[N], w[N], nxt[N], idx;
int n, m, d[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, nxt[idx] = h[a], h[a] = idx ++;
}

void spfa()
{
    queue<int> q;

    memset(d, 0x3f, sizeof d);
    d[1] = 0;

    memset(st, 0, sizeof st);
    q.push(1);
    st[1] = true;  //st数组:标记1号点已经在队列中了

    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;  //标记t号点已经不在队列中了

        for(int i = h[t]; i != -1; i = nxt[i])
        {
            int j = e[i];

            if(d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];

                if(!st[j])    //如果j号点不在队列中,将其加入队列
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);

    cin >> n >> m;

    while(m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    spfa();

    if(d[n] == INF) puts("impossible");
    else cout << d[n] << endl;

    return 0;
}



欢迎访问==> 【考研OR保研】机试题


题目描述

给定一个 $n$ 个点 $m$ 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出从 $1$ 号点到 $n$ 号点的最多经过 $k$ 条边的最短距离,如果无法从 $1$ 号点走到 $n$ 号点,输出 impossible

注意:图中可能 存在负权回路

输入格式

第一行包含三个整数 $n,m,k$。

接下来 $m$ 行,每行包含三个整数 $x,y,z$,表示存在一条从点 $x$ 到点 $y$ 的有向边,边长为 $z$。

点的编号为 $1 \sim n$。

输出格式

输出一个整数,表示从 $1$ 号点到 $n$ 号点的最多经过 $k$ 条边的最短距离。

如果不存在满足条件的路径,则输出 impossible

数据范围

$1 \le n,k \le 500$,
$1 \le m \le 10000$,
$1 \le x,y \le n$,
任意边长的绝对值不超过 $10000$。

输入样例:

3 3 1
1 2 1
2 3 1
1 3 3

输出样例:

3

C++ 代码

/*
注解:用结构体存边即可
1、循环n次
2、每次循环所有边a,b,w
3、更新最短距离 d[b] = min(d[b],d[a]+w)
*/

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

struct Edges{
    int a,b,w;
}e[N];

int d[N],backup[N];
int n,m,k;

int bellman_ford()
{
    memset(d,0x3f,sizeof d); //细节0:初始化!!!
    d[1] = 0;

    for(int i = 0; i < k; i++)
    {
        memcpy(backup,d,sizeof d); //细节1:每次更新都需要备份一下,只能使用上一次的d数组进行更新,防止串联
        for(int j = 0; j < m; j++)
        {
            int a = e[j].a, b = e[j].b, w = e[j].w;
            d[b] = min(d[b], backup[a] + w);//细节2:用backup[a],不是d[a]
        }
    }

    if(d[n] > INF / 2) return INF; //细节3:不存在,不是等于INF!有可能是INF被一个负权边更新了
    return d[n];
}
int main()
{
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++)
    {
        int a,b,w;
        cin >> a >> b >> w;
        e[i] = {a,b,w};
    }

    int ans = bellman_ford();

    if(ans == INF) puts("impossible");
    else cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 4507. 子数组异或和

欢迎访问==> 【考研OR保研】机试题


题目描述

给定一个长度为 $n$ 的整数数组 $a_1,a_2,…,a_n$。

请你统计一共有多少个数组 $a$ 的非空连续子数组能够同时满足以下所有条件:

  • 该连续子数组的长度为偶数。
  • 该连续子数组的前一半元素的异或和等于其后一半元素的异或和。

例如,当给定数组为 $[1,2,3,4,5]$ 时,满足条件的连续子数组只有 $1$ 个:$[2,3,4,5]$。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$。

输出格式

一个整数,表示满足条件的连续子数组的数量。

数据范围

前三个测试点满足 $2 \le n \le 10$。
所有测试点满足 $2 \le n \le 3 \times 10^5$,$0 \le a_i < 2 ^{20}$。

输入样例1:

5
1 2 3 4 5

输出样例1:

1

输入样例2:

6
3 2 2 3 7 6

输出样例2:

3

输入样例3:

3
42 4 2

输出样例3:

0

C++ 代码

/*
异或性质:相同数异或结果为0
异或前缀和:
s[i]表示前i个字母的异或前缀和,求[i ~ j]这一段的异或和:s[j] ^ s[i - 1]
因为s[j]是a[1] ^ a[2] ^ ... ^ a[i - 1] ^ a[i] ^ ... ^ a[j]
s[i - 1]是a[1] ^ a[2] ^ ... ^ a[i - 1]
所以s[j] ^ s[i - 1] == a[i] ^ ... ^ a[j],即是[i ~ j]这一段的异或和

【条件1】该连续子数组的前一半元素的异或和等于其后一半元素的异或和
说明 左半边 ^ 右半边 = 0
假设这一连续子数组的下标是[i ~ j],所以即是[i ~ j]这一段的异或和等于0
所以s[j] ^ s[i - 1] == 0,所以由第一个条件可知 ==> s[j] == s[i - 1]
所以可以枚举每一个j,找到j左边异或前缀和与s[j]相等的数目,并加入到答案中
可以使用哈希表来记录之前的异或前缀和的值出现的次数
【条件2】该连续子数组的长度为偶数
对于枚举没有一个j时,只需要将下标奇偶性与j相同的并且满足条件1的数目加到答案中即可
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 300010;

int n, a[N];

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

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

    unordered_map<int, int> h[2]; //h[0]是下标为偶数的哈希表,h[1]是下标为奇数的哈希表

    int s = 0;  //异或前缀和
    ll res = 0; //记录答案

    h[0][s] ++;

    for(int i = 1; i <= n; i ++) //枚举
    {
        s ^= a[i];  //异或前缀和s[i]

        res += h[i % 2][s];  //将之前的异或前缀和为s的数目加入答案
        h[i % 2][s] ++;     //将异或前缀和为s的数目加1
    }

    cout << res << endl;

    return 0;
}



欢迎访问==> 【考研OR保研】机试题


题目描述

给定一个长度为 $n$ 的整数数组 $a_1,a_2,…,a_n$。

请你统计一共有多少个数组 $a$ 的非空连续子数组能够同时满足以下所有条件:

  • 该连续子数组的长度为偶数。
  • 该连续子数组的前一半元素的异或和等于其后一半元素的异或和。

例如,当给定数组为 $[1,2,3,4,5]$ 时,满足条件的连续子数组只有 $1$ 个:$[2,3,4,5]$。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$。

输出格式

一个整数,表示满足条件的连续子数组的数量。

数据范围

前三个测试点满足 $2 \le n \le 10$。
所有测试点满足 $2 \le n \le 3 \times 10^5$,$0 \le a_i < 2 ^{20}$。

输入样例1:

5
1 2 3 4 5

输出样例1:

1

输入样例2:

6
3 2 2 3 7 6

输出样例2:

3

输入样例3:

3
42 4 2

输出样例3:

0

C++ 代码

/*
异或性质:相同数异或结果为0
异或前缀和:
s[i]表示前i个字母的异或前缀和,求[i ~ j]这一段的异或和:s[j] ^ s[i - 1]
因为s[j]是a[1] ^ a[2] ^ ... ^ a[i - 1] ^ a[i] ^ ... ^ a[j]
s[i - 1]是a[1] ^ a[2] ^ ... ^ a[i - 1]
所以s[j] ^ s[i - 1] == a[i] ^ ... ^ a[j],即是[i ~ j]这一段的异或和

【条件1】该连续子数组的前一半元素的异或和等于其后一半元素的异或和
说明 左半边 ^ 右半边 = 0
假设这一连续子数组的下标是[i ~ j],所以即是[i ~ j]这一段的异或和等于0
所以s[j] ^ s[i - 1] == 0,所以由第一个条件可知 ==> s[j] == s[i - 1]
所以可以枚举每一个j,找到j左边异或前缀和与s[j]相等的数目,并加入到答案中
可以使用哈希表来记录之前的异或前缀和的值出现的次数
【条件2】该连续子数组的长度为偶数
对于枚举没有一个j时,只需要将下标奇偶性与j相同的并且满足条件1的数目加到答案中即可
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 300010;

int n, a[N];

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

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

    unordered_map<int, int> h[2]; //h[0]是下标为偶数的哈希表,h[1]是下标为奇数的哈希表

    int s = 0;  //异或前缀和
    ll res = 0; //记录答案

    h[0][s] ++;

    for(int i = 1; i <= n; i ++) //枚举
    {
        s ^= a[i];  //异或前缀和s[i]

        res += h[i % 2][s];  //将之前的异或前缀和为s的数目加入答案
        h[i % 2][s] ++;     //将异或前缀和为s的数目加1
    }

    cout << res << endl;

    return 0;
}