8 条题解

  • 2
    @ 2023-5-20 18:30:12

    路径最大异或和

    #include<bits/stdc++.h>
#define int long long
#define enel "\n"
#define MOD 1000000007
using namespace std;
const int MAXN=50000;
const int MAXL=60;
struct NOTE
{
	signed v;
	int s;
};
vector<NOTE> e[MAXN+5];
int tot[MAXN+5];
int a[MAXL+5];
int n,m,ans;
bool book[MAXN+6];
void insert(int num)
{
	for(int j=60;j>=0;j--)
	{
		if(!num)
			return;
		if(!(num&(1ll<<j)))
			continue;
		if(a[j]!=0)
		{
			num=num^a[j];
			continue;
		}
		for(int k=0;k<j;k++)
			if(num&(1ll<<k))
				num=num^a[k];
		for(int k=j+1;k<=60;k++)
			if(a[k]&(1ll<<j))
				a[k]=a[k]^num;
		a[j]=num;
		break;
	}
	return;
}
void dfs(int now,int sum)
{
	book[now]=true;
	tot[now]=sum;
	for(int i=0;i<e[now].size();i++)
	{
		signed v=e[now][i].v;
		int w=e[now][i].s;
		if(book[v])
		{
			insert(sum ^ w ^ tot[v]);
			continue;
		}
		dfs(v,sum^w);
	}
	return;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,x;
		cin>>u>>v>>x;
		e[u].push_back((NOTE){v,x});
		e[v].push_back((NOTE){u,x});
	}
	dfs(1,0);
	ans=tot[n];
	for(int i=0;i<=MAXL;i++)
		ans=max(ans,ans^a[i]);
	cout<<ans<<endl;
	return 0;
}
    • 0
      @ 2023-5-20 16:13:46

      P4151 [WC2011]最大XOR和路径

      #include <bits/stdc++.h>
using namespace std;
// template from men.ci
const int MAXL = 60;
struct LinearBasis
{
    long long a[MAXL + 1];
    LinearBasis()
    {
        std::fill(a, a + MAXL + 1, 0);
    }
    LinearBasis(long long *x, int n)
    {
        build(x, n);
    }
    void insert(long long t)
    {
        for (int j = MAXL; j >= 0; j--)
        {
            if (!t)
                return;
            if (!(t & (1ll << j)))
                continue;
            if (a[j])
                t ^= a[j];
            else
            {
                for (int k = 0; k < j; k++)
                    if (t & (1ll << k))
                        t ^= a[k];
                for (int k = j + 1; k <= MAXL; k++)
                    if (a[k] & (1ll << j))
                        a[k] ^= t;
                a[j] = t;
                break;
            }
        }
    }
    // 数组 x 表示集合 S，下标范围 [1...n]
    void build(long long *x, int n)
    {
        std::fill(a, a + MAXL + 1, 0);
        for (int i = 1; i <= n; i++)
        {
            insert(x[i]);
        }
    }
    long long queryMax()
    {
        long long res = 0;
        for (int i = 0; i <= MAXL; i++)
            res ^= a[i];
        return res;
    }
    void mergeFrom(const LinearBasis &other)
    {
        for (int i = 0; i <= MAXL; i++)
            insert(other.a[i]);
    }
    static LinearBasis merge(const LinearBasis &a, const LinearBasis &b)
    {
        LinearBasis res = a;
        for (int i = 0; i <= MAXL; i++)
            res.insert(b.a[i]);
        return res;
    }
} lb;
int n, m;
vector<pair<int, long long>> e[51234];
long long xorSum[51234]; // 1->i 的异或和
bool vis[51234];
void dfs(int u, long long nowXorSum)
{
    vis[u] = true;
    xorSum[u] = nowXorSum;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i].first;
        long long w = e[u][i].second;
        if (!vis[v])
            dfs(v, nowXorSum ^ w);
        else
            lb.insert(nowXorSum ^ w ^ xorSum[v]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        e[u].push_back(make_pair(v, w));
        e[v].push_back(make_pair(u, w));
    }
    dfs(1, 0);
    long long ans = xorSum[n];
    for (int i = MAXL; i >= 0; i--)
        ans = max(ans, ans ^ lb.a[i]);
    cout << ans << "\n";
    return 0;
}
      • 0
        @ 2023-5-20 16:13:13

        P3812 【模板】线性基

        #include <bits/stdc++.h>
using namespace std;
const int MAXL = 50;
// template from men.ci
struct LinearBasis
{
    long long a[MAXL + 1];
    LinearBasis()
    {
        std::fill(a, a + MAXL + 1, 0);
    }
    LinearBasis(long long *x, int n)
    {
        build(x, n);
    }
    void insert(long long t)
    {
        for (int j = MAXL; j >= 0; j--)
        {
            if (!t)
                return;
            if (!(t & (1ll << j)))
                continue;
            if (a[j])
                t ^= a[j];
            else
            {
                for (int k = 0; k < j; k++)
                    if (t & (1ll << k))
                        t ^= a[k];
                for (int k = j + 1; k <= MAXL; k++)
                    if (a[k] & (1ll << j))
                        a[k] ^= t;
                a[j] = t;
                break;
            }
        }
    }
    // 数组 x 表示集合 S，下标范围 [1...n]
    void build(long long *x, int n)
    {
        std::fill(a, a + MAXL + 1, 0);
        for (int i = 1; i <= n; i++)
        {
            insert(x[i]);
        }
    }
    long long queryMax()
    {
        long long res = 0;
        for (int i = 0; i <= MAXL; i++)
            res ^= a[i];
        return res;
    }
    void mergeFrom(const LinearBasis &other)
    {
        for (int i = 0; i <= MAXL; i++)
            insert(other.a[i]);
    }
    static LinearBasis merge(const LinearBasis &a, const LinearBasis &b)
    {
        LinearBasis res = a;
        for (int i = 0; i <= MAXL; i++)
            res.insert(b.a[i]);
        return res;
    }
} lb;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long n, x;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        lb.insert(x);
    }
    cout << lb.queryMax() << "\n";
    return 0;
}
        • 0
          @ 2023-5-17 15:22:24

          P1939 【模板】矩阵加速（数列）

          #include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXR = 3; // 矩阵最大行数
const int MAXC = 3; // 矩阵最大列数
int MOD = 1000000000 + 7;
struct Mat
{
    int r, c; // 行数列数
    int m[MAXR + 1][MAXC + 1];
    Mat() { memset(m, 0, sizeof(m)); }
};
Mat operator*(const Mat &a, const Mat &b)
{
    assert(a.c == b.r);
    Mat res;
    res.r = a.r, res.c = b.c;
    for (int i = 1; i <= a.r; i++)
        for (int k = 1; k <= a.c; k++)
        {
            int temp = a.m[i][k];
            for (int j = 1; j <= b.c; j++)
                res.m[i][j] = (res.m[i][j] + temp * b.m[k][j]) % MOD;
        }
    return res;
}
Mat quick_pow(Mat a, int b)
{
    assert(a.r == a.c);
    Mat res;
    res.r = res.c = a.r;
    for (int i = 1; i <= res.r; i++)
        res.m[i][i] = 1;
    while (b > 0)
    {
        if (b % 2)
            res = res * a;
        a = a * a;
        b = b / 2;
    }
    return res;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    // 构造矩阵
    Mat now;
    now.r = 1, now.c = 3;
    now.m[1][1] = 1, now.m[1][2] = 1, now.m[1][3] = 1;
    Mat ans;
    ans.r = ans.c = 3;
    ans.m[1][1] = 0, ans.m[1][2] = 0, ans.m[1][3] = 1;
    ans.m[2][1] = 1, ans.m[2][2] = 0, ans.m[2][3] = 0;
    ans.m[3][1] = 0, ans.m[3][2] = 1, ans.m[3][3] = 1;
    while (T--)
    {
        int x;
        cin >> x;
        // 计算答案
        Mat ans_ = quick_pow(ans, x - 1);
        Mat now_ = now * ans_;
        cout << now_.m[1][1] % MOD << "\n";
    }
    return 0;
}
          • 0
            @ 2023-5-16 16:15:25

            P1349 广义斐波那契数列

            #include <bits/stdc++.h>
#define int long long
using namespace std;
int p, q, a1, a2, n, m;
const int MAXR = 3; // 矩阵最大行数
const int MAXC = 3; // 矩阵最大列数
int MOD;
struct Mat
{
    int r, c; // 行数列数
    int m[MAXR + 1][MAXC + 1];
    Mat() { memset(m, 0, sizeof(m)); }
};
Mat operator*(const Mat &a, const Mat &b)
{
    assert(a.c == b.r);
    Mat res;
    res.r = a.r, res.c = b.c;
    for (int i = 1; i <= a.r; i++)
        for (int k = 1; k <= a.c; k++)
        {
            int temp = a.m[i][k];
            for (int j = 1; j <= b.c; j++)
                res.m[i][j] = (res.m[i][j] + temp * b.m[k][j]) % MOD;
        }
    return res;
}
Mat quick_pow(Mat a, int b)
{
    assert(a.r == a.c);
    Mat res;
    res.r = res.c = a.r;
    for (int i = 1; i <= res.r; i++)
        res.m[i][i] = 1;
    while (b > 0)
    {
        if (b % 2)
            res = res * a;
        a = a * a;
        b = b / 2;
    }
    return res;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> p >> q >> a1 >> a2 >> n >> m;
    MOD = m;
    // 构造矩阵
    Mat now;
    now.r = 1, now.c = 2;
    now.m[1][1] = a1, now.m[1][2] = a2;
    Mat ans;
    ans.r = ans.c = 2;
    ans.m[1][1] = 0, ans.m[1][2] = q;
    ans.m[2][1] = 1, ans.m[2][2] = p;
    // 计算答案
    ans = quick_pow(ans, n - 1);
    now = now * ans;
    cout << now.m[1][1] % MOD << "\n";
    return 0;
}
            • 0
              @ 2023-5-16 16:11:46

              P1962 斐波那契数列

              #include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXR = 3; // 矩阵最大行数
const int MAXC = 3; // 矩阵最大列数
const int MOD = 1000000000 + 7;
struct Mat
{
    int r, c; // 行数列数
    int m[MAXR + 1][MAXC + 1];
    Mat() { memset(m, 0, sizeof(m)); }
};
Mat operator*(const Mat &a, const Mat &b)
{
    assert(a.c == b.r);
    Mat res;
    res.r = a.r, res.c = b.c;
    for (int i = 1; i <= a.r; i++)
        for (int k = 1; k <= a.c; k++)
        {
            int temp = a.m[i][k];
            for (int j = 1; j <= b.c; j++)
                res.m[i][j] = (res.m[i][j] + temp * b.m[k][j]) % MOD;
        }
    return res;
}
Mat quick_pow(Mat a, int b)
{
    assert(a.r == a.c);
    Mat res;
    res.r = res.c = a.r;
    for (int i = 1; i <= res.r; i++)
        res.m[i][i] = 1;
    while (b > 0)
    {
        if (b % 2)
            res = res * a;
        a = a * a;
        b = b / 2;
    }
    return res;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    // 构造矩阵
    Mat now;
    now.r = 1, now.c = 2;
    now.m[1][1] = 1, now.m[1][2] = 1;
    Mat ans;
    ans.r = ans.c = 2;
    ans.m[1][1] = 0, ans.m[1][2] = 1;
    ans.m[2][1] = 1, ans.m[2][2] = 1;
    // 计算答案
    ans = quick_pow(ans, n - 1);
    now = now * ans;
    cout << now.m[1][1] % MOD << "\n";
    return 0;
}
              • 0
                @ 2023-5-16 15:46:50

                P2455 [SDOI2006]线性方程组

                #include <bits/stdc++.h>
using namespace std;
int n;
//------------高斯消元模板-Start--------------
const double eps = 1e-12;
double a[105][105]; // 高斯消元的方程，a[i][0] 记录第 i 个方程的主元
// 无解：返回 -1
// 多解：返回 0
// 有解：返回 1
int gauss(int x)
{
    bool flag = false;           // 多解flag
    int line = 1;                // 当前方程的编号
    for (int i = 1; i <= x; i++) // 主元编号
    {
        // 当前方程是第 line 个方程
        // 试图把当前方程主元变量(第i个变量)系数调整为 1
        // 找到下面主元系数最大的方程
        int row = line;
        for (int j = line + 1; j <= x; j++)
            if (fabs(a[row][i]) < fabs(a[j][i]))
                row = j;
        // 用系数最大的那个作为当前方程
        if (row != line)
            std::swap(a[row], a[line]);
        // 如果最大的系数都是 0 了，下面所有方程的就都是 0 了，不用往下调整了
        double div1 = a[line][i];
        if (fabs(div1) < eps)
            continue;
        a[line][0] = i;
        // 调整当前方程
        for (int j = 1; j <= x + 1; j++)
            a[line][j] /= div1;
        // 用当前方程调整下面的方程，把下面方程的第 i 个系数小调
        for (int j = line + 1; j <= x; j++)
        {
            double div2 = a[j][i];
            for (int k = 1; k <= x + 1; ++k)
                a[j][k] -= a[line][k] * div2;
        }
        line++;
    }
    // 判无解和多解
    if (line <= x)
    {
        for (int i = line; i <= x; i++)
            if (a[i][x + 1] != 0)
                return -1;
        return 0;
    }
    // 有唯一解时依次处理
    for (int i = x; i >= 1; i--)
    {
        for (int j = i - 1; j >= 1; j--)
        {
            a[j][x + 1] -= a[j][i] * a[i][x + 1];
            a[j][i] = 0;
        }
    }
    return 1;
}
//------------高斯消元模板-End--------------
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n + 1; j++)
            cin >> a[i][j];
    int typ = gauss(n);
    if (typ <= 0)
    {
        cout << typ << "\n";
        return 0;
    }
    cout << fixed << setprecision(2);
    for (int i = 1; i <= n; i++)
        cout << "x" << i << "=" << a[i][n + 1] << "\n";
    return 0;
}
                • 0
                  @ 2023-5-16 15:14:13

                  P5027 Barracuda

                  #include <bits/stdc++.h>
using namespace std;
int n;
double base[105][105]; // 初始 n+1 个方程
//------------高斯消元模板-Start--------------
const double eps = 1e-12;
double a[105][105]; // 高斯消元的方程
bool gauss(int x)
{
    for (int i = 1; i <= x; i++)
    {
        // 当前方程是第 i 个方程
        // 试图把当前方程第 i 个变量系数调整为 1
        // 找到下面第 i 个变量系数最大的方程
        int row = i;
        for (int j = i; j <= x; j++)
            if (fabs(a[row][i]) < fabs(a[j][i]))
                row = j;
        // 用系数最大的那个作为当前方程
        if (row != i)
            std::swap(a[row], a[i]);
        // 如果最大的系数都是 0 了，下面所有方程的就都是 0 了
        double div1 = a[i][i];
        if (fabs(div1) < eps)
            return false;
        // 调整当前方程
        for (int j = 1; j <= x + 1; j++)
            a[i][j] /= div1;
        // 用当前方程调整下面的方程，把下面方程的第 i 个系数小调
        for (int j = i + 1; j <= x; j++)
        {
            double div2 = a[j][i];
            for (int k = 1; k <= x + 1; ++k)
                a[j][k] -= a[i][k] * div2;
        }
    }
    // 每个方程向上把对应系数清零
    for (int i = x; i >= 1; i--)
        for (int j = i - 1; j >= 1; j--)
        {
            a[j][x + 1] -= a[j][i] * a[i][x + 1];
            a[j][i] = 0;
        }
    return true;
}
//------------高斯消元模板-End--------------
// 检查一个double是不是整数
bool zheng(double x)
{
    return fabs(x - round(x)) < eps;
}
// 检查答案是否合法（只有一个最大值、都是正整数）
// 非法返回 0，否则返回最大值的变量
int check(int x)
{
    if (a[1][x + 1] <= 0 || !zheng(a[1][x + 1]))
        return false;
    double maxAns = a[1][x + 1];
    int maxPos = 1;
    int maxCnt = 1;
    for (int i = 2; i <= x; i++)
    {
        if (a[i][x + 1] <= 0 || !zheng(a[i][x + 1]))
            return false;
        if (fabs(a[i][x + 1] - maxAns) < eps)
            maxCnt++;
        else if (a[i][x + 1] > maxAns)
        {
            maxAns = a[i][x + 1];
            maxPos = i;
            maxCnt = 1;
        }
    }
    if (maxCnt > 1)
        return 0;
    return maxPos;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n + 1; i++)
    {
        int m;
        cin >> m;
        for (int j = 1; j <= m; j++)
        {
            int x;
            cin >> x;
            base[i][x] = 1;
        }
        cin >> base[i][n + 1];
    }
    // work
    int okCnt = 0;  // 有几种合法情况
    int okAns = -1; // 最重三角形编号
    // 枚举哪条称量非法
    for (int error = 1; error <= n + 1; error++)
    {
        // 拿来当前待处理的方程
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n + 1; j++)
            {
                if (i < error)
                    a[i][j] = base[i][j];
                else
                    a[i][j] = base[i + 1][j];
            }
        // 高斯消元
        bool flag = gauss(n); // 是否有多解/无解
        if (!flag)
            continue;
        int now = check(n); // 答案是否符合题意
        if (now == 0)
            continue;
        // 检查当前有多少个error情况是合法的
        okCnt++;
        if (okCnt > 1)
        {
            cout << "illegal\n";
            return 0;
        }
        okAns = now;
    }
    if (okCnt < 1)
        cout << "illegal\n";
    else
        cout << okAns << "\n";
    return 0;
}
                  • 1

                  扩展题单 - 线性代数

                  信息

                  ID
                  1277
                  时间
                  1000ms
                  内存
                  256MiB
                  难度
                  6
                  标签
                  递交数
                  15
                  已通过
                  13
                  上传者
                  1. 评测队列
                  2. 服务状态
                  3. 兼容模式
                  4. 主题
                  2. 陕ICP备2022006801号-1
                  3. Worker 0, 10ms
                  4. Powered by Hydro v4.14.1 Community, Modified by 33DAI