A.Ilya and Bank Account
Ilya得到了一个礼物，可以在删掉银行账户最后和倒数第二位的数字（账户有可能是负的），也可以不做任何处理。
//codeforces 313A //2013-05-31-13.47 #include <stdio.h> #include <algorithm> using namespace std; int main() { int n; scanf("%d", &n); if (n) { if (n >= 0) { printf("%d\n", n); } else { n = -n; int a = n/10; int b = n/100 * 10 + n%10; printf("%d\n", -min(a, b)); } } return 0; }
B.Ilya and Queries
给你一个字符串，然后有M个询问，寻问的是从l到r之间有多少对字符串满足 s[i] == s[i+1]。
简单的树状数组题目
//codeforces 313 B //2013-05-31-14.15 #include <stdio.h> #include <string.h> const int maxn = 100005; char s[maxn]; int a[maxn]; int n; inline int lowbit(int x) { return x&-x; } void update(int x) { while (x <= n) { a[x] += 1; x += lowbit(x); } } int getsum(int x) { int sum = 0; while (x) { sum += a[x]; x -= lowbit(x); } return sum; } int main() { while (scanf("%s", s) != EOF) { int m, l, r; n = strlen(s); memset(a, 0, sizeof(a)); for (int i = 0; i < n-1; i++) { if (s[i] == s[i+1]) update(i+1); } scanf("%d", &m); while (m--) { scanf("%d %d", &l, &r); printf("%d\n", getsum(r-1) - getsum(l-1)); } } return 0; }
C.Ilya and Matrix
给你4^n个数，让你放进那个2^n * 2^n的矩阵里让这个矩阵beauty值最大，beauty值的计算方法题里说了。。。
The beauty of a 2n × 2n-sized matrix is an integer, obtained by the following algorithm:
Find the maximum element in the matrix. Let's denote it as m.
If n = 0, then the beauty of the matrix equals m. Otherwise, a matrix can be split into 4 non-intersecting 2n - 1 × 2n - 1-sized submatrices, then the beauty of the matrix equals the sum of number m and other four beauties of the described submatrices.
As you can see, the algorithm is recursive
贪心吧，贪心就行，排个序解决了
//codeforces 313c //2013-06-03-15.55 #include <stdio.h> #include <algorithm> using namespace std; const int maxn = 2*1000006; __int64 a[maxn]; bool cmp(int x, int y) { return x > y; } int main() { int n; while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; i++) scanf("%I64d", &a[i]); sort(a+1, a+n+1, cmp); int x = n; __int64 ans = 0; while (x) { for (int i = 1; i <= x; i++) ans += a[i]; x /= 4; } printf("%I64d\n", ans); } return 0; }
D.Ilya and Roads
E.Ilya and Two Numbers
