2021-01-04 17:08 已编辑南京航空航天大学算法工程师

关注

2021/01/04训练记录

衔尾蛇

https://ac.nowcoder.com/acm/contest/9854/D

@[toc]

P1446 [HNOI2008]Cards

题目链接:P1446 [HNOI2008]Cards
题目大意:给定r张红牌,g张绿牌,b张蓝牌，再给定m个洗牌方式，求本质不同的牌摆列方式有多少个。两种摆列方式是一样的是指一种排列方式可以通过一次洗牌变成另一种。
数据范围: $m\le60,max(r,g,b)\le 20$
题解：考虑使用Burnside引理。本质不同的方案数为在每个置换下稳定不动的方案平均值。每一个置换都可以表示为多个小置换(或者叫环?群论里面的东西)，要保证环内元素在置换后稳定不动，即同一个环的卡牌颜色要是相同的。所以我们大致思路就是，对每一个置换求出环数与每个环的长度，再去考虑每一个环上的卡牌颜色。这里我们使用 $dp$ 来解决。 $f[i][j][k]$ 表示使用 $i$ 个红牌, $j$ 个绿牌， $k$ 个蓝牌的方案数。其实就是一个背包了。具体看代码吧。
AC代码:

#include<bits/stdc++.h>

#define ld long double
#define ll long long
using namespace std;
template<class T>
void read(T& x)
{
    T res = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {
        if (c == '-')f = -1; c = getchar();
    }
    while (isdigit(c)) {
        res = (res << 3) + (res << 1) + c - '0'; c = getchar();
    }
    x = res * f;
}
const ll N = 100 + 10;
int ans = 0;
int r, b, g, m, mod,n,a[N],f[N][N][N];
int cnt[N], vis[N];
void solve()
{
    for (int i = 0; i <= r; i++)
        for (int j = 0; j <= b; j++)
            for (int k = 0; k <= g; k++)
                f[i][j][k] = 0;
    f[0][0][0] = 1;
    memset(cnt, 0, sizeof(cnt));
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++)
    {
        if (vis[i])continue;
        vis[i] = 1;
        int x = a[i]; cnt[0]++; cnt[cnt[0]] = 1;
        while (!vis[x])
        {
            vis[x] = 1;
            x = a[x];
            cnt[cnt[0]]++;
        }
    }
    for(int i=1;i<=cnt[0];i++)
        for(int j=r;j>=0;j--)
            for(int k=b;k>=0;k--)
                for (int l = g; l >= 0; l--)
                {
                    if (j >= cnt[i])f[j][k][l] = (f[j][k][l] + f[j - cnt[i]][k][l]) % mod;
                    if (k >= cnt[i])f[j][k][l] = (f[j][k][l] + f[j][k - cnt[i]][l]) % mod;
                    if (l >= cnt[i])f[j][k][l] = (f[j][k][l] + f[j][k][l - cnt[i]]) % mod;
                }
    ans = (ans + f[r][b][g]) % mod;
}
int fpow(int x, int y)
{
    int ans = 1;
    while (y)
    {
        if (y & 1)ans = ans * x % mod;
        x = x * x % mod; y >>= 1;
    }
    return ans;
}
int main()
{
    //ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif // ONLINE_JUDGE
    read(r), read(b), read(g), read(m), read(mod);
    n = r + b + g;
    for (int i = 1; i <= n; i++)a[i] = i;
    solve();
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            read(a[j]);
        }
        solve();
    }
    printf("%d\n", ans * fpow(m+1, mod - 2)%mod);
    return 0;
}

牛客2020跨年场D-衔尾蛇

题目链接:D-衔尾蛇
题目大意:一共有 $a$ 条红蛇， $b$ 条蓝蛇， $c$ 条绿蛇。她们想知道一共可以形成多少种不同的衔尾蛇的环？(蛇可以不用完)
数据范围: $1\le{a+b+c}\le12$
题解：终于到了这两天问题的起点，一看 ${a+b+c}\le{12}$ ,当时直接想着丢一个爆搜上去，不过写了2小时还是没调出来,然后去学了一圈 $Pólya$ 定理和 $Burnside$ 引理，有点杀鸡用牛刀了。不过 $Burnside$ 引理可以很好这一类本质不同问题，而且时间复杂度很良好。
好了，我们考虑用 $Burnside$ 引理来解决这题，我们不妨考虑 $i$ 条红蛇， $j$ 条蓝蛇， $k$ 条绿蛇可以组成多少本质不同的环(要求全用完)。令 $n=i+j+k$ ,因为我们可以选择旋转环，比如顺时针旋转1格，2格...。所以这里相当于有着n个置换，其中第 $i$ 个置换中,第1个位置->第i个位置，然后以此类推。本质不同的方案数为在每个置换下稳定不动的方案平均值。每一个置换都可以表示为多个小置换(或者叫环?群论里面的东西)，要保证环内元素在置换后稳定不动，即同一个小环的蛇颜色要是相同的。考虑第 $i$ 个置换，有着 $num=\gcd(i,n)$ 个小置换，每一个置换长度为 $len=\frac{n}{\gcd(i,n)}$ ,如果每一个小置换都可以被同一种颜色的蛇填充，那么答案就加上 $\binom{num}{\frac{a}{len}}*\binom{num-\frac{a}{len}}{\frac{b}{len}}$ .具体看代码吧。
AC代码:

#include<bits/stdc++.h>

#define ld long double
#define ll long long
using namespace std;
template<class T>
void read(T& x)
{
    T res = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {
        if (c == '-')f = -1; c = getchar();
    }
    while (isdigit(c)) {
        res = (res << 3) + (res << 1) + c - '0'; c = getchar();
    }
    x = res * f;
}
const ll N = 200000 + 10;
const int mod = 1e9 + 7;

ll a, b, c, f[N];
void init()
{
    f[0] = 1;
    for (int i = 1; i <= 15; i++)
    {
        f[i] = f[i - 1] * i;
    }
}
ll C(int x, int y)
{
    return f[x] / (f[y] * f[x - y]);
}
ll gcd(int x, int y)
{
    return y ? gcd(y, x % y) : x;
}
ll calc(ll a, ll b, ll c)
{
    ll res = 0;
    for (int i = 1; i <= a + b + c; i++)
    {
        int numh = gcd(a + b + c, i);
        int len = (a + b + c) / numh;
        if (a % len || b % len || c % len)continue;
        res += C(numh, a / len) * C(numh - a / len, b / len);
    }
    return res / (a + b + c);




}
int main()
{
    //ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif // ONLINE_JUDGE
    read(a); read(b), read(c);
    init();
    int ans = 0;
    for (int i = 0; i <= a; i++)
        for (int j = 0; j <= b; j++)
            for (int k = 0; k <= c; k++)
            {
                if (i == 0 && j == 0 && k == 0)continue;
                ans += calc(i, j, k);
            }
    printf("%d\n", ans);

    return 0;
}

牛客2020跨年场H-牛清楚的裙子!!!

题目链接:H-牛清楚的裙子!!!
题目大意:牛清楚有n条裙子，穿每条裙子的概率一样为 $\frac{1}{n}$ 。其中穿1号裙加10000分，其他裙子加1分。询问当每条裙子都穿过的时候，期望的得分是多少。t次询问。
数据范围： $n\le1e7,t\le1e5$ $. 题解:其实是是一个很简单的期望递推题，不过我刚写的时候想歪了，满脑子都是$ $min-max$ $容斥这些个骚操作。我们不妨先考虑每次要穿的期望次数。令$ $f[i]$ $表示已经穿过i条不同裙子，然后要结束的期望局数，显然有$ $f[n]=0$ $，而我们要求的就是$ $f[0]$ $。考虑递推式:$ $f[i]=\frac{i}{n}*f[i]+\frac{n-i}{n}*f[i+1]+1$ $解释下就是有$ $i$ $条穿过的，$ $n-i$ $条未穿过的，然后穿一次的转移。我们简化下式子有$ $f[i]=f[i+1]+\frac{n}{n-i}$ $然后我们知道$ $f[n]=0$ $。所以$ $f[n-1]=0+\frac{n}{1} f[n-2]=0+\frac{n}{1}+\frac{n}{2}$ $以此类推$ $f[0]=\sum\limits_{i=1}^{n}{\frac{n}{i}}=n*\sum\limits_{i=1}^{n}{\frac{1}{i}}$ $.即有$ $n$ $条裙子时的期望局数为$ $f[0]$ $,所以每一条裙子期望穿的次数为$ $\frac{f[0]}{n}=\sum\limits_{i=1}^{n}{\frac{1}{i}}$ $,所以$ $ans=(n+9999)*\sum\limits_{i=1}^{n}{\frac{1}{i}}$ $用$ dp $数组$ $O(n)$ $预处理下$ $\sum\limits_{i=1}^{n}{\frac{1}{i}}$ ,就可以快速求出答案了。
AC代码:

#include<bits/stdc++.h>

#define ld long double
#define ll long long
using namespace std;
template<class T>
void read(T& x)
{
    T res = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {
        if (c == '-')f = -1; c = getchar();
    }
    while (isdigit(c)) {
        res = (res << 3) + (res << 1) + c - '0'; c = getchar();
    }
    x = res * f;
}
const ll N = 10000000 + 10;
const int mod = 1e9 + 7;
int t, n;
double dp[N];
int main()
{
    //ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif // ONLINE_JUDGE
    for (int i = 1; i <= 1e7; i++)
    {
        dp[i] = dp[i - 1] + 1.0 / i;
    }
    read(t);
    while (t--)
    {
        read(n);
        double ans = (n + 9999)* dp[n];
        printf("%.7lf\n", ans);
    }
    return 0;
}

牛客2020跨年场F-开心消消乐

题目链接:F-开心消消乐
题目大意:给定一个01字符串s,可以消去数字1个数为数字0个数*2的一段，再进行01消除，即0在前1在后且相邻即可消除。问剩下的字符串最短长度。
数据范围: $|S|\le{10000}$
题解:瞧一眼数据范围， $O(n^2)$ 可以过去,考虑枚举删去的区间 $[l,r]$ ,然后将剩下的 $[1,l-1]$ 和 $[r+1,n]$ 拼接起来。对于 $[1,i]$ 的一段，我们可以用栈来模拟消去，可以得到消除的次数。并且栈中的元素必然是 $[1111110000000...]$ 这一类的。用 $pre[i]$ 表示 $[1-i]$ 中删去的次数， $rpre[i]$ 表示 $[i-n]$ 中删去的次数(这个是倒着做)。 $num[i][0/1]$ 表示对应栈中剩余的 $0,1$ 个数。对应模拟一下就出来了。
AC代码:

#include<bits/stdc++.h>

#define ld long double
#define ll long long
using namespace std;
template<class T>
void read(T& x)
{
    T res = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {
        if (c == '-')f = -1; c = getchar();
    }
    while (isdigit(c)) {
        res = (res << 3) + (res << 1) + c - '0'; c = getchar();
    }
    x = res * f;
}
const ll N = 200000 + 10;
const int mod = 1e9 + 7;
int n,sum[N],num[N][2],pre[N],rpre[N];
char s[N];
void init()
{
    for (int i = 1; i <= n; i++)sum[i] = sum[i - 1] + s[i] - '0';
    stack<int>pls;
    for (int i = 1; i <= n; i++)
    {
        pre[i] = pre[i - 1];
        if (!pls.size())
        {
            pls.push(i);
            num[i][0] = s[i] == '0';
            continue;
        }
        if (s[i] == '1' && s[pls.top()] == '0')
        {
            pls.pop();
            pre[i]++;
            if (pls.size())num[i][0] = num[pls.top()][0];
            else num[i][0] = 0;
            continue;
        }
        if (pls.size())num[i][0] = num[pls.top()][0] + (s[i] == '0');
        else num[i][0] = (s[i] == '0');
        pls.push(i);
    }
    while (pls.size())pls.pop();
    for (int i = n; i >= 1; i--)
    {
        rpre[i] = rpre[i + 1];
        if (!pls.size())
        {
            pls.push(i);
            num[i][1] = (s[i] == '1');
            continue;
        }
        if (s[i] == '0' && s[pls.top()] == '1')
        {
            pls.pop();
            rpre[i]++;
            if (pls.size())num[i][1] = num[pls.top()][1];
            else num[i][1] = 0;
            continue;
        }
        if (pls.size())num[i][1] = num[pls.top()][1] + (s[i] == '1');
        else num[i][1] = (s[i] == '1');
        pls.push(i);
    }
}
int calc(int x,int l,int r)
{
    if (x == 1)
    {
        return sum[r] - sum[l - 1];
    }
    else
    {
        return (r - l + 1) - (sum[r] - sum[l - 1]);
    }
}
int find(int l, int r)
{
    if (calc(1,l,r) != 2 * calc(0,l,r))return n-pre[n]*2;
    int al = pre[l - 1] + rpre[r + 1];
    int al2 = min(num[l - 1][0], num[r + 1][1]);
    return n - (r - l + 1) - (al + al2) * 2;

}
int main()
{
    //ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif // ONLINE_JUDGE
    read(n);
    scanf("%s", s + 1);

    init();
    int ans = n-pre[n]*2;
    for(int l=1;l<=n;l++)
        for (int r = l; r <= n; r++)
        {
            ans = min(ans,find(l, r));
        }
    printf("%d\n", ans);
    return 0;
}

牛客2020跨年场G-CoolCool的序列

题目链接:G-CoolCool的序列
题目大意:给定一个长度为 $n$ 的序列，要求翻转序列，其中交换 $a[i]$ 和 $a[j]$ 花费 $abs(i-j)$ ,问最小花费。
数据范围: $1\le a_i \le N\le1e5$
题解:考虑对相同的数进行变换，即两个位置数组进行变换，要求距离差最小，直接排序即可
AC代码:

#include<bits/stdc++.h>

#define ld long double
#define ll long long
using namespace std;
template<class T>
void read(T& x)
{
    T res = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {
        if (c == '-')f = -1; c = getchar();
    }
    while (isdigit(c)) {
        res = (res << 3) + (res << 1) + c - '0'; c = getchar();
    }
    x = res * f;
}
#define int long long
const ll N = 200000 + 10;
const int mod = 1e9 + 7;
int n, a[N];
vector<int>w[N], to[N];
signed main()
{
    //ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif // ONLINE_JUDGE
    read(n);
    for (int i = 1; i <= n; i++)
    {
        read(a[i]);
        w[a[i]].push_back(i);
        to[a[i]].push_back(n - i + 1);
    }
    int ans = 0;
    for (int i = 1; i <= 1e5; i++)
    {
        sort(w[i].begin(), w[i].end());
        sort(to[i].begin(), to[i].end());
        for (int j = 0; j < w[i].size(); j++)
        {
            ans += abs(to[i][j] - w[i][j]);
        }
    }
    printf("%lld\n", ans / 2);

    return 0;
}

``

全部评论

推荐最新楼层

11-27 01:03

天津工业大学 DSP工程师

秋招终于结束了

我也要为自己庆祝一下，因为我在网上上坚持不懈，终于直接拿到了offer！这一路走来，真的不容易。复试时还得准备PPT，心里想着时间紧迫，压力有点大。不过，今天我收到了好消息，初试表现得到了认可，直接进入了offer环节，真是太开心了！希望大家也能在求职路上顺利前行！

牛客创作赏金赛

点赞评论收藏

11-24 10:10

华中科技大学 Java

在拼多多工作的体验

首先，电梯真的是个大问题，等个电梯能等好久，尤其是饭点下楼，20到30分钟是常态。加班那么多，午休想休息一下，大家基本上都懒得出去吃饭，最后还是选择在公司吃。公司包四餐，早、中、晚和偶尔的夜宵（不是每天都有）。点餐得用系统，周五开放，能提前订下周的饭。要是没抢到好吃的，剩下的就只能将就了。其实餐食种类还挺丰富的，周边餐厅给拼多多供餐，但因为人多，好的餐很快就被抢光了。点餐后一定要按时去取，过了时间就算放弃，系统会记你的名字，几次不取就会被处罚。

拼多多集团-PDD公司福利 474人发布

点赞评论收藏

11-11 09:31

香港中文大学后端

“面试官出车祸了今天面试要取消了”

Hello_WordN：咱就是说，除了生命其他都是小事，希望面试官平安，希望各位平时也多注意安全

点赞评论收藏

11-09 14:54

已编辑

华南农业大学产品经理

请赐教😭😭

25届应届生，目前0 offer，焦虑坏了😭😭

大拿老师：这个简历，连手机号码和照片都没打码，那为什么关键要素求职职位就不写呢？从上往下看，都没看出自己到底是产品经理的简历，还是电子硬件的简历？这是一个大问题，当然，更大的问题是实习经历的描述是不对的不要只是去写实习流程，陈平，怎么去开会？怎么去讨论？面试问的是你的产品功能点，是怎么设计的？也就是要写项目的亮点，有什么功能？这个功能有什么难处？怎么去解决的？实习流程大家都一样，没什么优势，也没有提问点，没有提问，你就不得分另外，你要明确你投的是什么职位，如果投的是产品职位，你的项目经历写的全都是跟产品无关的，那你的简历就没用你的面试官必然是一个资深的产品经理，他不会去问那些计算机类的编程项目所以这种四不像的简历，在校招是大忌

点赞评论收藏