AOJ/搜索与递归及分治法习题集
ALDS1_4_A-LinearSearch.
Description:
You are given a sequence of n integers S and a sequence of different q integers T. Write a program which outputs C, the number of integers in T which are also in the set S.
Input:
In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers are given.
Output:
Print C in a line.
Constraints:
n ≤ 10000
q ≤ 500
0 ≤ an element in S ≤ 109
0 ≤ an element in T ≤ 109
SampleInput1:
5
1 2 3 4 5
3
3 4 1
SampleOutput1:
3
SampleInput2:
3
3 1 2
1
5
SampleOutput2:
0
Codes:
//#define LOCAL
#include <cstdio>
int search(int A[], int n, int key) {
int i = 0; A[n] = key;
while(A[i] != key) ++i;
return i!=n;
}
int main()
{
#ifdef LOCAL
freopen("E:\\Temp\\input.txt", "r", stdin);
freopen("E:\\Temp\\output.txt", "w", stdout);
#endif
int i, n, q, key, sum = 0, A[10010];
scanf("%d", &n);
for(i=0; i<n; ++i) scanf("%d", &A[i]);
scanf("%d", &q);
for(i=0; i<q; ++i) {
scanf("%d", &key);
if(search(A, n, key)) ++sum;
}
printf("%d\n", sum);
return 0;
}
ALDS1_4_B-BinarySearch.
Description:
You are given a sequence of n integers S and a sequence of different q integers T. Write a program which outputs C, the number of integers in T which are also in the set S.
Input:
In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers are given.
Output:
Print C in a line.
Constraints:
Elements in S is sorted in ascending order
n ≤ 100000
q ≤ 50000
0 ≤ an element in S ≤ 109
0 ≤ an element in T ≤ 109
SampleInput1:
5
1 2 3 4 5
3
3 4 1
SampleOutput1:
3
SampleInput2:
3
1 2 3
1
5
SampleOutput2:
0
Codes:
//#define LOCAL
#include <cstdio>
int n, A[1000010];
int binarySearch(int key) {
int left = 0, right = n;
while(left < right) {
int mid = (left+right)/2;
if(key > A[mid]) left = mid+1;
else if(key == A[mid]) return 1;
else right = mid;
}
return 0;
}
int main()
{
#ifdef LOCAL
freopen("E:\\Temp\\input.txt", "r", stdin);
freopen("E:\\Temp\\output.txt", "w", stdout);
#endif
int i, q, key, sum = 0;
scanf("%d", &n);
for(i=0; i<n; ++i) scanf("%d", &A[i]);
scanf("%d", &q);
for(i=0; i<q; ++i) {
scanf("%d", &key);
if(binarySearch(key)) ++sum;
}
printf("%d\n", sum);
return 0;
}
ALDS1_4_C-Dictionary.
Description:
Your task is to write a program of a simple dictionary which implements the following instructions:
insert str: insert a string str in to the dictionary
find str: if the distionary contains str, then print 'yes', otherwise print 'no'
Input:
In the first line n, the number of instructions is given. In the following n lines, n instructions are given in the above mentioned format.
Output:
Print yes or no for each find instruction in a line.
Constraints:
A string consists of 'A', 'C', 'G', or 'T'
1 ≤ length of a string ≤ 12
n ≤ 1000000
SampleInput1:
5
insert A
insert T
insert C
find G
find A
SampleOutput1:
no
yes
SampleInput2:
13
insert AAA
insert AAC
insert AGA
insert AGG
insert TTT
find AAA
find CCC
find CCC
insert CCC
find CCC
insert T
find TTT
find T
SampleOutput2:
yes
no
no
yes
yes
yes
Codes:
//#define LOCAL
#include <cstdio>
#include <cstring>
#define M 1046527
#define NIL (-1)
#define L 14
char H[M][L];
int getChar(char ch) {
if(ch == 'A') return 1;
else if(ch == 'C') return 2;
else if(ch == 'G') return 3;
else if(ch == 'T') return 4;
else return 0;
}
long long getKey(char str[]) {
int len = strlen(str);
long long sum = 0, p = 1, i;
for(i=0; i<len; ++i) {
sum += p*(getChar(str[i]));
p *= 5;
}
return sum;
}
int h1(int key) {return key%M;}
int h2(int key) {return 1+(key%(M-1));}
int find(char str[]) {
long long key, i, h;
key = getKey(str);
for(i=0; ; ++i) {
h = (h1(key)+i*h2(key))%M;
if(strcmp(H[h], str) == 0) return 1;
else if(strlen(H[h]) == 0) return 0;
}
return 0;
}
int insert(char str[]) {
long long key, i, h;
key = getKey(str);
for(i=0; ; ++i) {
h = (h1(key)+i*h2(key))%M;
if(strcmp(H[h], str) == 0) return 1;
else if(strlen(H[h]) == 0) {
strcpy(H[h], str);
return 0;
}
}
return 0;
}
int main()
{
#ifdef LOCAL
freopen("E:\\Temp\\input.txt", "r", stdin);
freopen("E:\\Temp\\output.txt", "w", stdout);
#endif
int i, n, h;
char str[L], com[9];
for(i=0; i<M; ++i) H[i][0] = '\0';
scanf("%d", &n);
for(i=0; i<n; ++i) {
scanf("%s %s", com, str);
if(com[0] == 'i') insert(str);
else {
if(find(str)) printf("yes\n");
else printf("no\n");
}
}
return 0;
}
ALDS1_4_D-Allocation.
Codes:
#include <iostream>
using namespace std;
#define MAX 100000
typedef long long llong;
int n, k; llong T[MAX];
int check(llong P) {
int i = 0;
for(int j=0; j<k; ++j) {
llong s = 0;
while(s+T[i] <= P) {
s += T[i++];
if(i == n) return n;
}
}
return i;
}
int solve() {
llong mid, left = 0, right = 1000000000;
while(right-left > 1) {
mid = (left+right)/2;
int v = check(mid);
if(v >= n) right = mid;
else left = mid;
}
return right;
}
int main()
{
cin >> n >> k;
for(int i=0; i<n; ++i) cin >> T[i];
cout << solve() << endl;
}
ALDS1_5_A-ExhaustiveSearch.
Description:
Write a program which reads a sequence A of n elements and an integer M, and outputs "yes" if you can make M by adding elements in A, otherwise "no". You can use an element only once.
You are given the sequence A and q questions where each question contains Mi.
Input:
In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers (Mi) are given.
Output:
For each question Mi, print yes or no.
Constraints:
n ≤ 20
q ≤ 200
1 ≤ elements in A ≤ 2000
1 ≤ Mi ≤ 2000
SampleInput:
5
1 5 7 10 21
8
2 4 17 8 22 21 100 35
SampleOutput:
no
no
yes
yes
yes
yes
no
no
Codes:
//#define LOCAL
#include <cstdio>
int n, A[50];
int solve(int i, int k) {
if(!k) return 1;
if(i >= n) return 0;
return solve(i+1, k)||solve(i+1, k-A[i]);
}
int main()
{
#ifdef LOCAL
freopen("E:\\Temp\\input.txt", "r", stdin);
freopen("E:\\Temp\\output.txt", "w", stdout);
#endif
int i, q, k;
scanf("%d", &n);
for(i=0; i<n; ++i) scanf("%d", &A[i]);
scanf("%d", &q);
for(i=0; i<q; ++i) {
scanf("%d", &k);
if(solve(0, k)) printf("yes\n");
else printf("no\n");
}
return 0;
}
ALDS1_5_C-KochCurve.
Description:
Write a program which reads an integer n and draws a Koch curve based on recursive calles of depth n.
The Koch curve is well known as a kind of fractals.
You can draw a Koch curve in the following algorithm:
Divide a given segment (p1, p2) into three equal segments.
Replace the middle segment by the two sides of an equilateral triangle (s, u, t) of the same length as the segment.
Repeat this procedure recursively for new segments (p1, s), (s, u), (u, t), (t, p2).
You should start (0, 0), (100, 0) as the first segment.
Input:
An integer n is given.
Output:
Print each point (x, y) of the Koch curve. Print a point in a line. You should start the point(0, 0), which is the endpoint of the first segment and end with the point (100, 0), the other endpoint so that you can draw the Koch curve as an unbroken line. Each solution should be given as a decimal with an arbitrary number of fractional digits, and with an absolute error of at most 10-4.
Constraints:
0 ≤ n ≤ 6
SampleInput1:
1
SampleOutput1:
0.00000000 0.00000000
33.33333333 0.00000000
50.00000000 28.86751346
66.66666667 0.00000000
100.00000000 0.00000000
SampleInput2:
2
SampleOutput2:
0.00000000 0.00000000
11.11111111 0.00000000
16.66666667 9.62250449
22.22222222 0.00000000
33.33333333 0.00000000
38.88888889 9.62250449
33.33333333 19.24500897
44.44444444 19.24500897
50.00000000 28.86751346
55.55555556 19.24500897
66.66666667 19.24500897
61.11111111 9.62250449
66.66666667 0.00000000
77.77777778 0.00000000
83.33333333 9.62250449
88.88888889 0.00000000
100.00000000 0.00000000
Codes:
//#define LOCAL
#include <cstdio>
#include <cmath>
struct Point{ double x, y;};
void koch(int n, Point a, Point b) {
if(!n) return ;
Point s, t, u;
double th = M_PI*60.0/180.0;
s.x = (2.0*a.x+1.0*b.x)/3.0;
s.y = (2.0*a.y+1.0*b.y)/3.0;
t.x = (1.0*a.x+2.0*b.x)/3.0;
t.y = (1.0*a.y+2.0*b.y)/3.0;
u.x = (t.x-s.x)*cos(th)-(t.y-s.y)*sin(th)+s.x;
u.y = (t.x-s.x)*sin(th)+(t.y-s.y)*cos(th)+s.y;
koch(n-1, a, s);
printf("%.8f %.8f\n", s.x, s.y);
koch(n-1, s, u);
printf("%.8f %.8f\n", u.x, u.y);
koch(n-1, u, t);
printf("%.8f %.8f\n", t.x, t.y);
koch(n-1, t, b);
}
int main()
{
#ifdef LOCAL
freopen("E:\\Temp\\input.txt", "r", stdin);
freopen("E:\\Temp\\output.txt", "w", stdout);
#endif
int n; Point a, b;
scanf("%d", &n);
a.x = 0, a.y = 0, b.x = 100, b.y = 0;
printf("%.8f %.8f\n", a.x, a.y);
koch(n, a, b);
printf("%.8f %.8f\n", b.x, b.y);
return 0;
}最新文章
- 【Java每日一题】20161215
- 基于jquery的bootstrap在线文本编辑器插件Summernote
- JDBC相关的类介绍
- bash快捷建
- oracle数据库的乱码问题解决方案
- oracle错误（ORA-01691），单个数据文件大小限制问题
- Ubuntu下输入su - [root]后提示“su:认证失败”
- Javascript 插件统一的实现步骤
- 谈 DevOps 自动化时，也应该考虑到 SOX 等法案
- iOS学习之根据文本内容动态计算文本框高度的步骤
- Spring Ldap 的增删改查
- 《转载》常用算法经典代码（C++版）
- revel框架教程之权限控制
- 其他应用和技巧-用JS实现的抽奖程序
- 在Ubuntu上安装PHPStudy组件
- 二、IPC机制
- Python3-高阶函数、闭包
- java web(七): mybatis的动态sql和mybatis generator自动生成pojo类和映射文件
- Linux后台开发工具箱
- git+jenkins在windows机器上新建一个slave节点【转载】