CF521 / Codeforces Round 295 (Div. 1)

README.md

链接 ᴮᵃᶜᵏᵘᵖ

a.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    static char c;
    static bool neg;
    c = getchar(), neg = false, x = 0;
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;

int n;
char str[N];
int cnt[26];

inline int power(int base, int exp)
{
    int res = 1;
    while (exp > 0)
    {
        if (exp & 1)
        {
            res = (ll)res * base % MOD;
        }
        base = (ll)base * base % MOD;
        exp >>= 1;
    }
    return res;
}

int main()
{
    read(n);
    scanf("%s", str);
    for (int i = 0; i < n; ++i)
    {
        ++cnt[str[i] - 'A'];
    }
    int ans = 0, mx = *max_element(begin(cnt), end(cnt));
    for (const auto &x : cnt)
    {
        if (x == mx)
        {
            ++ans;
        }
    }
    printf("%d\n", power(ans, n));
}

b.cpp

#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
                           << (#x) << ": " << x << std::endl

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    static char c;
    static bool neg;
    x = 0, c = getchar(), neg = false;
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 1e5 + 5;
const int MOD = 1e9 + 9;
const int INF = 0x3f3f3f3f;

inline int power(int base, int exp)
{
    int res = 1;
    while (exp > 0)
    {
        if (exp & 1)
        {
            res = (ll)res * base % MOD;
        }
        base = (ll)base * base % MOD;
        exp >>= 1;
    }
    return res;
}
inline int inv(int x)
{
    return power(x, MOD - 2);
}

inline int inc(int &x, const int &y)
{
    x += y;
    if (x >= MOD)
    {
        x -= MOD;
    }
    else if (x < 0)
    {
        x += MOD;
    }
    return x;
}

inline int dec(int &x, const int &y)
{
    x -= y;
    if (x >= MOD)
    {
        x -= MOD;
    }
    else if (x < 0)
    {
        x += MOD;
    }
    return x;
}

inline int mul(const int &x, const int &y)
{
    int res = (ll)x * y % MOD;
    if (res < 0)
    {
        res += MOD;
    }
    return res;
}

inline int sum(const int &x, const int &y)
{
    int res = x + y;
    if (res >= MOD)
    {
        res -= MOD;
    }
    else if (res < 0)
    {
        res += MOD;
    }
    return res;
}

int n;
unordered_map<int, int> L[N];

struct Removable : map<int, pii>
{
    inline int depend(int x, int y)
    {
        if (y <= 0 || !L[y].count(x))
        {
            return INF;
        }
        return L[y - 1].count(x - 1) + L[y - 1].count(x) + L[y - 1].count(x + 1);
    }
    inline bool removable(int x, int y)
    {
        return depend(x - 1, y + 1) > 1 && depend(x, y + 1) > 1 && depend(x + 1, y + 1) > 1;
    }
    inline void update(int x, int y)
    {
        for (int i = -2, nx, ny, num; i <= 2; ++i)
        {
            for (int j = -2; j <= 2; ++j)
            {
                nx = x + i, ny = y + j;
                if (ny >= 0 && L[ny].count(nx))
                {
                    num = L[ny][nx];
                    if (removable(nx, ny))
                    {
                        this->operator[](num) = (pii){nx, ny};
                    }
                    else
                    {
                        auto iter = this->find(num);
                        if (iter != this->end())
                        {
                            this->erase(iter);
                        }
                    }
                }
            }
        }
    }
};

int main()
{
    read(n);
    int m = 0;
    for (int i = 0, x, y; i < n; ++i)
    {
        read(x), read(y);
        m = std::max(m, y);
        L[y][x] = i;
    }
    Removable removable;
    for (int i = 0; i <= m; ++i)
    {
        for (const auto &p : L[i])
        {
            if (removable.removable(p.first, i))
            {
                removable[p.second] = (pii){p.first, i};
            }
        }
    }
    int ans = 0, invm = inv(n);
    decltype(removable.begin()) ptr;
    for (int i = 1, now = power(n, n - 1), x, y; i <= n; ++i, now = mul(now, invm))
    {
        if (i & 1)
        {
            ptr = prev(removable.end());
        }
        else
        {
            ptr = removable.begin();
        }
        x = ptr->second.first, y = ptr->second.second;
        L[y].erase(x);
        inc(ans, mul(ptr->first, now));
        removable.erase(ptr);
        removable.update(x, y);
    }
    printf("%d\n", ans);
    return 0;
}

c.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
	static char c;
	static bool neg;
	c = getchar(), neg = false, x = 0;
	for (; !isdigit(c); c = getchar())
	{
		if (c == '-')
		{
			neg = true;
		}
	}
	for (; isdigit(c); c = getchar())
	{
		x = x * 10 + c - '0';
	}
	if (neg)
	{
		x = -x;
	}
}

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;

namespace M
{
	inline int inc(int &x, const int &y)
	{
		x += y;
		if (x >= MOD)
		{
			x -= MOD;
		}
		else if (x < 0)
		{
			x += MOD;
		}
		return x;
	}

	inline int dec(int &x, const int &y)
	{
		x -= y;
		if (x >= MOD)
		{
			x -= MOD;
		}
		else if (x < 0)
		{
			x += MOD;
		}
		return x;
	}

	inline int mul(const int &x, const int &y)
	{
		int res = (ll)x * y % MOD;
		if (res < 0)
		{
			res += MOD;
		}
		return res;
	}

	inline int sum(const int &x, const int &y)
	{
		int res = x + y;
		if (res >= MOD)
		{
			res -= MOD;
		}
		else if (res < 0)
		{
			res += MOD;
		}
		return res;
	}
} // namespace M

using M::inc;
using M::mul;

inline int power(int base, int exp)
{
	int res = 1;
	while (exp > 0)
	{
		if (exp & 1)
		{
			res = (ll)res * base % MOD;
		}
		base = (ll)base * base % MOD;
		exp >>= 1;
	}
	return res;
}
inline int inv(int x)
{
	return power(x, MOD - 2);
}

int fac[N], facInv[N];
inline void init()
{
	fac[0] = facInv[0] = 1;
	for (int i = 1; i < N; ++i)
	{
		fac[i] = (ll)fac[i - 1] * i % MOD;
	}
	facInv[N - 1] = inv(fac[N - 1]);
	for (int i = N - 2; i >= 1; --i)
	{
		facInv[i] = (ll)facInv[i + 1] * (i + 1) % MOD;
	}
}
inline int C(int n, int m)
{
	if (n < m)
	{
		return 0;
	}
	return (ll)fac[n] * facInv[m] % MOD * facInv[n - m] % MOD;
}

int n, k;
char str[N];
int a[N], sum[N];

inline bool comp(const int &x, const int &y)
{
	return x > y;
}

int main()
{
	init();
	read(n), read(k);
	scanf("%s", str + 1);
	for (int i = 1; i <= n; ++i)
	{
		a[i] = str[i] - '0';
		sum[i] = sum[i - 1] + a[i];
	}
	int res = 0;
	for (int i = 1, pow10 = 1; i <= n - k; ++i, pow10 = mul(pow10, 10))
	{
		inc(res, mul(pow10, M::sum(mul(sum[n - i], C(n - 1 - i, k - 1)),
								   mul(a[n - i + 1], C(n - i, k)))));
	}
	printf("%d\n", res);
}

d.another.cpp

#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
                           << (#x) << ": " << x << std::endl

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    static char c;
    static bool neg;
    x = 0, c = getchar(), neg = false;
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

typedef pair<long double, int> pldi;

const int N = 1e5 + 5;

int k, n, m;
int a[N], t[N];
pii ass[N];
vector<pii> inc[N];
vector<pldi> mul;

inline bool compareByT(const pldi &x, const pldi &y)
{
    return t[x.second] < t[y.second];
}

int main()
{
    read(k), read(n), read(m);
    for (int i = 1; i <= k; ++i)
    {
        read(a[i]);
    }
    for (int i = 1, ti, ii, bi; i <= n; ++i)
    {
        read(ti), read(ii), read(bi);
        t[i] = ti;
        if (ti == 1)
        {
            if (bi > ass[ii].first)
            {
                ass[ii] = (pii){bi, i};
            }
        }
        else if (ti == 2)
        {
            inc[ii].emplace_back(bi, i);
        }
        else
        {
            mul.emplace_back(bi, i);
        }
    }
    for (int i = 1; i <= k; ++i)
    {
        if (ass[i].first > a[i])
        {
            inc[i].emplace_back(ass[i].first - a[i], ass[i].second);
        }
    }
    ll cur;
    for (int i = 1; i <= k; ++i)
    {
        sort(inc[i].begin(), inc[i].end(), greater<pii>());
        cur = a[i];
        for (const auto &p : inc[i])
        {
            mul.emplace_back((long double)(cur + p.first) / cur, p.second);
            cur += p.first;
        }
    }
    sort(mul.begin(), mul.end(), greater<pldi>());
    mul.erase(mul.begin() + std::min((size_t)m, mul.size()), mul.end());
    sort(mul.begin(), mul.end(), compareByT);
    printf("%lu\n", mul.size());
    for (const auto &p : mul)
    {
        printf("%d ", p.second);
    }
    return 0;
}

d.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long double, int> pldi;

template <typename Tp>
inline void read(Tp &x)
{
	static char c;
	static bool neg;
	c = getchar(), neg = false, x = 0;
	for (; !isdigit(c); c = getchar())
	{
		if (c == '-')
		{
			neg = true;
		}
	}
	for (; isdigit(c); c = getchar())
	{
		x = x * 10 + c - '0';
	}
	if (neg)
	{
		x = -x;
	}
}

const int N = 1e5 + 5;

int k, n, m;
int a[N], t[N];
pii ass[N];
vector<pii> inc[N];
vector<pldi> mul;

inline bool compareByT(const pldi &x, const pldi &y)
{
	return t[x.second] < t[y.second];
}

int main()
{
	read(k), read(n), read(m);
	for (int i = 1; i <= k; ++i)
	{
		read(a[i]);
	}
	for (int i = 1, ti, ii, bi; i <= n; ++i)
	{
		read(ti), read(ii), read(bi);
		t[i] = ti;
		if (ti == 1)
		{
			ass[ii] = std::max(ass[ii], (pii){bi, i});
		}
		else if (ti == 2)
		{
			inc[ii].emplace_back((pii){bi, i});
		}
		else
		{
			mul.emplace_back(bi, i);
		}
	}
	for (int i = 1; i <= k; ++i)
	{
		if (ass[i].first > a[i])
		{
			inc[i].emplace_back((pii){ass[i].first - a[i], ass[i].second});
		}
	}
	ll cur;
	for (int i = 1; i <= k; ++i)
	{
		sort(inc[i].begin(), inc[i].end(), greater<pii>());
		cur = a[i];
		for (const auto &p : inc[i])
		{
			mul.emplace_back((long double)(cur + p.first) / cur, p.second);
			cur += p.first;
		}
	}
	sort(mul.begin(), mul.end(), greater<pldi>());
	m = std::min(m, (int)mul.size());
	mul.erase(mul.begin() + m, mul.end());
	sort(mul.begin(), mul.end(), compareByT);
	printf("%lu\n", mul.size());
	for (const auto &p : mul)
	{
		printf("%d ", p.second);
	}
}

e.cpp

#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
						   << (#x) << ": " << x << std::endl

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
	static char c;
	static bool neg;
	x = 0, c = getchar(), neg = false;
	for (; !isdigit(c); c = getchar())
	{
		if (c == '-')
		{
			neg = true;
		}
	}
	for (; isdigit(c); c = getchar())
	{
		x = x * 10 + c - '0';
	}
	if (neg)
	{
		x = -x;
	}
}

const int N = 2e5 + 5;

int head[N], E = 0;
struct Edge
{
	int to, next;
} e[N * 2];
inline void addEdge(int u, int v)
{
	e[++E] = (Edge){v, head[u]};
	head[u] = E;
}

int n, m;

int fa[N], dep[N];
bool vis[N], inS[N];

inline int lca(int u, int v)
{
	if (dep[u] < dep[v])
	{
		swap(u, v);
	}
	while (dep[u] > dep[v])
	{
		u = fa[u];
	}
	while (u != v)
	{
		u = fa[u];
		v = fa[v];
	}
	return u;
}

int a[N], b[N];

inline void print(const vector<int> &vec)
{
	printf("%lu ", vec.size());
	for (const auto &x : vec)
	{
		printf("%d ", x);
	}
	puts("");
}

inline void explore(int u, int v, vector<int> &vec)
{
	while (u != v)
	{
		vec.emplace_back(u);
		u = fa[u];
	}
	vec.emplace_back(v);
}

inline void output(int a, int b, int c, int d)
{
	puts("YES");
	if (dep[b] > dep[d])
	{
		swap(a, c);
		swap(b, d);
	}
	vector<int> vec;
	int e = lca(a, c);
	// d -> lca(a, c)
	explore(e, d, vec);
	reverse(vec.begin(), vec.end());
	print(vec);
	vec.clear();
	// d -> b -> a -> lca(a, c)
	explore(d, b, vec);
	explore(a, e, vec);
	print(vec);
	vec.clear();
	// d -> c-> lca(a, c)
	vec.emplace_back(d);
	explore(c, e, vec);
	print(vec);
	exit(0);
}

void dfs(int u)
{
	vis[u] = true;
	inS[u] = true;
	dep[u] = dep[fa[u]] + 1;
	for (int i = head[u], v, far = fa[u]; v = e[i].to, i; i = e[i].next)
	{
		if (v != far)
		{
			if (!vis[v])
			{
				fa[v] = u;
				dfs(v);
			}
			else if (inS[v])
			{
				for (int x = u; x != v; x = fa[x])
				{
					if (a[x] != 0 && b[x] != 0)
					{
						output(a[x], b[x], u, v);
					}
					else
					{
						a[x] = u;
						b[x] = v;
					}
				}
			}
		}
	}
	inS[u] = false;
}

int main()
{
	read(n), read(m);
	for (int i = 1, u, v; i <= m; ++i)
	{
		read(u), read(v);
		addEdge(u, v);
		addEdge(v, u);
	}
	for (int i = 1; i <= n; ++i)
	{
		if (!vis[i])
		{
			dfs(i);
		}
	}
	puts("NO");
	return 0;
}

e.ref.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
struct
{
    inline operator int()
    {
        int x;
        return scanf("%d", &x), x;
    }
    inline operator ll()
    {
        ll x;
        return scanf("%lld", &x), x;
    }
    inline operator char()
    {
        char x[3];
        return scanf("%s", x), *x;
    }
} read;

const int maxn = 200005;
std::vector<int> G[maxn];
bool vis[maxn], ins[maxn];
int fa[maxn], deep[maxn];
int cx[maxn], cy[maxn];

int lca(int x, int y)
{
    while (deep[x] > deep[y])
        x = fa[x];
    while (deep[y] > deep[x])
        y = fa[y];
    while (x != y)
        x = fa[x], y = fa[y];
    return x;
}

int tmp[maxn], tp;
void print()
{
    printf("%d", tp);
    for (int i = 1; i <= tp; i++)
        printf(" %d", tmp[i]);
    puts("");
    tp = 0;
}

void add_path(int x, int y)
{
    while (x != y)
    {
        tmp[++tp] = x;
        x = fa[x];
    }
    tmp[++tp] = y;
}

void get(int a, int b, int c, int d)
{
    if (deep[b] > deep[d])
    {
        std::swap(a, c);
        std::swap(b, d);
    }
    int e = lca(a, c);

    puts("YES");

    add_path(e, d);
    std::reverse(tmp + 1, tmp + tp + 1);
    print();

    add_path(d, b);
    add_path(a, e);
    print();

    tmp[++tp] = d;
    add_path(c, e);
    print();

    exit(0);
}

void dfs(int u)
{
    deep[u] = deep[fa[u]] + 1;
    vis[u] = ins[u] = 1;
    for (int v : G[u])
        if (v != fa[u])
        {
            if (!vis[v])
            {
                fa[v] = u;
                dfs(v);
            }
            else if (ins[v])
            {
                for (int x = u; x != v; x = fa[x])
                    if (cx[x] and cy[x])
                        get(cx[x], cy[x], u, v);
                    else
                    {
                        cx[x] = u;
                        cy[x] = v;
                    }
            }
        }
    ins[u] = 0;
}

int main()
{
    int n = read, m = read;
    for (int i = 1; i <= m; i++)
    {
        int u = read, v = read;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i);
    puts("NO");
}

vector_test.cpp

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> vec, res;
    for (int i = 1; i <= 10; ++i)
    {
        vec.emplace_back(i);
    }
    for (int i = 11; i <= 20; ++i)
    {
        res.emplace_back(i);
    }
    vec.insert(vec.end(), res.begin(), res.end());
    for (const auto &x : vec)
    {
        printf("%d ", x);
    }
}