Link 9.23

Link 9.24

文章目錄

NEFU 9.23
- A - Valid BFS?
- - 題意
  - 思路
  - 代碼
NEFU 9.24
- A - Modulo Equality
- - 題意
  - 思路
  - 代碼
- B - Maximum Sum on Even Positions
- - 題意
  - 思路
  - 代碼
- C - Sasha and a Bit of Relax
- - 題意
  - 思路
  - 代碼

NEFU 9.23

A - Valid BFS?

題意
給出一個樹和一個 b f s bfs bfs序，問是否是它的其中一個
思路
每次進行彈出隊列時，将它的子節點全部放進一個 s e t set set裡，周遊題目給的 b f s bfs bfs序，如果在 s e t set set裡找到了，那麼在 s e t set set裡删去，并加入隊列；如果到最後 s e t set set還有值，說明 b f s bfs bfs序是錯的

代碼

/*
 * @Author: NEFU AB-IN
 * @Date: 2021-09-23 20:03:59
 * @FilePath: \ACM\CF\2021.9.23\a.cpp
 * @LastEditTime: 2021-09-23 20:44:24
 */
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;

const int N = 1e6 + 10;
struct Edge
{
    int v, ne;
} e[N << 2];
int h[N], vis[N];
int cnt;
void add(int u, int v)
{
    e[cnt].v = v;
    e[cnt].ne = h[u];
    h[u] = cnt++;
}
void init()
{
    memset(h, -1, sizeof(h));
    cnt = 0;
}
vector<int> vv;
int pos;
void bfs(int x)
{
    queue<int> q;
    q.push(x);
    vis[x] = 1;

    while (q.size())
    {
        int u = q.front(), cnt1 = 0;
        q.pop();
        set<int> s;
        for (int i = h[u]; ~i; i = e[i].ne)
        {
            int v = e[i].v;
            if (vis[v])
                continue;
            vis[v] = 1;
            s.insert(v);
        }
        for (int i = pos; i < SZ(vv); ++i)
        {
            if (!SZ(s))
                break;
            if (s.find(vv[i]) != s.end())
            {
                s.erase(vv[i]);
                q.push(vv[i]);
                cnt1++;
            }
        }
        if (SZ(s))
        {
            cout << "No" << '\n';
            return;
        }
        pos += cnt1;
    }
}
signed main()
{
    IOS;
    init();
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        vv.push_back(x);
    }
    if (vv[0] != 1)
    {
        cout << "No" << '\n';
        return 0;
    }
    vv.erase(vv.begin());
    bfs(1);
    if (pos == SZ(vv))
    {
        cout << "Yes" << '\n';
    }
    return 0;
}

NEFU 9.24

A - Modulo Equality

題意
給出兩個數組 a a a ， b ，b ，b，問 a a a數組每個數加多少次 1 1 1并取模 m m m才能和 b b b數組相同
思路
用 m u l t i s e t multiset multiset模拟即可，看 a a a數組的哪個值到達 b b b的最大值時， a a a就和 b b b數組相等了

代碼

/*
    * @Author: NEFU AB-IN
    * @Date: 2021-09-24 20:21:23
 * @FilePath: \ACM\CF\2021.9.24\a.cpp
 * @LastEditTime: 2021-09-24 21:21:32
    */
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MP make_pair
#define SZ(X) ((LL)(X).size())
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<LL, LL> PII;
const LL N = 2010;
LL a[N];

multiset<LL> b;
signed main()
{
    IOS;
    LL n, m;
    cin >> n >> m;
    for (LL i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    LL max = 0;
    for (LL i = 1; i <= n; ++i)
    {
        LL x;
        cin >> x;
        b.insert(x);
    }
    LL t = *(b.rbegin());
    sort(a + 1, a + 1 + n, greater<LL>());
    LL minx = 0x3f3f3f3f;
    for (LL i = 1; i <= n; ++i)
    {
        LL tmp = t - a[i] >= 0 ? t - a[i] : (t - a[i] + m);
        multiset<LL> s;
        for (LL i = 1; i <= n; ++i)
        {
            s.insert((a[i] + tmp) % m);
        }
        if (s == b)
        {
            minx = min(minx, tmp);
        }
    }
    cout << minx << '\n';
    return 0;
}

B - Maximum Sum on Even Positions

題意
給定一個包含 n n n 個元素的序列（下标從 0 0 0 到 n − 1 n-1 n−1），你可以選擇一個連續區間進行翻轉，使得翻轉過後的序列偶數項的總和（即 a 0 , a 2 , … , a 2 k a_0,a_2,\ldots,a_{2k} a0,a2,…,a2k 的和，其中 k = ⌊ n − 1 2 ⌋ k=\lfloor \dfrac{n-1}{2} \rfloor k=⌊2n−1⌋）最大。
思路

首先翻轉奇數元素個數的區間時沒有意義的，那麼就翻轉偶數元素個數的區間，翻轉之後的結果是奇數的位置和偶數的位置互換了，那麼就找某個長度為偶數，并且奇數位和 − - −偶數位的和最大的區間即可，最後的答案就是 m a x ( 原先偶數位的和 , 原先偶數位的和 + ( 奇數位和 − 偶數位的和最大值 ) ) max(原先偶數位的和, 原先偶數位的和+(奇數位和-偶數位的和最大值)) max(原先偶數位的和,原先偶數位的和+(奇數位和−偶數位的和最大值))

如何實作呢？
- 首先分兩種情況的奇數位-偶數位
  - a 1 − a 0 , a 3 − a 2 , … a_1-a_0, a_3-a_2,\dots a1−a0,a3−a2,…
  - a 1 − a 2 , a 3 − a 4 , … a_1-a_2,a_3-a_4,\dots a1−a2,a3−a4,…
  畫一畫圖就明白了
- 最大子段和，來求連續區間的最大和是多少，用到dp
  
  最後周遊數組求出最大值，注意，
  dp[n] 不是最大值

代碼

/*
 * @Author: NEFU AB-IN
 * @Date: 2021-09-24 21:29:09
 * @FilePath: \ACM\CF\2021.9.24\b.cpp
 * @LastEditTime: 2021-09-29 23:02:03
 */
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;

const int N = 1e6 + 10;
LL a[N], b[N], c[N], dp[N];

void solve()
{
    // construct the minus array
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; i += 2)
    {
        if (i + 1 >= n)
            break;
        b[++cnt1] = a[i + 1] - a[i];
    }
    for (int i = 1; i < n; i += 2)
    {
        if (i + 1 >= n)
            break;
        c[++cnt2] = a[i] - a[i + 1];
    }
    // start dp function 1
    dp[0] = 0;
    for (int i = 1; i <= cnt1; ++i)
    {
        dp[i] = max(dp[i - 1] + b[i], b[i]);
    }
    LL mx = dp[1];
    for (int i = 1; i <= cnt1; ++i)
    {
        mx = max(mx, dp[i]);
    }
    // start dp function 2
    dp[0] = 0;
    for (int i = 1; i <= cnt2; ++i)
    {
        dp[i] = max(dp[i - 1] + c[i], c[i]);
    }
    for (int i = 1; i <= cnt2; ++i)
    {
        mx = max(mx, dp[i]);
    }
    LL ans = 0;
    for (int i = 0; i < n; ++i)
    {
        if (i % 2 == 0)
            ans += a[i];
    }
    cout << max(ans, ans + mx) << '\n';
}

signed main()
{
    IOS;
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C - Sasha and a Bit of Relax

題意
長度為 n n n的數列，求有多少區間滿足
- 長度為偶數
- 前一半異或值等于後一半異或值
思路

如果前一半異或值等于後一半異或值，說明兩者異或為 0 0 0，說明這個區間異或值為 0 0 0

根據異或字首和的性質， [ l , r ] [l,r] [l,r]的區間異或值為 s u m [ r ] x o r s u m [ l − 1 ] sum[r] \ xor \ sum[l - 1] sum[r] xor sum[l−1]，那麼就是找 s u m [ r ] x o r s u m [ l − 1 ] = 0 sum[r] \ xor \ sum[l - 1] = 0 sum[r] xor sum[l−1]=0的，也就是 s u m [ r ] = s u m [ l − 1 ] sum[r] = sum[l - 1] sum[r]=sum[l−1]

是以就是找 s u m [ r ] = s u m [ l − 1 ] sum[r] = sum[l - 1] sum[r]=sum[l−1]且 ( r − l + 1 ) % 2 = = 0 (r-l+1)\%2==0 (r−l+1)%2==0的區間有多少個

代碼十分精妙

做到這點，可以運用 d p dp dp，即開一個數組 d p [ N ] [ 2 ] dp[N][2] dp[N][2]
- 初始值 d p [ 0 ] [ 0 ] = 1 dp[0][0] = 1 dp[0][0]=1，代表異或字首和為 0 0 0，且下标為偶數的有一個，就是在 0 0 0點
- d p [ i ] [ 0 ] dp[i][0] dp[i][0]表示異或字首和為 i i i，且下标為偶數
- d p [ i ] [ 1 ] dp[i][1] dp[i][1]表示異或字首和為 i i i，且下标為奇數
這樣就確定了區間長度為偶數

題目問有多少個，如果有 3 3 3個相同的異或字首和，那麼就是 3 3 3對，即 1 + 2 1 + 2 1+2，是以在遞增的時候就加上即可

代碼

/*
 * @Author: NEFU AB-IN
 * @Date: 2021-09-29 23:25:32
 * @FilePath: \ACM\CF\2021.9.24\c.cpp
 * @LastEditTime: 2021-09-29 23:52:57
 */
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;

int n;
const int N = 3e6 + 10;
LL a[N], sum[N], dp[N][2];

signed main()
{
    IOS;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        sum[i] = a[i] ^ sum[i - 1];
    }
    LL ans = 0;
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        ans += dp[sum[i]][i & 1];
        dp[sum[i]][i & 1]++;
    }
    cout << ans << '\n';
    return 0;
}

NEFU 9.23 && 9.24NEFU 9.23NEFU 9.24

文章目錄

NEFU 9.23

A - Valid BFS?

題意

思路

代碼

NEFU 9.24

A - Modulo Equality

題意

思路

代碼

B - Maximum Sum on Even Positions

題意

思路

代碼

C - Sasha and a Bit of Relax

題意

思路

代碼

繼續閱讀

HDU Reorder the Books

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

hdu 4741 Save Labman No.004（計算幾何） Save Labman No.004

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希

NEFU 9.23 &amp;&amp; 9.24NEFU 9.23NEFU 9.24

文章目錄

NEFU 9.23

A - Valid BFS?

題意

思路

代碼

NEFU 9.24

A - Modulo Equality

題意

思路

代碼

B - Maximum Sum on Even Positions

題意

思路

代碼

C - Sasha and a Bit of Relax

題意

思路

代碼

繼續閱讀

NEFU 9.23 && 9.24NEFU 9.23NEFU 9.24