CheaSim Blog

9.9-9.15计划

一周计划 9.9 - 9.15

数学

  • 完成线性代数部分,一天一章李永乐强化
  • 每天回顾错题以及一元函数积分的习题 5题

英语

  • 单词达标。
  • 三天阅读模拟+完型+新题型 第一天集中做, 第二第三天精读
  • 三天中最后一天背一篇范文。

政治

《知识点精讲精练》《讲真题》《1000题》

  • 一天一章,如果学累了看视频,看完一章立刻做完1000题中对应单元
  • 课余时间看徐涛视频

专业课

  • 一天半章 数据结构选择题,争取这周选择题结束,并且摘错题。
  • C语言教材无聊的时候看一下。

[pat1139]First Contact 前导零

First Contact

题意

给定一个图,图中的点只有男的点或者女的点。给定两个不同的点AB,问他们第一个点通过两个不同的点找到第二个点,并且A找到的点和A同性,B连接的点跟B同性,这样的点对有多少对。

题解

暴力枚举即可,找到所有相邻的同性点,之后同性点之间有连接就是一对点对。

  • wa点 前导零输出,-0000输入
  • 中间的点不能是两边的点,必须是不同的四个点

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
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
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
map<int,int> mx;
const int maxn = 3e2+10;
int vis[maxn][maxn];
int idx[maxn];
int gender[maxn];
void output(int x){
char ch[10];
ch[0] = '0';
ch[1] = '0';
ch[2] = '0';
ch[3] = '0';
ch[4] = '\0';
int cnt = 3;
while(x){
ch[cnt--] = (x%10)+'0';
x /= 10;
}
printf("%s",ch);
}
int trans(string x,int &sign){
int a = 0;
int sz = x.size();
if(x[0] == '-'){
rep(i,1,sz){
a += pow(10,4-i) * (x[i] - '0');
}
sign = 1;
}else{
rep(i,0,sz){
a += pow(10,3-i) * (x[i] - '0');
}
}
return a;
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
int n,m;
scanf("%d%d",&n,&m);
int cnt = 1;
rep(i,0,m){
string a,b; cin>>a>>b;
int x,y;
int sign1 = 0,sign2 = 0;
x = trans(a,sign1) ; y = trans(b,sign2);
if(mx[x] == 0){
mx[x] = cnt++;
if(sign1) gender[mx[x]] = 1;
idx[mx[x]] = x;
}
if(mx[y] == 0){
mx[y] = cnt++;
if(sign2) gender[mx[y]] = 1;
idx[mx[y]] = y;
}
int id1 = mx[x];
int id2 = mx[y];
vis[id1][id2] = vis[id2][id1] = 1;
}
int k;scanf("%d",&k);
rep(i,0,k){
int x,y; scanf("%d%d",&x,&y);
x = max(-1*x,x);
y = max(-1*y,y);
int id1 = mx[x]; int id2 = mx[y];
vector<int> xx;vector<int> yy;
if(id1 == 0 || id2 == 0){
puts("0");
continue;
}
rep(j,1,cnt+1)
if(j != id2 && vis[id1][j] && (gender[id1]^gender[j]) == 0)
xx.push_back(j);
rep(j,1,cnt+1)
if(j != id1 && vis[id2][j] && (gender[id2]^gender[j]) == 0)
yy.push_back(j);
vector<pair<int,int>> ans;
for(auto x:xx){
for(auto y:yy){
if(vis[x][y] == 1){
ans.push_back(make_pair(idx[x],idx[y]));
}
}
}
sort(ans.begin(),ans.end());
printf("%d\n",ans.size());
for(auto x:ans){
output(x.fi); printf(" "); output(x.se);
puts("");
//printf("%d %d\n",x.fi,x.se);
}
}
return 0;
}

上海科技大学信息学院夏令营随笔

随笔

以此记录我人生中的第一次面试

前因

因为在报名夏令营的时候,一个公众号将上海科技大学加入列表中,我才知道有上海科技大学这所大学。之后查了以后发现上科大是一所2013年建成的精致的大学。查了以后发现上科大的师资力量和学校经济实力十分得强大,所以就报名了上科大的信息学院夏令营并通过了初审。

过程

我选择的是第一批次,之后在生产实习的时候请假来到上海,来到上科大的第一感觉就是这个学校很精致,很有设计感。里面的每一栋建筑明显都是有设计过的痕迹,并且没有一座建筑是长得一样的!

之后入住了上科大的研究生宿舍,2人一间,宿舍是酒店标间的设计。

面试

上一届上科大夏令营是3个老师来面试每一个人。这一届上科大选择了老师同学双向选择面试,你可以面试很多老师,只要你去找这个老师即可。我一开始的目标老师是tkw老师,但是这位老师一直没有回我邮件。所以我就去给hxm老师和yjy老师发了邮件。之后他们都有回复。第一天上午是参观学校并介绍学校的毕业生去向。下午自由活动,由于给hxm老师发邮件的人实在是太多,所以老师选择先让我们笔试。笔试的内容大概就是计算机专业课+机器学习中的线性代数和概率论+程序设计算法思维题。我由于计算机网络还没有复习完,并且专业课的内容学得也没有那么扎实,所以第二天没有能够和hxm老师面试,惨遭淘汰。之后第二天上午,我去了yjy老师,yjy老师有两次面试,一次是让他的博士生来面试,主要的内容就是简历中他们感兴趣的内容,之后我程序竞赛还算是比较认真的。通过了一面,来到了二面,二面中,老师会先让你自我介绍,之后会让你提一些你感兴趣的问题。但是作为一个死读书的,我哪里来那么多问题。如果在给我一次机会的话,我会问:博士毕业后创业,我看先前有学姐介绍有一个人就是通过他自己研究生的课题发展成为一家公司,并且我在乔布斯访谈中也了解到,乔布斯当时在车库中创业是因为他们组装的电脑收到了很大的欢迎,那么老师,如果您推荐创业,您的课题中有哪一些课题是比较适合落地并且创业的呢?二面我感觉蛮糟糕的。之后我去了zr老师的面试,老师是比较偏硬件的,但是人面试的时候十分好,hin温柔。之后老师问我有没有问题,我当时有点紧张,所以就没有问老师。。如果再给我一个机会的话,我会问:老师由于我大一到现在基本上都在程序设计竞赛,没有完整地参加过一次科研活动,我就想问一下您,您觉得一次科研的过程大概是怎样的。之后科研在现在到底是会对这个社会产生怎样的影响。因为我看现在的公司工业界感觉创造的成就比学术界更加强力并且落地的程度更加完善。您觉得工业界和学术界各有什么优劣势吗?

结尾

食堂不咋地,但是住宿很舒服,环境很好,并且听说研究生的补助很高,大概每个人2000+每个月是肯定的。觉得有点遗憾的就是,没有面试足够多的老师,本来我就是来积累面试经验的,结果就面试了两个老师,有点亏。。

总结

自我介绍,还是需要整理一下的,必须要让老师有亮眼的地方!

前端修炼手册

前端修炼手册

使用工具

语言:js+html

框架:echarts+impress

经历

一开始我就在寻找有什么能够跟ppt一样,展示出我们的数据分析图表的框架,之后我就搜索到了impress.js这个框架。他的效果很酷炫,非常适合拿来展示自己的作品甚至代替ppt来使用。

官方demo:https://impress.js.org/#/bored

半小时因为impress.js的版本不对,搞了半天。应该直接去github下载就行了。

之后遇到了一个坑点,jsp嵌入html5的时候,载入js脚本的时候,必须声明是javascript,否则可能会出错。

并且jsp声明html5的格式为

1
2
3
4
5
6
7
8
9
10
11
12
<!DOCTYPE HTML>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport"
content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Document</title>
</head>
<body>

</body>

echarts+ajax+struts2 实现数据图表动态加载并显示

echarts+ajax+struts2 实现数据图表动态加载并显示

echarts

百度出品的良心可视化数据js库。

简单小例子

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
<%--
Created by IntelliJ IDEA.
User: cheasim
Date: 2019/5/7
Time: 10:33 AM
To change this template use File | Settings | File Templates.
--%>
<%@ page contentType="text/html;charset=UTF-8" language="java" %>
<html>
<head>
<title>图表分析</title>
<script src="https://cdn.bootcss.com/echarts/4.2.1-rc1/echarts-en.common.min.js"></script>
</head>
<body>
<%--新建一个dom 存放图表--%>
<div id="main" style="width: 600px;height:400px;"></div>
<script type="text/javascript">
// 基于准备好的dom,初始化echarts实例
var myChart = echarts.init(document.getElementById('main'));

// 指定图表的配置项和数据
option = {
backgroundColor: '#2c343c',
visualMap: {
show: false,
min: 80,
max: 600,
inRange: {
colorLightness: [0, 1]
}
},
series : [
{
name: '访问来源',
type: 'pie',
radius: '55%',
data:[
{value:235, name:'视频广告'},
{value:274, name:'联盟广告'},
{value:310, name:'邮件营销'},
{value:335, name:'直接访问'},
{value:400, name:'搜索引擎'}
],
roseType: 'angle',
label: {
normal: {
textStyle: {
color: 'rgba(255, 255, 255, 0.3)'
}
}
},
labelLine: {
normal: {
lineStyle: {
color: 'rgba(255, 255, 255, 0.3)'
}
}
},
itemStyle: {
normal: {
color: '#c23531',
shadowBlur: 200,
shadowColor: 'rgba(0, 0, 0, 0.5)'
}
}
}
]
};
// 使用刚指定的配置项和数据显示图表。
myChart.setOption(option);
</script>
</body>
</html>

PAT练习

PAT练习

为了拿PAT的50元代金券,刷一刷牛客网上的PAT真题。

点我连接

Rational Sum

题意

求一百个分数的和。

题解

大整数秒了。

其实我想用python,现在acm区域赛都让用python了

ac代码

##Read Number in Chinese

题意

给定一个数字,用中文拼音输出他。

题解

模拟。

  • 如果是负数,输出”Fu”
  • 每四位分隔一下,都是一样的。

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
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
96
97
98
99
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
char s[20];
string chinese[10] = {"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
ll n;
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%s",s);
int t = 0;
int sz = strlen(s);

if(s[0] == '-') t = 1;
per(i,t,sz) s[i+10-sz] = s[i];
rep(i,t,10-sz+t) s[i] = '0';
vector<string> ans;
if(s[0] == '-') ans.push_back("Fu");
bool flag = true;
int idx = 0;
rep(i,1,10) if(s[i] > '0'){
idx = i;
break;
}
rep(i,1,10) s[i] -= '0';
if(s[1] != 0){
ans.push_back(chinese[s[1]]);
ans.push_back("Yi");
}
if(s[2] != 0){
ans.push_back(chinese[s[2]]);
ans.push_back("Qian");
}else{
if(s[1] && (s[3] || s[4] || s[5])) ans.push_back("ling");
}
if(s[3] != 0){
flag = true;
ans.push_back(chinese[s[3]]);
ans.push_back("Bai");
}else{
if(s[4] != 0 || s[5] != 0) ans.push_back("ling");
}
if(s[4] != 0){
flag = true;
ans.push_back(chinese[s[4]]);
ans.push_back("Shi");
}else{
if(s[5] != 0) ans.push_back("ling");
}
if(s[5] != 0){
ans.push_back(chinese[s[5]]);
}else if((s[2] == 0 && s[3] == 0 && s[4] == 0) && (s[6] || s[7] || s[8] || s[9])) ans.push_back("ling");
if(s[2] || s[3] || s[4] || s[5]) ans.push_back("Wan");

// gewei
flag = true;


if(s[6] != 0){
ans.push_back(chinese[s[6]]);
ans.push_back("Qian");
}else{
if(idx <= 5 && (s[7] || s[8] || s[9])) ans.push_back("ling");
}
if(s[7] != 0){
ans.push_back(chinese[s[7]]);
ans.push_back("Bai");
}else{
if(s[8] != 0 || s[9] != 0) ans.push_back("ling");
}
if(s[8] != 0){
ans.push_back(chinese[s[8]]);
ans.push_back("Shi");
}else{
if(s[9] != 0) ans.push_back("ling");
}
if(s[9] != 0) ans.push_back(chinese[s[9]]);
if(ans.size() == 0) ans.push_back("ling");
bool lingling = true;
rep(i,0,ans.size()){
if(ans[i] == "ling" && lingling && ans.size()>1) {
continue;
}
if(ans[i] != "ling" && ans[i] != "Fu") lingling = false;
else lingling = true;
cout<<ans[i];
if(i==ans.size()-1) cout<<'\n';
else cout<<' ';
}
return 0;
}

List Grades (25)

题意

给定最多100个人,给他们排序,输出指定成绩区间内的人名和ID。

题解

模拟,sort

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
struct node{
string name;
string id;
int grade;
bool operator<(const node& x) const{
return grade > x.grade;
}
node(){}
node(string a,string b,int g){
name = a;
id = b;
grade = g;
}
};
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
vector<node> ve;
int n; scanf("%d",&n);
rep(i,0,n){
string a,b; int g;
cin>>a>>b>>g;
ve.push_back(node(a,b,g));
}
sort(ve.begin(),ve.end());
int st,ed;
scanf("%d%d",&st,&ed);
bool flag = false;
rep(i,0,n) if(ve[i].grade <= ed && ve[i].grade >= st) flag = true;
int cnt = 0;
while(cnt < n && ve[cnt].grade > ed) cnt++;
while(cnt < n && ve[cnt].grade >= st){
cout<<ve[cnt].name<<' '<<ve[cnt].id<<' '<<'\n';
cnt++;
}
if(!flag) puts("NONE");

return 0;
}

Tree Traversals Again (25)

题意

用栈表示一个树的先根遍历,求这颗二叉树的后跟遍历。

题解

dfs模拟一下即可。

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
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

char s[30];
struct node{
int id;
node *left = NULL,*right = NULL;
};
void addnode(node * root,int n,int f){
if(f){
root->left = new node();
root->left->id = n;
}else{
root->right = new node();
root->right->id = n;
}
}
void dfs(node* u){
int n; scanf("%s",s);
// left
if(s[1] == 'u'){
cin>>n;
addnode(u,n,1);
dfs(u->left);
}
scanf("%s",s);
if(s[1] == 'u'){
cin>>n;
addnode(u,n,0);
dfs(u->right);
}else{
return;
}
}
void post_order(node * rt){
if(rt->left != NULL){
post_order(rt->left);
}
if(rt->right != NULL){
post_order(rt->right);
}
printf("%d ",rt->id);
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
node * root = new node();
int n;scanf("%d",&n);
scanf("%s %d",s,&n);
root->id = n;
dfs(root);
post_order(root);
return 0;
}

DNA Sequence

DNA Sequence

题意

给定$m$个指定串,寻找长度为$n$的不含指定串的字符串。

题解

AC自动机+dp+矩阵快速幂。

如果要不含病毒串,那么我们相当于在每个状态中不能指向那个病毒终点串。对于每个状态来说,可以选择的就是4个字母去掉下一个状态是病毒的字母。

$dp[i] += dp[j] (j是非病毒终点)$

初始化$dp[i]$为可以选择的字母。相当于$i$状态加上状态$j$乘上字母数。可以构造一个矩阵mx。$mx[i][j]$表示$i$到$j$的字母数,矩阵的$n$次方之后就是经过$n$个状态转化后的值。

举个例子,比如我们是AC,AT,AG,AA这四个病毒串,那么root = 0,A是1,C=2,T=3,A=4。有五个状态。

当我们状态为0的时候,有两种选择。我们到状态0的选择字母可以选3个’C’’T’’G’。到状态1可以选1个’A’。之后到状态1没有选择了,因为全是病毒串。所以我们的矩阵是

3 1

0 0

之后矩阵乘就完事了。

我感觉讲得有点不清楚。。。

+2 TLE因为矩阵的大小是有build的trie树决定的,所以越小越好用ac.tot来表示矩阵的大小,也就是状态的大小。

+10 矩阵的大小其实是状态的大小,状态的大小是 输入的病毒串长度*病毒串的次数。最大tot为这么大。

+1 因为转移的状态只有四种,所以maxson为4就好了,大了的话创造矩阵的时候会出现问题。

###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
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxson = 4;
const ll mod = 100000;
int n,m;
const int MAX = 110;
int tot = 0;
struct Matrix{
ll mx[MAX][MAX];
int n;
Matrix(){memset(mx,0,sizeof(mx)); n = MAX;}
Matrix operator +(const Matrix &b)const{
Matrix res;
rep(i,0,MAX) rep(j,0,MAX)
res.mx[i][j] = (mx[i][j]+b.mx[i][j])%mod;
return res;
}
Matrix operator *(const Matrix &b) const{
Matrix res;
rep(i,0,tot) rep(j,0,tot) {
rep(k,0,tot){
res.mx[i][j] += mx[i][k]*b.mx[k][j];
}
res.mx[i][j] %= mod;
}
return res;
}
void debug(){
rep(i,0,n){
rep(j,0,n){
cout<<mx[i][j]<<' ';
}
cout<<endl;
}
}
}U,V;
Matrix pow3(Matrix f,int n){
Matrix res;
rep(i,0,MAX) res.mx[i][i] = 1;
while(n){
if(n&1) res = res*f;
n>>=1;
f = f*f;
}
return res;
}
struct Trie{
int next[20*20][maxson],fail[20*20],flag[20*20];
int root,tot;
int encode[256];
int newnode(){
rep(i,0,maxson) next[tot][i] = -1;
flag[tot++] = 0;
return tot-1;
}
void init(){
tot = 0;
root = newnode();
encode['A'] = 0;
encode['T'] = 1;
encode['C'] = 2;
encode['G'] = 3;
memset(flag,0,sizeof(flag));
}
void insert(char *s,int id){
int len = strlen(s);
int now = root;
rep(i,0,len){
int k = encode[s[i]];
if(next[now][k] == -1)
next[now][k] = newnode();
now = next[now][k];
}
flag[now] = id;
}
void build(){
queue<int> q;
fail[root] = root;
rep(i,0,maxson){
if(next[root][i] == -1){
next[root][i] = root;
}else{
fail[next[root][i]] = root;
q.push(next[root][i]);
}
}
while(!q.empty()){
int now = q.front(); q.pop();
if(flag[fail[now]]) flag[now] = 1;
rep(i,0,maxson){
if(next[now][i] == -1){
next[now][i] = next[fail[now]][i];
}else{
fail[next[now][i]] = next[fail[now]][i];
q.push(next[now][i]);
}
}
}
}
Matrix build_mx(){
Matrix res;
rep(i,0,tot) rep(j,0,maxson){
if(flag[i] != 1 && flag[next[i][j]] != 1 ){
res.mx[i][next[i][j]] ++;
}
}
return res;
}
void debug(){
for (int i = 0; i < tot; i++){
printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], flag[i]);
for (int j = 0; j < maxson; j++) printf("%2d", next[i][j]);
printf("]\n");
}
}
}ac;
char s[30];
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif // LOCAL
scanf("%d%d",&n,&m);
ac.init();
rep(i,0,n){
scanf("%s",s);
ac.insert(s,1);
}
ac.build();
tot = ac.tot;
Matrix res1 = ac.build_mx();
Matrix res = pow3(res1,m);
ll ans = 0;
res1.debug();
rep(i,0,ac.tot){
ans += res.mx[0][i];
}
ans = ans % mod;
printf("%d\n",ans);

return 0;
}

[dp+graph] CodeForces - 721C

[dp+graph] CodeForces - 721C

题意

给定一个有向无环图DAG,之后问从点$1$走到点$n$中,在一定的费用要求下,最多能经过多少个点。并给出经过的点。

题解

$n \leq 5000$

我们可以考虑一下二维dp,定义一个dp数组

  • $dp[i][j]$代表着在$i$这个点到终点,经过$j$个点所需要花费的最少时间。

之后利用dfs进行更新。因为是深度优先,所以经过的点不用在遍历一遍。

对于记录经过的点,可以用一个二维数组代表,第$j$个点的时候下一个点是什么。


错误的思想。 WA14

定义两个数组,一个记录已知这个点到达$n$最少耗-费的时间,一个记录已知这个点到达$n$最多的点数。之后利用这两个数组进行剪枝,但是已知wa14的点,我也不知道为什么。可能是dfs的顺序有关。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e3+10;
int n,m,T,cnt;
int head[maxn],vis[maxn];
struct node{
int to,next;
ll val;
}G[maxn];
void init(){
memset(head,-1,sizeof(head));
cnt = 1;
}
void addedge(int u,int v,int val){
G[cnt].to = v;
G[cnt].val = val;
G[cnt].next = head[u];
head[u] = cnt++;
}
int dp[maxn][maxn], bef[maxn][maxn];
void dfs(int u){
vis[u] = 1;
if(u==n) return;
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(vis[v]==0) dfs(v);
rep(j,1,n){
if(dp[v][j] + G[i].val < dp[u][j+1]){
dp[u][j+1] = dp[v][j] + G[i].val;
bef[u][j+1] = v;
}
}
}
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%d%d%d",&n,&m,&T);
init();
memset(dp,0x3f,sizeof(dp));
rep(i,1,m+1){
int u,v,val; scanf("%d%d%d",&u,&v,&val);
addedge(u,v,val);
}
dp[n][1] = 0;
dfs(1);
int idx = 1;
per(i,1,n+1){
if(dp[1][i] <= T){
printf("%d\n",i);
idx = i;
break;
}
}
printf("1 ");
int cnt = 1;
while(idx > 1){
printf("%d ",bef[cnt][idx]);
cnt = bef[cnt][idx--];
}
return 0;
}

TCP,UDP,Socket学习笔记

Linux自学网络

What is Socket 系统调用

TCP UDP
是否连接 面上连接 面上非连接
传输可靠性 可靠 不可靠
应用场合 传输大量的数据,对可靠性要求较高的场景 传输少量数据,对可靠性要求不高的场景
速度