Fan_HD's Blog

#include <cstdio>

using namespace std;
int N, K, V[100005];
inline bool Ckd(long long T)
{
	int Sc = 0;
	long long C = T;
	for (int i = 1; i <= N; i ++, C += T)
	{
		if (C <= V[i]) C = 0;
		else ++ Sc, C = C - V[i];
	}
	return Sc + Sc > N;
}
int main()
{
	scanf("%d%d", &N, &K);
	for (int i = 1; i <= N; i ++) scanf("%d", V + i);
	int L = 1, R = K + 1, M;
	while (L < R - 1)
	{
		M = (L + R) >> 1;
		Ckd(M) ? R = M : L = M;
	}
	printf("%d\n", R);
	return 0;
}

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
char Map[102][102];
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int Sp[102][102];
int Sx, Sy, N, M;
queue<pair<int, int> > Q;
inline bool check(int x, int y)
{
	return x >= 1 && x <= N && y >= 1 && y <= M && Map[x][y] != '#' && Map[x][y] != 'P' && !Sp[x][y];
}
int main()
{
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i ++) scanf("%s", Map[i] + 1);
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= M; j ++)
			if (Map[i][j] == 'H')
			{
				Sx = i, Sy = j;
				break;
			}
	Sp[Sx][Sy] = 1;
	Q.push(make_pair(Sx, Sy));
	while (!Q.empty())
	{
		pair<int, int> u = Q.front();
		Q.pop();
		for (int i = 0, x, y; i < 4; i ++)
		{
			x = u.first + dx[i], y = u.second + dy[i];
			if (check(x, y))
			{
				Sp[x][y] = Sp[u.first][u.second] + 1;
				if (Map[x][y] != 'S') Q.push(make_pair(x, y));
			}
		}
	}
	int Res = 1 << 20;
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= M; j ++)
		if (Map[i][j] == 'S' && Sp[i][j])
			for (int k = 0; k < 4; k ++)
				if (Map[i + dx[k]][j + dy[k]] == 'S' && Sp[i + dx[k]][j + dy[k]]) Res = min(Res, Sp[i][j] + Sp[i + dx[k]][j + dy[k]]);
	if (Res == (1 << 20)) puts("Hi and Ho will not have lunch.");
	else printf("%d\n", Res - 2);
	return 0;
}

又被水题虐智商

#include <cstdio>
#include <algorithm>
using namespace std;

int N;
struct Car
{
	int X, Y;
	double L;
	inline void Read()
	{
		scanf("%d%d%lf", &X, &Y, &L);
	}
} C[1003];
int p[1003], o[1003];
double Res[1003], t[1003];
inline bool cmp(int a, int b)
{
	return C[a].X > C[b].X;
}
int main()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i ++) C[o[i] = i].Read(), p[i] = C[i].Y;
	sort(p + 1, p + N + 1), sort(o + 1, o + N + 1, cmp);
	for (int i = 1; i <= N; i ++)
	{
		int Cur = o[i], Pos = C[Cur].X;
		double T = 0;
		for (int j = 1; j <= N; j ++)
			if (p[j] >= Pos)
			{
				T += (double)(p[j] - Pos) / C[Cur].L;
				T = t[j] = max(t[j], T), Pos = p[j];
				if (Pos == C[Cur].Y)
				{
					Res[Cur] = T;
					break;
				}
			}
	}
	for (int i = 1; i <= N; i ++) printf("%.2lf\n", Res[i]);
	return 0;
}

闲来做水题，结果把线段树码成了Spaly。。。。。。

智商果然下降了。。。

#include <cstdio>
#include <cstring>
using namespace std;

int N, M;
char S[50004];
struct Splay
{
    Splay *P, *L, *R;
    int v, c, d, f;// v : Value, d : Delta, c : Current, f : Cover;
    bool ff;// ff : Whether Cover;
    int Size;
    Splay()
    {
        P = L = R = NULL;
        v = c = d = f = 0;
        ff = false;
        Size = 1;
    }
    void Update()
    {
        Size = 1;
        if (L) Size += L->Size;
        if (R) Size += R->Size;
    }
}Data[50004], *Top;
inline void Zig(Splay *X)
{
    Splay *Y = X->P;
    if (Y->P) (Y->P->L == Y) ? Y->P->L = X : Y->P->R = X;
    X->P = Y->P, Y->P = X;
    Y->L = X->R, X->R = Y;
    if (Y->L) Y->L->P = Y;
    Y->Update();
}
inline void Zag(Splay *X)
{
    Splay *Y = X->P;
    if (Y->P) (Y->P->L == Y) ? Y->P->L = X : Y->P->R = X;
    X->P = Y->P, Y->P = X;
    Y->R = X->L, X->L = Y;
    if (Y->R) Y->R->P = Y;
    Y->Update();
}
Splay *T[50004];
int Cnt;
inline void Cover(Splay *X, int f)
{
    if (X)
    {
        X->ff = true;
        X->v = X->f = f;
        X->d = X->c = 0;
    }
}
inline void Plus(Splay *X, int c, int d)
{
    c = c % 26;
    if (c < 0) c += 26;
    X->v += c, X->c += c, X->d += d;
}
inline int Rs(Splay *X)
{
    return (X->R) ? X->R->Size : 0;
}
inline int Ls(Splay *X)
{
    return (X->L) ? X->L->Size : 0;
}
inline void Down(Splay *X)
{
    if (X->ff)
    {
        Cover(X->L, X->f), Cover(X->R, X->f);
        X->ff = false;
    }
    if (X->L) Plus(X->L, X->c - (Rs(X->L) + 1) * X->d, X->d);
    if (X->R) Plus(X->R, X->c + (Ls(X->R) + 1) * X->d, X->d);
    X->c = X->d = 0;
}
inline void splay(Splay *X)
{
    Splay *Y, *Z, *K;
    for (K = X, Cnt = 0; K; T[++ Cnt] = K, K = K->P);
    for (int i = Cnt; i; i --) Down(T[i]);
    while (X->P)
    {
        Y = X->P;
        if (Y->P)
        {
            Z = Y->P;
            if (Z->L == Y)
            {
                if (Y->L == X) Zig(Y), Zig(X);
                else Zag(X), Zig(X);
            }else
            {
                if (Y->R == X) Zag(Y), Zag(X);
                else Zig(X), Zag(X);
            }
        }else
        {
            if (Y->L == X) Zig(X);
            else Zag(X);
        }
    }
    X->Update(), Top = X;
}
Splay *Build(Splay *S, int Len, Splay *P = NULL)
{
    if (Len == 1)
    {
        S[1].P = P;
        return S + 1;
    }
    if (Len == 0) return NULL;
    int mid = (1 + Len) >> 1;
    S[mid].P = P;
    S[mid].L = Build(S, mid - 1, S + mid);
    S[mid].R = Build(S + mid, Len - mid, S + mid);
    S[mid].Update();
    return S + mid;
}
inline Splay *Find(int x)
{
    Splay *C = Top;
    int ss;
    while (true)
    {
        ss = Ls(C);
        if (ss + 1 == x) break;
        if (ss >= x) C = C->L;
        else {
            x -= ss + 1;
            C = C->R;
        }
    }
    splay(C);
    return C;
}
inline void CMD1()
{
    int i, j, X;
    scanf("%d%d%s", &i, &j, S);
    X = S[0] - 'A';
    if (i == j)
    {
        Find(j)->v = X;
        return;
    }
    Splay *u = Find(j), *v = Find(i);
    while (u->P != v)
    {
        Down(u->P);
        if (u->P->L == v) Zig(u);
        else Zag(u);
        u->Update();
    }
    Down(v), Down(u);
    Cover(u->L, X);
    v->v = u->v = X;
}
inline void CMD2()
{
    int i, j, X;
    scanf("%d%d%d", &i, &j, &X);
    if (i == j)
    {
        Find(j)->v += X;
        return;
    }
    Splay *u = Find(j), *v = Find(i);
    while (u->P != v)
    {
        Down(u->P);
        if (u->P->L == v) Zig(u);
        else Zag(u);
        u->Update();
    }
    Down(v), Down(u);
    v->v +=X, u->v +=X;
    if (u->L) Plus(u->L, X, 0);
}
inline void CMD3()
{
    int K;
    scanf("%d", &K);
    if (K == N) return;
    Splay *u = Find(K), *v = u->R;
    v->P = NULL;
    u->R = NULL, u->Update();
    u = Find(1), u->L = v;
    v->P = u, u->Update();
}
inline void CMD4()
{
    int i, j;
    scanf("%d%d", &i, &j);
    if (i == j)
    {
        Find(i)->v ++;
        return;
    }
    Splay *u = Find(j), *v = Find(i);
    while (u->P != v)
    {
        Down(u->P);
        if (u->P->L == v) Zig(u);
        else Zag(u);
        u->Update();
    }
    Down(v), Down(u);
    if (u->L) Plus(u->L, Ls(u->L) + 2, 1);
    v->v ++, u->v += j - i + 1;
}
inline void Print(Splay *X = Top)
{
    Down(X);
    if (X->L) Print(X->L);
    putchar('A' + X->v % 26);
    if (X->R) Print(X->R);
}
int main()
{
    scanf("%d%d", &N, &M);
    scanf("%s", S + 1);
    for (int i = 1; i <= N; i ++) Data[i].v = S[i] - 'A';
    Top = Build(Data, N);
    for (int i = 1, opt; i <= M; i ++)
    {
        scanf("%s", S);
        scanf("%d", &opt);
        if (opt == 1) CMD1();
        if (opt == 2) CMD2();
        if (opt == 3) CMD3();
        if (opt == 4) CMD4();
    }
    Print();
    return 0;
}