Codeforces Round #377 (Div. 2) Analyses
拖了两天、不能再懒更多了
Problem:你有∞多的10和一个r∈[0, 9]以及一个物品的价格k,问你买多少该物品可以恰好不用找钱
Analysis:不用找钱 <=> 10的倍数或者10的倍数+r,模拟即可
Tags:Implementation
B.Cormen --- The Best Friend Of a Man
Problem:给定一串长度为n的序列,要求相邻两项之和不得小于k,支持修改,问最小代价
Analysis:贪心显然成立(改变第二天对后继的更优),所以模拟修改的过程即可。然而坑点在于n == 1的情况,是不用特判的
Tags:Greedy
Problem:有个人在医院里不知道呆了几天,只知道自己吃的早饭,中饭,晚饭数量,问你他最少没吃多少餐
Analysis:知道最小天数就可以反向推出他最少没吃多少餐了,而前者显然是max{ breakfast, dinner, supper }-1;
Tags:Math, Greedy
D.Exams
Problem:n天内需要考m门试题,每天可以选择考试(当天只能考当天提供的考试),复习,或者什么都不做、求最小需要的天数
Analysis:二分显然,重点在于如何判断。注意到最后一天其实只能考试了,然后逆推统计复习天数判断是否可行就可以了
Tags:Binary search, Greedy
#include<cstdio> #include<cstring> #include<algorithm> //#include<iostream> #include<cmath> #include<queue> #include<map> #include<string> #include<vector> using namespace std; #define INF 2000000000 #define Clear(x, Num) memset(x, Num, sizeof(x)) #define Dig(x) ((x>='0') && (x<='9')) #define Neg(x) (x=='-') #define G_c() getchar() #define Maxn 100010 typedef long long ll; int n, m, d[Maxn], a[Maxn]; bool Pass[Maxn]; inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); } inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; } //inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; } inline bool Judge(int Day) { Clear(Pass, 0); int Cnt=0; for (int i=Day; i>=1; i--) if ((d[i]) && (!Pass[d[i]])) Pass[d[i]]=1, Cnt+=a[d[i]]; else Cnt--, Cnt=max(Cnt, 0); if (Cnt) return 0; for (int i=1; i<=m; i++) if (!Pass[i]) return 0; return 1; } int main() { read(n); read(m); for (int i=1; i<=n; i++) read(d[i]); for (int i=1; i<=m; i++) read(a[i]); int l=1, r=n; while (l<=r) { int mid=(l+r)>>1; if (Judge(mid)) r=mid-1; else l=mid+1; } if (Judge(l)) printf("%d\n", l); else puts("-1"); }
E.Sockets
Problem:有n个电脑需要供电,你有m个电源,和∞多个适配器,每个适配器可以使某个电源电压减半,供电必要的条件为电脑的电压<=电源电压,问最大所连接的电脑数和最小需要的适配器的数量
Analysis:贪心,将电源排序,如果一个小的电源匹配不了的话,那么用更大的加适配器就是浪费,所以从电源电压小的开始匹配,由于数据范围,需要用map来保存。(还有一种优先队列的模拟方法)
Tags:Greedy, Sorting, Implementation
#include<cstdio> #include<cstring> #include<algorithm> //#include<iostream> #include<cmath> #include<queue> #include<map> #include<string> #include<vector> using namespace std; #define INF 2000000000 #define Clear(x, Num) memset(x, Num, sizeof(x)) #define Dig(x) ((x>='0') && (x<='9')) #define Neg(x) (x=='-') #define G_c() getchar() #define Maxn 200010 typedef long long ll; struct Socket { int s, id; }s[Maxn]; int n, m, x, Apt, Match; int Link[Maxn], Ans[Maxn]; map<int, vector<int > > Com; inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); } inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; } //inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; } inline bool cmp(const Socket &a, const Socket &b) { return (a.s<b.s) || ((a.s==b.s) && (a.id<b.id)); } int main() { read(n); read(m); for (int i=1; i<=n; i++) read(x), Com[x].push_back(i); for (int i=1; i<=m; i++) read(s[i].s), s[i].id=i; sort(s+1, s+m+1, cmp); for (int i=1; i<=m; i++) { int Current=s[i].s, Cnt=0; while (1) { if (Com[Current].size()!=0) { int Cp=Com[Current][Com[Current].size()-1]; Com[Current].pop_back(); Match++, Apt+=Cnt; Link[Cp]=s[i].id, Ans[s[i].id]=Cnt; break; } if (Current==1) break; Cnt++, Current=(Current+1)>>1; } } printf("%d %d\n", Match, Apt); for (int i=1; i<=m; i++) printf("%d ", Ans[i]); puts(""); for (int i=1; i<=n; i++) printf("%d ", Link[i]); puts(""); }
Problem:给你一个无向无环图,让你确定每条边的方向,使得所有点能到达的点的个数种最小值的最大值
Analysis:首先想到二分+缩点,但手推几个图后发现其实答案就是max{ V’ },V’为某个强连通块中的点的个数,那么两遍Tarjan即可,第一遍寻找该节点,第二遍模拟建图
Tags:Dfs and similar, Algorithm
#include<cstdio> #include<cstring> #include<algorithm> //#include<iostream> #include<cmath> #include<queue> #include<map> #include<string> #include<vector> using namespace std; #define INF 2000000000 #define Clear(x, Num) memset(x, Num, sizeof(x)) #define Dig(x) ((x>='0') && (x<='9')) #define Neg(x) (x=='-') #define G_c() getchar() #define Maxn 400010 #define Maxe 800010 typedef long long ll; struct Answer { int u, v; }Link[Maxe]; int n, m, x, y, Res, Cnv, Index, dfn[Maxn], low[Maxn], Stack[Maxe], Point; int To[Maxe], Id[Maxe], Head[Maxn], Cnt, Next[Maxe]; inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); } inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; } inline void Insert(int u, int v, int w) { To[Cnt]=v; Id[Cnt]=w; Next[Cnt]=Head[u]; Head[u]=Cnt++; } inline void Init_Tarjan() { for (int i=1; i<=n; i++) dfn[i]=0; Cnv=Index=Res=0; } inline void Tarjan(int u, int father) { dfn[u]=low[u]=++Index; Stack[++Cnv]=u; for (int p=Head[u]; p!=-1; p=Next[p]) { int v=To[p], pos=Id[p]; if (v==father) continue; if (!dfn[v]) { Link[pos].u=v, Link[pos].v=u; Tarjan(v, u); low[u]=min(low[u], low[v]); } else Link[pos].u=u, Link[pos].v=v, low[u]=min(low[u], dfn[v]); } if (dfn[u]==low[u]) { int Tmp, Count=0; do { Tmp=Stack[Cnv--]; Count++; }while (Tmp!=u); if (Res<Count) Res=Count, Point=u; } } /*inline bool Judge(int Current) { for (int i=1; i<=n; i++) dfn[i]=0; Cnv=Index=Res=0; Tarjan(1, -1); return (Res>=Current); }*/ int main() { read(n); read(m); Clear(Head, -1); Cnt=0; for (int i=1; i<=m; i++) read(x), read(y), Insert(x, y, i), Insert(y, x, i); /*int l=1, r=n; while (l<=r) { int mid=(l+r)>>1; if (Judge(mid)) l=mid+1; else r=mid-1; }*/ Init_Tarjan(); Tarjan(1, -1); printf("%d\n", Res); Init_Tarjan(); Tarjan(Point, -1); for (int i=1; i<=m; i++) printf("%d %d\n", Link[i].u, Link[i].v); }