Dylan's Blog
0%

Posted on Edited on In

问题描述：

考虑一个边权为非负整数的无向连通图，节点编号为$1$到$N$，试求出一条从 $1$号节点到$N$号节点的路径，使得路径上经过的边的权值的 XOR 和最大。

路径可以重复经过某些点或边，当一条边在路径中出现了多次时，其权值在计算 XOR 和时也要被计算相应多的次数。

输入：

第一行包含两个整数$N(n<=50000)$和$M(m<=100000)$，表示该无向图中点的数目与边的数目。 接下来$M$行描述$M$条边，每行三个整数$S_i,T_i,D_i$，表示$S_i$与$T_i$之间存在一条权值为$D_i$的无向边（图中可能有重边或自环）

输出：

仅包含一个整数，表示最大的 XOR 和

思路：

这种玄学的做法自然的想不到的啦。。。

首先异或路径有一个很有趣的地方就是你可以“瞬移”到任何地方，严谨的说就是你从$x$到$y$，再从$y$回到$x$这一段路径对答案的贡献为0。所以你从1到n的路径可以看成是：一条1到n的简单路径加上图中的一些环。形象的说就是你可以瞬移到环上一点绕一圈再瞬移回来。

如果只有一条1到n的路径，我们就可以直接利用线性基求出它们的最大异或和就好了。但如果有多条路径该如何维护？其实这也很简(xuan)单(xue)，随意选任意一条就好了！！因为这多条路径其实是构成了多个环的，如果你选了一条使答案更小路径，那么你再选这个路径构成的环就好了。那条小的路径走了两遍，相当于你走了另一条路径。所以你可以随意选一条路径，同样用线性基维护就好了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100005
#define LL long long
using namespace std;

int n, m, cnt, tot, head[MAXN];
LL ans, dis[MAXN], cir[MAXN], base[MAXN];
bool vis[MAXN];

struct Edge {int next, to; LL dis;} edge[MAXN*2];

void addedge(int from, int to, LL dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void insert(LL x)
{
    for(int i=62; i>=0; i--)
    {
        if(!(x>>i)) continue;
        if(!base[i])  {base[i]=x; break;}
        x^=base[i];
    }
}

void dfs(int x)
{
    vis[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!vis[to])
        {
            dis[to]=dis[x]^edge[i].dis;
            dfs(to);
        }
        else insert(dis[to]^edge[i].dis^dis[x]);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y; LL z;
        scanf("%d%d%lld", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    dfs(1);
    ans=dis[n];
    for(int i=62; i>=0; i--)
        if((ans^base[i])>ans) ans=ans^base[i];
    printf("%lld\n", ans);
}

Posted on Edited on In

7月30号 Codeforces Round #500 题目链接：http://codeforces.com/contest/1013

A - Piles With Stones

过水，不说。

B - And

思路： 首先可以发现答案只能是-1,0,1,2，所以我们一个一个判断。如果已经有重复元素，答案就是0；如果与x后有重复元素，答案就是1；如果两个元素与x后相等，答案就是2；其余的情况答案就是-1。然后就是一些细节注意处理。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#define INF 0x3f3f3f3f
#define MAXN 1000005
#define LL long long
#define LB long double
using namespace std;

int n, k, a[MAXN], vis1[MAXN], vis2[MAXN];

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), vis1[a[i]]++;
    for(int i=1; i<=n; i++) if(vis1[a[i]]>=2)
    {
        printf("0\n");
        return 0;
    }
    for(int i=1; i<=n; i++)
        if(a[i]!=(a[i]&k)) vis2[a[i]&k]++;
    for(int i=1; i<=n; i++) if(vis2[a[i]]>=1) 
    {
        printf("1\n");
        return 0;
    }
    for(int i=1; i<=n; i++) if(vis2[a[i]&k]>=2)
    {
        printf("2\n");
        return 0;
    }
    printf("-1\n");
    return 0;
}

C - Photo of The Sky

思路： 蛮神奇的一题。我们可以先将这些坐标排序，并将它们分为两类，横坐标集合与纵坐标集合。可以发现横坐标集合一定是连续的n个，如果你随意交换一对使它不连续，那么纵坐标的极差不变，很坐标的极差增大了，而答案就是两个极差之积。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#define INF 1e18+5
#define MAXN 100005
#define LL long long
#define LB long double
using namespace std;

int n;
LL ans=INF, a[MAXN*2];

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n*2; i++) scanf("%lld", &a[i]);
    sort(a+1, a+2*n+1);
    for(int i=1; i<=n; i++)
    {
        LL x=a[i+n-1]-a[i], y;
        if(i==1) y=a[2*n]-a[n+1];
        else y=a[2*n]-a[1];
        if(x*y<ans) ans=x*y;
    }
    printf("%lld\n", ans);
}

D - Chemical table

思路： 首先用类似于连二分图的方法连边，把行和列作为节点。那么可以发现，我们要做的就是使整个图变为一个联通块。于是我们可以统计联通块个数，每加一个点就相当于连一条边，所以我们只需要加联通块个数-1个点就好了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 500005
using namespace std;

int n, m, q, cnt, ans, head[MAXN], x[MAXN], y[MAXN];
bool vis[MAXN];

struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs(int x)
{
    vis[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!vis[to]) dfs(to);
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for(int i=1; i<=q; i++)
    {
        scanf("%d%d", &x[i], &y[i]);
        addedge(x[i], y[i]+n);
        addedge(y[i]+n, x[i]);
    }
    for(int i=1; i<=n+m; i++)
        if(!vis[i]) dfs(i), ans++;
    printf("%d\n", ans-1);
}

E - Hills

思路： 就是一个DP，首先我们设$f[i][j][k]$为第i个位置，建了j座房子所花的代价，$k$表示在位置$i$有没有建房子。然后我可以把位置$i$造房子的代价拆成两个：把左边变的更低的代价$l[i]$，把右边变得更低的代价$r[i]$。

然后就按照DP来，转移方程就看代码吧（懒得写了）。其中有一些细节要注意：如果两座房子中间之隔了一个，那么前一座房子的代价$r[i]$与这一座房子的代价$l[i]$有重合，于是我们特别地把这时的代价记为$val$，于是转移时还要特别考虑这个情况。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 5005
#define INF 0x3f3f3f
using namespace std;

int n, a[MAXN], l[MAXN], r[MAXN], f[MAXN][MAXN][2];

int main()
{
    scanf("%d", &n);
    memset(f, 0x3f, sizeof(f));
    f[0][0][0]=0;
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=n; i++)
    {
        l[i]=max(0, a[i-1]-a[i]+1);
        r[i]=max(0, a[i+1]-a[i]+1);
    }
    for(int i=1; i<=n; i++)
    {
        f[i][0][0]=f[i-1][0][0];
        for(int j=1; j<=(i+1)/2; j++)
        {
            int val= i<=2 ? INF:f[i-2][j-1][1]+max(0, a[i-2]-a[i])+r[i];
            f[i][j][0]=min(f[i-1][j][0], f[i-1][j][1]);
            f[i][j][1]=min(f[i-1][j-1][0]+l[i]+r[i], val);
        }
    }
    for(int i=1; i<=(n+1)/2; i++) printf("%d ", min(f[n][i][0], f[n][i][1]));
}

Posted on Edited on In

问题描述：

给你一个$W*H$的矩形网格，两个人轮流水平或垂直地剪去一部分，如果轮到某个人只剩下1*1的网格时，则认为那个人输了。

输入：

有多组数据，每组数据两个数$W,H(2<=W,H<=200)$

输出：

每组数据一行，如果先手能赢输出”WIN”，否则”LOST”

思路：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 205
using namespace std;

int x[MAXN][MAXN], tag[MAXN<<3];

int sg(int n, int m)
{
    if(x[n][m]!=-1) return x[n][m];
    memset(tag, 0, sizeof(tag));
    for(int i=2; i<=n/2; i++) tag[sg(i, m)^sg(n-i, m)]=1;
    for(int i=2; i<=m/2; i++) tag[sg(n, i)^sg(n, m-i)]=1;
    for(int i=0; ;i++) if(tag[i]==0) {x[n][m]=i; return i;}
}

int main()
{
    int n, m;
    memset(x, -1, sizeof(x));
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        if(sg(n, m)) printf("WIN\n");
        else printf("LOSE\n");
    }
}

Posted on Edited on In

问题描述：

简单来说就是让你计算：

输入：

两个数N、G

输出：

一个数，表示答案除以999911659的余数

思路：

很好的一道题呢，涵盖了大部分数论知识点呢：欧拉定理、中国剩余定理，Lucas定理，组合数取模，逆元….

不过思路不会很复杂。首先指数那么大，肯定不难想到利用欧拉定理将指数缩小，原理可以看这篇文章。所以我们可以将指数变为$\sum_{d|n}C_n^d mod 999911658$，求这个就是求组合数取模，用lucas定理。。。

那么问题来了，我们普通的Lucas定理中模数要求是质数，但这题中模数不是质数，因此我们要用扩展Lucas。首先将模数质因数分解，分解为2，3，4679，35617四个质数。分别在模这四个质数的意义下求出我们要的结果$a_1, a_2, a_3, a_4$。这样答案就可以表示为： $ans \equiv a_1 (mod 2) $ $ans \equiv a_2 (mod 3) $ $ans \equiv a_3 (mod 4769) $ $ans \equiv a_4 (mod 35617) $ 那这样就是中国剩余定理的形式，解出$ans$并利用快速幂$G^{ans}$就好了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define LL long long
#define mod 999911659
#define MAXN 40005
using namespace std;

const LL prime[5]={0, 2, 3, 4679, 35617};

LL n, g, num[MAXN], fac[MAXN], inv[MAXN];

LL ksm(LL x, LL y, LL p)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum=(sum*x)%p;
        y>>=1; x=(x*x)%p;
    }
    return sum;
}

LL comb(LL n, LL m, LL p)
{
    if(n<m) return 0;
    return fac[n]*inv[n-m]%p*inv[m]%p;
}

LL lucas(LL n, LL m, LL p)
{
    if(m==0) return 1;
    return comb(n%p, m%p, p)*lucas(n/p, m/p, p)%p;
}

LL crt()
{
    LL ans=0;
    for(int i=1; i<=4; i++)
    {
        LL m=(mod-1)/prime[i];
        ans=(ans+num[i]*m%(mod-1)*ksm(m, prime[i]-2, prime[i]))%(mod-1);
    }
    return ans;
}

int main()
{
    scanf("%lld%lld", &n, &g);
    if(g==mod) {printf("0\n"); return 0;}
    for(int i=1; i<=4; i++)
    {
        fac[0]=fac[1]=inv[0]=inv[1]=1;
        for(int j=2; j<=prime[i]; j++)
        {
            fac[j]=fac[j-1]*j%prime[i];
            inv[j]=inv[prime[i]%j]*(prime[i]-prime[i]/j)%prime[i];
        }
        for(int j=2; j<=prime[i]; j++) inv[j]=inv[j-1]*inv[j]%prime[i];

        for(int j=1; j*j<=n; j++)
        {
            if(n%j) continue;
            num[i]=(num[i]+lucas(n, j, prime[i]))%prime[i];
            if(j*j==n) continue;
            num[i]=(num[i]+lucas(n, n/j, prime[i]))%prime[i];
        }
    }
    printf("%lld\n", ksm(g, crt(), mod));
}

Posted on Edited on In

问题描述：

脸哥最近在玩一款神奇的游戏，这个游戏里有 $n $件装备，每件装备有$ m$ 个属性，用向量$z_i(a_j ,…..,a_m)$ 表示。每个装备需要花费 $ci$，现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。

如果脸哥买了 $z_{i1},…..z_{ip}$这$ p$ 件装备，那么对于任意待决定的 $z_h$，不存在 $b_1,….,b_p$ 使得 $b_1z_{i1} + … + b_pz_{ip} = z_h$（$b$ 是实数），那么脸哥就会买 $z_h$，否则 $z_h$ 对脸哥就是无用的了，自然不必购买。脸哥想要在买下最多数量的装备的情况下花最少的钱，你能帮他算一下吗？

输入：

第一行两个数 $n$，$m$。接下来$ n $行，每行 $m$ 个数，其中第$ i $行描述装备$ i $的各项属性值。 接下来一行$ n $个数，其中$ c_i $表示购买第 $i $件装备的花费。

输出：

一行两个数，第一个数表示能够购买的最多装备数量，第二个数表示在购买最多数量的装备的情况下的最小花费

思路：

题目说简单一点就是你要在一组向量中，要求出最大的线性无关子集，也就是线性基。

线性基的求法就是把$n$个向量看成是$n*m$的系数矩阵，然后进行高斯消元，剩下的非零向量就是线性基，那么最多的装备数量就是线性基的大小。但是我们还要维护它的最小花费，这时我们就可以使用贪心的策略了，可以将价格排一个序，消元时尽可能用价格低的消去其他的，这样就可以了。

这个的证明也很有趣，因为线性基是是线性无关的，如果有一个价格更低的能被它们表示，那么我们可以放进去一个价格低的，取出一个价格高的。这样，价格高的一定能被新的线性基表示，所以我们可以使用这种贪心策略。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define LB long double
#define eps 1e-6
#define MAXN 505
using namespace std;

int n, m, num, val, f[MAXN];

struct Weap {LB z[MAXN]; int val;} weap[MAXN];

bool CMP(Weap x, Weap y) {return x.val<y.val;}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) scanf("%llf", &weap[i].z[j]);
    for(int i=1; i<=n; i++) scanf("%d", &weap[i].val);

    sort(weap+1, weap+n+1, CMP);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            if(fabs(weap[i].z[j])<eps) continue;
            if(f[j]==0)
            {
                f[j]=i;
                num++; val+=weap[i].val;
                break;
            }
            else
            {
                LB rate=weap[i].z[j]/weap[f[j]].z[j];
                for(int k=j; k<=m; k++) weap[i].z[k]-=rate*weap[f[j]].z[k];
            }
        }
    printf("%d %d\n", num, val);
}