题意：给出一个现在的时间和一个经过的时间，问开始时间是多少。
分析:直接模拟。
/**************************************** * File Name: 227a.cpp * Author: sky0917 * Created Time: 2014年01月30日 23:30:04 ****************************************/ #include <map> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; char s[10]; char t[10]; int main(){ int nh, ns, th, ts; int ah, as; while (scanf("%d:%d %d:%d",&nh,&ns,&th,&ts)!=EOF){ ah = nh - th; as = ns - ts; if (ns < ts){ as += 60; ah--; } if (ah < 0){ ah += 24; } printf("%02d:%02d\n",ah,as); } return 0; }
题意：给出n个数字的序列， a1,?a2,?...,?an ，表示要出的题数和难度要求，再给出m个数字序列，b1,?b2,?...,?bm
表示已经存在的题目的数目和难度，可以把现在出好的题目难度降低，问最少再出多少道可以满足要求。
分析：贪心，对于ai，尽量用最小的bj去满足它，如果不能满足，说明需要出一道题目。
/**************************************** * File Name: 227b.cpp * Author: sky0917 * Created Time: 2014年01月30日 23:46:17 ****************************************/ #include <map> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 3003; int n, m; int a[maxn]; int b[maxn]; int v[maxn]; int main(){ while (scanf("%d %d",&n,&m)!=EOF){ for (int i=0; i<n; i++){ scanf("%d",&a[i]); } for (int i=0; i<m; i++){ scanf("%d",&b[i]); } int pa=n-1, pb=m-1; int res = 0; for (int i=n-1; i>=0; i--){ for (int j=0; j<m; j++){ if (!v[j] && b[j] >= a[i]){ v[j] = 1; res++; break; } } } printf("%d\n",n-res); } return 0; }
D. George and Interesting Graph
题意：给出一个有n个点和m条边且无重边的有向图，每次操作可以删除一条边或者加上一条边，问最少多少次操作可以让图变成“有趣图”。
“有趣图”要求：
存在一个中心点u,满足图中任意一点v，存在 u->v 和 v->u,(包括u->u)
除了上述的点u，其它所有的点的入度和出度都为2.
分析：枚举点u，首先计算出让中心点满足要求要增加的边数。
对剩下的点拆点，变成v1,v2, v1作为左集合，v2作为右集合的点，
由于要求剩下的点出度和入度都等于2，且由于和中心点之间有u->v和v->u,
那么剩下的点只要满足拆点之后的图是完全匹配即可。
/**************************************** * File Name: 227d.cpp * Author: sky0917 * Created Time: 2014年01月31日 0:25:49 ****************************************/ #include <map> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 505; const int maxm = 2002; const int INF = 0x1f1f1f1f; struct node{ int to, next; }e[maxm]; int tot; int head[maxn]; void add(int s, int t){ e[tot].to = t; e[tot].next = head[s]; head[s] = tot++; } int n, m; int ind[maxn]; int oud[maxn]; int v[maxn]; int lik[maxn]; int g[maxn][maxn]; int sa; int tn; int find(int u){ for (int i=head[u]; i!=-1; i=e[i].next){ int k = e[i].to; if (!v[k] && k!=tn){ v[k] = 1; if (lik[k] == 0 || find(lik[k])){ lik[k] = u; return 1; } } } return 0; } int cal(int u){ tn = u; int sum = 0; int rs = sa - ind[u] - oud[u]; sum += 2*n-oud[u] - ind[u]; if (g[u][u]) rs++; else sum--; int tmp = 0; memset(lik, 0, sizeof(lik)); for (int i=1; i<=n; i++){ if (i != u){ memset(v, 0, sizeof(v)); if (find(i)){ tmp++; } } } sum += (rs-tmp) + (n-1-tmp); return sum; } void solve(){ int res = INF; for (int i=1; i<=n; i++){ int tmp = cal(i); res = min(res, tmp); } printf("%d\n",res); } int main(){ while (scanf("%d %d",&n,&m)!=EOF){ int a, b; memset(head, -1, sizeof(head)); tot = 0; sa = 0; for (int i=0; i<m; i++){ scanf("%d %d",&a,&b); g[a][b] = 1; sa++; oud[a]++; ind[b]++; add(a, b); } solve(); } return 0; }