A.George and Sleep
题意: 一个人知道几点睡醒的, 以及睡了多久, 问他是几点睡觉的
思路: 直接相减得到答案
代码:
- #include <bits/stdc++.h>
- using namespace std;
- int main()
- {
- int a,b,c,d;
- scanf("%d:%d", &a, &b);
- scanf("%d:%d", &c, &d);
- a -= c; b -= d;
- if(b <0) b += 60, a--;
- if(a < 0) a += 24;
- printf("%02d:%02d\n", a, b);
- return 0;
- }
- View Code
- B. George and Round
题意: 现在有 n(3000)个难度的题, 以及 m(3000)个已经有的难度的题, 可以用难度高的题去替代难度低的题, 问最少还需要在出几个题
思路: 设立两个指针, 分别指向两个数组, 遍历一下即可
代码:
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 3007;
- int a[maxn],b[maxn];
- int main()
- {
- int n, m;
- scanf("%d%d", &n, &m);
- for(int i = 1; i <= n; i++) {
- scanf("%d", &a[i]);
- }
- for(int i = 1; i <= m; i++) {
- scanf("%d", &b[i]);
- }
- int i = 1, j = 1;
- while(i <= n && j <= m) {
- if(a[i] <= b[j]) {
- i++; j++;
- }
- else {
- j++;
- }
- }
- // printf("%d %d\n", i, j);
- if(i == n + 1) printf("0\n");
- else printf("%d\n", n - i + 1);
- return 0;
- }
- View Code
- C. George and Number
题意: 集合中有一些数, 每次可以从集合中任意去两个数 a,b, 可以合并成 ab 一个数, 放回到集合中, 可以合并的条件是 a>b, 不满足的不能合并, 现在有集合中最后的一个数, 问集合中最初最多有多少个元素(集合中没有 0)
思路: 从左向右扫, 每次取出相邻的两个数 a,b 如果 a>=b, 表明可以是后两个数合并得到, 不然前面的整体只能是一个数, 不可拆分
代码:
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 1e5 + 7;
- char a[maxn];
- int ans;
- bool check(string x, string y)
- {
- if(y == "") {
- return false;
- }
- int lenx = x.size(), leny = y.size();
- if(lenx> leny) return true;
- if(lenx <leny) return false;
- for(int i = 0; i < lenx; i++) {
- if(x[i]> y[i]) return true;
- if(x[i] <y[i]) return false;
- }
- return true;
- }
- int main()
- {
- scanf("%s", a + 1);
- int len = strlen(a + 1);
- ans = 1;
- string b = "", c ="";
- for(int j = 1; j <= len; ) {
- // b = c; c = "";
- int i = j, ok;
- if(b == "") ok = 1;
- else ok = 0;
- // printf("aa i == %d ok == %d\n",i,ok);
- for(i = j; i <= len; i++) {
- if(ok) {
- b += a[i];
- if(a[i + 1] != '0') ok = 0;
- }
- else {
- c += a[i];
- if(a[i + 1] != '0') break;
- }
- }
- // printf("test i == %d",i);
- // cout << b << " " << c <<endl;
- if(check(b, c)) {
- ans ++;
- b += c; c = "";
- }
- else {
- ans = 1;
- b += c; c = "";
- }
- j = i + 1;
- }
- printf("%d\n",ans);
- return 0;
- }
- View Code
- D. George and Interesting Graph
题意: 有 n(500)个点 m(1000)条边的 DAG, 你可以每次添加一条边, 或者删除一个边, 问你最少操作几次可以是图满足:
有一个点 center, 它和每个点都有 (u,v),(v,u) 的两条边, 除 center 点之外, 其他的每个点的入度和出度都必须为 2
思路: 枚举中心点, 先把每个点都补上到中心点的两条边, 然后只剩下剩余 n - 1 个点的一个出度和入度, 建图跑二分匹配, 如果所有的点都能够匹配, 那么不需要加边和删边, 如果不能满足所有的点都能匹配, 需要删边和加一些边
代码:
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 507;
- int xx[1007], yy[1007];
- int mp[maxn][maxn];
- int mat[maxn], vis[maxn];
- int n, m;
- int dfs(int x)
- {
- for(int i = 1; i <= n; i++) {
- if(mp[x][i] && !vis[i]) {
- vis[i] = 1;
- if(mat[i] == -1 || dfs(mat[i])) {
- mat[i] = x;
- return 1;
- }
- }
- }
- return 0;
- }
- int solve(int x)
- {
- int ans = 0, cnt = 0;
- memset(mp,0,sizeof(mp));
- for(int i = 1; i <= m; i++) {
- mp[xx[i]][yy[i]] = 1;
- }
- for(int i = 1; i <= n; i++) {
- for(int j = 1; j <= n; j++) {
- if(mp[i][j] && (i != x && j != x)) {
- cnt++;
- }
- if(mp[i][j] == 0 &&(i == x || j == x)) {
- ans ++;
- }
- if(mp[i][j] && (i == x || j == x)){
- mp[i][j] = 0;
- }
- }
- }
- memset(mat,-1,sizeof(mat));
- int res = 0;
- for(int i = 1; i <= n; i++) {
- memset(vis,0,sizeof(vis));
- if(i == x) continue;
- if(dfs(i)) res++;
- }
- ans += n - 1 - res;
- ans += cnt - res;
- return ans;
- }
- int main()
- {
- scanf("%d%d", &n, &m);
- for(int i = 1; i <= m; i++) {
- scanf("%d%d", &xx[i], &yy[i]);
- }
- int ans = 0x3f3f3f3f;
- for(int i = 1; i <= n; i++) {
- ans = min (ans, solve(i));
- }
- printf("%d\n",ans);
- return 0;
- }
- View Code
- E. George and Cards
题意: 给出一个原始的数组 n(1e6), 以及删除后的数组 m(1e6), 每次可以选一个连续的 w 区间中删除, 区间中的最小值, 那么可以得到 w 的值, 问把原数组删除为第二个数组 m 可以得到最大的 w 价值为多少
思路: 最优的方法是从小到大删除, 这样获得的价值是最多的, 对于删除的每个数都选取最大的区间, 使最后的结果变大. 用一个 set 维护现在小于 i 的值的位置 (删除后数组中的数), 如果不在删除后的数组的数肯定在之前被删除了,, 在用一个树状数组维护区间[l,r] 中还剩几个数
代码:
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 1e6 + 7;
- int c[maxn];
- int id[maxn], vis[maxn];
- set<int> st;
- int lowbit(int x)
- {
- return x & -x;
- }
- void update(int n, int x, int val)
- {
- while(x <= n) {
- c[x] += val;
- x += lowbit(x);
- }
- }
- int query(int x)
- {
- int res = 0;
- while(x> 0) {
- res += c[x];
- x -= lowbit(x);
- }
- return res;
- }
- int main()
- {
- int n, k;
- scanf("%d%d", &n, &k);
- for(int i = 1; i <= n; i++) {
- int x;
- scanf("%d", &x);
- id[x] = i;
- update(n,i,1);
- }
- for(int i = 1; i <= k; i++) {
- int x;
- scanf("%d", &x);
- vis[x] = 1;
- }
- st.clear();
- st.insert(0); st.insert(n + 1);
- long long ans = 0;
- set<int>:: iterator it;
- for(int i = 1; i <= n; i++) {
- if(vis[i]) {
- st.insert(id[i]);
- }
- else {
- // it = upper_bound(st.begin(),st.end(),id[i]);
- it = st.upper_bound(id[i]);
- int r = *it - 1, l = *(--it);
- ans += query(r) - query(l);
- update(n,id[i],-1);
- }
- }
- printf("%lld\n",ans);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2970082.html