[jzoj NOIP2018模拟11.02]

嗯T1忘记取模了，100到20

嗯T2忘记了那啥定理，暴力也写炸了，这题我认

嗯T3线段树合并分裂没有写炸，考场上就知道妥妥的70分。但是，分数出的时候听到有人说暴力也是70分，我？？？脸黑，枉我敲了一个半小时

据说有大佬的线段树合并分裂A掉了T3，然而我这份极限数据跑了2.4s的代码不敢说话，至今还是黄黄的70分TLE挂在那里

T1：昆特牌

题目链接：

https://jzoj.net/senior/#contest/show/2546/0

题目：

作为一个资深OIer，你被邀请到位于波兰的CDPR总部参观。但没想到你刚一到就遇到了麻烦。昆特牌的数据库发生了故障。原本昆特牌中有 k种卡牌和n 种阵营，为了平衡，每个阵营拥有的卡牌种数都是相等的，并且每个阵营的数据顺序排列。由于故障，卡牌数据被打乱了，每个阵营现在有ai 种卡牌。因为昆特牌即将迎来重大更新，每种牌的所属阵营并不重要，工程师只想尽快让每个阵营拥有相同数量的卡牌。由于数据库的结构原因，你每单位时间只能将一种牌向左边或右边相邻的一个阵营移动。作为OI选手，这自然是难不倒你，但作为一名卡牌游戏爱好者，你想知道最终的卡牌分布有多少种方案。两种方案不同当且仅当存在一种卡牌，它在两种方案中所属阵营不同。对998244353取模

题解：

就是均分纸牌问你方案数。

很自然联想均分纸牌的做法，发现变成负数的时候好像搞不了方案数啊。

于是很大胆的猜测只要给出去牌之后自己还是正的，现在给和以后给都是一样的。

那么我就是要尽可能的让当前要给牌的位置牌足够多。什么时候足够多呢？所有的该给它的牌都给它就是了。

发现就是连个边拓扑排序一下就ok了，边权就是需要给的牌的数量

哎，别忘了取模

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<iostream>

#include<vector>

#include<queue>

using namespace std;

typedef long long ll;

const int N=1e6+;

const ll mo=;

int n,k;

ll a[N],b[N],fac[N],in[N];

struct node{

    int to;

    ll w;

};

vector <node> p[N];

inline ll read(){

    char ch=getchar();ll s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

queue <int> q;

ll qpow(ll a,ll b)

{

    ll re=;

    for (;b;b>>=,a=a*a%mo) if (b&) re=re*a%mo;

    return re;

}

ll C(ll a,ll b)

{

    return fac[a]*qpow(fac[b],mo-)%mo*qpow(fac[a-b],mo-)%mo;

}

ll topo()

{

    ll ans=;

    while (!q.empty()) q.pop();

    for (int i=;i<=n;i++) if (!in[i]) q.push(i);

    while (!q.empty())

    {

        int k=q.front();q.pop();

        for (int i=;i<p[k].size();i++)

        {

            node u=p[k][i];

            ans=ans*C(b[k],u.w)%mo;

            b[k]-=u.w;

            b[u.to]+=u.w;

            in[u.to]--;

            if (!in[u.to]) q.push(u.to);

        }

    }

    return ans;

}

int main()

{

    freopen("gwent.in","r",stdin);

    freopen("gwent.out","w",stdout);

    fac[]=;

    for (int i=;i<N;i++) fac[i]=fac[i-]*i%mo;

    int T=read();

    while (T--)

    {

        n=read();k=;

        for (int i=;i<=n;i++)

        {

            a[i]=read();

            b[i]=a[i];

            k+=a[i];

            p[i].clear();

        }

        k/=n;

        for (int i=;i<=n;i++)

        {

            if (a[i]==k) continue;

            if (a[i]>k)

            {

                ll q=a[i]-k;

                p[i].push_back((node){i+,q});

                in[i+]++;

                a[i]-=q;

                a[i+]+=q;

            }

            else

            {

                ll q=k-a[i];

                p[i+].push_back((node){i,q});

                in[i]++;

                a[i]+=q;

                a[i+]-=q;

            }

        }

        printf("%lld\n",topo());

    }

    return ;

}

T2：时空幻境

题目链接：

https://jzoj.net/senior/#contest/show/2546/1

题目：

Tim拥有控制时间的能力。他学会了BFS后，出了一道题：求出一张无向图中连通块的个数。他想请你做出这道题来

题解：

我们定义每次从x到超过n被取模为一轮，有个结论就是说若是初始的x不同，这一轮中的边都不同。更深入的就是说，在碰到x重复出现之前，每连一条边都会减少一个连通块（这两个结论都不是很准确，看看下面就懂了）

我们定义从开始到回到x为一个循环，显然一旦我们找到最小循环节后面就不需要做下去了，可以直接计算答案

首先我们找最小循环节，$x \times k^p \,\ \equiv \,\ x (\mod n)$，最小循环节为使得上式成立的最小p

根据$x \times k^{\varphi(n)} \,\ \equiv \,\ x \,\ (\mod n)$，我们知道$p|\varphi(n)$

由于n是固定的，我们预处理$\varphi(n)$的约数从小到大枚举快速幂判断即可

找到最小循环节之后呢？

最小循环节是偶数就是隔一个连一条边，直到某个$a_y==x$就停下；是奇数就是一直合并，第二次到某个$a_y==x$才停下，也就是直到成环，但是注意最后一条完成环的边不能算入答案

画画图对理解有帮助

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long ll;

const int N=;

int cnt;

ll pri[N];

void div(ll x)

{

    for (int i=;1ll*i*i<=x;i++)

    {

        if (x%i) continue;

        pri[++cnt]=i;if (1ll*i*i!=x) pri[++cnt]=x/i;

    }

}

ll qpow(ll a,ll b,ll mod)

{

    ll re=;

    for (;b;b>>=,a=a*a%mod) if (b&) re=re*a%mod;

    return re;

}

int main()

{

    freopen("braid.in","r",stdin);

    freopen("braid.out","w",stdout);

    div();

    sort(pri+,pri++cnt);

    int T;

    ll n,m,x,k;

    scanf("%d",&T);

    while (T--)

    {

        scanf("%lld%lld",&n,&m);

        scanf("%lld%lld",&x,&k);

        ll ans;

        for (int i=;i<=cnt;i++)

        {

            if (qpow(k,pri[i],n)==)

            {

                ans=pri[i];

                break;

            }

        };

        if (ans==) ans=;//特判一下

        if (ans&) ans--;//完成了环

        else ans/=;//边数等于点数除2

        if (ans<m) printf("%lld\n",n-ans);

        else printf("%lld\n",n-m);

    }

    return ;

}

T3：初音未来

题目链接：

https://jzoj.net/senior/#contest/show/2546/2

题目：

Hercier作为一位喜爱Hatsune Miku的OIer，痛下决心，将Vocaloid买回了家。打开之后，你发现界面是一个长为n的序列，代表音调，并形成了全排列。你看不懂日语，经过多次尝试，你只会用一个按钮：将一段区间按升序排序。不理解音乐的Hercier决定写一个脚本，进行m次操作，每次对一段区间进行操作。可惜Hercier不会写脚本，他找到了在机房里的你，请你模拟出最后的结果。

题解：

部分分：经典题目，二分答案后变为区间查询，区间set1,0.见 [HEOI2016/TJOI2016]排序

一个序列交换相邻的两个数进行排序的话，最小次数就是逆序对个数，具体操作方法就是每次交换相邻逆序对。

所以将排序过程变为交换相邻位置直到没有逆序对。记录哪些位置是逆序对。

这个过程可以用set维护，每次二分出逆序对的位置，如果再区间内，则交换之，并将两侧出现的新逆序对加入。

由于只会交换$O(n^2)$次，总的时间复杂度为$O((n^2+m)log n)$

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<iostream>

#include<set>

using namespace std;

const int N=+;

int n,m,L,R;

int a[N];

set <int> s;

inline int read(){

    char ch=getchar();int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

int main()

{

    freopen("miku.in","r",stdin);

    freopen("miku.out","w",stdout);

    n=read();m=read();L=read();R=read();

    for (int i=;i<=n;i++) a[i]=read();

    for (int i=;i<n;i++) if (a[i]>a[i+]) s.insert(i);

    set <int>::iterator it;

    while (m--)

    {

        int l=read(),r=read();

        while ()

        {

            it=s.lower_bound(l);

            int pos=*it;

            if (pos>=r||it==s.end()) break;

            s.erase(it);

            swap(a[pos],a[pos+]);

            if (a[pos-]>a[pos]) s.insert(pos-);

            if (a[pos+]>a[pos+]) s.insert(pos+);

        }

    }

    for (int i=L;i<=R;i++) printf("%d ",a[i]);

    return ;

}

巴特西

[jzoj NOIP2018模拟11.02]

T1：昆特牌

题目链接：

题目：

题解：

T2：时空幻境

题目链接：

题目：

题解：

T3：初音未来

题目链接：

题目：

题解：

最新文章

热门文章