openjudge题库刷题

  1. 1 1481:Maximum sum
  2. 2 6377:生日相同 2.0
  3. 3 1551:Sumsets
  4. 4 1350:Euclid's Game
  5. 5 1526:宗教信仰
  6. 6 1538:Gopher II
  7. 7 1249:Humble Numbers
  8. 8 1413:Mondriaan's Dream
  9. 9 1455:An Easy Problem
  10. 10 1768:最大子矩阵
  11. 11 2469:电池的寿命
  12. 12 2704:寻找平面上的极大点

NOI题库的一些题

1 1481:Maximum sum

Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below: \[d(A) = max\{ \sum_{i=s1}^{t1} ai + \sum_{i=s2}^{t2}aj , 1 \le s1 \le t1 \lt s2 \le t2 \le n \}\] Your task is to calculate d(A).

动态规划

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
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int T,n,ans,a[50001],b[50001],f[50001],g[50001];
int main()
{
scanf("%d",&T);
while(T--)
{
memset(a,0,sizeof(a));
memset(b,-0x7f,sizeof(b));
memset(f,-0x7f,sizeof(f));
memset(g,-0x7f,sizeof(g));
ans=-500000000;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=max(b[i-1]+a[i],a[i]);
}
for(int i=n;i;i--)
{
f[i]=max(f[i+1]+a[i],a[i]);
g[i]=max(g[i+1],f[i]);
}
for(int i=1;i<n;i++)
ans=max(ans,b[i]+g[i+1]);
printf("%d\n",ans);
}
}

2 6377:生日相同 2.0

【描述】
在一个有180人的大班级中,存在两个人生日相同的概率非常大,现给出每个学生的名字,出生月日。试找出所有生日相同的学生。
【输入】
第一行为整数n,表示有n个学生,n ≤ 180。此后每行包含一个字符串和两个整数,分别表示学生的名字(名字第一个字母大写,其余小写,不含空格,且长度小于20)和出生月(1 ≤ m ≤ 12)日(1 ≤ d ≤ 31)。名字、月、日之间用一个空格分隔
【输出】
每组生日相同的学生,输出一行,其中前两个数字表示月和日,后面跟着所有在当天出生的学生的名字,数字、名字之间都用一个空格分隔。对所有的输出,要求按日期从前到后的顺序输出。对生日相同的名字,按名字从短到长按序输出,长度相同的按字典序输出。如没有生日相同的学生,输出”None”

结构

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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,yes,a[181],b[181],c[181],f[13][32][181];
char s1[181][21];
struct node{
int num,len;
char s[21];
} g[181];
int mycomp(const node &a,const node &b)
{
if(a.len<b.len) return 1;
if(a.len>b.len) return 0;
for(int x=0;x<a.len;x++)
{
if(a.s[x]<b.s[x]) return 1;
if(a.s[x]>b.s[x]) return 0;
}
return 0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>g[i].s;
g[i].len=strlen(g[i].s);
g[i].num=i;
scanf("%d%d",&a[i],&b[i]);
}
sort(g+1,g+n+1,mycomp);
for(int i=1;i<=n;i++)
{
c[g[i].num]=i;
for(int j=0;j<g[i].len;j++) s1[i][j]=g[i].s[j];
}
for(int i=1;i<=n;i++)
f[a[i]][b[i]][++f[a[i]][b[i]][0]]=c[i];
for(int i=1;i<=12;i++)
for(int j=1;j<=31;j++)
if(f[i][j][0]>1)
{
yes=1;
int d[181]={0};
for(int t=1;t<=f[i][j][0];t++)
d[t]=f[i][j][t];
sort(d+1,d+f[i][j][0]+1);
printf("%d %d",i,j);
for(int t=1;t<=f[i][j][0];t++)
cout<<' '<<s1[d[t]];
printf("\n");
}
if(!yes) printf("None");
}

3 1551:Sumsets

Given S, a set of integers, find the largest d such that a + b + c = d where a, b, c, and d are distinct elements of S.

哈希

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
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
int n,a[1001],ans;
int main()
{
while(scanf("%d",&n)==1&&n)
{
memset(a,0,sizeof(a));
ans=0;
map<int,int> m1,m2;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
m1[a[i]+a[j]]=i,m2[a[i]+a[j]]=j;
for(int i=n;i;i--)
{
for(int j=1;j<i;j++)
if(m1[a[i]-a[j]]&&m1[a[i]-a[j]]!=i&&m2[a[i]-a[j]]!=i&&m1[a[i]-a[j]]!=j&&m2[a[i]-a[j]]!=j)
{ans=i;break;}
if(ans) break;
}
if(ans) printf("%d\n",a[ans]);
else printf("no solution\n");
}
}

4 1350:Euclid's Game

Two players, Stan and Ollie, play, starting with two natural numbers. Stan, the first player, subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, provided that the resulting number must be nonnegative. Then Ollie, the second player, does the same with the two resulting numbers, then Stan, etc., alternately, until one player is able to subtract a multiple of the lesser number from the greater to reach 0, and thereby wins. For example, the players may start with (25,7):
25 7
11 7
4 7
4 3
1 3
1 0
an Stan wins.

数论(博弈论)
假设两个数为a,b(a>=b)
如果a%b==0 就是a是b的倍数,那么也是先手获胜。
如果a>=2*b 那么那个人肯定知道a%b,b是必胜态还是必败态。如果是必败态,先手将a,b变成a%b,b,那么先手肯定赢。如果是必胜态,先手将a,b变成a%b+b,b.那么对手只有将这两个数变成a%b,b,先手获胜。
如果是b<a<2*b 那么只有一条路:变成a-b,b (这个时候0<a-b<b).这样一直下去看谁先面对上面的必胜状态。
所以假如面对b<a<2*b的状态,就先一步一步走下去。直到面对一个a%b==0 || a≥2*b的状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
using namespace std;
int x,y,z,ans;
int main()
{
while(scanf("%d%d",&x,&y)&&(x||y))
{
for(int i=1;;i++)
{
if(x<y) z=x,x=y,y=z;
if(!y) {ans=(i-1)%2;break;}
if(x/y>=2) {ans=i%2;break;}
x-=y;
}
if(ans) printf("Stan wins\n");
else printf("Ollie wins\n");
}
}

5 1526:宗教信仰

世界上有许多宗教,你感兴趣的是你学校里的同学信仰多少种宗教。
你的学校有n名学生(0 < n <= 50000),你不太可能询问每个人的宗教信仰,因为他们不太愿意透露。但是当你同时找到2名学生,他们却愿意告诉你他们是否信仰同一宗教,你可以通过很多这样的询问估算学校里的宗教数目的上限。你可以认为每名学生只会信仰最多一种宗教。

图论(并查集)

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
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,x,y,f1,f2,f,tot,a[50001],fa[50001];
int father(int x)
{
if(fa[x]==x) return x;
else return fa[x]=father(fa[x]);
}
int main()
{
for(int num=1;;num++)
{
memset(a,0,sizeof(a));tot=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i;
if(!n&&!m) return 0;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
f1=father(x);f2=father(y);
fa[f1]=f2;
}
for(int i=1;i<=n;i++)
{
f=father(i);
if(!a[f]) a[father(i)]=1,tot++;
}
printf("Case %d: %d\n",num,tot);
}
}

6 1538:Gopher II

The gopher family, having averted the canine threat, must face a new predator.
The are n gophers and m gopher holes, each at distinct (x, y) coordinates. A hawk arrives and if a gopher does not reach a hole in s seconds it is vulnerable to being eaten. A hole can save at most one gopher. All the gophers run at the same velocity v. The gopher family needs an escape strategy that minimizes the number of vulnerable gophers.

图论(二分图)
网络流:

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
#include<cstring>
#include<cstdio>
#include<queue>
#define LINK(x) for(int e=head[x];e;e=E[e].next)
using namespace std;
const int inf=1e9;
struct Edge{int to,rest,next;}E[10300];
queue<int> Q;
int head[210],ds[210];
int n,m,s,v,S,T,ecnt;
double x,y,px[101],py[101];
inline void AddEdge(int x,int y,int r)
{
++ecnt;E[ecnt].to=y,E[ecnt].rest=r,E[ecnt].next=head[x];head[x]=ecnt;
++ecnt;E[ecnt].to=x,E[ecnt].rest=0,E[ecnt].next=head[y];head[y]=ecnt;
}
inline bool BFS()
{
for(int i=S;i<=T;i++) ds[i]=-1;
Q.push(S);ds[S]=0;
while(!Q.empty())
{
int x=Q.front(); Q.pop();
LINK(x) if(E[e].rest && ds[E[e].to]==-1)
ds[E[e].to]=ds[x]+1,Q.push(E[e].to);
}
return ds[T]>-1;
}
inline int DFS(int x,int flow)
{
if(x==T) return flow;
int a=0,b;
LINK(x) if(E[e].rest&&ds[E[e].to]==ds[x]+1)
{
b=DFS(E[e].to, min(flow-a,E[e].rest));
E[e].rest-=b, E[e^1].rest+=b;
a+=b;
if(a==flow) return flow;
}
if(a==0) ds[x]=-1;
return a;
}
inline int dinic()
{
int ans=0;
while(BFS()) ans+=DFS(S,inf);
return ans;
}
int main()
{
while(scanf("%d%d%d%d",&n,&m,&s,&v)==4)
{
while(!Q.empty()) Q.pop();
memset(E,0,sizeof(E));
memset(head,0,sizeof(head));
memset(ds,0,sizeof(ds));
s=s*s*v*v;
ecnt=1;S=0;T=n+m+1;
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&px[i],&py[i]);
AddEdge(0,i,1);
}
for(int i=1;i<=m;i++)
{
scanf("%lf%lf",&x,&y);
for(int j=1;j<=n;j++)
if((x-px[j])*(x-px[j])+(y-py[j])*(y-py[j])-s<=0.00001)
AddEdge(j,n+i,1);
AddEdge(n+i,T,1);
}
printf("%d\n",n-dinic());
}
}

7 1249:Humble Numbers

A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... shows the first 20 humble numbers.
Write a program to find and print the nth element in this sequence.
【output】
For each test case, print one line saying "The nth humble number is number.". Depending on the value of n, the correct suffix "st", "nd", "rd", or "th" for the ordinal number nth has to be used like it is shown in the sample output.

动态规划

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
#include<iostream>
#include<cstdio>
using namespace std;
int n=1,x,p2=1,p3=1,p5=1,p7=1,a[5850];
int main()
{
a[1]=1;
while(a[n]<2000000000)
{
a[++n]=min(min(a[p2]*2,a[p3]*3),min(a[p5]*5,a[p7]*7));
if(a[n]==a[p2]*2) p2++;
if(a[n]==a[p3]*3) p3++;
if(a[n]==a[p5]*5) p5++;
if(a[n]==a[p7]*7) p7++;
}
while(scanf("%d",&x)&&x)
{
if(x%10==1&&x%100!=11)
printf("The %dst humble number is %d.\n",x,a[x]);
else if(x%10==2&&x%100!=12)
printf("The %dnd humble number is %d.\n",x,a[x]);
else if(x%10==3&&x%100!=13)
printf("The %drd humble number is %d.\n",x,a[x]);
else
printf("The %dth humble number is %d.\n",x,a[x]);
}
}

8 1413:Mondriaan's Dream

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways. Expert as he was in this material, he saw at a glance that he'll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won't turn into a nightmare!

动态规划
n和m均为奇数的话,矩形面积就是奇数,可知是不可能完全覆盖的。
偶数:
最上面的为第1行,最下面为第n行
从上到下按行DP
其中一行的状态我们用一个二进制表示,0表示没有被覆盖,1表示被覆盖了
最后得到一个01串,这个串变回十进制就是一个状态
定义状态dp[i][s],表示前i-1行已经放满,第i行的状态为s的方案数
状态转移方程为 dp[i][s]=sum{ dp[i-1][ss] } ,其中状态s与状态ss兼容
这个状态转移方程的内涵在于理解s和ss如何兼容
1. 第i行的第j列为1,第i-1行的第j列为1,这样的话,说明第i行的第j列一定不是竖放而是横放否则会与第i-1行的第j列冲突
所以马上紧接着判断第i行第j+1列,如果是1,那么满足横放的规则,同时也要第i-1行第j+1列也要为1,否则的话这个格子没办法填充
成立后向左移动两格
不满足上述条件的,就是两个不兼容或者不合法的状态
2. 第i行第j列为1,第i-1行第j列为0,那么说明第i行第j列应该竖放并填充第i-1行第j列,成立后向左移动一格 3. 第i行第j列为0,说明不放方块,那么第i-1行第j列必须为1,否则没法填充这个格子。若第i-1行第j列也为0,不兼容不合法

9 1455:An Easy Problem

As we known, data stored in the computers is in binary form. The problem we discuss now is about the positive integers and its binary form.
Given a positive integer I, you task is to find out an integer J, which is the minimum integer greater than I, and the number of '1's in whose binary form is the same as that in the binary form of I.
For example, if "78" is given, we can write out its binary form, "1001110". This binary form has 4 '1's. The minimum integer, which is greater than "1001110" and also contains 4 '1's, is "1010011", i.e. "83", so you should output "83".

贪心

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
#include<cstring>
#include<cstdio>
using namespace std;
int n,len,tot,x,ans,a[21];
int main()
{
while(scanf("%d",&n)==1&&n)
{
ans=tot=0;
memset(a,0,sizeof(a));
for(len=1;n&&len<=20;len++)
a[len]=n%2,n/=2;
len--;
for(x=1;x<=len;x++)
if(a[x]&&!a[x+1])
{
if(x==len) len++;
a[x+1]=1;a[x]=0;
break;
}
for(int j=1;j<x;j++) tot+=a[j],a[j]=0;
for(int j=1;j<=tot;j++) a[j]=1;
for(int j=len;j>=1;j--) ans=ans*2+a[j];
printf("%d\n",ans);
}
}

10 1768:最大子矩阵

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。
比如,如下4 * 4的矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
的最大子矩阵是
9 2
-4 1
-1 8
这个子矩阵的大小是15。

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
using namespace std;
int n,x,maxx=-127,sum[101][101];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&x),sum[i][j]=sum[i-1][j]+x;
for(int l=1;l<=n;l++)
for(int r=l;r<=n;r++)
{
x=0;
for(int i=1;i<=n;i++)
{
x+=sum[r][i]-sum[l-1][i];
if(x>maxx) maxx=x;
if(x<0) x=0;
}
}
printf("%d",maxx);
}

11 2469:电池的寿命

小S新买了一个掌上游戏机,这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏,他买了很多5号电池,这些电池的生产商不同,质量也有差异,因而使用寿命也有所不同,有的能使用5个小时,有的可能就只能使用3个小时。显然如果他只有两个电池一个能用5小时一个能用3小时,那么他只能玩3个小时的游戏,有一个电池剩下的电量无法使用,但是如果他有更多的电池,就可以更加充分地利用它们,比如他有三个电池分别能用3、3、5小时,他可以先使用两节能用3个小时的电池,使用半个小时后再把其中一个换成能使用5个小时的电池,两个半小时后再把剩下的一节电池换成刚才换下的电池(那个电池还能用2.5个小时),这样总共就可以使用5.5个小时,没有一点浪费。 现在已知电池的数量和电池能够使用的时间,请你找一种方案使得使用时间尽可能的长。

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
using namespace std;
int x,y,n,tot,maxx;
float ans;
int main()
{
while(scanf("%d",&n)==1)
{
ans=0;tot=0;maxx=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
tot+=x;
if(x>maxx) maxx=x;
}
if(tot>=maxx*2) ans=tot/2.0;
else ans=tot-maxx;
printf("%.1f\n",ans);
}
}

12 2704:寻找平面上的极大点

在一个平面上,如果有两个点(x,y),(a,b),如果说(x,y)支配了(a,b),这是指x>=a,y>=b;
用图形来看就是(a,b)坐落在以(x,y)为右上角的一个无限的区域内。
给定n个点的集合,一定存在若干个点,它们不会被集合中的任何一点所支配,这些点叫做极大值点。
编程找出所有的极大点,按照x坐标由小到大,输出极大点的坐标。
本题规定:n不超过100,并且不考虑点的坐标为负数的情况。

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
using namespace std;
int n,x,y,maxx,maxy,tot,g[101],ans[101][2];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
if(y>g[x]) g[x]=y;
if(x>maxx) maxx=x;
}
ans[++tot][0]=maxx;ans[tot][1]=g[maxx];
maxy=g[maxx];
for(int i=maxx-1;i>=0;i--)
if(g[i]>maxy)
maxy=g[i],ans[++tot][0]=i,ans[tot][1]=g[i];
for(int i=tot;i>1;i--)
printf("(%d,%d),",ans[i][0],ans[i][1]);
printf("(%d,%d)",ans[1][0],ans[1][1]);
}