省赛刷题训练（二）
Values whose Sum is 0
UVA 1152
一个简单的二分题目，将a数组和b数组排个序，c数组和d数组排个序，然后对第二个数组进行二分查找。这里要找的是个数，所以upper_bound和lower_bound一相减然后加起来就是答案。
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
| #include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
int e[4001 * 4001],f[4001 * 4001];
int a[4001],b[4001],c[4001],d[4001];
int main()
{
int t, n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i = 0; i < n; ++i)
{
scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
}
int tot = 0;
for(int i = 0 ; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
e[tot++] = a[i] + b[j];
}
}
tot = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0 ;j < n; ++j)
{
f[tot++] = c[i] + d[j];
}
}
sort(e , e + tot);
sort(f , f + tot);
int sum = 0;
for(int i = 0; i < tot; ++i)
{
int m = upper_bound(f , f + tot , -e[i]) - lower_bound(f ,f + tot, -e[i]);
sum += m;
}
cout << sum << '\n';
if(t)
cout << '\n';
}
}
|
Humble numbers
HDU 1058
再一次做感觉思路清晰了挺多，第一次做没有理解本质，再一次做的时候，想到每一个数其实都可以通过它前面的数字乘积得到。2 3 5 7作为乘积的一个参数，另一个参数就是前面已经出现过的数字。比如8，通过2 * 4得到，2是一个因子，4是因为前边已经出现过了。
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
| #include <bits/stdc++.h>
using namespace std;
int a[10001];
int elect()
{
int aa = 1, bb = 1, cc = 1, dd = 1;
a[1] = 1;
for(int i = 2; i <= 5842; ++i)
{
a[i] = min(2 * a[aa], min(3 * a[bb], min(5 * a[cc] , 7 * a[dd])));
if(a[i] == 2 * a[aa])
aa++;
if(a[i] == 3 * a[bb])
bb++;
if(a[i] == 5 * a[cc])
cc++;
if(a[i] == 7 * a[dd])
dd++;
}
}
int main()
{
int n;
elect();
while(scanf("%d" ,&n) != EOF && n)
{
if(n % 10 == 1 && n % 100 != 11)
{
printf("The %dst humble number is %d.\n",n,a[n]);
}
else if(n % 10 == 2 && n % 100 != 12)
{
printf("The %dnd humble number is %d.\n",n,a[n]);
}
else if(n % 10 == 3 && n % 100 != 13)
{
printf("The %drd humble number is %d.\n",n,a[n]);
}
else{
printf("The %dth humble number is %d.\n",n,a[n]);
}
}
}
|
Train Problem I
HDU 1022
模拟火车的进出站。注意栈为空就要停止。
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
| #include <bits/stdc++.h>
using namespace std;
struct node{
string s;
}b[1001];
int main()
{
int n;
while(cin >> n)
{
stack<char>S;
string s,s1;
cin >> s;
cin >> s1;
int tot = 0;
int ans = 0;
for(int i = 0; i < s.size(); ++i)
{
S.push(s[i]);
b[ans++].s = "in";
while(s1[tot] == S.top())
{
S.pop();
tot++;
b[ans++].s = "out";
if(tot == s1.size() || S.empty())
break;
}
}
if(S.size() == 0)
{
cout << "Yes." << '\n';
for(int i = 0; i < ans; ++i)
{
cout << b[i].s << '\n';
}
cout << "FINISH" << '\n';
}
else{
cout << "No." << '\n';
cout << "FINISH" << '\n';
}
}
}
|
Prime Friend
HDU 3823
需要注意的是输入的A和B的大小关系不一定，素数打表范围要开的很大。第一次WA是因为没有搞懂什么是prime neighbor . 比如说输入2 和 4这两个数字，我们找到了1，因为1 + 2 和 1 + 4是素数，同时 3 和 5 还是素数相邻。 这样的话我们最终在枚举的时候，就枚举相邻的两个素数就行了，满足条件的话就输出对应的数字。而不是从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
46
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 20000001;
bool is[maxn];
int tot;
int prime[maxn];
void Prime()
{
memset(is,0,sizeof(is));
is[0] = is[1] = 1;
tot = 0;
for(int i = 2; i < maxn; ++i)
{
if(!is[i])
{
prime[tot++] = i;
for(int j = i + i; j < maxn; j += i)
{
is[j] = 1;
}
}
}
}
int main()
{
Prime();
int t,caser = 1,A,B;
cin >> t;
while(t--)
{
scanf("%d %d",&A,&B);
if(A > B)
swap(A,B);
printf("Case %d: ",caser++);
int flag = -1;
for(int i = 0; i + 1 < tot; ++i)
{
if(prime[i + 1] - prime[i] == B - A && prime[i] >= A)
{
flag = prime[i] - A;
break;
}
}
cout << flag << '\n';
}
}
|