头像

墨宇




离线:1个月前



墨宇
1个月前
#include<iostream>
using namespace std;
int n, m;
pair<string, int> a[100005];
int calc(int bit, int now)
{
    for(int i = 1; i <= n; i++)
    {
        int x = a[i].second >> bit & 1;
        if(a[i].first == "AND") now &= x;
        else if(a[i].first == "OR") now |= x;
        else if(a[i].first == "XOR") now ^= x;
    }
    return now;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        char str[5];
        int x;
        scanf("%s%d", str, &x);
        a[i] = make_pair(str, x);
    }
    int val = 0, ans = 0;
    for(int bit = 29; bit >= 0; bit--)
    {
        int res0 = calc(bit, 0);
        int res1 = calc(bit, 1);
        if(val + (1 << bit) <= m && res0 < res1)
            val += 1 << bit, ans += res1 << bit;
        else ans += res0 << bit;
    }
    cout << ans << endl;
}


活动打卡代码 AcWing 91. 最短Hamilton路径

墨宇
1个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstring>
using namespace std;
const int N = 20;
int n, a[N][N], f[1 << N][N];
int main(void)
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> a[i][j];
    memset(f, 0x3f, sizeof f);
    // f[i][j] 表示已经选的点的集合为 i(zipped), 目前正处于j点的最短路径
    f[1][0] = 0;
    for(int i = 1; i < (1 << n); i++)
        for(int j = 0; j < n; j++) if((i >> j) & 1)
            for(int k = 0; k < n; k++) 
                if(((i ^ (1 << j)) >> k) & 1) 
                    f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + a[k][j]);

    cout << f[(1 << n) - 1][n - 1];
}


活动打卡代码 AcWing 90. 64位整数乘法

墨宇
1个月前
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
ll gsc(ll a, ll b, ll p)
{
    ll res = 0;
    while(b)
    {
        if(b & 1) res = (res + a) % p;
        b >>= 1;
        a = (a + a) % p;
    }
    return res % p;
}
int main(void)
{
    ll a, b, p;
    cin >> a >> b >> p;
    cout << gsc(a, b, p);
}


活动打卡代码 AcWing 89. a^b

墨宇
1个月前
#include<iostream>
#define int long long
using namespace std;
int ksm(int a, int b, int p)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res % p;
}
signed main(void)
{
    int a, b, p;
    cin >> a >> b >> p;
    cout << ksm(a, b, p);
}



墨宇
1个月前

题目描述

给定 $n$ 个整数(可能重复),现在需要从中挑选任意个整数,使得选出整数的异或和最大。

请问,这个异或和的最大可能值是多少。

数据范围

$$
1 \le n \le 10^5
$$
$$
0 \le S_i \le 2^{63} - 1
$$

样例

input:
3
5 2 8
output:
15

解法

此题,我们可以使用线性基解决

  • 线性基的定义

对于一个数列 A 来说,P 是他的线性基当且仅当
1. A任意数字都能通过P中的一些数字异或出来
2. P只能异或出A中的数或A中的数能异或出来的东西
3. P中任意数都不能被P中其他数异或出来
4. P中数最高位不重复

由3容易得出
$$
P_i \oplus P_j \neq P_k \oplus P_l
$$

所以,A中数可以异或出来的最大值就是P中数可以异或出来的最大值

// 1.已知线性基求最大值
int findmax(int *p, int len)
{
    sort(p + 1, p + len + 1, greater<int>());
    int v = 0;
    for(int i = 1; i <= len; i++)
        v = max(v, v ^ p[i]);
    return v;
}

这种看似贪心的做法为什么是对的呢?
让我们看一张图:

首先1一定要选,为什么呢?
我们知道一个常识,那就是大位压死小位(官大一级压死你)
1000000000 > 111111111
如果不选1那么以后再也没有一个数可以使得最高位为1了,那么结果一定更劣
然后,分别考虑,优先看最高位
当前数 $\oplus$ 最高位 = 0 不选, 否则选
写出来,就是简单的取max了~~

那么,如何求线性基呢?
为了满足4要求,我们要比较所有最高位,如果当前要插入的数最高位已经有了,就异或上这个有的数,重复直到没有再插入(0就不用了),容易证明符合123条件。

void add(int v)
{
    for(int i = 1; i <= cnt; i++)
        v = min(v, v ^ p[i]);

    if(v)
    {
        p[++cnt] = v;
        sort(p + 1, p + cnt + 1, greater<int>());
    }
}

注意long long,现在就可以给出代码了:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
long long n, p[N], a[N], cnt;
void add(long long v)
{
    for(int i = 1; i <= cnt; i++)
        v = min(v, v ^ p[i]);

    if(v)
    {
        p[++cnt] = v;
        sort(p + 1, p + cnt + 1, greater<long long>());
    }
}
int main(void)
{
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%lld", a + i), add(a[i]);

    long long v = 0;
    for(int i = 1; i <= cnt; i++)
        v = max(v, v ^ p[i]);

    cout << v;
}


活动打卡代码 AcWing 1091. 理想的正方形

墨宇
1个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int n, m, k, a[N][N], mx[N][N], mn[N][N], mmx[N], mmn[N], t1[N], t2[N];
int q[N], hh, tt;

int gtmx(int *src, int *dst, int len) // 在src上建立k大小滑动窗口
{
    hh = 0, tt = -1;

    for(int i = 1; i <= len; i++)
    {
        while(hh <= tt && q[hh] + k <= i) hh++;
        while(hh <= tt && src[q[tt]] <= src[i]) --tt;
        q[++tt] = i;
        if(i >= k) dst[i] = src[q[hh]];
    }
    return 0; // ok
}
int gtmn(int *src, int *dst, int len) // 在src上建立k大小滑动窗口
{
    hh = 0, tt = -1;

    for(int i = 1; i <= len; i++)
    {
        while(hh <= tt && q[hh] + k <= i) hh++;
        while(hh <= tt && src[q[tt]] >= src[i]) --tt;
        q[++tt] = i;
        dst[i] = src[q[hh]];
    }
    return 0; // ok
}

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

    for(int i = 1; i <= n; i++)
    {
        gtmx(a[i], mx[i], m);
        gtmn(a[i], mn[i], m);
    }
    int ans = 1e9 + 7;
    for(int i = k; i <= m; i++)
    {
        for(int j = 1; j <= n; j++) t1[j] = mx[j][i], t2[j] = mn[j][i];
        gtmx(t1, mmx, n);
        gtmn(t2, mmn, n);
        for(int j = k; j <= n; j++) ans = min(ans, mmx[j] - mmn[j]);
    }
    cout << ans;
}


活动打卡代码 AcWing 1107. 魔板

墨宇
1个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

char g[2][4];
unordered_map<string, pair<char, string>> pre;
unordered_map<string, int> dist;

void set(string state)
{
    for (int i = 0; i < 4; i ++ ) g[0][i] = state[i];
    for (int i = 7, j = 0; j < 4; i --, j ++ ) g[1][j] = state[i];
}

string get()
{
    string res;
    for (int i = 0; i < 4; i ++ ) res += g[0][i];
    for (int i = 3; i >= 0; i -- ) res += g[1][i];
    return res;
}

string move0(string state)
{
    set(state);
    for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]);
    return get();
}

string move1(string state)
{
    set(state);
    int v0 = g[0][3], v1 = g[1][3];
    for (int i = 3; i >= 0; i -- )
    {
        g[0][i] = g[0][i - 1];
        g[1][i] = g[1][i - 1];
    }
    g[0][0] = v0, g[1][0] = v1;
    return get();
}

string move2(string state)
{
    set(state);
    int v = g[0][1];
    g[0][1] = g[1][1];
    g[1][1] = g[1][2];
    g[1][2] = g[0][2];
    g[0][2] = v;
    return get();
}

int bfs(string start, string end)
{
    if (start == end) return 0;

    queue<string> q;
    q.push(start);
    dist[start] = 0;

    while (!q.empty())
    {
        auto t = q.front();
        q.pop();

        string m[3];
        m[0] = move0(t);
        m[1] = move1(t);
        m[2] = move2(t);

        for (int i = 0; i < 3; i ++ )
            if (!dist.count(m[i]))
            {
                dist[m[i]] = dist[t] + 1;
                pre[m[i]] = {'A' + i, t};
                q.push(m[i]);
                if (m[i] == end) return dist[end];
            }
    }

    return -1;
}

int main()
{
    int x;
    string start, end;
    for (int i = 0; i < 8; i ++ )
    {
        cin >> x;
        end += char(x + '0');
    }

    for (int i = 1; i <= 8; i ++ ) start += char('0' + i);

    int step = bfs(start, end);

    cout << step << endl;

    string res;
    while (end != start)
    {
        res += pre[end].first;
        end = pre[end].second;
    }

    reverse(res.begin(), res.end());

    if (step > 0) cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 252. 树

墨宇
5个月前
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 10010, M = N * 2;
int n, m, h[N], e[M], w[M], ne[M], idx;
int st[N], p[N], q[N];

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

int gtsiz(int u, int fa)
{
    if(st[u]) return 0;
    int res = 1;
    for(int i = h[u]; ~i; i = ne[i])
        if(e[i] != fa) res += gtsiz(e[i], u);
    return res;
}

int gtwc(int u,int fa, int tot, int &wc)
{
    if(st[u]) return 0;
    int sum = 1, ms = 0;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        int t = gtwc(j, u, tot, wc);
        ms = max(ms, t);
        sum += t;
    }
    ms = max(ms, tot - sum);
    if(ms <= tot / 2) wc = u;
    return sum;
}

void gtd(int u, int fa, int dist, int &qt)
{
    if(st[u]) return;
    q[qt++] = dist;
    for(int i = h[u]; ~i; i = ne[i])
        if(e[i]!=fa) 
            gtd(e[i], u, dist + w[i], qt);
}

int get(int a[], int k)
{
    sort(a, a + k);
    int res = 0;
    for(int i = k - 1, j = -1; i >= 0; i--)
    {
        while(j + 1 < i && a[j + 1] + a[i] <= m) j++;
        j = min(j, i - 1);
        res += j - 1;
    }
    return res;
}

int calc(int u)
{
    if(st[u]) return 0;
    int res = 0;
    gtwc(u, -1, gtsiz(u, -1), u); // 获得重心
    st[u] = true; // 删除重心, 通过重心来分治

    int pt = 0;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i], qt = 0;
        gtd(j, -1, w[i], qt);
        res -= get(q, qt);
        for(int k = 0; k < qt; k++)
        {
            if(q[k] <= m) res++;
            p[pt++] = q[k];
        }
    }
    res += get(p, pt);

    for(int i = h[u]; ~i; i = ne[i]) res += calc(e[i]);
    return res;
}

int main(void)
{
    while(scanf("%d%d", &n, &m), n || m)
    {
        memset(st, 0, sizeof st);
        memset(h, -1, sizeof h);
        idx = 0;
        for(int i = 0; i < n - 1; i++)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c), add(b, a, c);
        }
        printf("%d\n", calc(0));
    }
    return 0;
}


活动打卡代码 AcWing 214. Devu和鲜花

墨宇
5个月前
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
typedef long long LL;
using namespace std;
const int N = 20 + 10, mod = 1e9 + 7;
int n;
LL m, A[N], down;

int qpow(int a, int x, int p)
{
    int res = 1;
    while(x)
    {
        if(x & 1) res = res * a % p;
        a = a * a % p;
        x /= 2;
    }
    return res;
}

int C(LL a, LL b)
{
    if (a < b) return 0;
    int up = 1;
    for (LL i = a; i > a - b; i -- ) up = i % mod * up % mod;

    return (LL)up * down % mod; // 费马小定理
}

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

    for(int j = 1; j <  n; j++) down = down * (LL)j % mod;
    down = qpow(down, mod - 2, mod);

    int res = 0;
    for(int i = 1; i < 1 << n; i++)
    {
        LL a = m + n - 1, b = n - 1;
        int sign = 1;
        for(int j = 0; j < n; j++)
            if(i >> j & 1) // cun zai ta aba aba
            {
                sign = -sign;
                a -= A[j] + 1;
            }
        res = (res + C(a, b) * sign) % mod;
    }
    cout << (res % mod + mod) % mod;
}


活动打卡代码 AcWing 265. 营业额统计

墨宇
5个月前
#include<iostream>
#include<set>
using namespace std;
const int N = 4e4 + 10;
int a[N], n;
set<int> s;
int main(void)
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        if(i == 1) res += a[i];
        else
        {
            int l = *s.lower_bound(a[i]);
            set<int>::iterator it = s.upper_bound(a[i]);
            if(it != s.begin()) it--;
            int r = *it;
            res += min(abs(l - a[i]), abs(a[i] - r));
        }
    }
    cout << res;
}