ACSL Diff


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

public class Diff {
static String s1,s2;
static String[] word1;
static String[] word2;

static void input() {
Scanner input = new Scanner(System.in);
s1 = input.nextLine();
s2 = input.nextLine();
int len1 = s1.length();
int len2 = s2.length();

// for(int i=0;i<word1.length;i++) System.out.println(word1[i]);
}

static String process(String A, String B)
{
String common="";
word1 = A.split(" ");
word2 = B.split(" ");
int len1 = word1.length;
int len2 = word2.length;
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
int pos = word2[j].indexOf(word1[i]);
if(pos!=-1)
{
word2[j] = word2[j].substring(0,pos) + word2[j].substring(pos+word1[i].length());
common = common + word1[i];
break;
}
}
}
return common;
}

static String declan(String c1, String c2)
{
String ans="";
int len1 = c1.length();
for(int i=0;i<len1;i++)
{
String tmp = c1.substring(i, i+1);

int pos = c2.indexOf(tmp);
if(pos==-1) continue;
ans = ans + tmp;

c2 = c2.substring(pos+1);
}
return (ans=="")?("NONE"):(ans);
}

public static void main(String[] args)
{
for(int i=0;i<5;i++)
{
System.out.println("Please enter No."+(i+1)+" line of the input data:");
input();
String common1 = process(s1,s2);
String common2 = process(s2,s1);
System.out.println("The answer to No."+(i+1)+"line is:");
System.out.println(declan(common1,common2));
// System.out.println(common1);
// System.out.println(common2);
}
System.out.println("All output done...");
System.out.println("Thanks for your testing");

// return;
}
}
/*
The quick brown fox did jump over a log
The brown rabbit quickly did outjump the fox
How much wood would a woodchuck chuck if a woodchuck could
chuck wood He would chuck as much wood as a woodchuck could
I scream you scream we all scream for ice cream
He screams she screams they all scream for a creamery
A skunk sat on a stump and thunk the stump stunk
but the stump thunk the skunk stunk
I have got a date at a quarter to eight
I will see you at the gate so do not be late

abc defgh ijkl mnopq rstuv wxyz
ab cdefgh ijklmn opq rst uv w xy z
*/

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

*/

My first Arduino Project

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


Data Structure

ArrayList


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// the data type must be a type of class
ArrayList<String> a = new ArrayList<String>();
ArrayList<Integer> b = new ArrayList<Integer>();

// the size of the ArrayList
arrayList.size();

// add data to the ArrayList
arrayList.add("DATA");

// replace data by returning the value of the replaced data
arrayList.set();

// remove data by returning the value of the removed data
arratList.remove();

How to traverse the ArrayList

济南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
求最大的价值

思路

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

动态规划习题2

P1970 花匠


分析

  • 第一次很容易就能想到转移方程:

    1
    2
    if(a[i]>a[i+1] && a[i]>a[i-1]) f[i]=f[i-1]+1;
    else if(a[i]<a[i+1] && a[i]<a[i-1]) f[i]=f[i-1]+1;

    但是这样做有一个很大的问题,无法确定最后一个状态的转移是否合法

    然后我就想找到最后一个状态是从哪里转移过来的,最后再额外判断一遍。虽然有点不像动态规划,只要用last1last2两个变量储存倒数第二个和第三个留下的点,但还是WA了2个点。

    原因好像是我丢掉了一些状态:我默认了只要这棵花能选就选,不满足无后效性

  • 动态规划

    正解:一维无法解决问题,那么就升一维。

    定义状态为f[i][j]表示第i个花处在上升或下降序列中能选的最多的花数

    状态转移方程为

    1
    2
    3
    4
    if(a[i]<a[i+1] && a[i]<a[i-1]) f[i][0]=f[i-1][1]+1;
    else f[i][0]=f[i-1][0];
    if(a[i]>a[i+1] && a[i]>a[i-1]) f[i][1]=f[i-1][0]+1;
    else f[i][1]=f[i-1][1];
  • 贪心

    为了方便我们设当前的花为A,下一盆花为B\

    • 第一盆花肯定要选,如果不选的话第二盆就成了第一盆,花的总数就会减少,一定不会比选第一盆花更优
    • 如果B比A还高,那么一定会选择B,因为落差的区间变大了,能够容纳的合法的花也变多了;同理,如果BA还小,那么一定会选择B
    • 通过以上两个判断不停地找波峰和波谷,记录答案就可以了

P1020 导弹拦截


非常恶心的一道题,我已经被搞晕了\

分析

  • 第一问就是求最长不上升子序列,想象有一个栈,如果当前数小于等于栈顶的数,则直接入栈;否则二分查找栈内第一个大于等于当前数的数并替换它,因为与当前数相等的数是有贡献的
  • 第二问就是求最长上升子序列,我不会证明,只能大概的胡诌,因为相当于我只关心子序列的长度,而只要有一个高度大于当前长度,就必须去新建一个序列,有点类似于木桶原理……

遇到的坑

  • 最长不下降子序列 等价于 倒序的最长不上升子序列
  • 最长下降子序列 等价于 倒序的最长上升子序列
  • lower_bound 二分查找第一个大于等于基准数的数(涵盖的范围更广)
  • upper_bound 二分查找第一个大于基准数的数

P1103 书本整理


很有感触的一道题\

分析

  • 可以抽象为:给定一串数列,首先对数列进行排序然后从数列中删除K个数使得整个数列每相邻两个数的差的绝对值的和最小,输出最小的和,即最小不整齐度。好拗口

  • f[i][j]表示长度为j的数列,数列最后一个的位置标号为j

  • 假设当前状态数列长度为j,现在以第i位为数列的最后一个,即最后一个肯定留下的最小不整齐度。因为这一位肯定要保留,所以状态肯定是从j-1转移过来的。其次我们就要枚举数列长度为j-1时,数列最后一个保留的数到底是多少,由此我们可以计算出应该增加的不整齐度

  • 转移方程:

    1
    f[i][j]=min(f[t][j-1]+abs(a[i]-a[t]),f[i][j]);//最后一个保留a[i],数列长度为j的最小不整洁度
  • 接下来考虑边界问题

    • j<=i 序列里的数肯定不会超过所有当前的数
    • t>=j-1 由上式同理可以得出,状态中的第一维度肯定大于等于第二维度
    • t<i 数列里的最后一个数肯定不可能达到现在及以后的数
    • j<=n-K 由题意可得……

    分析最清晰的一回

遇到的坑

  • f[n][n-k]并不是最终答案!!!只要状态里最后一个位置编号大于n-K,并且序列里有n-K个数,就有可能成为答案,所以我们要扫一遍找到最终答案
  • 赋初值!!! 因为我们状态转移选择的是最小值,最开始所有状态都是0,无论怎么转移都是0。所以我们把所有初值赋值为无穷大?显然不可行。我们可以每当需要转移该状态时,在确定该状态一定会被改变的前提下提前赋值为无穷大****
  • 真的都是很深很深的坑

AC代码

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>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N=110;
struct ty
{
int h,w;
};
ty b[N];
int n,K,f[N][N];//是否保留

bool operator < (const ty &a,const ty &b)
{
return a.h<b.h;
}

int main()
{
scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++)
scanf("%d%d",&b[i].h,&b[i].w);

K=n-K;
sort(b+1,b+n+1);

//第i个数保留j个的最小整齐度,序列的最后一个数序号为i
for(int i=1;i<=n;i++)
{
for(int j=1;j<=K&&j<=i;j++)
{
if(j==1) continue;
f[i][j]=0x3f3f3f3f;
for(int t=j-1;t<i;t++)
{
f[i][j]=min(f[t][j-1]+abs(b[i].w-b[t].w),f[i][j]);
}
// printf("f[%d][%d]=%d\n",i,j,f[i][j]);
}
}

int ans=0x3f3f3f3f;
for(int i=K;i<=n;i++)
ans=min(ans,f[i][K]);
printf("%d\n",ans);
return 0;
}

P1429 平面最近点对(加强版)

P1429 平面最近点对(加强版)

题目

题目描述
给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的

输入输出格式
输入格式:
第一行:n;2≤n≤200000

接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。

输出格式:
仅一行,一个实数,表示最短距离,精确到小数点后面4位。

输入输出样例
输入样例#1:
3
1 1
1 2
2 2
输出样例#1:
1.0000

思路

  • 首先考虑暴力,枚举所有点对,复杂度为O(N^2)

  • 然后就是正解:

    分治算法

    • 每一次把平面分成两个部分,找出左边的最近点对,右边的最近点对以及穿越分割线的最近点对。
    • 在求穿越分割线的最近点对时,用左右已经算出的最小值作为参考,一旦大于就停止搜索

动态规划1

笔记

最优子结构:子结构最优,全局一定最优
无后效性:各个决策部分单独存在,不会相互影响

  1. 确定状态
    • 维度从低往高试
  2. 确定转移方程
    • 每一个状态的决策
    • 初始值
    • 边界问题
  3. 是否可以降低维度或其他优化

最大子串和


题意:给你一个有正有负的序列,求一个=子串(连续的一段),使其和最大!
样例输入: -5 6 -1 5 4 -7
样例输出: 14

状态:f[i]表示前i个数的最大子串和,每个状态只有两种决策:1. 与前面构成一个子串 2. 单独成为一个子串的开头
转移方程: f[i]=max(f[i−1]+a[i],a[i])f[i]=max(f[i−1]+a[i],a[i])

不相交的两个子串的最大和


给你一个有正有负的序列,求两个不重叠的子串,使其和最大!

方法一

两个不重叠的子串中间一定有一个分界点,我们可以枚举这个分界点,分别求出这个点左边的最大子串和以及右边的最大子串和

方法二

定义状态f[i][j]为前i个数组成了j个子串的最大值,当前状态下有两种选择,一种是与前面组成子串,一种是单独成为一个子串,但是需要枚举这个数前面的串的结尾在哪里
状态转移方程为f[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<if[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<i​
优化:可以用前缀和维护k维度,算出前k个数的最大和

最大子矩形


在一个矩阵中找到一个子矩阵,该子矩阵和最大!!输出最大和即可。

从暴力的角度考虑,这道题需要枚举矩形的两个顶点,也就是O(n^4)
我们可以只枚举两个顶点的行坐标,即找到这个矩形的高度所在的位置,然后把每一列的数之和求出来当做一个数,可以提前求出每一列前缀和,也就转化成了求最大子串和。

最长公共子序列


给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。
最长公共子序列:公共子序列中长度最长的子序列。
给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…, yn},找出X和Y的一个最长公共子序列。

状态f[i][j]表示X的前i位与Y的前j位最长公共子序列的长度
转移方程

1
2
3
4
5
6
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(X[i]==Y[j]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=max(f[i-1][j],f[i][j-1]);
}

回文词


回文词是一种对称的字符串——也就是说,一个回文词,从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串,通过插入若干字符,都可以变成一个回文词。你的任务是写一个程序,求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”,在插入两个字符后可以变成一个回文词(“dAb3bAd”或“Adb3bdA”)。然而,插入两个以下的字符无法使它变成一个回文词。
给出一个字符串求出使其变为回文串需要插入的最少字符数。

思路:需要添加的字符的长度为原字符串的总长度减去现有的回文串长度,所以只要求出原字符串的回文串的长度就可以解决了
回文串的定义是正串与反串一样,那么正串与反串的最长公共子序列长度就是回文串的长度
为什么不是最长公共子串长度?\ 在添加字符的时候可以在任意位置插入,所以不必要求连续。所以如果只能从左右两边加入,那么就是最长公共子串长度

乘积最大


设有一个长度为N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。
如:有一个数字串:312, 当N=3,K=1时会有以下两种分法: 1) 312=36 2) 312=62
这时,符合题目要求的结果是:31*2=62

状态:f[i][j]表示前i位使用k个乘号的最大乘积
决策

  1. 这个数与前面的数组成更大的数,需要枚举这个数的起点
  2. 单独成为一个新数

在算乘积的时候可以先算出前缀‘乘’\
转移方程:

1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++)
muti[i]*=muti[i-1]*a[i];
muti[0]=1;

for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
{
f[i][j]=f[i-1][j-1]*a[i];
for(int k=1;k<i;k++)
f[i][j]=f[k][j-1]*(muti[i]/muti[k-1]);
}
Your browser is out-of-date!

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

×