又是斐波那契数列??(HPUOJ 1471)
Description:
大家都知道斐波那契数列吧?斐波那契数列的定义是这样的: f0=0; f1=1; fi=fi−1+fi−2 现在给你一个数x,聪明的你一定知道这是斐波那契数列中的第几项。 (数据保证x一定有对应的项y,且 2 <= y < 1e4)
Input:
第一行一个整数T,表示测试组数。
之后的T行,每行一个数x
Output:
对于每个测试数据,输出一行表示数x是第几项
Sample Input:
2
2
5
Sample Output:
3
5
题目链接
递推算出1e4之内的所有斐波那契数列,建立map映射映射到下标即可。
我以为最大数据会很大还写了一个string大数加法斐波那契数列,结果TLE…
太蠢了…这道题目直接用unsigned long long就可以。
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
Finish_read = 1;
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') {
f = -1;
}
if (ch == EOF) {
return;
}
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
Finish_read = 1;
};
ull f[maxn];
map<ull, int> m;
int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
f[0] = 0;
f[1] = 1;
for (int i = 2; i < maxn; ++i) {
f[i] = f[i - 1] + f[i - 2];
m[f[i]] = i;
}
int t;
read(t);
for (int Case = 1; Case <= t; ++Case) {
ull x;
read(x);
cout << m[x] << endl;
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}
Simplest (HPUOJ 1473)
Description:
给你一段由数字0 - 9组成的字符串,请你输出它的最简自然数形式
Input:
第一行一个T,表示T组测试数据.(1 ≤ T ≤ 100)
每一组数据占一行,每一行一串字符 S. (1 ≤ strlen(S) ≤ 100000)
Output:
输出字符串对应的最简自然数形式
Sample Input:
2
2018722
02018722
Sample Output:
2018722
2018722
题目链接
字符串读取,把数字前面的0去掉即可,注意特判0。
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4+5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
Finish_read = 1;
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
if (ch == EOF)
return;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
Finish_read = 1;
};
int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
string str;
cin >> str;
bool flag = 0;
for (int i = 0; i < int(str.length()); ++i) {
if (str[i] != '0') {
flag = 1;
}
if (flag) {
cout << str[i];
}
}
if (!flag) {
cout << 0;
}
cout << endl;
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}
zz’s math problem Ⅰ (HPUOJ 1474)
Description:
有些人心如花木,皆向阳而生
|《剑来》
zz很喜欢数学,但是他又是一个数学渣,我们称这种生物叫做学渣,
zz又碰到了一个数学小问题,定义一个函数P (x)
例如:P (123) = 1! ∗ 2! ∗ 3! 现在需要找到的就是最大的大于等于x大的数z的函数值和x相等,
即P (z) = P (x) 当然z这个数不能包含1或者0
还请输出最大的符合要求数z(不一定比x大)
Input:
第1行输入T (1 ≤ T ≤ 20)组数据
第2行输入n(1 ≤ n ≤ 100),表示x的数字个数
第3行输入正整数 x
Output:
输出最大的z(数据保证x内含大于1的数,所以z必定有解)
Sample Input:
2
4
1234
3
555
Sample Output:
33222
555
题目链接
对每一个数进行分解,分解为非0、1数字的阶乘相乘,把所有分解的数字按照降序输出即可。
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 5;
const int mod = 1e5 + 3;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
Finish_read = 1;
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') {
f = -1;
}
if (ch == EOF) {
return;
}
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
Finish_read = 1;
};
int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int c[10];
int t;
read(t);
while (t--) {
mem(c, 0);
int n;
read(n);
char a;
while (n--) {
cin >> a;
if (a == '4') {
c[2] += 2;
c[3]++;
}
else if (a == '6') {
c[3]++;
c[5]++;
}
else if (a == '8') {
c[2] += 3;
c[7]++;
}
else if (a == '9') {
c[2]++;
c[3] += 2;
c[7]++;
}
else {
c[a - '0']++;
}
}
for (int i = 9; i > 1; --i) {
if (c[i]) {
while (c[i]--) {
cout << i;
}
}
}
cout << endl;
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}
zz’s math problem Ⅱ (HPUOJ 1475)
Description:
zz作为一个数学盲也认为这个数学题真的很简单, 学弟学妹们终于可以顺利签到了qwq
给出 N个正整数 a1,a2,...,aN
我们寻找一个这个表达式的最大的值 f(m)=(mmoda1)+(mmoda2)+...+(mmodaN)
mod的意思即为 A/B的余数
Input:
第 1行输入 T(1≤T≤20)组数据
第 2行输入 N(1≤N≤1e3)
第 3行输入 n个数字 ai(1≤ai≤1e5),
Output:
输出 f的最大值
Sample Input:
1
3
3 4 6
Sample Output:
10
题目链接
一定有一个数num使所有 num%ai=ai−1成立。
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
Finish_read = 1;
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') {
f = -1;
}
if (ch == EOF) {
return;
}
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
Finish_read = 1;
};
int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t;
read(t);
while (t--) {
int n;
read(n);
vector<int> a(n);
ll ans = 0;
for (int i = 0; i < n; ++i) {
read(a[i]);
ans += a[i] - 1;
}
printf("%lld\n", ans);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}
Operation on sequence (HPUOJ 1478)
Description:
井底之蛙,偶见圆月,便欣然忘忧。
—《剑来》
为什么总是要为难学弟学妹呢,zz并不想这样,zz决定把出一道简单的题来福利学弟学妹们。
一组下标从1开始的数组s,进行q次操作:
考虑两种操作:
1 r,将子序列a[1] 到 a[r] 从小到大排序
2 r,将子序列a[1] 到 a[r] 从大到小排序
Input:
第一行输入T组数据 T(1≤T≤10)
第一行输入两个数字 n,q(1≤n,q≤1e4)
第二行包含n个整数 ai(−1e9≤ai≤1e9) — 初始序列
然后q行表示m个操作. 第i行包含两个整数 op(1≤op≤2),r(1≤r≤n)
Sample Input:
2
3 1
1 2 3
2 2
4 2
1 2 4 3
2 3
1 2
Sample Output:
2 1 3
2 4 1 3
题目链接
从后往前查找,只进行范围比之前大的操作。
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
Finish_read = 1;
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') {
f = -1;
}
if (ch == EOF) {
return;
}
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
Finish_read = 1;
};
int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t;
read(t);
for (int Case = 1, n, q; Case <= t; ++Case) {
read(n); read(q);
vector<int> a(n);
for (int i = 0; i < n; ++i) {
read(a[i]);
}
vector<PII> operate(q);
for (int i = 0; i < q; ++i) {
read(operate[i].first);
read(operate[i].second);
}
stack<PII> op;
int temp = -1;
for (int i = q - 1; i >= 0; --i) {
if (operate[i].second > temp) {
op.push(operate[i]);
temp = operate[i].second;
}
}
while (!op.empty()) {
sort(a.begin(), a.begin() + op.top().second);
if (op.top().first == 2) {
reverse(a.begin(), a.begin() + op.top().second);
}
op.pop();
}
for (auto i : a) {
printf("%d ", i);
}
printf("\n");
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}
Operation on sequence (HPUOJ 1477)
Description:
真·签到题
输入一个表达式A op B op操作为′+′,′−′,′∗′ ,A,B为整数
Input:
第一行输入T 组数据 T(1≤T≤1e2)
第二行输入 AopB(−1e9≤A,B≤1e9) — 初始序列
Output:
输出表达式结果并换行即可
Sample Input:
1
1 + 1
Sample Output:
2
题目链接
emm…
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 5;
const int mod = 1e5 + 3;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
Finish_read = 1;
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') {
f = -1;
}
if (ch == EOF) {
return;
}
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
Finish_read = 1;
};
int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
ll a, b, ans;
char op;
cin >> a >> op >> b;
if (op == '+') {
ans = a + b;
}
else if (op == '-') {
ans = a - b;
}
else {
ans = a * b;
}
cout << ans << endl;
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}
又是划分问题 (HPUOJ 1480)
Description:
给你一个正整数n,将其划分,要求划分成的数必须是2的幂,有多少种划分方法??
结果可能很大,我们输出对1e9+7取模的结果
Input:
一个正整数n,代表要划分的数;
1<=n<=1e7
Output:
输出可划分的方法数
Sample Input:
15
67
Sample Output:
26
2030
Hint:
当n=6时,我们可以将其划分为
1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2
1 1 4
2 4
这6种划分方法
题目链接
和这道题一样
POJ 2229 HDU 2709 Sumsets
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e7 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
Finish_read = 1;
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') {
f = -1;
}
if (ch == EOF) {
return;
}
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
Finish_read = 1;
};
ll dp[maxn];
int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n;
while (~scanf("%d", &n)) {
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; ++i) {
if (i & 1) {
dp[i] = dp[i - 1];
dp[i] %= mod;
}
else {
dp[i] = dp[i - 2] + dp[i / 2];
dp[i] %= mod;
}
}
printf("%lld\n", dp[n]);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}
台阶问题 (HPUOJ 1479)
Description:
有 N 级的台阶,你一开始在底部,每次可以向上迈最多 K 级台阶(最少 1 级),问到达第 N 级台阶有多少种不同方式。
Input:
多组输入,两个正整数N(N ≤ 1000),K(K ≤ 100)。
Output:
一个正整数,为不同方式数,由于答案可能很大,你需要输出 ans mod 100003 后的结果。
Sample Input:
5 2
Sample Output:
8
题目链接
每次走 n阶楼梯可以选择先走一格,再走剩下 n−1格即为 f[n−1],或者先走 2格,再走剩下 n−2格即为 f[n−2],以此类推,把每种走法都加起来即为结果。
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 5;
const int mod = 1e5 + 3;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
Finish_read = 1;
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') {
f = -1;
}
if (ch == EOF) {
return;
}
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
Finish_read = 1;
};
int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n, k;
while (~scanf("%d %d", &n, &k)) {
vector<ll> f(n + 1, 0);
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
if (i - j >= 0) {
f[i] += f[i - j];
f[i] %= mod;
}
}
}
printf("%lld\n", f[n]);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}
括号括号 (HPUOJ 1476)
Description:
小明今年上大学,在大学里发现有很多同学都女朋友,两人整天都在一起腻歪,小明看到后感觉很孤单,现在,给你一行括号序列,你来判断一下其中的括号是否配对。
Input:
多组输入,每一组第一行输入一个数T(0<<N≤≤100),表示有T组测试数据。后面的T行输入多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),测试数据组数少于5组。数据保证S中只含有"[", “]”, “(”, “)” 四种字符
Output:
每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出No。
Sample Input:
3
[(])
(])
([])
Sample Output:
No
No
Yes
题目链接
栈的入门题目括号匹配。
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f40;
const int maxn = 1e4 + 5;
const int mod = 1e5 + 3;
const double eps = 2e-8;
const double pi = asin(2.0) * 2;
const double e = 3.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
Finish_read = 1;
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') {
f = -1;
}
if (ch == EOF) {
return;
}
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
Finish_read = 1;
};
int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n;
while (cin >> n) {
string str;
bool flag;
while (n--) {
cin >> str;
flag = 1;
stack<char> a;
for (int i = 0; i < int(str.length()); ++i) {
if (str[i] == '(' || str[i] == '[') {
a.push(str[i]);
}
else {
if (a.empty()) {
flag = 0;
break;
}
else {
if (str[i] == ')') {
if (a.top() == '(') {
a.pop();
}
else {
flag = 0;
break;
}
}
else {
if (str[i] == ']') {
if (a.top() == '[') {
a.pop();
}
else {
flag = 0;
break;
}
}
}
}
}
}
if (flag && a.empty()) {
printf("Yes\n");
}
else {
printf("No\n");
}
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}