随机数基本使用方法

基本公式:

要取得[a,b)的随机整数,使用(rand() % (b-a))+ a;
要取得[a,b]的随机整数,使用(rand() % (b-a+1))+ a;
要取得(a,b]的随机整数,使用(rand() % (b-a))+ a + 1;
通用公式:a + rand() % n;其中的a是起始值,n是整数的范围。
要取得a到b之间的随机整数,另一种表示:a + (int)b * rand() / (RAND_MAX + 1)。
要取得0~1之间的浮点数,可以使用rand() / double(RAND_MAX)。

Digital Reassembly

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
import java.util.Scanner;
public class digitReassembly {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);

String s1 = input.next();
String s2 = input.next();

input.close();

int num = Integer.valueOf(s2);

while(s1.length()%num!=0)
{
s1 = s1 + "0";
}

int ans = 0;
int cnt = s1.length()/num;
int p = 0;
for(int i=0;i<cnt;i++)
{
ans += Integer.valueOf(s1.substring(p,p+num));
p = p+num;
}

System.out.println(ans);
}
}

ACSL CHMOD

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
import java.util.Scanner;

public class CHMOD
{
static String[] num = new String[4];
public static void input()
{
Scanner input = new Scanner(System.in);
String s = input.next();
int len = s.length();
int cnt = 0;
num[cnt++] = s.substring(0, 1);
for(int i=1;i<len;i++)
{
if(s.charAt(i)>='0' && s.charAt(i)<='9')
{
num[cnt++] = Integer.toBinaryString(s.charAt(i)-'0');
}
}
input.close();
}

public static void process()
{
String[] ans = new String[]{"","","",""};
for(int i=1;i<4;i++)
{
while(num[i].length()<3) num[i] = '0' + num[i];
if(num[i].charAt(0) == '1') ans[i] += 'r'; else ans[i] += '-';
if(num[i].charAt(1) == '1') ans[i] += 'w'; else ans[i] += '-';
if(num[i].charAt(2) == '1') ans[i] += 'x'; else ans[i] += '-';
}

boolean flag1,flag2,flag3;
flag1 = flag2 = flag3 = false;

if(num[0].charAt(0)=='1' && ans[1].charAt(2)=='x') flag1 = true;
if(num[0].charAt(0)=='2' && ans[2].charAt(2)=='x') flag2 = true;
if(num[0].charAt(0)=='4' && ans[3].charAt(2)=='x') flag3 = true;

for(int i=1;i<4;i++)
{
System.out.print(num[i]+" ");
}
System.out.print("and ");


if(ans[1].charAt(2)=='x' && flag1 == true)
{
System.out.print( ans[1].charAt(0) );
System.out.print( ans[1].charAt(1) );
System.out.print("s");
}
else System.out.print(ans[1]+" ");

if(ans[2].charAt(2)=='x' && flag2 == true)
{
System.out.print( ans[2].charAt(0) );
System.out.print( ans[2].charAt(1) );
System.out.print("s");
}
else System.out.print(ans[2]+" ");

if(ans[3].charAt(2)=='x' && flag3 == true)
{
System.out.print( ans[3].charAt(0) );
System.out.print( ans[3].charAt(1) );
System.out.print("t");
}
else System.out.print(ans[3]);


}


public static void main(String[] args)
{
input();
process();
}
}

/*
0,5,2,6
1,7,3,0
2,4,1,5
4,2,3,4
4,5,6,7

*/

ACSL STRING

Question


My thought


Nothing… The problem is pretty easy, however it troubled me for a quite long time. Just follow the instruction of the problem and simulate the whole process by coding.

Points to note


  • The conversion between String and int
  • How to handle carry
  • Pay attention to the additional sign
  • Sometimes we can use char to simplify the process

Code


济南Day3 坐标型动态规划及背包

花店橱窗布置


思路

  • f[i][j]f[i][j]表示前i个花瓶前j个花束的最大美学价值
  • f[i][j]=max(f[i−1][k],f[i][j])f[i][j]=max(f[i−1][k],f[i][j])

当然还有另外一种思路(太强了!!!\):

  • 整张表都是向右下方走的,向下走加上数值,向右走无影响
  • 如果向下走代表花束放入花瓶,向右走无影响代表不放入
1
2
3
4
int f[N][N],mp[N][N];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=max(f[i-1][j]+mp[i][j],f[i][j-1]);

矩阵取数


思路

  • 因为每次取头和尾,所以一定是一个连续的区间
  • f[i][j]f[i][j]表示从i取到j的最大得分
  • $f[i][j]=max(f[i][j-1]+a[j]2^(i-1+n-j+1+1) \ , \ f[i-1][j]+a[i]2^(i-1+n-j+1+1))$
  • 指数是轮数,当前数前面有多少个数被取走,就有多少轮,注意一下1的问题

传纸条


思路

  • f[i][j][k][l]f[i][j][k][l]表示现在去的到了(i,j),回来的到了(k,l)

  • 一共有四种情况,上上,左左,上左,左上

  • 保证两条路径不相交if(j1==j2 && i1==i2) continue

  • f[i][j][k][l]=max(f[i−1][j][k−1])f[i][j][k][l]=max(f[i−1][j][k−1])

  • 步数为i+j−1i+j−1

  • 判断不合法的状态

    1
    2
    if(i1+j1!=i2+j2) continue;
    if(i1==i2 && j1==j2 && i1+j1!=2 && i1+j1!=m+n) f[i1][j1][i2][j2]=-0x3f3f3f3f;
  • 当m,n<100m,n<100时,四维数组开不下了,因为i1+j1=i2+j2i1+j1=i2+j2的时候才是合法的,并且三个数都确定时,我们可以直接算出j2j2,直接变成了三维

免费馅饼


题目

地面长度为L,高度为H,天上掉馅饼

人在地上每单位时间可以向左或向右移动0~2格,馅饼每单位时间掉落一格

求最多接到多少馅饼(馅饼有分值)

思路

  • f[i][j]f[i][j]表示第i秒到达第j个格子的最大得分
  • 该状态是从哪里转移过来的呢? 他可以从5个地方转移过来(没有到边界的时候)
  • 运动具有相对性,我们可以把该问题类比成数字三角形,相当于馅饼不动,人每次向上移动一个单位
  • f[i][j]=ff[i][j]=f

三角蛋糕


思路

  • 像数字三角形一样压缩成正三角形
  • f[i][j]=min(f[i+1][j],f[i+1][j+1])+1f[i][j]=min(f[i+1][j],f[i+1][j+1])+1

金明的预算方案


思路:分组背包

  • f[i][j]f[i][j]表示前i组物品重量不超过j的最大价值
  • 一共5种转移方式
  • f[i][j]=max(f[i−1][j],f[i−1][j−w[i][k]]+v[i][k]),k=1,2,3,4,5f[i][j]=max(f[i−1][j],f[i−1][j−w[i][k]]+v[i][k]),k=1,2,3,4,5,五种情况已经重新配置的前提下

01/完全背包混合


  • 根据物品的类型选择状态转移方程

二维限制的背包


  • 把数组扩展成三维
  • f[i][j][k]=max(f[i−1][j][k],f[i−1][j−w[i]][k−v[i]]+c[i])f[i][j][k]=max(f[i−1][j][k],f[i−1][j−w[i]][k−v[i]]+c[i])

面包


题目

有N种面包,每种面包数量无限多,有高度和价值,高度是5的倍数
将面包叠成一个面包塔,高度不得超过T
给定常数k,若一个面包高度>=k,则它下面所有面包都会被压扁
一个面包最多被压扁一次,它的高度变为原来的4/5
求最大的价值

思路

  • 如果没有面包被压扁,就是一个完全背包问题
  • 如果有大面包,肯定要放到最上面,使得压缩高度尽可能大
  • 枚举最上面是哪一个大面包,然后其余所有面包的高度都变为原来的五分之四,就转化成了一半的完全背包问题

高精度模板

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
define N 1e5
struct bign
{
int len;
int v[N];

// 赋值 bign=bign
bign operator = (char* s)
{
len=strlen(s);
memset(v,0,sizeof(v));
for(int i=0;i<len;i++)
v[i]=s[len-i-1]-'0';
return *this;
}
//赋值 bign=int
bign operator = (int x)
{
char s[N];
sprintf(s,"%d",x);
return *this=s;
}

// 高精加
bign operator + (const bign &b) const
{
bign c;
memset(c.v,0,sizeof(c.v));
c.len=max(len,b.len);
for(int i=0;i<c.len;i++)
c.v[i]=v[i]+b.v[i];
for(int i=0;i<c.len;i++)
{
c.v[i+1]+=c.v[i]/10;
c.v[i]%=10;
}
if(c.v[c.len]) c.len++;
return c;
}
// 高精乘
bign operator * (const bign &b) const
{
bign c;
memset(c.v,0,sizeof(c.v));
c.len=len+b.len;
for(int i=0;i<len;i++)
for(int j=0;j<b.len;j++)
c.v[i+j]+=v[i]*b.v[j];
for(int i=0;i<len;i++)
{
c.v[i+1]=c.v[i]/10;
c.v[i]%=10;
}
while(c.len>1 && c.v[c.len-1]) c.len--;
return c;
}
// 高精加等于
bign operator += (const bign &b)
{
return *this+b;
}

// 比大小
bool operator < (const bign &b) const
{
if(len<b.len) return 1;
if(len>b.len) return 0;
for(int i=len-1;i>=0;i--)
{
if(v[i]<b.v[i]) return 1;
if(v[i]>b.v[i]) return 0;
}
return 0;//两个数相等返回flase
}

bool operator > (const bign &b) const
{
return b<*this;
}

bool operator <= (const bign &b) const
{
return !(b>*this);
}

bool operator >= (const bign &b) const
{
return !(b<*this);
}

bool operator == (const bign &b) const
{
return (b>*this)^(b<*this)
}
};

树形DP

二叉苹果树


思路

  • $dp[u][j表示节点u留下j条边的最大价值,每一次决策只有三种情况:剪左子树,剪右子树,两个都不剪
  • 剪左边:dp[u][j]=dp[rson][j−1]+v[rson]dp[u][j]=dp[rson][j−1]+v[rson],同理,剪右边:dp[u][j]=dp[lson][j−1]+v[lson]dp[u][j]=dp[lson][j−1]+v[lson]
  • 两边都不剪:dp[u][j]=dp[lson][j]+dp[rson][k−j−2]dp[u][j]=dp[lson][j]+dp[rson][k−j−2]

代码:记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int f[N][N];
bool t[N][N];
int dp(int u,int k)
{
if(t[u][k]) return f[u][k];
t[u][k]=1;
if(!k) return f[u][k]=0;
int tmp1=dp(lson[u],k-1)+v[sonl[u]];
int tmp2=dp(rson[u],k-1)+v[sonr[u]];
int tmp3=0;
for(int l=0;l<k-2;l++)
tmp3=max(tmp3,dp(lson[u],l)+dp(rson[u],k-l-2));
return f[u][k]=max(tmp1,max(tmp2,tmp3+lson[u]+rson[u]));
}

先修课


题目

课的先修关系形成一棵树的结构,每门课有一门或者没有先修课。选M门课,能获得的最大学分是多少?

思路

  • dp[u][j]dp[u][j]以u为根的子树选j门课
  • 把j-1门课分配给子树,就是一个背包?
  • 然后我们用f[i][j]f[i][j]表示当前树中,前i棵子树选择j门课的最大学分。这样就能够通过f算出dp[i][j]dp[i][j],相当于树上DP套背包。对于每一个状态dp[i][j]dp[i][j]都需要用f算出学分分配的最佳方案

K-set


题目

在一棵树中选出最多的点,使得这些点中每个点最多与其他点连了k条边

思路

  • dp[u][0/1][0/1]dp[u][0/1][0/1]表示以u为父亲,取/不取父亲,取/不取自己的最大值

  • dp[u][0][0]dp[u][0][0]:自己和父亲都不取,u的儿子随便取。$f[u][0][0]=size∑i=1max( dp(vi,0,0) , dp(vi,0,1) )f[u][0][0]=∑i=1sizemax( dp(vi,0,0) , dp(vi,0,1) )$

  • dp[u][1][0]dp[u][1][0]:父亲要取,u自己不取,u的儿子同样随便取。f[u][1][0]=f[u][0][0]f[u][1][0]=f[u][0][0]

  • dp[u][1][1]dp[u][1][1]

    :父亲要取,自己也要取,儿子取k-1条边。

    • 这时我们就要考虑取哪几条边,也就是哪几个点。
    • 对于任意一个u的儿子vivi,如果取这个点,那么它的贡献就是dp(vi,1,1)dp(vi,1,1),如果不取这个点,那么它的贡献就是dp(vi,1,0)dp(vi,1,0)
    • 因此这个点取或者不取,带来的贡献就是两种情况的差,所以我们只要按两种情况的差从大到小排序就好了。最后选取差值最大的k-1个点就OK了(前提是这k-1个点带来的贡献都是正的,如果有负贡献那么就取不满k-1个点)
  • dp[u][0][1]dp[u][0][1]:父亲不取,自己要取,儿子取k条边

四子连棋

这是我到目前为止写过最长的代码之一……


题意

44的棋盘,一共有三种属性:白棋,黑棋,空格(有且仅有两个),每一次可以移动一颗棋子,*黑白棋交替进行,只能移到空格的地方。求达成四子连棋局面(横竖斜都算**)所需的最小步数

分析

  • 广搜,和八数码问题差不多,但是更繁琐了。
  • 黑白棋交替进行,那么我们需要在搜索的时候除了当前地图和步数还需要保存当前该哪一方行棋
  • 广搜要搜两遍,分别是黑棋先走或白棋先走
  • 每一次需要考虑两个空格,所以从两个当前点搜状态

遇到的坑

  • 很多都是重复的代码,只要细心就好了,但有一个最坑的……\

  • 黑棋先走和白棋先走走到的棋局相同的情况也是两种情况,不能判重删去!!!

STL

STL

C++ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组,list封装了链表,map和set封装了二叉树等,在封装这些数据结构的时候,STL按照程序员的使用习惯,以成员函数方式提供的常用操作,如:插入、排序、删除、查找等。让用户在STL使用过程中,并不会感到陌生。

迭代器

1
2
set<int>::iterator it_set//一个set<int>类型的迭代器
map<string,int>::iterator it_map//一个map<string,int>类型的迭代器

SET

set的各成员函数列表

  1. begin()–返回指向第一个元素的迭代器
  2. clear()–清除所有元素
  3. count()–返回某个值元素的个数
  4. empty()–如果集合为空,返回true
  5. end()–返回指向最后一个元素的迭代器
  6. equal_range()–返回集合中与给定值相等的上下限的两个迭代器
  7. erase()–删除集合中的元素
  8. find()–返回一个指向被查找到元素的迭代器
  9. get_allocator()–返回集合的分配器
  10. insert()–在集合中插入元素
  11. lower_bound()–返回指向大于(或等于)某值的第一个元素的迭代器
  12. key_comp()–返回一个用于元素间值比较的函数
  13. max_size()–返回集合能容纳的元素的最大限值
  14. rbegin()–返回指向集合中最后一个元素的反向迭代器
  15. rend()–返回指向集合中第一个元素的反向迭代器
  16. size()–集合中元素的数目
  17. swap()–交换两个集合变量
  18. upper_bound()–返回大于某个值元素的迭代器
  19. value_comp()–返回一个用于比较元素间的值的函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#include <set>

using namespace std;
set<int> s;
set<int>::iterator it_set;

int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int tmp;
scanf("%d",&tmp);
s.insert(tmp);
}
for(it_set=s.begin();it_set!=s.end();it_set++)
{
printf("%d\n",*it_set);
}
return 0;
}

链接

容器set和multiset

三角形牧场

P1284三角形牧场


题意

现在有n段木棍,全部使用组成三角形的三条边,使三角形的面积最大

分析

  • 首先看数据范围,边长最大为40*40/3,并且因为要使用所有的木棍,所以只要两条边确定就可以知道第三条边的确定长度。因此我们可以设状态f[i][j]表示三角形的两条边分别是i,j的情况是否成立

  • f[i][j]=f[i−a[k]][j] || f[i][j−a[k]] || f[i][j]f[i][j]=f[i−a[k]][j] || f[i][j−a[k]] || f[i][j],相当于01背包,就不解释了……

  • 定义初始状态f[0][0]=1f[0][0]=1

  • 三条边都知道了,如何求面积呢?这里我们需要用到海伦公式

    S=√p(p−a)(p−b)(p−c)S=p(p−a)(p−b)(p−c),p=12(a+b+c)p=12(a+b+c)

遇到的坑

好像没有什么

P1929 迷之阶梯

真的好坑,做了一下午……

题意

登上阶梯必须要按照它要求的方法, 否则就无法登上阶梯。它要求的方法有以下三个限制:

  1. 如果下一步阶梯的高度只比当前阶梯高 1,则可以直接登上。
  2. 除了第一步阶梯外,都可以从当前阶梯退到前一步阶梯。
  3. 当你连续退下 k 后,你可以一次跳上不超过当前阶梯高度 2^{k}2k的阶梯。比如说你现 在位于第 j 步阶梯,并且是从第 j+k 步阶梯退下来的,那么你可以跳到高度不超过当前阶 梯高度+2^{k}2k的任何一步阶梯。跳跃这一次只算一次移动。

开始时我们在第一步阶梯,由于时间紧迫,我们需要用最少的移动次数登上迷之阶梯。 请你计算出最少的移动步数。

分析

  • 定义状态为f[i]表示到第i个阶梯的最小步数
  • 由2可以直接得出if(h[i]==h[i-1]+1) f[i]=f[i-1]+1

遇到的坑

  • if(f[n]>=0x3f3f3f3f) f[n]=-1;在状态转移的过程中有可能比初始值更大,所以是大于等于
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×