头像

github_smallzhong

南昌大学




离线:1天前


活动打卡代码 AcWing 892. 台阶-Nim游戏

#include <iostream>
#include <stdio.h>

using namespace std;

int main()
{
    int res = 0;
    int T;
    cin >> T;
    while (T -- )
    {
        int t;
        cin >> t;
        res ^= t;
    }

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

    return 0;
}


活动打卡代码 AcWing 3485. 最大异或和

最大异或和

  • 这道题是求整个序列里面的长度小于 $m$ 的序列的最大异或和。可以使用前缀和。然后只有m个结点可以被插入,用一个滑动窗口,滑出去的就通过 insert 函数将 cnt 减一。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 10000010;

int n, m;
int s[N], son[N][2], idx, cnt[N];

void insert(int x, int v)
{
  int u = 0; 
  for (int i = 30; i >= 0; i -- )
  {
      int t = x >> i & 1;
      if (!son[u][t]) son[u][t] = ++ idx;
      u = son[u][t];
      cnt[u] += v;
  }
}

int query(int x)
{
  int res = 0;
  int u = 0;
  for (int i = 30; i >= 0; i -- )
  {
      int t = x >> i & 1;
      res <<= 1;
      if (cnt[son[u][!t]]) u = son[u][!t], res |= 1;
      else u = son[u][t];
  }

  return res;
}

int main()
{
  cin >> n >> m;
  for (int i = 1; i <= n; i ++ ) cin >> s[i];
  for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] ^ s[i];

  int res = 0;
  insert(s[0], 1);
  for (int i = 1; i <= n; i ++ )
  {
      if (i > m) insert(s[i - m - 1], -1); // 清除
      insert(s[i], 1);
      res = max(res, query(s[i]));
  }

  cout << res << endl;

  return 0;
}



最大异或和

  • 这道题是求整个序列里面的长度小于 $m$ 的序列的最大异或和。可以使用前缀和。然后只有m个结点可以被插入,用一个滑动窗口,滑出去的就通过 insert 函数将 cnt 减一。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 10000010;

int n, m;
int s[N], son[N][2], idx, cnt[N];

void insert(int x, int v)
{
  int u = 0; 
  for (int i = 30; i >= 0; i -- )
  {
      int t = x >> i & 1;
      if (!son[u][t]) son[u][t] = ++ idx;
      u = son[u][t];
      cnt[u] += v;
  }
}

int query(int x)
{
  int res = 0;
  int u = 0;
  for (int i = 30; i >= 0; i -- )
  {
      int t = x >> i & 1;
      res <<= 1;
      if (cnt[son[u][!t]]) u = son[u][!t], res |= 1;
      else u = son[u][t];
  }

  return res;
}

int main()
{
  cin >> n >> m;
  for (int i = 1; i <= n; i ++ ) cin >> s[i];
  for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] ^ s[i];

  int res = 0;
  insert(s[0], 1);
  for (int i = 1; i <= n; i ++ )
  {
      if (i > m) insert(s[i - m - 1], -1); // 清除
      insert(s[i], 1);
      res = max(res, query(s[i]));
  }

  cout << res << endl;

  return 0;
}


活动打卡代码 AcWing 1534. 字符串减法

#include <iostream>
#include <stdio.h>

using namespace std;

bool st[123];

int main()
{
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);

    for (auto i : s2) st[i] = true;
    for (auto i : s1)
    {
        if (st[i]) continue;
        putchar(i);
    }

    return 0;
}



#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 1E5 + 10;

vector<int> a, b;
int e[N], ne[N], h, n;
unordered_set<int> s;

int main()
{
    cin >> h >> n;
    for (int i = 0; i < n; i ++ )
    {
        int addr, d, nt;
        cin >> addr >> d >> nt;
        e[addr] = d, ne[addr] = nt;
    }

    for (int i = h; ~i; i = ne[i])
    {
        if (s.count(abs(e[i])))
            b.push_back(i);
        else
        {
            s.insert(abs(e[i]));
            a.push_back(i);
        }
    }

    for (int i = 0; i < a.size(); i ++ )
    {
        if (i == a.size() - 1) printf("%05d %d -1\n", a[i], e[a[i]]);
        else
            printf("%05d %d %05d\n", a[i], e[a[i]], a[i + 1]);
    }

    for (int i = 0; i < b.size(); i ++ )
        if (i == b.size() - 1) printf("%05d %d -1\n", b[i], e[b[i]]);
        else printf("%05d %d %05d\n", b[i], e[b[i]], b[i + 1]);

    return 0;
}


活动打卡代码 AcWing 1560. 反转链表

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int h, n, k;
int e[N], ne[N];

int main()
{
    cin >> h >> n >> k;
    for (int i = 0; i < n; i ++ ) 
    {
        int addr, d, nt;
        cin >> addr >> d >> nt;
        e[addr] = d, ne[addr] = nt;
    }

    vector<int> v;
    for (int i = h; ~i; i = ne[i])
        v.push_back(i);

    for (int i = 0; i < v.size(); i += k)
    {
        if (i + k - 1 >= v.size()) break;
        reverse(v.begin() + i, v.begin() + i + k);
    }

    for (int i = 0; i < v.size(); i ++ )
    {
        printf("%05d %d", v[i], e[v[i]]);
        if (i == v.size() - 1) puts(" -1");
        else printf(" %05d\n", v[i + 1]);
    }

    return 0;
}


活动打卡代码 AcWing 1516. 共享

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

const int N = 100010;

int h1, h2, n, e[N], ne[N];

bool st[N];

int main()
{
    cin >> h1 >> h2 >> n;
    for (int i = 0; i < n; i ++ )
    {
        int addr, nt;
        char ch;
        cin >> addr >> ch >> nt;
        e[addr] = ch, ne[addr] = nt;
    }

    for (int i = h1; ~i; i = ne[i])
        st[i] = true;

    for (int i = h2; ~i; i = ne[i])
        if (st[i])
        {
            printf("%05d\n", i);
            return 0;
        }
    cout << "-1";

    return 0;
}



#include <stdio.h>

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 110;

int n;
int a[N];

bool judge(int x, int i, int j)
{
    int t = a[x];
    if (t < 0)
    {
        t = abs(t);
        if (t == i || t == j)
            return 0;
        return 1;
    }
    else
    {
        t = abs(t);
        if (t == i || t == j)
            return 1;
        return 0;
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            int s = judge(i, i, j);
            s += judge(j, i, j);
            if (s != 1)
                continue;

            s = 0;
            for (int k = 1; k <= n; k++)
                s += judge(k, i, j);

            if (s != 2)
                continue;
            cout << i << " " << j << endl;

            return 0;
        }

    puts("No Solution");

    return 0;
}


活动打卡代码 AcWing 1581. 急性中风

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>

using namespace std;
const int M = 1286, N = 128, L = 60;
int n, m, l, T;

int d[][3] = {
    {1, 0, 0},
    {-1, 0, 0},
    {0, 1, 0},
    {0, -1, 0},
    {0, 0, 1},
    {0, 0, -1},
};

struct Node
{
    int x, y, z;
};

int g[L][M][N];

bool check(int x, int y, int z)
{
    if (x < 0 || y < 0 || z < 0 || x >= l || y >= m || z >= n)
        return false;
    if (g[x][y][z] == 0) return false;

    return true;
}

int bfs(int x, int y, int z)
{
    queue<Node> q;
    q.push({x, y, z});
    g[x][y][z] = 0;

    int cnt = 1;
    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 6; i ++ )
        {
            int a = t.x + d[i][0], b = t.y + d[i][1], c = t.z + d[i][2];
            if (a >= 0 && a < l && b >= 0 && b < m && c >= 0 && c < n && g[a][b][c])
            {
                g[a][b][c] = 0;
                q.push({a, b, c});
                cnt ++ ;
            }
        }
    }

    return cnt;
}

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

    for (int i = 0; i < l; i ++ )
        for (int j = 0; j < m; j ++ )
            for (int k = 0; k < n; k ++ )
                scanf("%d", &g[i][j][k]);

    int res = 0;
    for (int i = 0; i < l; i ++ )
        for (int j = 0; j < m; j ++ )
            for (int k = 0; k < n; k ++ )
                if (g[i][j][k])
                {
                    int t = bfs(i, j, k);
                    if (t >= T) res += t;
                }

    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 1571. 完美序列

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <limits.h>

using namespace std;

const int N = 1E5 + 10;
int n, p;
int a[N];

int main()
{
    cin >> n >> p;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    int res = INT_MIN;
    sort(a, a + n);
    for (int i = 0, j = 0; i < n; i ++ )
    {
        while ((long long)a[j] * p < a[i]) j ++ ;
        res = max(res, i - j + 1);
    }

    cout << res << endl;

    return 0;
}