Note
In the first sample George went to bed at "00:06". Note that you should print the time only in the format "00:06".
That‘s why answers "0:06", "00:6" and others will be considered
incorrect.
In the second sample, George went to bed yesterday.
In the third sample, George didn‘t do to bed at all.
A:水题，直接模拟时间即可。
#include <stdio.h>
#include <string.h>
int hh, mm;
int hhh, mmm;
int main() {
scanf("%d%*c%d", &hh, &mm);
scanf("%d%*c%d", &hhh, &mmm);
int ansh, ansm;
if (mm >= mmm) ansm = mm - mmm;
else {ansm = mm + 60 - mmm; hh--;}
if (hh >= hhh) ansh = hh - hhh;
else ansh = hh + 24 - hhh;
printf("%02d:%02d\n", ansh, ansm);
return 0;
}
George decided to prepare a Codesecrof round, so he has prepared m problems for the round. Let‘s number the problems with integers1 through m.
George estimates the i-th problem‘s complexity by integer bi.
To make the round good, he needs to put at least n problems there. Besides, he needs to
have at least one problem with complexity exactly a1,
at least one with complexity exactly a2,
..., and at least one with complexity exactly an.
Of course, the round can also have problems with other complexities.
George has a poor imagination. It‘s easier for him to make some already prepared problem simpler than to come up with a new one and prepare it. George is magnificent at simplifying problems. He can simplify any already prepared problem with complexity c to
any positive integer complexity d (c?≥?d),
by changing limits on the input data.
However, nothing is so simple. George understood that even if he simplifies some problems, he can run out of problems for a goodround. That‘s why he decided to find out the minimum number of problems
he needs to come up with in addition to the m he‘s prepared in order to make a good round. Note that George can come up with a new problem of any complexity.
Output
Print a single integer — the answer to the problem.
Note
In the first sample the set of the prepared problems meets the requirements for a good round.
In the second sample, it is enough to come up with and prepare two problems with complexities 2 and 3 to
get a good round.
In the third sample it is very easy to get a good round if come up with and prepare extra problems with complexities: 2,?3,?4.
B题：先两个数组排序，把能用的B用完，看还剩多少个A没用。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1000005;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
int n, m, i, j;
int a[3005], b[3005];
int Max = 0;
int main() {
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
for (i = 0; i < m; i++)
scanf("%d", &b[i]);
sort(a, a + n);
sort(b, b + m);
int ans = 0;
int l = 0, r = 0;
while (l < n && r < m) {
if (a[l] <= b[r]) {
l++; r++;
}
else {
r++;
}
}
ans = n - l;
printf("%d\n", ans);
return 0;
}
George is a cat, so he really likes to play. Most of all he likes to play with his array of positive integers b. During the game, George modifies the array
by using special changes. Let‘s mark George‘s current array as b1,?b2,?...,?b|b| (record |b| denotes
the current length of the array). Then one change is a sequence of actions:
-
Choose two distinct indexes i and j (1?≤?i,?j?≤?|b|; i?≠?j),
such that bi?≥?bj.
-
Get number v?=?concat(bi,?bj),
where concat(x,?y) is a number obtained by adding number y to
the end of the decimal record of number x. For example, concat(500,?10)?=?50010, concat(2,?2)?=?22.
-
Add number v to the end of the array. The length of the array will increase by one.
-
Remove from the array numbers with indexes i and j.
The length of the array will decrease by two, and elements of the array will become re-numbered from 1 to current length of the array.
George played for a long time with his array b and received from array b an
array consisting of exactly one number p. Now George wants to know: what is the maximum number of elements array b could
contain originally? Help him find this number. Note that originally the array could contain only positive integers.
Output
Print an integer — the maximum number of elements array b could contain originally.
C题：贪心，从后面往前推，如果可以分离就直接分离ans++，不行就在继续添加数字。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 100005;
char seq[N];
int i, j;
char save[N];
int sn = 0;
int len;
bool judge(int len) {
if (i > sn) return true;
if (i < sn) return false;
if (i == sn) {
for (int j = sn - 1; j >= 0; j--) {
if (seq[sn - 1 - j] < save[j]) return false;
}
}
return true;
}
int main() {
int ans = 1;
scanf("%s", seq);
len = strlen(seq);
for (i = len - 1; i >= 0; i--) {
if (seq[i] != ‘0‘) {
save[sn++] = seq[i];
if (judge(i)) {
ans++;
sn = 0;
}
}
else {
save[sn++] = seq[i];
}
}
printf("%d\n", ans);
return 0;
}
George loves graphs. Most of all, he loves interesting graphs. We will assume that a directed graph is interesting, if it meets the following criteria:
-
The graph doesn‘t contain any multiple arcs;
-
There is vertex v (we‘ll call her the center), such that for any vertex of graph u,
the graph contains arcs (u,?v) and (v,?u).
Please note that the graph also contains loop (v,?v).
-
The outdegree of all vertexes except for the center equals two and the indegree of all vertexes except for the center equals two.
The outdegree of vertex u is the number of arcs that go out of u,
the indegree of vertex u is the number of arcs that go in u.
Please note that the graph can contain loops.
However, not everything‘s that simple. George got a directed graph of n vertices and m arcs
as a present. The graph didn‘t have any multiple arcs. As George loves interesting graphs, he wants to slightly alter the presented graph and transform it into an interesting one. In one alteration he can either remove an arbitrary existing arc from the graph
or add an arbitrary arc to the graph.
George wonders: what is the minimum number of changes that he needs to obtain an interesting graph from the graph he‘s got as a present? Help George and find the answer to the question.
Output
Print a single integer — the answer to George‘s question.
D题：二分图匹配，先枚举中心点，然后剩余点去求最大匹配数。就可以找出需要添加和删除的边。
代码：
#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define INF 0x3f3f3f3f
const int N = 505;
int n, m, g[N][N], ind[N], out[N], match[N], vis[N];
bool find(int u, int i) {
for (int j = 1; j <= n; j++) {
if (u == j || vis[j] || !g[i][j]) continue;
vis[j] = 1;
if (match[j] == -1 || find(u, match[j])) {
match[j] = i;
return true;
}
}
return false;
}
int cal(int u) {
int ans = 0;
memset(match, -1, sizeof(match));
for (int i = 1; i <= n; i++) {
if (i == u) continue;
memset(vis, 0, sizeof(vis));
if (find(u, i)) ans++;
}
return ans;
}
int solve(int u) {
int uedge = ind[u] + out[u] - g[u][u];//与u点相连的边数
int ans = 2 * n - 1 - uedge;
int Max = cal(u);
ans += m - uedge - Max; //需要删除的边数
ans += n - 1 - Max; //需要添加的边数
return ans;
}
int main() {
scanf("%d%d", &n, &m);
int x, y, ans = INF, mm = m;
while (mm--) {
scanf("%d%d", &x, &y);
g[x][y] = 1;
ind[y]++;
out[x]++;
}
for (int i = 1; i <= n; i++) {
int t = solve(i);
ans = min(ans, t);
}
printf("%d\n", ans);
return 0;
}
E题：二分。树状数组。先保留数字位置，然后优先从小的开始move，计算区间长度的时候利用树状数组去计算并维护。
代码：
#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int N = 1000005;
#include <set>
using namespace std;
#define INF 0x3f3f3f3f
int n, k, v[N], vis[N], i, bit[N];
void Insert(int x, int v) {
while (x <= n) {
bit[x] += v;
x += (x&(-x));
}
}
int Sum(int x) {
int ans = 0;
while (x > 0) {
ans += bit[x];
x -= (x&(-x));
}
return ans;
}
__int64 solve() {
__int64 ans = 0;
set<int> s;
s.insert(0);
s.insert(n + 1);
for (int i = 1; i <= n; i++) {
if (vis[i]) {
s.insert(v[i]);
}
else {
set<int>::iterator it = s.lower_bound(v[i]);
int r = *it - 1;
int l = *(--it);
ans += Sum(r) - Sum(l);
Insert(v[i], -1);
}
}
return ans;
}
int main() {
scanf("%d%d", &n, &k);
int num;
for (i = 1; i <= n; i++) {
scanf("%d", &num);
v[num] = i;
Insert(i, 1);
}
for (i = 1; i <= k; i++) {
scanf("%d", &num);
vis[num] = 1;
}
printf("%I64d\n", solve());
return 0;
}
