AtCoder Grand Contest 047

2023-12-26 15:25:21

A - Integer Product

考虑将原来的数全部化为整数，乘上 \(10^9\)，那么问题就变成了是否有两个数的乘积是 \(10^{18}\) 的倍数。考虑如果是 \(10^{18}\) 的倍数的话必然是 \(2^{18}\) 和 \(5^{18}\) 的倍数，那么分解出每个数的 \(2,5\) 因子数量，然后再看看有多少个数与它 \(2,5\) 的因子个数之和分别大于 \(18\)。

代码：

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
const int N=200005;
int n;
long long a[N];
map<pair<int,int>,int>book;
int main()
{
	scanf("%d",&n);
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		double x;
		scanf("%lf",&x);
		a[i]=x*1e9+0.5;
		int cnt2=0,cnt5=0;
		while(a[i]%2==0) cnt2++,a[i]/=2;
		while(a[i]%5==0) cnt5++,a[i]/=5;
		for(auto [x,num]:book)
			if(x.first+cnt2>=18&&x.second+cnt5>=18) ans+=num;
		book[make_pair(cnt2,cnt5)]++;
	}
	printf("%lld",ans);
	return 0;
}

B - First Second

不妨将所有串翻转，方便计算。考虑两个字符串合法的条件即为一个串为另一个串的前缀或者一个串在倒数第二个字符和倒数第一个字符之间插入若干个字符是另一个串的前缀。那么用 Trie 搞一搞就好了，维护一下当前节点子树中有多少个 \(j\)，每次插入的时候更新一下就好了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200005,M=1000005;
int n;
string s[N];
struct Node
{
	int col[26];
	int ch[26];
}trie[M];
int tot=1;
void insert(const string &s)
{
	static int col[26];
	int len=s.size();
	for(int i=0;i<len;i++)
		col[s[i]-'a']++;
	int u=1;
	for(int i=0;i<len;i++)
	{
		int c=s[i]-'a';
		for(int j=0;j<26;j++)
			if(col[j]) trie[u].col[j]++;
		if(!trie[u].ch[c]) trie[u].ch[c]=++tot;
		u=trie[u].ch[c];
		col[c]--;
	}
	return;
}
int query(const string &s)
{
	int len=s.size();
	int u=1;
	for(int i=0;i<len-1;i++)
		u=trie[u].ch[s[i]-'a'];
	return trie[u].col[s[len-1]-'a']-1;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		reverse(s[i].begin(),s[i].end());
		insert(s[i]);
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
		ans+=query(s[i]);
	cout<<ans;
	return 0;
}

C - Product Modulo

令 \(f(x)=\sum\limits_{i=1}^n [a_i=x]\)，\(g(xy)=f(x)f(y)\)，那么答案就是 \(\frac{\sum\limits_i (i \bmod p)g_i - \sum\limits_i a_i^2\bmod p}2\)，发现 \(xy\) 的值可能很大，不方便计算。考虑求出 \(P\) 的一个原根，那么 \(xy\equiv g^{p_x}g^{p_y} \equiv g^{p_x+p_y}\pmod P\)，这就成了一个卷积的形式，直接 FFT 就行了。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=2000005;
const int MOD=200003;
const double Pi=acos(-1);
struct Complex
{
	double x,y;
	Complex(double xx=0,double yy=0)
	{
		x=xx,y=yy;
		return;
	}
	Complex operator+(Complex const &b)const
	{
		return (Complex){x+b.x,y+b.y};
	}
	Complex operator-(Complex const &b)const
	{
		return (Complex){x-b.x,y-b.y};
	}
	Complex operator*(Complex const &b)const
	{
		return (Complex){x*b.x-y*b.y,x*b.y+y*b.x};
	}
};
Complex W[N<<1];
void dft(vector<Complex> &f,int len)
{
	if(len==1) return;
	vector<Complex> fl,fr;
	fl.resize(len/2),fr.resize(len/2);
	for(int k=0;k<len/2;k++)
		fl[k]=f[k*2],fr[k]=f[k*2+1];
	dft(fl,len/2);
	dft(fr,len/2);
	Complex w=W[len],buf=(Complex){1,0};
	for(int k=0;k<len/2;k++)
	{
		f[k]=fl[k]+buf*fr[k];
		f[k+len/2]=fl[k]-buf*fr[k];
		buf=buf*w;
	}
	return;
}
void idft(vector<Complex> &f,int len)
{
	if(len==1) return;
	vector<Complex> fl,fr;
	fl.resize(len/2),fr.resize(len/2);
	for(int k=0;k<len/2;k++)
		fl[k]=f[k*2],fr[k]=f[k*2+1];
	idft(fl,len/2);
	idft(fr,len/2);
	Complex w=(Complex){W[len].x,-W[len].y},buf=(Complex){1,0};
	for(int k=0;k<len/2;k++)
	{
		f[k]=fl[k]+buf*fr[k];
		f[k+len/2]=fl[k]-buf*fr[k];
		buf=buf*w;
	}
	return;
}
typedef vector<long long> poly;
poly fft(const poly &F,const poly &G)
{
	vector<Complex> f,g;
	int n=F.size()-1,m=G.size()-1;
	f.resize(n+1),g.resize(m+1);
	for(int i=0;i<=n;i++)
		f[i].x=F[i];
	for(int i=0;i<=m;i++)
		g[i].x=G[i];
	for(m+=n,n=1;n<=m;n<<=1);
	for(int i=1;i<=n;i++)
		W[i]=(Complex){cos(2*Pi/i),sin(2*Pi/i)};
	f.resize(n);
	g.resize(n);
	dft(f,n);
	dft(g,n);
	for(int i=0;i<n;i++)
		f[i]=f[i]*g[i];
	idft(f,n);
	poly res;
	res.resize(m+1);
	for(int i=0;i<=m;i++)
		res[i]=(long long)(f[i].x/n+0.5);
	return res;
}
const int G=2;
int n;
int a[N];
long long powG[N],logG[N];
void init()
{
	powG[0]=1;
	logG[1]=0;
	for(int i=1;i<=MOD-2;i++)
	{
		powG[i]=powG[i-1]*G%MOD;
		logG[powG[i]]=i;
	}
	return;
}
int cnt[N];
int main()
{
	init();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]) cnt[logG[a[i]]]++;
	}
	poly f;
	f.resize(MOD-1);
	for(int i=0;i<=MOD-2;i++)
		f[i]=cnt[i];
	f=fft(f,f);
	long long ans=0;
	for(int i=0;i<f.size();i++)
		ans+=f[i]*powG[i%(MOD-1)];
	for(int i=0;i<=MOD-2;i++)
		ans-=cnt[i]*(powG[i]*powG[i]%MOD);
	printf("%lld",ans/2);
	return 0;
}

D - Twin Binary Trees

考虑第一棵树中的 LCA，计算跨过当前点的答案，将左子树中所有的叶子节点遍历一遍，找到对应的第二棵树中的节点，然后暴力往上跳，将所有的祖先都打上路径上的乘积的标记就行了，然后在遍历右子树中的所有叶子节点，然后在第二课树中合并一下答案就好了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=(1<<18)+5;
const int MOD=1000000007;
int H,L;
int n;
int p[N];
long long tag[N];
void jump(int u,long long fac)
{
	if(!u) return;
	tag[u]=(tag[u]+fac)%MOD;
	jump(u/2,fac*(u/2)%MOD);
	return;
}
void add(int u,long long fac)
{
	if(u>n) return;
	if(u>=L)
	{
		jump(L+p[u]-1,fac*(L+p[u]-1)%MOD);
		return;
	}
	add(u*2,fac*(u*2)%MOD),add(u*2+1,fac*(u*2+1)%MOD);
	return;
}
long long ans;
void getans(int u,long long fac,int pre)
{
	if(!u) return;
	ans=(ans+(tag[u]-tag[pre]*u%MOD+MOD)*fac%MOD)%MOD;
	getans(u/2,fac*u%MOD,u);
	return;
}
void solve(int u,long long fac)
{
	if(u>n) return;
	if(u>=L)
	{
		getans(L+p[u]-1,fac*u%MOD,0);
		return;
	}
	solve(u*2,fac*u%MOD),solve(u*2+1,fac*u%MOD);
	return;
}
void clear(int u)
{
	if(!u) return;
	tag[u]=0;
	clear(u/2);
	return;
}
void remove(int u)
{
	if(u>n) return;
	if(u>=L)
	{
		clear(L+p[u]-1);
		return;
	}
	remove(u*2),remove(u*2+1);
	return;
}
void dfs(int u)
{
	if(u>n) return;
	add(u*2,u*2),solve(u*2+1,u);
	remove(u*2);
	dfs(u*2),dfs(u*2+1);
	return;
}
int main()
{
	scanf("%d",&H);
	n=(1<<H)-1;
	L=1<<(H-1);
	for(int i=1;i<=L;i++)
		scanf("%d",&p[L+i-1]);
	dfs(1);
	printf("%lld",ans);
	return 0;
}

E - Product Simulation

如果 \(A=B=0\) 的话，无论怎么做答案都是 \(0\)，可以不用管这种情况。

可以先搞出 \(2\) 的幂次来，方便以后的操作。

考虑 \(A\leq 1,B\leq 1\) 时怎么做，这就相当于 \(\min\) 的操作，看下 \(1\leq A+B\) 的值就好了。

那么就可以将 \(A,B\) 分别二进制拆分，然后答案就是 \(\sum\limits_{i}\sum\limits_{j} A_iB_j 2^{i+j}\)。

其中对于 \(a=0/1\) 乘 \(2^{x}\) 次可以用将 \(a\) 自增 \(x\) 次的方法。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200005;
int tot=2;
long long a[N];
struct Node
{
	int op,x,y,k;
};
vector<Node>res;
void _add(int x,int y,int k)
{
	a[k]=a[x]+a[y];
	res.push_back((Node){0,x,y,k});
	return;
}
void _comp(int x,int y,int k)
{
	a[k]=a[x]<a[y];
	res.push_back((Node){1,x,y,k});
	return;
}
int getmin(int x,int y)
{
	int k=++tot;
	_comp(k,x,k);
	_comp(k,y,++tot);
	_add(k,tot,k);
	_add(x,y,tot);
	_comp(k,tot,k);
	return k;
}
int pos2[N];
int get1(int x,int y)
{
	int k=++tot;
	_add(x,y,k);
	_add(k,k,k);
	_comp(x,k,k);
	return k;
}
void get2()
{
	pos2[0]=get1(0,1);
	for(int i=1;i<=30;i++)
	{
		pos2[i]=++tot;
		_add(pos2[i-1],pos2[i-1],pos2[i]);
	}
	return;
}
int Pw(int p,int b)
{
	int r=++tot;
	_add(r,p,r);
	for(int i=1;i<=b;i++)
		_add(r,r,r);
	return r;
}
void divide(vector<int>&res,int p)
{
	int cur=++tot;
	res.resize(61);
	for(int i=30;i>=0;i--)
	{
		int tmp1=++tot;
		_add(cur,pos2[i],tmp1);
		int tmp2=++tot;
		_add(p,pos2[0],tmp2);
		res[i]=++tot;
		_comp(tmp1,tmp2,res[i]);
		_add(cur,Pw(res[i],i),cur);
	}
	return;
}
void mul(const vector<int>&A,const vector<int>&B)
{
	int res=2;
	for(int i=0;i<=30;i++)
		for(int j=0;j<=30;j++)
		{
			int c=getmin(A[i],B[j]);
			_add(res,Pw(c,i+j),res);
		}
	return;
}
int main()
{
	a[0]=2,a[1]=3;
	get2();
	vector<int>A,B;
	divide(A,0);
	divide(B,1);
	mul(A,B);
	printf("%u\n",res.size());
	for(Node u:res)
		if(u.op==0) printf("+ %d %d %d\n",u.x,u.y,u.k);
		else printf("< %d %d %d\n",u.x,u.y,u.k);
	return 0;
}

F - Rooks

考虑一个朴素的想法，令 \(f_{l,r,0/1}\) 表示 \([l,r]\) 区间内的点已经吃掉，那么从 \(f_{l-1,r,0/1}\) 和 \(f_{l+1,r,0/1}\) 转移过来就是了，答案就是 \(f_{i,i,0}\)。

考虑对于单调的一些点怎么做，那么肯定是先走到左下角或者右上角然后在走到另一个点是最优的，取个最小值即可。

考虑如果只求一个点的答案，那么答案是将原图划分成一层层单调的矩形的样子，外面的矩形是包含当前矩形的，然后从当前矩形向外面矩形转移。

那么将所有的单调的块缩起来，然后跑记搜就好了，注意吃掉一个点它就要在曼哈顿距离的基础上 \(-1\)。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
const int N=200005;
const long long INF=1e18;
int n;
int x[N],y[N];
int pre[N],nxt[N];
struct Node
{
	int x,y,id;
}pos[N];
vector<int>val;
int id[N];
int dis(int a,int b)
{
	return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
map<int,long long>dp[2][N];
long long solve(int l,int r,int side,int Min,int Max)
{
	if(dp[side][l][r]) return dp[side][l][r];
	long long res=INF;
	if(l>1&&(pos[l-1].y==Min-1||pos[l-1].y==Max+1))
	{
		int L=pre[l-1];
		long long tmp=solve(L,r,0,min(Min,pos[L].y),max(Max,pos[L].y))+dis(pos[L].id,pos[side?r:l].id);
		res=min(res,tmp);
	}
	if(r<n&&(pos[r+1].y==Min-1||pos[r+1].y==Max+1))
	{
		int R=nxt[r+1];
		long long tmp=solve(l,R,1,min(Min,pos[R].y),max(Max,pos[R].y))+dis(pos[R].id,pos[side?r:l].id);
		res=min(res,tmp);
	}
	if(res==INF) res=l-r;
	dp[side][l][r]=res;
	return res;
}
long long ans[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		val.push_back(y[i]);
		pos[i].x=x[i],pos[i].y=y[i],pos[i].id=i; 
	}
	sort(pos+1,pos+n+1,[](const Node &a,const Node &b){return a.x<b.x;}); 
	sort(val.begin(),val.end());
	for(int i=1;i<=n;i++)
		pos[i].y=lower_bound(val.begin(),val.end(),pos[i].y)-val.begin()+1;
	pre[1]=1;
	for(int i=2;i<=n;i++)
		if(abs(pos[i].y-pos[i-1].y)==1) pre[i]=pre[i-1];
		else pre[i]=i;
	nxt[n]=n;
	for(int i=n-1;i>=1;i--)
		if(abs(pos[i].y-pos[i+1].y)==1) nxt[i]=nxt[i+1];
		else nxt[i]=i;
	for(int i=1;i<=n;i++)
		ans[pos[i].id]=solve(i,i,0,pos[i].y,pos[i].y);
	for(int i=1;i<=n;i++)
		printf("%lld\n",ans[i]);
	return 0;
}
上一篇：UCF Local Programming Contest Round 1A 训练联盟暑假场1 题解


下一篇：AtCoder Regular Contest 120 C - Swaps 2(树状数组)