A Numbers
Problem Description
There is a number N.You should output "YES" if N is a multiple of 2, 3 or 5,otherwise output "NO".
Input
There are multiple test cases, no more than 1000 cases.
For each case,the line contains a integer N.(0<N<1030)
Output
For each test case,output the answer in a line.
Sample Input
2
3
5
7
Sample Output
YES
YES
YES
NO
Source
题目类型：高精度取模
算法分析：直接按位取模即可，也可以直接判断
|
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 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e3 + 66; long long Mod (string a, long long b)//高精度a除以单精度b { long long d = 0; for (long long i = 0; i < a.size(); i++) d = (d * 10 + (a[i] - '0')) % b;//求出余数 return d; } int main() { // CFF; string n; while (cin >> n) { if (Mod (n, 2) == 0 || Mod (n, 3) == 0 || Mod (n, 5) == 0) puts ("YES"); else puts ("NO"); } return 0; } |
B Sum
Problem Description
There is a number sequence A1,A2....An,you can select a interval [l,r] or not,all the numbers Ai(l≤i≤r) will become f(Ai).f(x)=(1890x+143)mod10007.After that,the sum of n numbers should be as much as possible.What is the maximum sum?
Input
There are multiple test cases.
First line of each case contains a single integer n.(1≤n≤105)
Next line contains n integers A1,A2....An.(0≤Ai≤104)
It's guaranteed that ∑n≤106.
Output
For each test case,output the answer in a line.
Sample Input
2
10000 9999
5
1 9999 1 9999 1
Sample Output
19999
22033
Source
题目类型：最大连续子区间的和
算法分析：可以先将每个数变化之后的值减去当前值的差计算出来，最后问题就转化成求一个连续的区间使得差值的和最大，这个问题就是简单的最大连续子区间问题
|
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 79 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7FFFFFFF; const int MOD = 1e4 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 66; LL aa[maxn], bb[maxn], dp[maxn]; int main() { // CFF; int n; while (scanf ("%d", &n) != EOF) { LL res = 0; for (int i = 1; i <= n; i++) { scanf ("%lld", &aa[i]); res += aa[i]; bb[i] = (1890 * aa[i] + 143) % MOD - aa[i]; } dp[1] = bb[1]; for (int i = 2; i <= n; i++) { dp[i] = max (dp[i-1] + bb[i], bb[i]); } LL tt = -INF; for (int i = 1; i <= n; i++) tt = max (tt, dp[i]); printf ("%lld\n", max (res, res + tt)); } return 0; } |
C Array
Problem Description
Vicky is a magician who loves math. She has great power in copying and creating.
One day she gets an array {1}。 After that, every day she copies all the numbers in the arrays she has, and puts them into the tail of the array, with a signle '0' to separat.
Vicky wants to make difference. So every number which is made today (include the 0) will be plused by one.
Vicky wonders after 100 days, what is the sum of the first M numbers.
Input
There are multiple test cases.
First line contains a single integer T, means the number of test cases.(1≤T≤2∗103)
Next T line contains, each line contains one interger M. (1≤M≤1016)
Output
For each test case,output the answer in a line.
Sample Input
3
1
3
5
Sample Output
1
4
7
Source
题目类型：递推预处理+前缀和
算法分析：首先将每个序列的长度、和递推出来。然后对于每个查询M，找长度小于等于M的序列并将该序列的和累加，再加上高位多出来的长度(因为高位每个数都比低位的数对应+1)。最后若多出来的长度大于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 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 79 80 81 82 83 84 85 86 87 88 89 90 |
/************************************************* Author :supermaker Created Time :2015/12/6 1:34:42 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; LL len[66], sum[66]; void Init () { len[1] = sum[1] = 1; for (int i = 2; i < 66; i++) { len[i] = 2 * len[i-1] + 1; sum[i] = 2 * sum[i-1] + len[i-1] + 1; } } LL SS (LL val, LL pos) { while (val < len[pos]) pos--; LL res = sum[pos] + (val - len[pos]); if (val - len[pos] > 1) res += SS (val - len[pos] - 1, pos); return res; } int main() { //CFF; //CPPFF; Init (); int t; scanf ("%d", &t); while (t--) { LL val; scanf ("%I64d", &val); printf ("%I64d\n", SS (val, 60)); } return 0; } |
- « 上一篇：hdu1011
- hdu3555：下一篇 »