比赛链接

https://www.51nod.com/contest/problemList.html#!contestId=72&randomCode=147206

这次考试的题非常有质量

这次考试暴露了非常多的问题，心理给自己设限，知识点不熟练等等问题。

只拿了暴力的分。

奈芙莲的护符

Nephren 有n个护符，每个护符的魔力容量都是无限的，并且每个护符在初始时已经被倾注了一些魔力。Nephren想要获得里面所有的魔力，但是她最后只能选择k个护符吸收。

所以，她需要将一些护符的魔力融合到一起。但是把i号护符的魔力移动到j号杯子需要花费c[i][j]的体力。

所以请您求出最小花费的体力。

【数据范围】

40%的数据保证n<=10。

100%的数据保证1≤ k≤ n ≤ 20

所有的c[i][j]<=100000,c[i][i]=0.

Input
第一行，输入n，k

下面N行，每行N个整数，描述c[i][j].
Output
输入一个整数，即所需的最小体力值。
Input示例
3 3 

0 1 1 

1 0 1 

1 1 0
Output示例
0






这道题复习状压dp，状压dp一般可以处理一个集合内的问题


这道题是第三题，但我放在这一题


因为这一题反而最水……


我当时一看到数据范围20，马上想到状压dp


但是一方面因为觉得这是第三题，应该会比较难，而且前面两道题都做不出来，所以心理障碍


很大，就没有怎么很深入的去想（不过说到底还是状压dp不熟练）。


考完后，5分钟秒了，发现这是我做过最水的状压dp题。


这道题和TSP问题很类似（不懂的可以百度一下，或者我博客里面有）


用1表示魔力还在，0表示没有了。


那么dp[S] = min(dp[S], dp[S^(1<<j)] + c[j][i])




#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int MAXM = ( << ) + ;

const int MAXN = ;

int c[MAXN][MAXN], dp[MAXM];

int num(int x) { return !x ?  :  + num(x & (x - )); } //二进制中1的个数 

int main()

{

    int n, k;

    scanf("%d%d", &n, &k);

    REP(i, , n)

        REP(j, , n)

            scanf("%d", &c[i][j]);

    int ans = 1e9;

    memset(dp, 0x3f, sizeof(dp)); //这里初始化要注意

    dp[(<<n)-] = ;

    for(register int S = ( << n) - ; S >= ; S--)

    {

        if(num(S) < k) continue;

        REP(i, , n) if(S & ( << i))

            REP(j, , n) if(!(S & ( << j)))

                dp[S] = min(dp[S], dp[S^(<<j)] + c[j][i]);

        if(num(S) == k) ans = min(ans, dp[S]);

    }

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

    return ;

}




珂朵莉的旅行




浮游大陆由n个浮游岛构成，其中不同的浮游岛之间存在着飞艇航线。


由于浮游大陆的经济比较紧张，花在交通的费用不能太多，因此在保证每一个浮游岛都是联通的基础上，大贤者只修筑了n-1条航线。


在击败第五号岛的兽之后，威廉决定带辛苦战斗的珂朵莉，奈芙莲，艾瑟雅去浮游大陆旅行。


“Are you going toScarborough Fair?”


每个浮游岛本质属于不同的政体，所以它们的政策等会存在诸多差异。在旅行之前，威廉将浮游岛划分成两种，可以认为权值为1和0.由于要保证这是一次开心的旅行，所以他希望旅行之后经过的路径浮游岛的权值异或和为0.


他们的旅行方案是这样的：从某一个节点开始，不经过重复的节点，随机的选择一个与当前节点相连的节点，直到走到无路可走，这算完成一次旅行。


由于威廉也才来到浮游大陆不久，所以他也不知道每一个节点的权值到底是1还是0.


他想问问你，总共有多少种可能的钦点某些浮游岛的权值为1（其他浮游岛权值为0）的方式，符合上文提出的条件？


由于他们没有学过数学，因此请你将答案对 109+7 （一个质数）取模。



【数据规模和约定】




对于20%的数据，满足1<=n<=10


对于40%的数据，满足1<=n<=1000


对于额外20%的数据，浮游岛的连接将会成为一条链。


对于100%的数据，1<=n<=10^6.


【样例解释】


如果威廉选择从1号浮游岛出发，那么可以设置0个或者2个浮游岛权值为1，因此共有4种可能。如果威廉选择从2号浮游岛出发，他可以走2-1,或者2-3,因此他可以设置0个浮游岛权值为1，或者三个浮游岛权值全部为1.从3出发和从1出发情况类似，因此共有4+2+4=10种方案。








Input


第一行一个整数n，表示浮游岛的数量

第二行开始每行两个整数u,v，表示浮游岛u和浮游岛v有无向的飞艇路线相连。


Output


一行一个整数，表示答案。


Input示例


3

1 2

2 3


Output示例


10




关于异或和，如果1的个数是偶数，那就是0，如果是奇数，就是1，和0取异或就不变，和1取异或就取反
n方的数据可以用树形dp过
我考试的时候dp方程都推出来了，可是竟然没有写，觉得是错的（我到底在干嘛？？？）（树形dp不熟练）
dp[i][0]表示从子树到子树根的路径异或和0的方案数，dp[i][1]是异或和为1
如果是dp[i][0]
如果根为1，那么除根以外的路径就要异或和为1，同时根据乘法原理，
方案数是dp[v1][1] * dp[v2][1]……
如果根为0，那么除根以外的路径就要异或和为0，同时根据乘法原理，
方案数是dp[v1][1] * dp[v2][1]……
然后根据加法原理，把这两个加起来
所以dp[i][0] = （dp[v1][1] * dp[v2][1]……）+（dp[v1][1] * dp[v2][1]……） 
dp[i][1]也类似，然后可以发现是一样的
dp[i][1] = （dp[v1][1] * dp[v2][1]……）+（dp[v1][1] * dp[v2][1]……）

但是不知道为什么只过了2个点，会RE2个点




#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + ;

const int mod = 1e9 + ;

struct Edge{ int to, next; };

Edge e[MAXN << ];

int head[MAXN], tot;

int d[MAXN], n;

ll dp[MAXN][];

void read(int& x)

{

    int f = ; x = ; char ch = getchar();

    while(!isdigit(ch)) { if(ch == '-') f = -; ch = getchar(); }

    while(isdigit(ch)) { x = x *  + ch - ''; ch = getchar(); }

    x *= f;

}

void AddEdge(int from, int to)

{

    e[tot] = Edge{to, head[from]};

    head[from] = tot++;

}

void dfs(int u, int fa)

{

    if(d[u] ==  && fa != -)

    {

        dp[u][] = dp[u][] = ;

        return;

    }

    ll a = , b = ;

    for(int i = head[u]; ~i; i = e[i].next)

    {

        int v = e[i].to;

        if(v == fa) continue;

        dfs(v, u);

        a = a * dp[v][] % mod;

        b = b * dp[v][] % mod;

    }

    dp[u][] = (dp[u][] + a + b) % mod;

    dp[u][] = (dp[u][] + a + b) % mod;

}

int main()

{

    read(n);

    if(n == ) { puts(""); return ; }

    memset(head, -, sizeof(head)); tot = ;

    REP(i, , n)

    {

        int u, v;

        read(u); read(v);

        AddEdge(u, v); AddEdge(v, u);

        d[u]++; d[v]++;

    }

    ll ans = ;

    _for(i, , n)

    {

        memset(dp, , sizeof(dp));

        dfs(i, -);

        ans = (ans + dp[i][]) % mod;

    }

    printf("%lld\n", ans);

    return ;

}




然后我考虑20分一条链的做法
其实这个部分分的做法再拓展一下就是满分做法了
0-0-0-0-0-……0-0-0-0-0
这是一条链
我们分两部分来考虑，端点和除了端点以外的点

如果是除了端点以外的点
0-0-0-0-0-……0-0-0-0-0
设总的点数为n，那么这样的点有n-2个
考虑其中一个点
中间n-2个点的方案有2^(n-2)个
对于其中一种方案
其中一个点到端点之前的一个点的异或和是确定的
那么端点的权值就是被动确定的
比如从当前点到端点之前的一个点的异或和为0
那么端点只能赋值为0，因为总的异或和为0
所以端点的值是被动确定的。
因此对于每一种方案，都可以通过调整端点的值来使得异或和
为0，且端点只有一种取值
也就是说，2^(n-2)全部成立
那么这只是对于其中一个点，那么对于n-2个点
就有（n-2）*2^(n-2)种方案

如果是端点
分析方法类似
对于其中一个端点，其他的点有2^(n-1)种方案
端点本身被动确定
那么有2个端点，也就是2*2^(n-1)方案

最后加起来就好了
2*2^(n-1) + （n-2）*2^(n-2)
= 2^(n-2) * (n+2)

这就是20分的做法。
其实我没想出来主要思维能力没有达到，还需要多做题

100分的做法只是把端点的数变成叶子的数罢了
推理的方式很像，把2（2个端点）换成k（k个叶子）就好了
所以答案为2^(n-k) * (n+k)
读者可以自己推一遍（我懒）

最后注意要特判一下n=1的情况，有点坑




#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + ;

const int mod = 1e9 + ;

int d[MAXN], n;

void read(int& x)

{

    int f = ; x = ; char ch = getchar();

    while(!isdigit(ch)) { if(ch == '-') f = -; ch = getchar(); }

    while(isdigit(ch)) { x = x *  + ch - ''; ch = getchar(); }

    x *= f;

}

ll pow(ll a, int b)

{

    ll res =  % mod; a %= mod;

    for(; b; b >>= )

    {

        if(b & ) res = res * a % mod;

        a = a * a % mod;

    }

    return res;

}

int main()

{

    read(n);

    if(n == ) { puts(""); return ; }

    REP(i, , n)

    {

        int u, v;

        read(u); read(v);

        d[u]++; d[v]++;

    }

    int k = ;

    _for(i, , n)

        if(d[i] == )

            k++;

    ll ans = ;

    ans = pow(ans, n - k);

    ans = ans * (n + k) % mod;

    printf("%lld\n", ans);

    return ;

}




奈芙莲的序列




有一天可爱的Nephren得到了一个序列，一开始，她取出序列的第一个数，形成一个新的序列B，然后取出序列A的第二个数，放在序列B的最左边或最右边，序列B此时有两个数，下一步，再取出序列A的第三个数放在序列B的最左边或最右边，……


现在的问题是，通过上面的步骤，可以得到B的最长上升子序列的长度是多少


【数据规模及约定】




30%的数据保证N<=20


50%的数据保证N<=1000


100%的数据保证1 ≤ N ≤  2×105


保证a序列所有数不会超过 109










Input


第一行，一个整数N.

第二行，N个整数，表示序列A。


Output


一行一个整数，表示最长上升子序列的长度


Input示例


4

2 1 3 4


Output示例


4





这道题的关键就是要推出一个性质，同时会用树状数组求LIS（二分的方法不行）
什么性质呢？
我们自己多造几组数据来算可以发现（然而我考试的时候并没有发现）
新生成的b序列的最长上升子序列的长度>=a序列的最长上升子序列长度（我们要考虑原序列和新序列的关系）
比如样例 2 1 3 4
如果一直放最右边，那么生成的序列和原来一样
那么我们可以通过某种策略来使新序列答案更大
对于这道题，可以
2
1 2
1 2 3
1 2 3 4
那么这种策略是什么呢，这是这道题的关键
拿样例来看，为什么新生成序列答案更大
答案中比原来序列的最长上升子序列多了一个1
这个1怎么来的。
原序列中在2的右边，然后放到2的左边来的。
1满足在2的右边，又比2小
最长下降子序列？？？
那么我们是不是可以猜一下
新序列的最长上升子序列等于以a[i]为起始的最长上升子序列+a[i]为起始的最长下降子序列-1（多算了一次a[i]）
我们这么想
先说最长上升子序列，我们可以把这一部分的数从左到右一直放到最右边，那么这一部分的数就是有效的
然后是最长下降子序列，我们可以把这一部分的数从左到右一直放到最左边，那么这一部分的数也是是有效的

比如 6 5 4 3 7 8 9
那么就是
6
5 6
4 5 6
3 4 5 6
3 4 5 6 7
3 4 5 6 7 8
3 4 5 6 7 8 9
这个数据可能有点水，但是就算最长上升子序列和最长下降子序列有交叉，也是成立的。
遇到了最长上升子序列中的数，就放最右边，下降就最左，其他的数无所谓
那么上面那个结论就成立了，也就是新序列的最长上升子序列等于以a[i]为起始的最长上升子序列+a[i]为起始的最长下降子序列-1（多算了一次a[i]）
那么枚举a[i]求max就好了。

那么这两个数组怎么求呢
可以n方暴力，拿50分
100分要用树状数组
不知道怎么用树状数组优化到nlogn的同学可以看我写的这篇博客
https://www.cnblogs.com/sugewud/p/9823222.html

然后这里有个细节，就是求最长上升的时候
把a[i]变成-a[i]
但是下标要>=1
所以改成m - a[i] + 1（m为离散化后最大的数值）
但是因为是严格上升，加入的时候要写成m - a[i] + 0
这个时候下标就会为0了
所以改成m - a[i] + 2， 加入的时候写m - a[i] + 1






#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 2e5 + ;

int a[MAXN], b[MAXN], n, m;

int dp[MAXN][], f[MAXN];

inline lowbit(int x) { return x & (-x); }

void motify(int x, int p)

{

    for(; x <= m + ; x += lowbit(x))

        f[x] = max(f[x], p);

}

int get_max(int x)

{

    int res = ;

    for(; x; x -= lowbit(x))

        res = max(res, f[x]);

    return res;

}

int main()

{

    scanf("%d", &n);

    _for(i, , n) scanf("%d", &a[i]), b[i] = a[i];

    sort(b + , b + n + );

    m = unique(b + , b + n + ) - b - ;

    _for(i, , n) a[i] = lower_bound(b + , b + m + , a[i]) - b;

    for(register int i = n; i >= ; i--)

    {

        dp[i][] = get_max(m - a[i] + ) + ;

        motify(m - a[i] + , dp[i][]);

    }

    memset(f, , sizeof(f));

    for(register int i = n; i >= ; i--)

    {

        dp[i][] = get_max(a[i] - ) + ;

        motify(a[i], dp[i][]);

    }

    int ans = ;

    _for(i, , n)

        ans = max(ans, dp[i][] + dp[i][] - );

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

    return ;

}





总结：收货还是蛮大的
T1 思维方式+复习树形dp
T2 手算样例找规律猜结论+学会树状数组求LIS
T3 复习状压dp













												


																

最新文章
	

    
						
  1. Css-深入学习之弧形切角矩形
		
    2. 
						
  2. Redis有序集合Zset（sorted set）
		
    3. 
						
  3. 微信公众平台中的openid是什么?
		
    4. 
						
  4. 解决安装sql server  需要重启问题
		
    5. 
						
  5. VS - 实用技巧
		
    6. 
						
  6. js中typeof可以准确判断哪些变量类型
		
    7. 
						
  7. eclipse创建多模块maven工程小结
		
    8. 
						
  8. .NET事件的指导原则
		
    9. 
						
  9. INTELLIJ IDEA集成CHECKSTYLE（转）
		
    10. 
						
  10. ubuntu通过tnvm安装Nodejs
		
    11. 
						
  11. 掌握这些知识，你的python水平能更上一层楼（续）
		
    12. 
						
  12. hdu 4533 线段树(问题转化+)
		
    13. 
						
  13. ASP.NET WebApi 自带Json返回日期带T无法格式化的问题
		
    14. 
						
  14. 很好的sql多表
		
    15. 
						
  15. windows的消息传递--消息盒子
		
    16. 
						
  16. 《算法》第四章部分程序 part 19
		
    17. 
						
  17. ubuntu安装vmare tools
		
    18. 
						
  18. Spark记录-spark与storm比对与选型（转载）
		
    19. 
						
  19. 安装ubuntu16.04系统后没有无线网络选项的解决方法
		
    20. 
						
  20. dedecms如何快速删除跳转的文章(记得清空内容回收站)
		
    21. 
		

	


热门文章
	

    
									
  1. bzoj1085 [SCOI2005]骑士精神——IDA*
			
    2. 
						
  2. SVN 打补丁 Apply Patch ***
			
    3. 
						
  3. JSP-Runood：Eclipse JSP/Servlet 环境搭建
			
    4. 
						
  4. 疫情控制  2012年NOIP全国联赛提高组(二分答案+贪心)
			
    5. 
						
  5. python自动化学习笔记10-数据驱动DDT与yml的应用
			
    6. 
						
  6. 2017杭电多校第五场Rikka with Subset
			
    7. 
						
  7. C#和Java在语法上的差异（原创，持续更新中）
			
    8. 
						
  8. Python 设计模式--策略模式
			
    9. 
						
  9. [ CQOI 2014 ] 数三角形
			
    10. 
						
  10. Position属性四个值：static、fixed、absolute和relative的区别
			
    11.