20160702 自勉

  • 钻研那些最需要脑力的事。

  • 去 SJTU ,去见见更大的世界。

  • 高考可以重来;而 OI ,无论是 Happy Endding 还是 Sad Endding ,真的没有 One More Chance 了。

  • 没有一场胜利的战役是按计划进行的,但是没有计划是打不赢胜仗的。

向上吧,少年!

分享到

20170828

Y 小姐,好久不见,你还好么

昨天想说却还没说的是

在大脸和播客以外

还在写些有的没的

我喜欢 YYYYMMDD 的时间戳样式

所以用这一天命名


我不知道 你看到这里的时候会在哪里

但我确定 那天我注视的是你看着我的你的眼睛

只有疑问没有答案

但又好像

没有疑问那就是确定的答案

你笑起来还蛮有感染力的

可爱 机智 率真

所以你要多笑笑


我的世界很骄傲,但也会有为之动容的例外

比如你

似乎 可能 也许

就是那个例外


我是二分图上的一个顶点

想和你之间连条边

如果把世界以你二分

一个是有你的世界

一个是没有你的世界

我已经无法想象后者


昨天虽说过 Good Day

还是想再说七夕快乐

即使今年的必须留给大脸

但愿下一个

以及以后的很多个

能够和你在一起

一起走到更远,甚至不曾敢想的地方

遇见更加强大的彼此


Kay

20170827 上海初秋,财大的阳光里

UTC+8.00

分享到

NOI OpenJudge 题库 8211 派

描述

我的生日要到了!根据习俗,我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对,每个人会拿到一块派(必须一个派的一块,不能由几个派的小块拼成;可以是一整个派)。

我的朋友们都特别小气,如果有人拿到更大的一块,就会开始抱怨。因此所有人拿到的派是同样大小的(但不需要是同样形状的),虽然这样有些派会被浪费,但总比搞砸整个派对好。当然,我也要给自己留一块,而这一块也要和其他人的同样大小。

请问我们每个人拿到的派最大是多少?每个派都是一个高为1,半径不等的圆柱体。

输入

第一行包含两个正整数N和F,1 ≤ N, F ≤ 10 000,表示派的数量和朋友的数量。
第二行包含N个1到10000之间的整数,表示每个派的半径。

输出

输出每个人能得到的最大的派的体积,精确到小数点后三位。

样例输入

1
2
3 3
4 3 3

样例输出

1
25.133

分析

先由半径求体积,而后二分查找,区间为(0,最大的单个派的体积)。

个人 WA 的原因:

  • π 的值一开始取 3.141569 ,小数点后 6 位,这样的精度居然还不够,可以用 math 库中的反余弦函数 acos(-1.0)
  • check 函数中表示当前能够分的块数的变量 sum 要用 int

代码

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
#define loop(i,n) for(int i=0;i<n;i++)
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n,f;
double a[10010];
const double PI=acos(-1.0);
int check(double x)
{
int sum=0;
loop(i,n)
{
sum+=a[i]/x;
if(sum>=f)
return 1;
}
return 0;
}
int main()
{
double left=0,right=0,mid;
cin >>n>>f;
f++;
loop(i,n)
{
cin >>a[i];
a[i]=a[i]*a[i]*PI;
if(a[i]>right)
right=a[i];
}
while(right - left>0.000001)
{
mid=(left+right)/2;
if(check(mid))
left=mid;
else right=mid;
}
printf("%.3lf\n",left);
return 0;
}
分享到

NOI OpenJudge 题库 7623 五户共井问题

描述

有A, B, C, D, E五家人共用一口井,已知井深不超过k米。A, B, C, D, E的绳长各不相同,而且厘米表示的绳长一定是整数。
从井口放下绳索正好达到水面时:
(a)需要A家的绳n1条接上B家的绳1条
(b)需要B家的绳n2条接上C家的绳1条
(c)需要C家的绳n3条接上D家的绳1条
(d)需要D家的绳n4条接上E家的绳1条
(e)需要E家的绳n5条接上A家的绳1条
问井深和各家绳长。

输入

输入只有1行。包括空格分开的6个整数。
第一个整数k(1 <= k <= 20),代表井的最大深度(单位:米)。
接下来是5个正整数n1, n2, n3, n4, n5。这五个整数的含义见上面的题目描述。

输出

输出只有1行。
如果找到了可行解,就输出6个整数,用空格分开,分别代表井的深度和A, B, C, D, E的绳长(单位都是厘米)。
如果有多组可行解,输出井的深度最小的那组解。
如果不存在可行解,就输出一行:
not found

样例输入

1
10 2 3 4 5 6

样例输出

1
721 265 191 148 129 76

代码

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
#include<iostream>
using namespace std;
int main()
{
int k;
int n1,n2,n3,n4,n5;
cin >>k>>n1>>n2>>n3>>n4>>n5;
int H,A,B,C,D,E;
int ANSH=2147483647,ANSA,ANSB,ANSC,ANSD,ANSE;
for(A=1;A<=k*100;A++)
for(B=1;B<=k*100;B++)
{
H = A * n1 + B;
C = H - B * n2;
D = H - C * n3;
E = H - D * n4;
if((E * n5 + A != H) || H>k*100 || C<=0 || D<=0 || E<=0 || A==B || A==C || A==D || A==E || B==C || B==D || B==E || C==D || C==E ||D==E)
continue;
if(H<ANSH)
{
ANSH=H;
ANSA=A;
ANSB=B;
ANSC=C;
ANSD=D;
ANSE=E;
}
}
if (ANSH==2147483647)
cout <<"not found"<<endl;
else cout <<ANSH<<" "<<ANSA<<" "<<ANSB<<" "<<ANSC<<" "<<ANSD<<" "<<ANSE<<endl;
return 0;
}
分享到

NOI OpenJudge 题库 7914 分数线划定

描述

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才,A市对所有报名的选手进行了笔试,笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定,即如果计划录取m名志愿者,则面试分数线为排名第m*150%(向下取整)名的选手的分数,而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线,并输出所有进入面试的选手的报名号和笔试成绩。

输入

第一行,两个整数n,m(5 ≤ n ≤ 5000,3 ≤ m ≤ n),中间用一个空格隔开,其中n 表示报名参加笔试的选手总数,m 表示计划录取的志愿者人数。输入数据保证m*150%向下取整后小于等于n。
第二行到第 n+1 行,每行包括两个整数,中间用一个空格隔开,分别是选手的报名号k(1000 ≤ k ≤ 9999)和该选手的笔试成绩s(1 ≤ s ≤ 100)。数据保证选手的报名号各不相同。

输出

第一行,有两个整数,用一个空格隔开,第一个整数表示面试分数线;第二个整数为进入面试的选手的实际人数。
从第二行开始,每行包含两个整数,中间用一个空格隔开,分别表示进入面试的选手的报名号和笔试成绩,按照笔试成绩从高到低输出,如果成绩相同,则按报名号由小到大的顺序输出。

样例输入

1
2
3
4
5
6
7
6 3
1000 90
3239 88
2390 95
7231 84
1005 95
1001 88

样例输出

1
2
3
4
5
6
88 5
1005 95
2390 95
1000 90
1001 88
3239 88

提示

样例说明:m150% = 3150% = 4.5,向下取整后为4。保证4个人进入面试的分数线为88,但因为88有重分,所以所有成绩大于等于88的选手都可以进入面试,故最终有5个人进入面试。

分析

sort() 函数很强大,需要注意的是 cmp 的写法。

代码

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
#define loop(i,n) for(int i=0;i<n;i++)
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int number,score;
}a[10010];
bool cmp(node a,node b)
{
if(a.score==b.score)
return a.number<b.number;
return a.score>b.score;
}
int main()
{
int n,m;
cin >>n>>m;
m=int(m*1.5);
loop(i,10010)
a[i].score=0;
loop(i,n)
cin >>a[i].number>>a[i].score;
sort(a,a+10010,cmp);
int j=m;
int count=m;
while(a[j].score==a[m-1].score)
{
count++;
j++;
}
cout <<a[m-1].score<<" "<<count<<endl;
loop(i,m)
cout <<a[i].number<<" "<<a[i].score<<endl;
j=m;
while(a[j].score==a[m-1].score)
{
cout <<a[j].number<<" "<<a[j].score<<endl;
j++;
}
return 0;
}
分享到

NOI OpenJudge 题库 1818 红与黑

描述

有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。

输入

包括多个数据集合。每个数据集合的第一行是两个整数W和H,分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中,每行包括W个字符。每个字符表示一块瓷砖的颜色,规则如下
1)‘.’:黑色的瓷砖;
2)‘#’:白色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时,表示输入结束。

输出

对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

样例输入

1
2
3
4
5
6
7
8
9
10
11
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0

样例输出

1
45

分析

深搜入门题,开始以为是求最大联通块,仔细看发现只要求源点所在的连通块大小。居然没有数据范围,于是我就开了 1100*1100 水过了。另外有一个注意点 -> 给的 W / H 是 列 / 行 ,而正常题目是 行 / 列,循环需要把 W / H 倒过来。

似乎也可以用宽搜写,有空填坑。

代码

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
#define loop(i,n) for(int i=0;i<n;i++)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int w,h;
int ans;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char tile[1100][1100];
int map[1100][1100];
bool flag[1100][1100];
struct node
{
int x,y;
}start;
bool check(int x,int y)
{
if(!flag[x][y] && map[x][y] && x>=0 && x<h && y>=0 && y<w)
return 1;
return 0;
}
void dfs(int x,int y)
{
ans++;
flag[x][y]=1;
loop(i,4)
{
int curx=x+dx[i],cury=y+dy[i];
if(check(curx,cury))
dfs(curx,cury);
}
}
int main()
{
while(scanf("%d%d",&w,&h)==2 && w && h)
{
ans=0;
memset(map,0,sizeof(map));
memset(flag,0,sizeof(flag));
loop(i,h)
loop(j,w)
{
cin >>tile[i][j];
if(tile[i][j]=='.')
map[i][j]=1;
if(tile[i][j]=='#')
map[i][j]=0;
if(tile[i][j]=='@')
{
map[i][j]=1;
flag[i][j]=1;
start.x=i;
start.y=j;
}
}
dfs(start.x,start.y);
cout <<ans<<endl;
}
return 0;
}
分享到

NOI OpenJudge 题库 6264 走出迷宫

描述

当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。
假设你已经得到了一个n*m的迷宫的图纸,请你找出从起点到出口的最短路。

输入

第一行是两个整数n和m(1<=n,m<=100),表示迷宫的行数和列数。
接下来n行,每行一个长为m的字符串,表示整个迷宫的布局。字符’.’表示空地,’#’表示墙,’S’表示起点,’T’表示出口。

输出

输出从起点到出口最少需要走的步数。

样例输入

1
2
3
4
3 3
S#T
.#.
...

样例输出

1
6

分析

最近在刷 OpenJudge ,怎么说也得拿个 200 分换省三呢。

宽搜入门题,试了一把 STL 队列,写完觉得链表、栈、队列这种东西还是自己实现算了 …… 这些用 STL 写实在太花哨,也并没有方便太多,但是 STL 的优先队列、堆倒还是很有用的。

代码

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
#define loop(i,n) for(int i=0;i<n;i++)
const int INF=2147483647;
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
char maze[110][110];
int dis[110][110];
bool map[110][110];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
typedef pair<int,int> matrix;
matrix start,end;
queue<matrix> q;
int n,m;
void init()
{
memset(map,0,sizeof(map));
loop(i,110)
loop(j,110)
dis[i][j]=INF;
cin >>n>>m;
loop(i,n)
loop(j,m)
{
cin >>maze[i][j];
if(maze[i][j]=='S')
{
start.first=i;
start.second=j;
map[i][j]=0;
}
if(maze[i][j]=='T')
{
end.first=i;
end.second=j;
map[i][j]=0;
}
if(maze[i][j]=='.')
map[i][j]=0;
if(maze[i][j]=='#')
map[i][j]=1;
}
}
int check(int x,int y)
{
if(dis[x][y]==INF && !map[x][y] && x>=0 && x<n && y>=0 && y<m)
return 1;
return 0;
}
int bfs()
{
dis[start.first][start.second]=0;
q.push(matrix(start.first,start.second));
while(q.size())
{
matrix tmp=q.front();
q.pop();
if(tmp.first==end.first && tmp.second==end.second)
break;
loop(i,4)
{
int curx=tmp.first+dx[i],cury=tmp.second+dy[i];
if(check(curx,cury))
{
q.push(matrix(curx,cury));
dis[curx][cury]=dis[tmp.first][tmp.second]+1;
}
}
}
return dis[end.first][end.second];
}
int main()
{
init();
cout <<bfs()<<endl;
return 0;
}
分享到

递推、搜索、贪心和动态规划的区别

递推:每个阶段只有一个状态;

搜索:每个阶段的最优状态是由之前所有阶段的状态的组合得到的;

贪心:每个阶段的最优状态都是由上一个阶段的最优状态得到的;

动态规划:每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到(最优子结构),而不管之前这个状态是如何得到的(无后效性)。

分享到

最短路径问题

问题描述

平面上有 n 个点(n<=100),每个点的坐标均在-10000~10000 之间。其中的一些点之间有连线 。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离 。现在的任务是找出从一点到另一点之间的最短路径 。

输入

输入共 n+m+3 行,其中:
第一行为整数 n。
第 2 行到第 n+1 行 (共 n 行 ),每行两个整数 x 和 y,描述了一个点的坐标。
第 n+2 行为一个整数 m,表示图中连线 的个数。
此后的 m 行(m<=1000),每行描述一条连线,由两个整数 i和 j 组成,表示第 i个点和第 j 个点之
间有连线 。
最后一行 :两个整数 s 和 t,分别表示源点和目标点。

输出

输出仅一行,一个实数(保留两位小数),表示从 s 到 t 的最短路径长度 。

样例输入

1
5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5

样例输出

1
3.41

分析

顶点数较小,不加优化的 Dijkstra 即可。

代码

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
const int INF=1<<29;
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int x[110],y[110];
double dist[110][110];
// dist 数组即用作存边权的边集数组,若两点间有边则存其边权,没有则赋为 ∞
bool flag[110];// flag 用作标记每个端点是否已访问
double getdist(int x1,int x2,int y1,int y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
memset(flag,0,sizeof(flag));
int n,m,s,t;
int i,j,k,pos;
for(i=0;i<110;i++)
{
flag[i]=0;
for(j=0;j<110;j++)
dist[i][j]=INF;
}
cin >>n;
for(i=1;i<=n;i++)
{
dist[i][i]=0;
cin >>x[i]>>y[i];
}
cin >>m;
for(i=1;i<=m;i++)
{
int a,b;
cin >>a>>b;
dist[a][b]=dist[b][a]=getdist(x[a],x[b],y[a],y[b]);
}
cin >>s>>t;
flag[s]=1;
for(i=1;i<=n;i++)
{
int minimum=INF;
for(j=1;j<=n;j++)//找离 s 最近点 j
{
if(!flag[j] && dist[s][j]<minimum)
{
pos=j;
minimum=dist[s][j];
}
}
flag[pos]=1;
for(j=1;j<=n;j++)
if(!flag[j] && dist[s][pos]+dist[pos][j]<dist[s][j])
//以找到的点为中间点,更新 s 到各顶点的最短距离
dist[s][j]=dist[s][pos]+dist[pos][j];
}
printf("%.2lf\n",dist[s][t]);
return 0;
}
分享到

收入计划

问题描述

高考结束后,同学们大都找到了一份临时工作,渴望挣得一些零用钱。从今天起,Matrix67将连续工作N天(1<=N<=100 000)。每一天末他可以领取当天及前面若干天里没有领取的工资,但他总共只有M(1<=M<=N)次领取工资的机会。Matrix67已经知道了在接下来的这N天里每一天他可以赚多少钱。为了避免自己滥用零花钱,他希望知道如何安排领取工资的时间才能使得领到工资最多的那一次工资数额最小。注意Matrix67必须恰好领工资M次,且需要将所有的工资全部领走(即最后一天末需要领一次工资)。

输入

第一行输入两个用空格隔开的正整数N和M
以下N行每行一个不超过10000正整数,依次表示每一天的薪水。

输出

输出领取到的工资的最大值最小是多少。

样例输入

1
2
3
4
5
6
7
8
7 5
100
400
300
100
500
101
400

样例输出

1
500

样例说明

采取下面的方案可以使每次领到的工资不会多于500。这个答案不能再少了。
100 400 300 100 500 101 400 每一天的薪水
<——1 <——-2 <—3 <—4 <—5 领取工资的时间
500 400 500 101 400 领取到的工资

分析

最小值最大/最大值最小类问题 -> 二分答案典型问题

二分答案模板,对于 l 与 r 的理解,不要仅仅用「二分法解方程」的思想理解,此类题 可把 l 看作不可行域, r 看作可行域

此题需要二分工资最大值(单次领取的最高工资必定在 [单日工资最大值,全部工资] 的区间内)利用贪心(从左到右能取就取),判断是否可行。

二分答案模板

1
2
3
4
5
6
7
8
9
10
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}

代码

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
# include<iostream>
using namespace std;
int n,m,sum=0,maximum=-1,ans;
int a[101000];
int check(int x)
{
int i;
int times=0,tot=0;
for(i=1;i<=n;i++)
{
tot=tot+a[i];
if(tot>x)
{
tot=a[i];
times++;
}
if(times+1>m)//判断是否恰好领 m 次,注意是 times+1
return 0;
}
return 1;
}
int main()
{
int i;
cin >>n>>m;
for(i=1;i<=n;i++)
{
cin >>a[i];
maximum=max(maximum,a[i]);
sum=sum+a[i];
}
int l=maximum,r=sum;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout <<ans<<endl;
return 0;
}
分享到