拖了两天、不能再懒更多了

A.Buy a Shovel

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

C.Sanatorium

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("");
}

F.Tourist Reform

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);
}