[CF1355] Codeforces Round #643 (Div. 2)

Codeforces Round #643 (Div. 2)

Problems

#	Name
A	Sequence with Digits		x17498
B	Young Explorers		x16642
C	Count Triangles		x7510
D	Game With Array		x12249
E	Restorer Distance		x3186
F	Guess Divisors Count		x511

A. Sequence with Digits

[a_{n+1}=a_n+minDigit(a_n)⋅maxDigit(a_n). ]

给定 (a_1) 和 (k) ，求 (a_k).

思路：观察到当 (minDigit(a_n)=0) 时，(a_{n+1}=a_n) , 后面的项都 (= a_n) 。

所以暴力求出这一项 (a_n) 即可。

时间复杂度证明可以参考 vectorwyx 的题解

只考虑 (a_{i}) 的百位数，那么，当 (a_{i}) 首次出现了百位向千位上的进位时，也就是当 (a_{i}-a_{1}ge 1000) 时，百位上一定会出现一次0。因为(1le MinDigit(x)cdot MaxDigit(x) le 81) 。

故而，累加的和最多为1000，那么累加的次数也就是 (i) 最大为1000。最坏时间复杂度为 (O(1000^{2}))，肯定不会超时。

from： https://www.luogu.com.cn/blog/_post/239684 ，侵删。

Code：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#define LL long long
using namespace std;
namespace _Bignum
{
char _c;
inline void reads(char *a)
{
	for(_c=getchar();_c<'0'||_c>'9';_c=getchar());
	for(int i=0;_c>='0'&&_c<='9';_c=getchar(),i++) 
		a[i]=_c;
	return;
}
//========================
const int _N=27;
char _ch[_N];
struct Bignum
{
	short a[_N];
	int len;
	void clear() 
	{
		memset(a,0,sizeof a);
		len=0;
		return;
	}
	template<class T>
	void equal(T x) 
	{
		clear();
		while(x) {
			a[++len]=x%10;
			x/=10;
		} 
		return;
	}
	void output()
	{
		if(len==0)
			putchar('0');
		else 
			for(int i=len;i>=1;i--) 
				putchar('0'+a[i]);
		putchar('
');
		return;
	}
	void input()
	{
		clear();
		memset(_ch,'',sizeof _ch);
		reads(_ch+1);
		len=strlen(_ch+1);
		for(int i=1;i<=len;i++) 
			a[i]=_ch[len-i+1]-'0';
		return;
	}
};
inline bool operator==(const Bignum &x,const Bignum &y)
{
	if(x.len!=y.len) 
		return false;
	for(int i=x.len;i>=1;i--) {
		if(x.a[i]!=y.a[i]) 
			return false;
	}
	return true;
}
inline Bignum operator+(const Bignum &x,const Bignum &y)
{
	int i;
	Bignum z;
	z.clear();
	z.len=max(x.len,y.len)+1;
	int tmp=0;
	for(i=1;i<=z.len;i++) {
		z.a[i]=x.a[i]+y.a[i]+tmp;
		tmp=z.a[i]/10;
		z.a[i]=z.a[i]%10;
	}
	while(z.len>1&&z.a[z.len]==0) z.len--;
	return z;
}
}
using namespace _Bignum;
//======================================
inline Bignum count(const Bignum &x)
{
	short cmax=x.a[1];
	short cmin=x.a[1];
	for(int i=2;i<=x.len;i++) {
		cmax=max(cmax,x.a[i]);
		cmin=min(cmin,x.a[i]);
	}
	Bignum z;
	z.equal(cmax*cmin);
	return z;
}
int T;
const int N=10000;
Bignum a[N];
int main()
{
//	freopen("1.in","r",stdin);
	register LL i;
	LL n;
	scanf("%d",&T);
	while(T--) {
		a[1].input();
		scanf("%lld",&n);
		for(i=2;i<=n;i++) {
			a[i]=a[i-1]+count(a[i-1]);
			if(a[i]==a[i-1]) {
				a[i].output();
				break;
			}
		}
		if(i==n+1) 
			a[i-1].output();
	}
	return 0;
}

P.S. 好像不用高精度也可以。

B. Young Explorers

题意：

给定一个正整数 N 和一个长度为 N 的数组 (e_{1},e_{2}…e_{N}(1le e_{i} le N))。

请你将这个数组尽可能多地划分成若干个两两之间没有重复元素的子序列，每个子序列的长度要大于等于这个子序列中最大的数。

请注意，你可以在划分之前把原数组的一些数去掉。换句话说，允许原数组中的一些数不属于你所划分的任意子序列。你只需要最大化划分的数量。

你需要回答 t 组独立的测试用例。

翻译 by vectorwyx from : https://www.luogu.com.cn/problem/CF1355B

思路：排序，小的小的放一起。

证明：调整法。

Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
namespace FastIO
{
const int _SIZE = (1 << 21) + 1;
char ibuf[_SIZE],obuf[_SIZE];
char *iS,*iT;
char c;
char qu[55];
char *oS=obuf,*oT=oS+_SIZE-1;
bool _sign=false;
int qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, _SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
// print the remaining part
inline void flush() 
{
    fwrite(obuf,1,oS-obuf,stdout);
    oS=obuf;
    return;
}
// putchar
inline void putc(const char &x) 
{
    *oS++=x;
    if(oS==oT)
        flush();
    return;
}
inline char getc()
{
	return gc();
}
// input a signed integer
template <class T>
inline void read(T &x) 
{
	x=0;
	_sign=false;
    for (c=gc();c<'0'||c>'9';c=gc())
        if (c=='-')
            _sign=true;
    for (;c>='0'&&c<='9';c=gc()) 
		x=(x<<1)+(x<<3)+(c&15);
    x=(_sign) ? (~x+1) : x;
    return;
}
// print a signed integer
template <class T>
inline void print(T x) {
    if (!x) {
    	putc('0');
    	return;
	}
    if (x<0)
        putc('-'),x=~x+1;
    while(x) qu[++qr]=x%10+'0',x/=10;
    while(qr) putc(qu[qr--]);
    return;
}
// no need to call flush at the end manually!
struct Flusher_ 
{
    ~Flusher_() { flush(); }
}io_flusher_;
}  // namespace io
using FastIO::read;
using FastIO::print;
using FastIO::putc;
using FastIO::getc;
//==========================================================
const int N=2e5+5;
int T;
int n;
int a[N];
int main()
{
//	freopen("1.in","r",stdin);
	register int i;
	register int x,z;
	bool flag;
	int ans;
	read(T);
	while(T--) {
		read(n);
		for(i=1;i<=n;i++) 
			read(a[i]);
		sort(a+1,a+n+1);
		flag=false;
		ans=0;
		x=0;
		z=0;
		for(i=1;i<=n;i++) {
			if(flag==false) {
				flag=true;
				x=a[i];
				z=1;
			}
			else {
				x=max(x,a[i]);
				z++;
			}
			if(z==x) {
				flag=true;
				ans++;
				x=0;
				z=0;
			}
		}
		print(ans);
		putc('
');
	}
	FastIO::flush();
	return 0;
}

C. Count Triangles

题意

Like any unknown mathematician, Yuri has favourite numbers: A , B , C, and D , where $A leq B leq C leq D $ . Yuri also likes triangles and once he thought: how many non-degenerate triangles with integer sides x , y , and z exist, such that (A leq x leq B leq y leq C leq z leq D) holds?

思路：枚举 (z) , (O(1)) 求 合法的 (x,y) 个数.

Code：

#include<cstdio>
#include<iostream>
#define LL long long
#define rint register int
using namespace std;
const int N=5e5+5;
LL f[N];
int main()
{
//	freopen("1.in","r",stdin);
	rint i;
	LL A,B,C,D;
	LL well=0,bad=0;
	cin>>A>>B>>C>>D;
	LL ans=(B-A+1)*(C-B+1)*(D-C+1);
	for(i=A+B;i<=D;i++) {
		well=min(well+1ll,B-A+1ll);
		bad=min(max(0ll,i-(A+B)+1-(C-B+1)),B-A+1ll);
		f[i]=f[i-1]+well-bad;
	}
	for(i=C;i<=D;i++) 
		ans-=f[i];
	cout<<ans;
	return 0;
}

细节挺多。

E. Game With Array

给出两个数N ,S

问是否可以找到一个序列和一个数 (K(0<=K<=S))满足：存在一个长度为N，和为S序列,在其中找不到一个子段的和为K或者S-K

from : https://www.luogu.com.cn/problem/CF1355D

构造题。

若中间一段为 (S-K) 则首尾两段加起来是 (K) .

所以不妨把数组首尾相接成一个环，那么要满足任何一段不为 (K) 即可。

然后一个很自然的想法就是让环上的每一个数都 (>K) , 这样任何一段和都不为 (K) 。

也就是我们要让 每个数的最大值最小 ， 把 (S) 分的均匀即可。

然后判断最小值是否 (>1) , 若可以，取 (K=1), 否则无解。

正确性证明：

• 充分性：充分性很好证明，上述过程就是。

• 必要性：最小的数为 (lfloor frac{S}{N} floor) , 只要证明 (lfloor frac{S}{N} floor=1) 时无解。

当 (lfloor frac{S}{N} floor=1) 时，考虑用前缀和，一扶苏一 的题解 。

Code：

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

int n,s;
int main()
{
//	freopen("1.in","r",stdin);
	
	int i;
	scanf("%d%d",&n,&s);
	if(s/n==1) return puts("NO")&0;
	
	puts("YES");
	int x=s/n+1,y=n*x-s;
	for(i=1;i<=y;i++) 
		printf("%d ",x-1);
	for(i=y+1;i<=n;i++)
		printf("%d ",x);
	printf("
%d
",s/n-1);
	return 0;
}

F. Guess Divisors Count

人生中第一道交互题。

猜一个 (X) 的约数个数, 你每次可以给出一个 (Q,1 leq Q leq 10^{18}) , 询问 (gcd(Q,X)) 。

只要满足 你的答案 与 标准答案 差不超过 (1) 或 不小于一半 且 不超过两倍 就 Accept 了。

最多询问 22 次。

思路：

考虑： (X=p_{1}^{c_{1}}p_{2}^{c_{2}}p_{3}^{c_{3}}...p_{n}^{c_{n}})

[d(X)=(c_{1}+1)(c_{2}+1)(c_{3}+1)...(c_n+1) ]

所以求质因数集合即可。

可以一个个质数询问，不过太慢了。

可以把质数乘起来一起问，如果有质因子的话，质因数幂次翻倍问。

22 次一定求不完整，观察到我们求出的 d 一定 <= ans , 输出 d*2 就完美了。

Code：

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL,LL> PLL;

LL hide;
LL gcd(LL a,LL b)
{
	if(b==0) return a;
	else return gcd(b,a%b);
}

const int N=1e5+5;

int p[N],tot;
bool tag[N];
void prime(int n)
{
	int i,j;
	for(i=2;i<=n;i++) {
		if(!tag[i]) p[++tot]=i;
		for(j=1;j<=tot && i*p[j]<=n;j++) {
			tag[i*p[j]]=true;
			if(i%p[j]==0) break;
		}
	}
}

void divide(LL x,vector<PLL>& v)
{
	v.clear();
	for(int i=1;i<=tot && x>1;i++) {
		if(x%p[i]==0) {
			v.push_back(PLL(p[i],0));
			while(x%p[i]==0) {
				v[v.size()-1].second++;
				x/=p[i];
			}
		}
	}
	if(x>1) v.push_back(PLL(x,1));
}

LL ans;
int times;

void query(LL x);
LL cur=1;
void insert(LL pr,int limit)
{
	if(times>=22) return;
	LL x=1,cnt=1;
	while(x<=1.5e9/ans/pr && cnt<=limit) x*=pr,cnt++;
	if(cur<=0.999e18/x) cur*=x;
	else {
		swap(cur,x);
		query(x);
	}
}

void query(LL x)
{
	if(times>=22) return;
	times++;
	cout<<"? "<<x<<endl;
	cout.flush();
	LL ret;
	cin>>ret; 
//	ret=gcd(hide,x);
//	cout<<ret<<endl;
	vector<PLL> v,vx;
	divide(x,vx);
	divide(ret,v);
	for(int i=0,k=0;i<(int)v.size();i++) {
		while(vx[k].first<v[i].first) k++;
		if(vx[k].second==v[i].second) {
			insert(v[i].first,v[i].second*6);
			continue;
		}
		for(int j=1;j<=v[i].second;j++) 
			ans*=v[i].first;
	}	
}

LL calc(LL ans)
{
	vector<PLL> v;
	divide(ans,v);
	LL cnt=1;
	for(int i=0;i<(int)v.size();i++) 
		cnt*=(v[i].second+1);
	return cnt;
}

vector<PLL> v;
int T;

int main()
{
	prime(N-1);
	
	cin>>T;
	while(T--) {
//		cin>>hide;
		ans=1,times=0;
		cur=1;
		for(int pcnt=1;pcnt<=tot && times<22;pcnt++) 	
			insert(p[pcnt],1);
			
		cout<<"! "<<(int)(2*calc(ans))<<endl;
		cout.flush();
		
//		if(calc(ans)*2<calc(hide) || calc(ans)>calc(hide)*2) {
//			puts("NO");
//			cout<<calc(hide)<<endl;
//			divide(hide,v);
//			for(int i=0;i<(int)v.size();i++) 
//				printf("%lld %lld
",v[i].first,v[i].second);
//			system("pause > nul");
// 		}
	}
	return 0;
}

// 54375734,731808000

具体实现的时候可以弄一个类似缓存区的东西，>1e18 就询问清空。

这样的方法大概可以把 (900) 以内的质数试一遍，而 (900) 以上最多有 (3) 个质因子。

• 若有 3 个 ，(d(x)=8) , 输出 (2) 符合题意。
• 若有 2 个，剩余在九百以内，差 4 倍 ，由于乘了 (2) , 差 2 倍，符合题意。
• 若有 1 个，完美命中。
• 若有 0 个， 会出输出实际的两倍，符合题意。

由此，此法正确。

若不 *2 , 有 2 个的情况就不行。