喜欢的话就坚持吧

10月 23

0.00 avg. rating (0% score) - 0 votes

一场垃圾的模拟赛


真是烦躁,
t1全场都切了,一道找规律的水题,出了有什么意义?(话说我还模拟了10min题意才找到规律),不放了。
t2简直气人,给你题目大概是说给你一堆字符串,多组询问,每组询问给你一个字符串,问这个字符串在几个之前给定的字符串中出现过。(自串出现就算)。
垃圾的我一想自己会的所有字符串算法都不能做,果断巧了60分暴力,结果没加文件,给挂成0分。

那么正解是什么呢?考完试交流时听到一个自串出现过肯定是某个给定串的后缀的前缀,(好像是个很常用的技巧?)知道后果断写了个trie树+set给a了。话说有神me更好的做法?

t3简直坑人,(还好我a了)题目大概是给你n个不相同的数字,(n<=30),然后给你一个数m,问有几种排列,满足相邻两个数的差不是m的倍数?

一个显然的思路就是爆搜全排列,然后…你懂得。
显然只有30分。
另一个显然的思路是状压dp,设dp[i][j]表示…你懂得。
竟然有70分?
然后考场上我就没想到什么70分状压,直接一波乱搞,
大概就是一个记忆化爆搜(其实状态数是存不下的,不过数据随机…你懂得)

我们发现题目说的差不能是m的倍数就是说两个数如果相邻,那么他们在%m的意义下不能相同。

那么我们就可以把这些书全部先mod m分类,然后不同类的数可以相邻,
然后我们可以先用记忆化爆搜搜出合法排列个数,然后再乘上每个组大小的阶乘即可。

注意单独的数全部分到一个组里,表示是能任意填的。

具体怎么爆搜可以看代码,思路大概是hash+map

#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>

#define int long long
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int bax1=998244353;
const int bax=10007;
const int mod=1234567891;

int n,m;
int h[35],num[35],tot,mx;
bool use[35];
int base[35],fac[35],st[35];
map<ll,ll>dp[35];
ll ans=1;
inline int dfs(int pos,int las)
{
//  printf("pos=%d\n",pos);
    if(pos>n) return 1;
    memset(st,0,sizeof st);
    //st数组表示我枚举排列时,每个集合还能放几个
    for(int i=0;i<=tot;++i) if(i!=las) st[num[i]]++;
    ll x=(ll)num[0];//hash是个好东西,选取10007和998244353做模数只是习惯
    for(int i=1;i<=mx;++i) x=x*bax+st[i],x%=bax1;
    if(las==0) x=x*bax,x%=bax1;
    else x=x*bax+num[las],x%=bax1;//用map判重
    if(dp[pos].count(x)) return dp[pos][x];
    //printf("wtf\n");
    ll res=0;
    for(int i=0;i<=tot;++i)
    {
        //枚举下一个可以放谁?
        if(i==0&&num[0]>0)
        {
            num[0]--;
            res=(res+dfs(pos+1,0))%mod;
            num[0]++;
        }
        if(i!=0&&i!=las&&num[i]>0)
        {
            num[i]--;
            res=(res+dfs(pos+1,i))%mod;
            num[i]++;
        }
    }//记忆化
    dp[pos][x]=res;
    return res;
}
signed main()
{
    freopen("ssy.in","r",stdin);
    freopen("ssy.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;++i) scanf("%lld",h+i);
    scanf("%lld",&m);
    for(int i=1;i<=n;++i){h[i]%=m;if(h[i]<0) h[i]+=m;}
    for(int i=1;i<=n;++i)
    {
        if(use[i]) continue;use[i]=true;
        int tm=0;
        for(int j=i+1;j<=n;++j) if(h[i]==h[j]) use[j]=true,tm++;
          //num[i]表示第i组有几个元素,num[0]为单独元素的个数
        if(tm==0) num[0]++;
        else num[++tot]=tm+1;
        mx=max(tm+1,mx);
    }
//  printf("mx=%d\n",mx);
//  for(int i=0;i<=tot;++i) printf("num=%d\n",num[i]);

    fac[0]=1;
    for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
    for(int i=0;i<=tot;++i) ans=ans*fac[num[i]]%mod;//乘上阶乘
    //应为每个集合可以任意排列
    //printf("ans=%d\n",ans);
    ans=ans*dfs(1,0)%mod;
    printf("%lld\n",ans);
}
0.00 avg. rating (0% score) - 0 votes
  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

活捉 2 条