Digital Reassembly

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);
}
}
Read More
ACSL CHMOD

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

*/
Read More
ACSL STRING

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 t
Read More

济南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]);

矩阵取数


思路

Read More

高精度模板

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)
}
};
Read More

树形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门课,能获得的最大学分是多少?

Read More

随机数基本使用方法

基本公式:

要取得[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)。

Read More