2018 Multi-University Training hdu Contest 2

Posted on | In , | Visitors:

嚯嚯嚯！补题！

hdu多校总链接

补题：6题/10题

  • 博弈论
  • 逆序对
  • 线段树
  • 树状数组

C. Cover

给一个无向图，求用最小的一笔画次数，覆盖整个图，输出边的编号，如果一笔画的过程，走某条边的顺序与题意给的顺序相反，输出负的边编号。

用fleury算法求路径。先绘制连通图，再跑dfs，如果这条边被选择，则下次回到这个点，就不可再访问这条边了！

几个理解的数据，首先是有环的；第二是增加奇数点的边的时候，将两个联通块联通了；动手想一遍，就会迎刃而解哒！

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1e5+10;
const int maxx=4e5+10;
struct Edge{
    int v,val;//下一个点，边的标号
    bool flag;//标记是否已经访问过了
    Edge* nex;//一个顶点出来的边的链
    Edge* rev;//无向边两个方向的关连
}e[maxx],*head[maxn],*now;
int n,m,cnt;
int b[maxn];//每个点的度数
bool node[maxn];//标记这个点是否已经考虑过了
vector<int>ans[maxn];//每个联通块的路径
void _add(int u,int v,int val){
    now->v=v;now->val=val;
    now->nex=head[u];head[u]=now;
    now++;
}
void add(int u,int v,int val){
    _add(u, v, val);
    _add(v, u, -val);
    head[u]->rev=head[v];
    head[v]->rev=head[u];
}
void dfs(int x){
    node[x]=true;
    for(Edge* i=head[x];i;i=i->nex){
        if(!i->flag){
            i->flag=(i->rev)->flag=true;
            dfs(i->v);
            if(i->val==0){
                ++cnt;
            }else{
                ans[cnt].push_back(-(i->val));
            }
        }
    }
}
void init(){
    memset(e,0,sizeof(e));
    memset(head,0,sizeof(head));
    now=e;
    memset(b,0,sizeof(b));
    memset(node,0,sizeof(node));
    cnt=0;
    for(int i=0;i<maxn;i++)
        ans[i].clear();
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        init();
        int x,y;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            add(x, y, i);
            b[x]++;b[y]++;
        }
        
        //增加奇数点的路径
        x=0;
        for(int i=1;i<=n;i++){
            if(b[i]&1){
                if(x){
                    add(x, i, 0);
                    x=0;
                }else{
                    x=i;
                }
            }
        }
        
        for(int i=1;i<=n;i++){
            if(!node[i]&&(b[i]&1)){
                dfs(i);
            }
        }
        
        for(int i=1;i<=n;i++){
            if(!node[i]&&b[i]){
                dfs(i);
                cnt++;
            }
        }
        
        printf("%d\n",cnt);
        for(int i=0;i<cnt;i++){
            int len=ans[i].size();
            printf("%d ",len);
            for(int j=0;j<len-1;j++){
                printf("%d ",ans[i][j]);
            }
            printf("%d\n",ans[i][len-1]);
        }
    }
    return 0;
}

D. Game

博弈论的题目，感觉就像是在玩游戏一样，所以一定要胜利啊！

这里呢，我们要先理解题目，不过被我蒙对了（其实是我英语太弱的缘故）

我们发现每个数的因子都有1，所以我们先考虑没有1的情况下，如果Alice，能赢，那么她必赢！

如果不可以赢，那么第一局的时候Alice先拿掉1，于是她又将战局转化了

这是第一次见到必赢局的博弈论（刷题少，不怪我！不怪我！不怪我！）

代码就不贴了吧，好傻的呢！

E. Hack It

看题解了，（因为过的人少

可以推广到完全平方的情况，但是sqrt(n)必须是素数，暂且以16来说明！

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
n=25时情况
10000 10000 10000 10000 10000 每一列退0个
10000 01000 00100 00010 00001 每一列退1个
10000 00100 00001 01000 00010 每一列退2个
10000 00010 01000 00001 00100 每一列退3个
10000 00001 00010 00100 01000 每一列退4个
01000 01000 01000 01000 01000 
01000 00100 00010 00001 10000 
01000 00010 10000 00100 00001 
01000 00001 00100 10000 00010 
01000 10000 00001 00010 00100
00100 00100 00100 00100 00100 
00100 00010 00001 10000 01000 
00100 00001 01000 00010 10000 
00100 10000 00010 01000 00001 
00100 01000 10000 00001 00010
00010 00010 00010 00010 00010 
00010 00001 10000 01000 00100 
00010 10000 00100 00001 01000 
00010 01000 00001 00100 10000 
00010 00100 01000 10000 00001
00001 00001 00001 00001 00001 
00001 10000 01000 00100 00010 
00001 01000 00010 10000 00100 
00001 00100 10000 00010 01000 
00001 00010 00100 01000 10000
n=16
1000 1000 1000 1000
1000 0100 0010 0001
1000 0010 1000 我们可以看到这里就不可以了吧！
其实可以马上想到，这里退的必须不可以是它的倍数，否则会回到原来的样子的！

然后我们可以知道1的个数不可以少于85000，那就索性用n的最大值好啦！省的计算了！

于是sqrt(2000) 最接近的质数是47 ，然后就可以码代码了！

网上都是代码，不想复制粘贴！

F. Matrix

首先我们先考虑行，因为行列对称，所以之后可以很好的扩展

其中我们令行的容斥系数为$fa[i]$，首先我们确定行数i，之后我们从n行中选择i行，并且对于剩下的行数我们可以黑也可以白，于是我们得到如下式子：

$\displaystyle ans=\sum^{n}_{i=a}(fa[i]C_n^i2^{n-i})$

对于一个小于j的数k，则在j的答案中，一定包含了“至少k行被染色”的答案，相当于是我在确定染色的j行中选择k行，然后再乘上容斥系数$fa[k]$。

$C^k_j*fa[k]$

所以有$\displaystyle fa[j]=1-\sum^{j-1}_{k=a}(C^k_j*fa[k])$

因此我先将fa,fb处理出来

之后用公式

$\displaystyle ans=\sum^{n}_{i=a}\sum^{m}_{j=b}(fa[i]fb[j]C_n^iC_m^j2^{n-i}*2^{m-j})$

不过若是代码写的不好看，就很容易超时，明明最多3000*3000*3=2.7e7，多组数据不是1e8么？？？？？

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
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=3000+10;
const ll mod=998244353;
int c[maxn][maxn];
int p[maxn*maxn];
int fa[maxn],fb[maxn];
int n,m,a,b;
int i,j,k;
void init(){
    for (i=0;i<maxn;i++) c[i][0]=1;
    for (i=1;i<=3000;i++){
        for (j=1;j<=i;j++){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
    p[0]=1;
    for (i=1;i<maxn*maxn;i++)
        p[i]=(ll)p[i-1]*2%mod;
}
int main(){
    init();
    while (scanf("%d%d%d%d",&n,&m,&a,&b)!=EOF){
        ll ans=0;
        for (i=a;i<=n;i++){
            fa[i]=1;
            for (k=a;k<=i-1;k++){
                fa[i]=((fa[i]-(ll)c[i][k]*fa[k])%mod+mod)%mod;
            }
        }
        for (j=b;j<=m;j++){
            fb[j]=1;
            for (k=b;k<=j-1;k++){
                fb[j]=((fb[j]-(ll)c[j][k]*fb[k])%mod+mod)%mod;
            }
        }
        ll tmp;
        for (i=a;i<=n;i++){
            tmp=(ll)fa[i]*c[n][i]%mod;
            for (j=b;j<=m;j++){
                ans=(ans+tmp*fb[j]%mod*c[m][j]%mod*p[(n-i)*(m-j)]%mod)%mod;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

G. Navie Operations

一看题目，就知道是线段树了！想要呼唤博博码代码，emmm……

真是奇了怪了，再嘟囔一下我和线段树的爱恨离愁！貌似还因为线段树和某人吵过冷架！

因为向下取整，对于每次更新，对区间是不一定影响的！只有当等于b的时候，才会使答案修正！修正过后，再将a赋值为零！相当于a是小数部分！

但是网上的题解都是反过来想的，不明白为什么，是不好实现么！

把bi放入对应节点，维护区间最小值，当最小值减到0时就再用线段维护一个答案，使得答案+1，并且重新给该节点赋值bi

不管啦，思路正确就ok啦！

所以，没有代码的呢！

当然也可以用树状数组啦！

J. Swaps and Inversions

首先这题还是题目的理解，好吧，我单词不认识，对于x的情况，是不符合原位置的数进行罚款呢？（其实应该只有我理解有误的吧！逆序对，一般都是这么说的啊！好像没有逆序数的吧！

那么对于y的，每一次和相邻位置进行调换所需要的花费，其实也是逆序对。

于是只需要求逆序对将其乘上min(x,y)

发现我之前的逆序对模版的离散化有点问题，郁闷！

难道我没有测试么！

好吧，反正现在模版优化了，很开心啦！

其实我不懂树状数组的，背下来就好啦！反正可以拿板子的么！

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
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int reflect[maxn];//离散化数组
struct type{
    int tree[maxn];//树状数组
    int lowbit(int x){
        return x&(-x);
    }
    void updata(int x,int value){
        while(x<=maxn){
            tree[x]+=value;
            x+=lowbit(x);
        }
    }
    int getsum(int x){
        int temp=0;
        while(x>0){
            temp+=tree[x];
            x-=lowbit(x);
        }
        return temp;
    }
}ty;
//点
struct Node{
    int v;
    int order;
}in[maxn];
bool cmp(Node a,Node b){
    return a.v<b.v;
}
int main() {
    int n,x,y;
    while(scanf("%d%d%d",&n,&x,&y)!=EOF){
        //离散化
        for(int i=1;i<=n;i++){
            scanf("%d",&in[i].v);
            in[i].order=i;
        }
        sort(in+1,in+n+1,cmp);
        int now=1;
        reflect[in[1].order]=1;
        for(int i=2;i<=n;i++){
            if(in[i].v!=in[i-1].v)now++;
            reflect[in[i].order]=now;
        }
        //利用树状数组求逆
        memset(ty.tree, 0, sizeof(ty.tree));
        ll ans=0;
        for(int i=1;i<=n;i++){
            ty.updata(reflect[i], 1);
            ans+=i-ty.getsum(reflect[i]);
        }
        ans=ans*min(x,y);
        printf("%lld\n",ans);
    }
    return 0;
}

碎碎念

2018.08.09 晚

西安的天气好可怕啊！每晚下雨就算了，能否温柔一些！

这风！这雨！感觉是因为今天提前走的原因呢！

刚补完cf的那套题，后面不想写了！对于选择语言的问题，踩了好多坑，果然自己会有很多细节不懂！继续补题啊！

补题！补题！补题！

2018.08.10 晚

我凡出新歌了，但我好像觉得不怎么好听

唔……我怕是真的是个假粉呢！

郁闷！

一只像知了那样会叫的超大的虫子被飞了进来，起因又是一个悲惨的故事：

我的一盆小花花翘翘了，然后感觉像是被压死的，可是我没有压它呀！然后就可能是被闷死的，渴死的，缺少太阳死的！于是，我就想把它放出去。

然后他就飞蛾扑火，一直乱叫，然后我也叫了，可是它叫的比我更恐怖！为了不被大晚上的吃掉，于是我决定，哼！大战虫子！

然后我就把灯光了，拿着所有的手电筒，结果它傻了，不来咬我！还找不到它在哪里；再开灯也没看到。于是乎，东抖抖，西抖抖；东敲敲，西敲敲；啊！出现了！

可是它又在灯那里乱叫；但是咋么办呢！打一下它，够不着；挥一下它，落荒而逃；

看到一扇窗户，打开窗，放入壁咚灯！

它还是很蠢！再次打它！窗户上！再打！出去了！

呼！cx大战虫子！胜！回合N次；时长 1小时！

所以我的花花回不了家了；希望明天太阳不要太大，不要刮风，下暴雨！

最后，百度上说，知了只是迷路了，它只能活一两个月，珍惜吧！

哎，累了！又是累累的一天！

晚安！

2018.08.18 日

百度之星，所以又没法提交了

睡了一觉，也许是因为空调的原因，昏昏沉沉的

很多时候，事与愿违，计划真的永远赶不上变化

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽