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

*/

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


Tech Flow

We do more than change the world.

We create it.

It’s an amazing, fantastic, incredible, unprecedented event about technology products I had ever seen. Now I believe that Microsoft is a company that will change the world more than once.

A touching movie

A moving film – Rudy

Today I cried

I have never imagined that I can be moved so deeply by a particular film. From my childhood, I have watched plenty of films including comedy, science friction, actin, plot… but none of them could make me cry. I even usually laugh at my mother crying while watching some TV series and reality show. However, now , it’s time for me to change my mind. I would like to introduce this film to you, a fantastic one that makes cold me cry.

Introduction

The film I want talk about is called Rudy, which is a famous biographical sports film directed by David Anspaugh. The film is an account of life of Daniel “Rudy” Ruettiger who has been fighting for his football dream by all efforts despite significant obstacle.

Watching by chance

I’m not myself today because of something that even I didn’t know. I simply searched on YouTube to find some introductions and recommendations about some inspirational films. Fortunately, the first text come into view is of course this film Rudy. Therefore, I downloaded it at once watching it.

Something really touch me

I am not going to spoil anything, just a few plots that really impressed me.

On his best friend’s funeral

He was despair and depress when the song begun. Rushing out of the church to cry and cry, to my surprise, he decided to go to Notre Dame University which he appreciated since his birth but nobody believed him could have done that. With no hesitate, no excess grief, he take the bus directly in the cold night.

Standing on the changing room reading the text graved on the wall

After he was allowed to take a job in charge of logistics of football team, he went to work. Once he got there, he looked at the text graved on the wall like a Saint reading the text devoutly. I can see the passion and dream from his words and eyes.

Everyone in the gym cheering for Rudy

After the friend in Rudy’s team first called his name, the voice spreading across the whole gym with everyone no matter if recognized Rudy beginning to cheer for Rudy including his old friends, teammates, family…

My personal feeling

I believed that a good film doesn’t require something spectacular or amazing, just a normal one with an unusual dream like the film. From some extent, Rudy is me, I am Rudy. I see myself on him. I cheer for myself, for my dream.

Rudy

Rudy

At last, some inspiring line for myself:

  • Having dreams is what makes life tolerable
  • In this life you don’t have to prove nothing to nobody except yourself. And after what you’ve done through, if you haven’t done by now, it ain’t gonna never happen. And I guarantee a week won’t go by, you won’t regret walking out letting them get the best of you.
  • My whole life, people have been telling me what I could do and couldn’t do. I’ve always listened to them, believed in what they said. I don’t want to do that anymore.

Rudy raised by his teammates running around the field

Rudy raised by his teammates running around the field

The last day in Seattle

西雅图夜未眠

“Country road, take me home, to the place, I belong……”, 完强老师的吉他演唱一直回荡在我耳边。从未想过,这里,如此让我留恋。

今天西雅图市区参观的行程很紧,很多地方都只停一小会儿,但整个体验还是不错的。当我站在gas park的岸边,远眺对岸的Seattle Downtown,偶尔有几只海鸥紧贴地面飞翔,看着远处的云朵被阳光穿透,一点一点地朝我们照来。一切都很安静,一切都很和谐,站在这里,吹着海风,一切烦恼都被抛在脑后,只希望这一刻可以永远持续下去……

下午很早就回到了酒店,然后换正装前往晚宴地点。乘坐电梯上至高层,来到了我们的晚宴地点。这里真的好高端啊,落地窗户直接可以看到整个西雅图(贝尔维尤?)市中心,风景十分美。

待大家坐定,没想到第一个环节就是激动人心的颁奖环节。也没有什么像电视节目中一秒剪成20秒的做作,仅仅只是丁老师平和地说出了获奖的优秀项目团队。当“Reflux”这个词说出来后,我的心跳就突然加快,我意识到也许是我们!仅仅一瞬之后,我确定是我们,就是我们!我们TinySoft这一组可能是最奇葩的一组了。三天挑战赛所有组员都没有熬夜,基本没有争吵,没有喝一杯咖啡,总之我们非常平常地坚持下来了,感觉所有项目环节也是稳步推进,一步一个脚印。但我们也未曾想过,第一名会是我们,这真的是一件意料之中却又是意料之外的事情。丁老师话音刚落,我激动地挥舞双手,不由自主地站了起来,看了看老师,看了看我的队友,又坐了下去,不知所措的样子……

几次非常尴尬地站起坐下后,我们组的四个人,机械大佬邰潇逸、视频大佬田成洋、文案大佬文劼还有我、李昊锦一同站在了舞台上(其实没有舞台)。当我看见台下Lewis鼓励的目光,以及老师们祝贺的目光,再环顾光晕下我们四人,百感交集。也许就是缘分,让我们相聚,让我们都在彼此的人生线上都有了交集。头脑风暴,我们一同站在风暴中心大开脑洞;三天的挑战,我们并肩前行,无畏困难。

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

  • 然后就是正解:

    分治算法

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

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

×