首页 > 其他分享 >Codeforces Round 861 (Div. 2)

Codeforces Round 861 (Div. 2)

时间:2023-04-05 12:11:09浏览次数:48  
标签:CI 861 Codeforces int Div include RI DP define

Preface

这场感觉都是一个礼拜前补题打的了,但由于上周末事情比较多都没来得及写题解

因此可能题意都记得不是很清楚了,就简略地谈一谈吧


A. Lucky Numbers

不难想到直接暴力从左端点枚举到右端点并对每个数进行暴力判断

一个很naive的结论就是当答案为\(9\)时直接输出即可,然后我们发现无论从哪个点开始显然都不用经过很久就能找到一个答案为\(9\)的数

证明略感觉很simple

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,l,r;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; scanf("%d%d",&l,&r); int ans=-1,num;
		for (i=l;i<=r&&ans!=9;++i)
		{
			int x=i,mi=9,mx=0;
			while (x) mi=min(mi,x%10),mx=max(mx,x%10),x/=10;
			if (mx-mi>ans) ans=mx-mi,num=i;
		}
		printf("%d\n",num);
	}
	return 0;
}

B. Playing in a Casino

不难想到先做每一列的贡献和原来是等价的,而且此时问题变得十分容易

我们只需要排序后就能把绝对值去掉了,然后就非常trivial了

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
int t,n,m,x; vector <int> v[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i) v[i].resize(n);
		for (i=0;i<n;++i) for (j=1;j<=m;++j) scanf("%d",&v[j][i]);
		long long ans=0; for (i=1;i<=m;++i)
		{
			long long pfx=0; sort(v[i].begin(),v[i].end());
			for (j=0;j<n;++j) ans+=1LL*v[i][j]*j-pfx,pfx+=v[i][j];
		}
		printf("%lld\n",ans);
	}
	return 0;
}

C. Unlucky Numbers

A题的反面题,感觉还是挺有趣的说

一个很直觉的方法就是数位DP了,但一般的数位DP都是记\(f(x)\)表示\(1\sim x\)的答案,然后用\(f(r)-f(l-1)\)来得到\([l,r]\)的答案的,但这题显然没有这种可减性

那怎么处理比较好呢,考虑原来我们在一般的数位DP中会针对不超上界在状态中记录一个信息表示从高位到这一位的所有数是否都卡在上界上,因此我们仿照这个对下界也做同样的处理

但是如果直接上手DP可能会有点不好设计状态,我们可以考虑枚举两个数字\(i,j\)表示所有使用的数必须在区间\([i,j]\)内部,此时我们强制令极差为\(j-i\)

然后此时我们的DP只要考虑可行性即可,设\(f_{i,0/1,0/1}\)表示做到从高到低的第\(i\)位,上界是否卡死,下界是否卡死的状态是否有解,若有解由于只要输出一个解可以直接记录下

但是直接这样做会有一个问题,那就是如果\(l,r\)在十进制下的位数不同,那么\(l\)前面的前导\(0\)会对DP产生影响

不过我们稍加分析后发现\(l,r\)位数不同的情况是很trivial的,因为我们总可以构造一个位数和\(l\)位数相同的全为\(9\)的数,它的答案就已经是\(0\)了

因此这题就做完了,感觉是最近做过的几场比赛里最难的一个C了,单次询问复杂度\(O(9^3\log n)\)

#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=20;
int t,L[N],R[N],cur[N],ans[N],mi,c1,c2; long long l,r; bool vis[N][2][2];
inline bool DP(CI now,CI LB,CI RB,CI FL,CI FR)
{
	if (!now) return 1; if (vis[now][FL][FR]) return 0;
	for (RI i=LB;i<=RB;++i)
	{
		if (FL&&i<L[now]) continue;
		if (FR&&i>R[now]) continue;
		if (DP(now-1,LB,RB,FL&&(i==L[now]),FR&&(i==R[now])))
		return cur[now]=i,1;
	}
	return vis[now][FL][FR]=1,0;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j,k; scanf("%lld%lld",&l,&r); c1=c2=0;
		while (l) L[++c1]=l%10,l/=10;
		while (r) R[++c2]=r%10,r/=10;
		if (c1!=c2)
		{
			for (i=1;i<=min(c1,c2);++i)
			putchar('9'); putchar('\n'); continue;
		}
		for (mi=10,i=0;i<=9;++i) for (j=i;j<=9;++j)
		{
			bool flag=0; memset(vis,0,sizeof(vis));
			for (k=i;k<=j;++k) if (L[c1]<=k&&k<=R[c1])
			if (cur[c1]=k,DP(c1-1,i,j,k==L[c1],k==R[c1])) { flag=1; break; }
			if (flag&&j-i<=mi) mi=j-i,memcpy(ans,cur,sizeof(ans));
		}
		for (i=c1;i;--i) putchar(ans[i]+'0'); putchar('\n');
	}
	return 0;
}

D. Petya, Petya, Petr, and Palindromes

这题真是过了快一周我草稿纸上都更新了二三十页的新内容了,翻了半天才把当时的想法翻出来

一个显然的想法在考虑回文串的对应位置时,只有下标奇偶性相同的位置之间可能可以产生贡献

我们不妨这样考虑原问题,先假设对于所有的回文串每对对应位置上的数均不相同,然后容斥算出相同的部分减去即可

一个很naive的想法就是把所有值相同的数的下标放在一起处理,那么现在就是要讨论两个下标是否会在某次计算中配对了

首先正着考虑,假设对应的下标差是\(i\),满足\(i\in[2,k-1]\and 2|i\),经过简单计算得到此时合法的起始比较下标为\(j\),满足\(a_j=a_{j+i}\)且\(j\in [\frac{k+1-i}{2},n-\frac{k+1-i}{2}+1]\)

然后考虑我们枚举的某个下标\(y\),以它作为右端点(即\(j+i\))考虑找出所有满足要求的\(x\)(即\(j\))的个数

但是不要忘记还有个隐含条件\(x+y\ge k+1\),我们把上面的式子用\(x,y\)表示出来就有\(x\in[\max(k+1-y,y-k+1),2n-k+1-y]\)

很显然这左右端点对应的值的个数都可以直接通过二分来找到,也许通过一定技巧也可以用two points,不过里面有\(\max\)感觉不太方便的说

总复杂度\(O(m\log n)\)

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,k,x; long long ans; vector <int> v[N][2];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,p; for (scanf("%d%d",&n,&k),i=1;i<=n;++i)
	scanf("%d",&x),v[x][i&1].push_back(i);
	for (ans=1LL*(k-1)/2*(n-k+1),i=1;i<=200000;++i) for (j=0;j<2;++j)
	{
		int len=v[i][j].size(); for (p=0;p<len;++p)
		{
			int LB=lower_bound(v[i][j].begin(),v[i][j].end(),max(k+1-v[i][j][p],v[i][j][p]-k+1))-v[i][j].begin();
			int RB=upper_bound(v[i][j].begin(),v[i][j].end(),2*n-k+1-v[i][j][p])-v[i][j].begin()-1;
			ans-=max(0,min(p-1,RB)-LB+1);
		}
	}
	return printf("%lld",ans),0;
}

E1. Minibuses on Venus (easy version)

第一次见到分了三个难度级的题目,被狠狠地震撼到了

不过这个Easy难度的直接暴力DP就行了,首先一眼枚举所有数的和\(s\),考虑求出所有和为\(s\)的合法序列的个数

很显然此时我们枚举每一个\([0,k-1]\)的数\(p\),若\(2p\bmod k=s\)则只要此时\(p\)出现就一定合法

但直接计算合法的方案数有点不太好下手,我们可以容斥一下用不加任何限制的情况减去只用不合法的\(p\)时的情况数

那么直接上DP,\(f_{i,j,0/1}\)表示处理了前\(i\)个位置,和对\(k\)取模为\(j\),是否有禁用限制的方案数,转移是很trivial的

总复杂度\(O(n\times k^3)\)

#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
int n,k,mod,f[105][35][2],ans;
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
int main()
{
	RI i,j,p,q; for (scanf("%d%d%d",&n,&k,&mod),p=0;p<k;++p)
	{
		int cur=0; for (memset(f,0,sizeof(f)),q=0;q<k;++q) if (q*2%k==p) cur|=(1<<q);
		for (f[0][0][0]=f[0][0][1]=i=1;i<=n;++i)
		for (j=0;j<k;++j) for (q=0;q<k;++q)
		{
			int pre=(j-q+k)%k; inc(f[i][j][1],f[i-1][pre][1]);
			if (!((1<<q)&cur)) inc(f[i][j][0],f[i-1][pre][0]);
		}
		inc(ans,(f[n][p][1]-f[n][p][0]+mod)%mod);
	}
	return printf("%d",ans),0;
}

E2. Minibuses on Venus (medium version)

点开E2一看好家伙\(n\)直接爆炸增长成\(10^{18}\)了,那么不难想到应该用类似于矩阵快速幂那样的科技优化下DP

但这里的状态转移怎么想感觉和矩阵也没关系的说,不过其实能用快速幂优化的除了矩阵其实还有一个,那就是循环卷积

首先考虑无限制的情况,如果我们用一个多项式\(a_0\cdot x^0+a_1\cdot x^1+a_2\cdot x^2+\cdots+a_{k-1}\cdot x^{k-1}\)来表示状态,\(x_i\)的系数\(a_i\)表示和在模\(k\)后为\(i\)的方案数

那么一次转移显然就是做一个循环卷积,其中转移多项式\(A=x^0+x^1+x^2+\cdots+x^{k-1}\),因此我们只要求\(A^n\)即可,这个是可以用快速幂加速的

那么接下来有禁用的也很明显了,我们把所有能用的位置对应的系数置为\(1\),不能用的置为\(0\),然后设这个转移多项式为\(B\),求出\(B^n\)后减一减即可

这题一个很大的启发就是加速DP的科技除了矩乘之外还有循环卷积,算是学到了

总复杂度是\(O(k^4\log n)\)的,可以通过此题

#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int k,ans,mod; long long n;
inline vector <int> Mul(vector <int>& A,vector <int>& B)
{
	vector <int> C(k);
	for (RI i=0;i<k;++i) for (RI j=0;j<k;++j)
	(C[(i+j)%k]+=1LL*A[i]*B[j]%mod)%=mod;
	return C;
}
inline vector <int> Pow(vector <int> A,long long p)
{
	vector <int> tmp(k); tmp[0]=1;
	for (;p;p>>=1,A=Mul(A,A)) if (p&1) tmp=Mul(tmp,A);
	return tmp;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%lld%d%d",&n,&k,&mod),i=0;i<k;++i)
	{
		vector <int> A(k),B(k);
		for (j=0;j<k;++j) if (A[j]=1,2*j%k!=i) B[j]=1;
		(ans+=(Pow(A,n)[i]-Pow(B,n)[i]+mod)%mod)%=mod;
	}
	return printf("%d",ans),0;
}

E3. Minibuses on Venus (hard version)

这种难度快直逼3000的题我肯定是写不动的

看了眼dalao的博客发现原来有技术可以直接推出一个封闭解的说,还是太恐怖了


Postscript

这场没打也可惜,看起来这场CD难度挺大的而且都是合我胃口的题,早知道翘课去打了

标签:CI,861,Codeforces,int,Div,include,RI,DP,define
From: https://www.cnblogs.com/cjjsb/p/17289105.html

相关文章

  • Codeforces Round 862 A-E
    CodeforcesRound862(Div.2)先简单写一下A-E的题解。A异或的经典性质:\(x\oplusx=0\)。B显然要把字典序最小的那个字母放到最前面。如果这个字母出现了很多次,那么应该选择最后一次出现的位置。这也很容易证明。C联立以后计算一下就行了。比赛的时候爆了一次int。......
  • Codeforces Round 717 (Div. 2) B. AGAGA XOOORRR(位运算)
    https://codeforces.com/contest/1516/problem/B题目大意:给定长度为n的数组a,问我们能不能一直选择两个相邻的元素进行异或后,删除这两个值,把异或值留下来,最后剩下>=2个数字,它们都是相同的?可以做到输出YES,不能的话输出NO。input23022423110outputYESNO题......
  • CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)-C
    参考了佬的c题题解思路,感觉很巧妙,记录一下https://zhuanlan.zhihu.com/p/618685370#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=2*100010;inta[N];voidsolve(){ intn,c,d; cin>>n>>c>>d; set<int>se......
  • Multimedia (MP3, MPEG-4, AVI, DiVX, etc.) support in Ubuntu 12.04 (Precise)
    Whydoesn’tUbuntusupportMP3‘outofthebox’?UbuntucannotincludesupportforMP3orDVDvideoplaybackorrecording.MP3formatsarepatented,andthepatentholdershavenotprovidedthenecessarylicenses.Ubuntualsoexcludesothermultimediasof......
  • cf-div.2-862d
    题目链接:https://codeforces.com/contest/1805/problem/D赛时没过的题。思路:首先发现一个性质:对于k来说,如果树上的一个点到树的直径的两个端点的距离都小于k的话,那么这个点一定是一个孤立点。证明:采用反证法:假设\(x,y\)为树的直径的两个端点,\(a,b\)为另外两个点,且有\(d[a][x]<k......
  • Codeforces Round 862 (Div. 2) A-D题解
    比赛地址A.WeNeedtheZero题意:给出一个数组,对任意1<=i<=n,令bi=aix,问是否存在x,使得b<sub>1</sub>b2...bn=0Solution如果n为奇数,那么x一定存在,因为偶数个x异或得到的是0,直接令x=0(a<sub>1</sub>a2...an)即可如果n为偶数,那么x取任何值都不会影响结果,所以只用看a1a<sub>2</sub......
  • Codeforces Round 862 (Div. 2) (4.2)
    CodeforcesRound862(Div.2)A-WeNeedtheZero思路:某个数被异或两次相当于没变,即判断n的奇偶性;n为偶数时判断所有数异或后的数是否为0,若为0,输出任意数;n为奇数时答案为所有数异或后的值#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;consti......
  • Codeforces Round 862 (Div. 2)A-C思路复盘
    感觉这场前三题都简单,复盘一下赛时的脑回路QAQ,c二分wa了四发赛后才过的血亏A题意:问是否能找到一个数x,有\(b_i=a_i⊕x\),使得\(b\)数组的总异或和为0。思路:赛时模拟样例可以发现先把a数组的总异或和求出来假设为x,然后由异或性质可知相同为0,不同为1,可知这个x可能就是答案。然......
  • css 设置 div等于屏幕的时候直角,小于屏幕圆角
    .card{border-radius:clamp(0px,((100vw-4px)-100%)*9999,8px);}clamp()clamp()函数的作用是把一个值限制在一个上限和下限之间,当这个值超过最小值和最大值的范围时,在最小值和最大值之间选择一个值使用。它接收三个参数:最小值、首选值、最大值。......
  • 加载更多 - 监听div的滚动scroll
    前言:某些情况下,在展示列表数据时,为了实现性能优化及用户更好的体验,可以先展示十几条数据,然后边滑动边加载更多,可以减少服务器压力及页面渲染时间。varpageNum=1;//页数vardomHeight=$(".listBox").height()*4;vardom=document.getElementById('list');dom.addEventList......