首页 > 其他分享 >义中常规赛430题解

义中常规赛430题解

时间：2023-04-30 13:34:09浏览次数：52  
标签：ch int 题解 ll right 义中 left 430 mod

T1

二分一个删除的数字个数

然后考虑删除的数字肯定是从大到小来的，所以预处理一个降序的数组，这样能知道二分的数字个数所对应的数字。

在原数组上跑最大子段和，如果碰到大于二分位置的数字就删了。

最终成绩26分，因为对于二分的个数mid，原数组中a[mid]不止1个的话，无法判断哪些该删，哪些不该删。

正确思路需要用到贪心和优先级队列。

首先，特判一下如果 \(S<0\)，只要数一下 \(\geq S\) 的个数就行。

\(S>0\) 的话，从左往右枚举，做类似最大子段和的步骤：

  1. 当 \(a[i]>0\) 时，则把 \(a[i]\) 加入 \(\texttt{SUM}\)。
    当 \(\texttt{SUM}>S\) 时，需要删除目前 \(\texttt{SUM}\) 中的最大值直至 \(\leq S\) 即可（反证即可证明贪心的正确性）
    当 \(\texttt{SUM}<0\) 时，则参考最大子段和的思路，直接舍弃所有数字。
  2. 当 \(a[i]<0\) 时，则它左边的值会”变假“，例如1 1 8 -7 4，左边有个最大的值8，但其实是”被负数-7减过了“，当要删数时，我们会发现删除4其实比删除8更好（删除8的话左边一段可以直接舍弃）
  3. 所以负数需要处理成正数，这也是本题最难的地方。仍旧考虑贪心，因为删的是最大数，所以负数需要用左边的最小数来抵消（大叔要留着删）。将最小数不断和负数抵消直至：

① 负数被抵消成正数，则新数入队，抵消掉的正数全部出队。
② 左边正数都没了，负数仍旧无法被抵消，则左边段是负数，直接舍弃。

虽然用的是优先级队列，但是需要随时删除最大最小值，所以还是用 \(\texttt{set}\) 方便一点。

这题主要让大家再熟悉一下 \(\texttt{STL}\)，赛前 \(\texttt{STL}\) 的 \(\texttt{set}\)、 \(\texttt{multiset}\)、 \(\texttt{vector}\)、 \(\texttt{bitset}\) 这三个务必用熟练。

源码如下：

#include<bits/stdc++.h>
using namespace std;
#define _f(i,a,b) for(register int i=a;i<=b;++i)
#define f_(i,a,b) for(register int i=a;i>=b;--i)
#define chu printf
#define ll long long
#define ull unsigned long long
#define rint register int
inline ll re()
{
    ll x=0,h=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')h=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*h;
}
const int N=131072+100;
int n;
multiset<ll>p;
ll S;
int main()
{
    freopen("score.in","r",stdin);
    freopen("score.out","w",stdout);
    n=re();S=re();
    if(S<=0)
    {
        int cnt=0;
        _f(i,1,n)
        {
            ll val=re();
            if(val>=S)++cnt;
        }
        chu("%d",cnt);
        return 0;
    }
    ll sum=0;int cnt=0;
    _f(i,1,n)
    {
        ll val=re();
        if(val<0)
        {
            while(!p.empty()&&val<0)
            {
                val+=*p.begin();
                sum-=*p.begin();
                p.erase(p.begin());
            }
            if(val>0) p.insert(val),sum+=val;
        }
        else
        {
            sum+=val;p.insert(val);
            while(!p.empty()&&sum>=S)
            {
                sum-=*p.rbegin();
                p.erase(prev(p.end()));
                ++cnt;
            }
        }
    }
    chu("%d",cnt);
    return 0;
}

T2

首先如果不考虑一开始扔掉x堆石子的情况那么这就是一个典型的NIM游戏，可以参考这个：(博弈论（Nim游戏、有向图游戏之SG函数）_有向图游戏的和_Selvaggia的博客-CSDN博客

当石子堆数量为1堆时，显然先手必胜或必败，取决于石子的数量。

当石子堆数量为2堆时，可以用归纳法证明先手必胜或必败。

假设当前有两堆石子，数量分别为a和b，且a≤b。如果a=b，那么先手必败，因为无论先手如何取，后手都可以模仿先手的操作，使得每次操作后两堆石子的数量相同。因此，先手必须要让两堆石子数量不同，这样才能保证后手无法模仿先手的操作。

如果a≠b，那么先手可以将两堆石子的数量变成(a, b-a)，这样就可以将游戏转化为一个nim和游戏，其解法为a xor (b-a) = b。因此，如果b是2的幂次方，那么先手必败，否则先手必胜。

假设对于k-1个石子堆，上述结论都成立，现在考虑k个石子堆的情况。

假设当前有k堆石子，数量分别为X1, X2, ..., Xk。可以先将这k堆石子的数量进行异或，得到一个数S，即S=X1 xor X2 xor ... xor Xk。如果S=0，那么先手必败，因为无论先手如何取，后手都可以模仿先手的操作，使得最终的异或结果为0。否则，先手可以从任意一堆石子中取走若干颗石子，使得剩下的石子数量使得异或结果为0。这样，就可以将游戏转化为k-1个石子堆的情况，根据归纳假设，先手必胜或必败。

因此，可以得出结论：如果所有石子堆的数量的异或和为0，那么先手必败，否则先手必胜。

然后考虑本题。

考虑暴力 \(DP\) ，设 \(f[i][j][k]\) 表示考虑了前 \(i\) 堆的石子，当前扔掉的堆数模 \(s\) 为 \(j\) ，没有扔掉的石子的异或和为 \(k\) 的方案数。但这样空间会炸，发现转移为 $f[i][j][k]=f[i-1][j-1][k \(^\)b[i]]+f[i-1][j][k]$ ，于是可以不用 \(i\) 那一维，直接同时转移 \(k\)^\(b[i]\) 和 \(k\) 。

T3

设 \(f_m(n)\) 表示满足以下要求的的所有序列：

  1. 序列长度为 \(m\)；

  2. 序列中元素均为 \([1,n]\) 内的整数；

  3. 序列中元素的最大公约数为 \(1\)。

则注意到，最大公约数为 \(d\) 的方案数即为 \(f_m\left(\left\lfloor\frac nd\right\rfloor\right)\)。

故显然有

\[\sum\limits_{d=1}^n f_m\left(\left\lfloor\frac nd\right\rfloor\right) = n^m \]

移项得

\[f_m(n) = n^m - \sum\limits_{d=2}^n f_m\left(\left\lfloor\frac nd\right\rfloor\right) \]

则可在 \(O(n^{3/4})\) 的时间内求得 \(f_m\) 在所有 \(\left\lfloor\frac nx\right\rfloor\) 处的值。

故答案为

\[\begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=1}^n f_m\left(\left\lfloor\frac n{\gcd(i,j)}\right\rfloor\right) &= \sum\limits_{d=1}^n f_m\left(\left\lfloor\frac nd\right\rfloor\right)\sum\limits_{i=1}^n \sum\limits_{j=1}^n [\gcd(i,j)=d] \\ &= \sum\limits_{d=1}^n f_m\left(\left\lfloor\frac nd\right\rfloor\right)\sum\limits_{i=1}^{\left\lfloor\frac nd\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac nd\right\rfloor} [\gcd(i,j)=1] \\ &= \sum\limits_{d=1}^n f_m\left(\left\lfloor\frac nd\right\rfloor\right)\left(2\sum\limits_{i=1}^{\left\lfloor\frac nd\right\rfloor}\varphi(i)-1\right) \end{aligned} \]

结合杜教筛，可在 \(O(n^{3/4})\) 的时间复杂度内解决。

标准代码

C++
#include <cmath>
#include <cstdio>
#include <cstring>
#define add(x,y) (x + y >= mod ? x + y - mod : x + y)
#define dec(x,y) (x < y ? x - y + mod : x - y)
using namespace std;
const int N = 1e9;
const int MX = 1e6;
const int LIM = 32e3;
const int mod = 998244353;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int n,lim;
long long m;
int vis[MX + 5],cnt,prime[MX + 5],phi[MX + 5];
int le[LIM + 5],ge[LIM + 5],tot;
int mem[2][2 * LIM + 5];
inline int &id(int x)
{
    return x <= lim ? le[x] : ge[n / x];
}
int sphi(int n)
{
    if(n <= MX)
        return phi[n];
    if(~mem[0][id(n)])
        return mem[0][id(n)];
    int ret = (long long)n * (n + 1) / 2 % mod;
    for(register int l = 2,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        ret = (ret - (long long)(r - l + 1) * sphi(n / l) % mod + mod) % mod;
    }
    return mem[0][id(n)] = ret;
}
int calc(int n)
{
    if(~mem[1][id(n)])
        return mem[1][id(n)];
    int ret = fpow(n,m % (mod - 1));
    for(register int l = 2,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        ret = (ret - (long long)(r - l + 1) * calc(n / l) % mod + mod) % mod;
    }
    return mem[1][id(n)] = ret;
}
int ans;
int main()
{
    memset(mem,-1,sizeof mem),phi[1] = 1;
    for(register int i = 2;i <= MX;++i)
    {
        if(!vis[i])
            phi[prime[++cnt] = i] = i - 1;
        for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
        phi[i] = add(phi[i],phi[i - 1]);
    }
    scanf("%d%lld",&n,&m),lim = sqrt(n);
    for(register int l = 1,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        id(n / l) = ++tot;
    }
    for(register int l = 1,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        ans = (ans + (r - l + 1) * (2LL * sphi(n / l) + mod - 1) % mod * calc(n / l)) % mod;
    }
    printf("%d\n",ans);
}

T4

注意到，当每一段的长度确定下来之后，不管空位是怎么分配的，走到这些地方的概率都相等。所以可以以此划分等价类，每个等价类只关心走到这里的总概率，而不需要关心每个状态的概率具体是多少。

设 \(dp[i][j]\) 表示现在分成了 \(i\) 段，还剩 \(j\) 个空位，所有情况的概率都相等，期望还有几步填满（或者任意的值）。

总情况数（包括这一步放哪）是 \(j \times C_{j-i-1}^{i-1}\)。

放到长度为 \(2\) 的段的方案数为 \(2i \times C_{(j-2)-(i-1)-1}^{(i-1)-1}\)。

放到长度为 \(3\) 的段的中间的方案数是 \(i \times C_{(j-3)-(i-1)-1}^{(i-1)-1}\)。

在剩下的情况中：

放到边界旁边的方案数是 \(2i \times C_{(j-1)-i-1}^{i-1}\)。

放到边界旁隔一格的方案数是 \(2i \times C_{(j-2)-i-1}^{i-1}\)。

用总方案数减去上面所说的就得到在中间把一段砍成两段的平凡情况。

得到走到每个等价类的概率之后即可用期望的线性性求出答案。

标准代码

C++
#include<bits/stdc++.h>
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	#define sz 2333
	#define mod 998244353ll
	typedef long long ll;
//	typedef long double ll;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
	void file()
	{
		#ifdef NTFOrz
		freopen("a.in","r",stdin);
		#endif
	}
	inline void chktime()
	{
		#ifdef NTFOrz
		cerr<<clock()/1000.0<<'\n';
		#endif
	}
	#ifdef mod
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll inv(ll x){return ksm(x,mod-2);}
	#else
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
	#endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

int n,K,t;
ll dp[sz][sz];
ll C[sz][sz];
void init()
{
	rep(i,0,sz-1) C[i][0]=1;
	rep(i,1,sz-1) rep(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
ll ch(int j,int i){if (!i&&!j) return 1;return j>i&&i>0?C[j-i-1][i-1]:0;}

int main()
{
	read(n,K,t);
	init();
	dp[n-1][1]=1;
	drep(j,n-1,2) rep(i,1,n) if (ch(j,i)&&dp[j][i])
	{
		ll tot=j*ch(j,i)%mod;
		ll c2=2*i*ch(j-2,i-1)%mod;
		ll c3=i*ch(j-3,i-1)%mod;
		ll t1=2*i*ch(j-1,i)%mod;
		ll t2=2*i*ch(j-2,i)%mod;
		ll t3=tot-c2-c3-t1-t2; t3=(t3%mod+mod)%mod;
		ll w=dp[j][i]*inv(tot)%mod;
		if (c2) (dp[j-2][i-1]+=c2*w%mod)%=mod;
		if (c3) (dp[j-3][i-1]+=c3*w%mod)%=mod;
		if (t1) (dp[j-1][i]+=t1*w%mod)%=mod;
		if (t2) (dp[j-2][i]+=t2*w%mod)%=mod;
		if (t3) (dp[j-1][i+1]+=t3*w%mod)%=mod;
	}
	ll ans=0;
	drep(j,n-1,K+1) rep(i,1,n) (ans+=dp[j][i]*n%mod*inv(j)%mod*ksm(n-j,t)%mod)%=mod;
	cout<<ans;
	return 0;
}

标签：ch,int,题解,ll,right,义中,left,430,mod
From： https://www.cnblogs.com/FJOI/p/17365177.html

相关文章

  • Android Bitmap内存溢出问题解释
    Android平台在图片处理方面经常会出现OOM的问题，在去年开发的一个项目中，我也一直被这个问题所困扰，在这方面也搜集了许多的资料，今天仅仅针对Android平台的Bitmap说事儿，今后再对内存的问题做详细的探讨，android平台对图片解码这块确实设置的有内存上限，在解码Bitmap的时候android平台会......
  • abc252_d Distinct Trio 题解
    这是数学题耶！题意给定一个整数\(n\)和一个长度为\(n\)的整数序列\(a\)，求满足以下要求的三元组个数：\(1\leqslanti<j<k\leqslantn\)。\(a_i\nea_j\)，\(a_j\nea_k\)，\(a_k\nea_i\)。思路先想正着做，好，不会。正着做不行就反着做，先算出所有情况，再去掉不合法。......
  • ABC G Ex 简要题解
    ABC212GPowerPair推柿子题\(\sum\limits_{x}^{P-1}\sum\limits_{y}^{P-1}\existsn\in\mathbb{N}\x^n\equivy(\bmodP)\)\(1+\sum\limits_{x=1}^{P-1}\sum\limits_{y=1}^{P-1}\existsn\in\mathbb{N}\x^n\equivy(\bmodP)\)考虑模\(P\)......
  • AT_abs300_e 题解
    一、题目描述：你有一个骰子，数字1~6可以被等概率扔到。初始时有一个数$ans=1$。当扔到数字$x$时，$ans=ans\timesx$。给你一个数字$n$，求$ans$能等于$n$的概率。$n<=1e18$。答案对$998244353$取模。 二、解题思路：当扔到$1$时，相当于......
  • 皇后游戏 题解
    luoguP2123题目描述皇后有\(n\)位大臣，每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临，皇后决定为\(n\)位大臣颁发奖金，其中第\(i\)位大臣所获得的奖金数目为第\(i－1\)位大臣所获得奖金数目与前\(i\)位大臣左手上的数的和的较大值再加上第\(i\)位大臣右手......
  • 题解
    D.RangeandPartition1800思维https://codeforces.com/contest/1631/problem/D题解：由于严格大于，故其最终前缀和s[n]>=k,而当s[n]>=k，s[0]=0,每步至多下降1，故其中必有至少k个点满足s[i]=x（1<=x<=k),故符合题意，故只需双指针找出最小的满足题意的区间即可。#include<bits/stdc++......
  • 4 月 27 日测试题解
    4月27日测试题解最短路专场T1\({\color{green}{\text{100pts}}}\text{/100pts}\)题意给出\(m\)个变量与\(n\)个约束，每个约束形如以下三种中的一种；\(x_i-x_j\lew\)\(x_i-x_j\gew\)\(x_i-x_j=w\)有\(q\)个询问，每个询问为形如\((x_i,x_j)\)的二元......
  • 4 月 21 日测试题解
    4月21日测试题解T1\({\color{green}{\text{100pts}}}\text{/100pts}\)题意给出平面上的两条线段，求线段之间的距离。\(\text{|线段端点坐标|}\le10^4\)。思路一开始想的是分讨，但是又怕自己写挂了，所以就写了三分套三分。至少这个不怕少讨论一个情况。既然是三分套三分，......
  • 问题解决：Component name "xxx" should always be multi-word vue/multi-word-compone
    如题，原因是单个单词命名时语法检测无法通过，可以在导出组件时通过name属性给组件名加一个后缀，比如Component。<script>exportdefault{//当组件名为一个单词时，语法检查是无法通过的，可以设置name的值为2个单词来规避检查。name:'HomeComponent'}<......
  • IdentityServer4 问题解决
    RedirectUris={"https://localhost:7098/signin-oidc"},PostLogoutRedirectUris={"https://localhost:7098/signout-callback-oidc"},服务端添加这个 RequirePkce=false,添加这一句......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99