思维

UVALive 7505 Hungry Game of Ants

Posted on

老实说,这题我在现场赛大概写不出来。

感觉还是比较需要脑洞。

题意:
一排不同重量的蚂蚁按重量排成一排玩饥饿游戏,每只蚂蚁最开始选择一个方向,左或者右,大蚂蚁吃小蚂蚁,并且使自己增加小蚂蚁的重量,如果重量相同,左吃右。
问 n 只蚂蚁,第 k 只活到最后的方案数。

思路:

直接切入正解。
首先第k只蚂蚁必须选择左边,不然只能被吃。( $n \neq k $ )
如果想要第 k 只蚂蚁获胜,必须满足以下两个条件

  1. $ weight[ max(p_1), k ] > weight[ 0, max(p_1) ) $
  2. $ weight[ 1, min(p_2) ] <= weight( min(p_2), n ] $

其中,$ max(p_1) $ 是指,满足第一条不等式的最大的 $p_1$
同理,$ max(p_2) $ 是指,满足第二条不等式的最小的 $p_2$

而其中,只要满足第一条不等式,则 $ [1, max(p_1)) $ 的方向任意,所以数量为 $ 2^{max(p_1)-1} $ 。同时这也是 k 只蚂蚁 k 胜出 的方案数。

下面有一个关键地方,就是如何通过 k 只蚂蚁 k 胜出来推出 n 只蚂蚁 k 胜出。
让第 n-1 选择左边,方案数减少一半,但是第 n 只选择任意,方案数增加一倍。故方案数不变。
以此类推。得 $ dp[n] = \sum_{i=w}^{n-1} dp[i]$ 其中 $(w = min(sum[w] \geq sum[n] - sum[w] ) ) $
这个地方只要求一下后缀和就好了。

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 5;

ll sum[maxn], dp[maxn], texp[maxn], tot[maxn];
int bit[maxn];

void init()
{
    texp[0] = 1;
    for (int i = 1; i < maxn; i++) {
        sum[i] = sum[i - 1] + i;
        texp[i] = texp[i - 1] * 2 % mod;
        bit[i] = lower_bound(sum, sum + i + 1, (sum[i] + 1) / 2) - sum;
    }
}

int main()
{
    int n, k, T;
    init();
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d%d", &n, &k);
        if (n == 1 && k == 1) {
            puts("2");
            continue;
        }
        ll s = k;
        memset(dp, 0, sizeof(dp));
        for (int i = k - 1; i >= 1; i--) {
            if (s > sum[i]) {
                tot[k] = dp[k] = texp[i + 1];
                break;
            }
            s += i;
        }
        for (int i = k + 1; i <= n; i++) {
            int tmp = bit[i];
            if (tmp - 1 >= k)
                dp[i] = ((tot[i - 1] - tot[tmp - 1]) % mod + mod) % mod;
            else
                dp[i] = tot[i - 1];
            tot[i] = (tot[i - 1] + dp[i]) % mod;
        }
        printf("Case #%d: %lld\n", cas, dp[n]);
    }
    return 0;
}
思维

HDU 5486 Difference of Clustering

Posted on

这种题目就是专门针对我的……
思路简单,所需注意细节多。

题意:
给你每个元素所在集合,问你有多少个,分割,聚集,映射关系。

思路:
首先很直接的思路就是把每个集合的元素都表示出来,进一步的说hash一下,但集合元素多,集合数量也不少,hash有点困难。
考虑将不同集合的所有相同元素用一个元素表示 (这个只要排序去重即可)
那么对于两个存在这个相同元素的集合 A, B,有如下四种讨论情况:

  1. A有若干个元素而B没有 ----> 聚集
  2. B有若干个元素而A没有 ----> 分割
  3. A,B各自存在不同元素是另一个集合不存在的 -----> 不参与讨论
  4. 不存在相异的元素 ----> 映射

顺便提示一下集合编号在 int 范围内, 要离散化……

AC Code

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
const int maxn = 2e6 + 6;

int head[maxn];
struct node {
    int to, next;
} edges[maxn];

int idx;
int deg[maxn];
pii nodes[maxn];
map<int, int> uid, vid;

bool cmp(const pii& a, const pii& b)
{
    return a.first == b.first ? a.second < b.second : a.first < b.first;
}

void addEdge(int u, int v)
{
    edges[idx] = (node){ v, head[u] };
    head[u] = idx++;
}

void init()
{
    memset(head, -1, sizeof head);
    memset(deg, 0, sizeof deg);
    uid.clear(), vid.clear();
    idx = 0;
}

int main()
{
    int T, n, cas = 0, u, v;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        init();
        int ui = 0, vi = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &u, &v);
            if (uid.count(u) == 0)
                uid[u] = ++ui;
            if (vid.count(v) == 0)
                vid[v] = ++vi;
            u = uid[u], v = vid[v];
            nodes[i] = make_pair(u, v);
        }
        sort(nodes, nodes + n, cmp);
        for (int i = 0; i < n; i++)
            if (i == n - 1 || nodes[i].first != nodes[i + 1].first || nodes[i].second != nodes[i + 1].second) {
                int old = nodes[i].first, now = nodes[i].second + n;
                addEdge(old, now);
                addEdge(now, old);
                deg[old]++, deg[now]++;
            }
        int ans1 = 0, ans2 = 0, ans3 = 0;
        for (int u = 1; u <= ui; u++) {
            if (deg[u] > 1) {
                bool flag = true;
                for (int id = head[u]; ~id; id = edges[id].next) {
                    if (deg[edges[id].to] != 1) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    ans1++;
            } else if (deg[u] == 1) {
                if (deg[edges[head[u]].to] == 1)
                    ans3++;
            }
        }
        for (int u = 1; u <= vi; u++) {
            if (deg[u + n] > 1) {
                bool flag = true;
                for (int id = head[u + n]; ~id; id = edges[id].next) {
                    if (deg[edges[id].to] != 1) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    ans2++;
            }
        }
        printf("Case #%d: %d %d %d\n", ++cas, ans1, ans2, ans3);
    }
    return 0;
}
思维

CodeForces 853 B Jury Meeting

Posted on

思维题,老实说我并没有想出来,应该说是我想歪了……

看了一个大佬的代码,真的是超整洁,这是我目前见过最整洁的代码。值得借鉴。

题意:
每个点距源点有几条单项路径,路径有个花费和另一个时间。要你买构造来回路径使得中间间隔时间不小于 k 。

思路:
首先按照日期排序,菜鸡第一想到的是按照花费权值排序
在相同日期的路径中找出所有花费权值最小的加入集合并维护其最小。如果集合已满就记录当前日期的花费。
一个道理在正向前往目的地来一次,反向返回来一次。
就得到了当前日期正向的的最小值,当前日期反向返回的最小值。
再正向找出当前日期之前的最小值,当前日期之后返回的最小值,使得中间区间尽可能大,越往中间花费越小。

再枚举间隔区间,将往返花费相加找出最小值就是答案。

AC Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxd = 1e6 + 5;
const int maxn = 1e5 + 5;

int n, m, k;
int fIn[maxn], fOut[maxn];
ll minInCost[maxd], minOutCost[maxd];
ll prefix[maxd], suffix[maxd];

struct Item {
    int d, f, t, c;
    bool operator<(const Item& item) const { return d < item.d; }
} items[maxn];

int main()
{
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        Item& item = items[i];
        scanf("%d %d %d %d", &item.d, &item.f, &item.t, &item.c);
    }

    sort(items, items + m);

    ll total = 0;
    int cnt = 0;
    for (int i = 0; i < m;) {
        int d = items[i].d;
        for (; i < m; i++) {
            Item& item = items[i];
            if (item.d != d)
                break;
            if (item.f == 0)
                continue;
            if (!fIn[item.f]) {
                cnt++;
                fIn[item.f] = item.c;
                total += item.c;
            } else if (item.c < fIn[item.f]) {
                total -= fIn[item.f] - item.c;
                fIn[item.f] = item.c;
            }
        }
        if (cnt == n)
            minInCost[d] = total;
    }

    cnt = total = 0;
    for (int i = m - 1; i >= 0;) {
        int d = items[i].d;
        for (; i >= 0; i--) {
            Item& item = items[i];
            if (item.d != d)
                break;
            if (item.t == 0)
                continue;
            if (!fOut[item.t]) {
                cnt++;
                fOut[item.t] = item.c;
                total += item.c;
            } else if (item.c < fOut[item.t]) {
                total -= fOut[item.t] - item.c;
                fOut[item.t] = item.c;
            }
        }
        if (cnt == n)
            minOutCost[d] = total;
    }

    int D = items[m - 1].d;

    for (int i = 1; i <= D; i++) {
        prefix[i] = prefix[i - 1];
        if (minInCost[i])
            prefix[i] = prefix[i] ? min(prefix[i], minInCost[i]) : minInCost[i];
    }

    for (int i = D; i > 0; i--) {
        suffix[i] = suffix[i + 1];
        if (minOutCost[i])
            suffix[i] = suffix[i] ? min(suffix[i], minOutCost[i]) : minOutCost[i];
    }

    ll ans = -1;
    for (int i = 1; i + k + 1 <= D; i++) {
        if (prefix[i] && suffix[i + k + 1]) {
            ll res = prefix[i] + suffix[i + k + 1];
            ans = ans != -1 ? min(ans, res) : res;
        }
    }
    printf("%lld\n", ans);
    return 0;
}
思维

HDU 6038 Function

Posted on

多校第一场没有怎么想的题,然而实际上是很简单的……就是题意在理解上有点绕。

题意:
给你两个序列a和b,每个序列中的每个元素各不相同,且分别为 [0,num)
要你求满足如下函数的数量。\( f ( i ) = b_{ f(a_i) } \)

思路:
一般人一眼就可以看出是一个递归的函数过程。
每次当我们知道了 \( f(i) \) ,我们就可以很顺利地得出 \( f(a_i) \) ,知道了 \( f(a_i) \) ,我们就可以很顺利的知道 \( f( a_{a_i} ) \)

又因为序列的特性,则对于这个函数,在a序列上必定会存在一个环。
而相应的,在a序列上的一个环与b序列上的元素相对应起来,只有在b序列上存在a序列环的因子才能成立。这个真的只要随便意淫一下就可以了,你要我证明我想还真有点烦

因此只要求出两个序列的环,对于每一对a序列的环与b序列的环,如果b序列环是a序列环的因子,则加上b序列环长度,因为对于a序列上的一个固定点,每一个b序列环上的点都可以对应与a序列固定点,且对应关系必不相同。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

int a[maxn], b[maxn];
bool vis[maxn];
vector<int> xa, xb;

int dfs(int pos, int ary[], int len)
{
    if (vis[pos])
        return len;
    vis[pos] = true;
    return dfs(ary[pos], ary, len + 1);
}

int main()
{
    int n, m, cas = 0;
    while (scanf("%d%d", &n, &m) != EOF) {
        each(i, n) scanf("%d", a + i);
        each(i, m) scanf("%d", b + i);
        fill(vis, false), xa.clear(), xb.clear();
        each(i, n) if (!vis[i]) xa.push_back(dfs(i, a, 0));
        fill(vis, false);
        each(i, m) if (!vis[i]) xb.push_back(dfs(i, b, 0));
        int sa = xa.size(), sb = xb.size();
        ll ans = 1;
        each(i, sa)
        {
            ll tmp = 0;
            each(j, sb) if (xa[i] % xb[j] == 0)(tmp += xb[j]) %= mod;
            ans = (ans * tmp) % mod;
        }
        printf("Case #%d: %lld\n", ++cas, ans);
    }
    return 0;
}
思维

CodeForces 279C Ladder

Posted on

比赛的时候又被数学题坑到了……

最后一场个人赛,并不知道是好是坏,但该来的还是要来……

题意:
给你一个序列,q个询问,每个询问为一个区间,问你这个区间的序列是否是Ladder序列。

所谓Ladder序列,就是A星序列,也可以说是峰型序列,包括非减和非增的断崖型。
比如说 1 2 2 1 或是 1 2 或是 2 1

思路:
我还在想到底得用什么数据结构……
实际上只要记录一下每个端点向左向右各能递减到的最大范围,再把端点值相加,看是否等于区间长度即可。

另一种想法是记录向左向右的峰,查询是检查两边中间的峰是否是同一个也可。

感觉第二个好理解一些。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

int ldes[maxn];
int rdes[maxn];
int ary[maxn];

int main()
{
    int n, q, l, r;
    scanf("%d %d", &n, &q);
    each(i, n) scanf("%d", ary + i);
    each(i, n) if (ary[i - 1] >= ary[i]) ldes[i] = ldes[i - 1] + 1;
    else ldes[i] = 1;
    reach(i, n) if (ary[i] <= ary[i + 1]) rdes[i] = rdes[i + 1] + 1;
    else rdes[i] = 1;
    while (q--) {
        scanf("%d %d", &l, &r);
        if (ldes[r - 1] + rdes[l - 1] < r - l + 1)
            puts("No");
        else
            puts("Yes");
    }
    return 0;
}
思维

CodeForces 349B Color the Fence

Posted on

大家好,我是煞笔。

今天的比赛,开局38分钟写到第一,然后就卡在这题……
真的我觉得我自己挺傻的……事实也是如此,一直卡着之后就去入了另一个弓形矩阵的大坑……还以为要一血来着……

题意:
有 n 块钱,1-9 一共9个数字,每个数字花费确定,要你求出最大的值。

思路
毫无疑问,位数是最重要的。我居然把这个加入了动态的思路上,其实位数应该是从一开始就该确定的。
就是 n / 最小的花费。
剩下的多余的前用来对每一个数进行更换,优先从最左边开始,更换最大的。

AC Code

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

using namespace std;

const int inf = 0x3f3f3f3f;

int ary[15];

int main()
{
    int tot, mn = inf;
    scanf("%d", &tot);
    range(i, 1, 9)
    {
        scanf("%d", ary + i);
        mn = min(mn, ary[i]);
    }
    if (tot < mn) {
        puts("-1");
        return 0;
    }
    int max_digit = tot / mn, l = tot % mn;
    each(i, max_digit)
    {
        bool flag = false;
        rrange(j, 1, 9)
        {
            if (mn + l >= ary[j]) {
                l = mn + l - ary[j];
                putchar(j + '0');
                flag = true;
                break;
            }
        }
        if (!flag)
            putchar(mn + '0');
    }
    return 0;
}