首页 > 其他分享 >AtCoder Grand Contest 047

AtCoder Grand Contest 047

时间:2023-09-27 18:56:03浏览次数:31  
标签:AtCoder return Contest int res long 047 const include

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;
}

标签:AtCoder,return,Contest,int,res,long,047,const,include
From: https://www.cnblogs.com/zhou-jk/p/17733442.html

相关文章

  • AtCoder Grand Contest 043
    A-RangeFlipFindRoute可以发现,一条路径的最小操作数等于路径上有多少#的块,令\(f_{i,j}\)表示到\((i,j)\)的最小操作次数,直接DP就行了。注意路径上一个\(1\)的块会被算两次,需要除以\(2\)。#include<iostream>#include<cstdio>#include<cstring>usingnamesp......
  • AtCoder Grand Contest 044
    A-PaytoWin不妨将操作倒过来考虑,问题就变成了每次除以\(2,3,5\)或者\(+1,-1\),令\(f_n\)表示将\(n\)变成\(0\)的最小花费,然后记忆化搜索即可,可以证明复杂度是对的。代码:#include<iostream>#include<cstdio>#include<map>usingnamespacestd;intT;longlong......
  • AtCoder Grand Contest 045
    A-XorBattle可以发现,从后往前扫,遇到一个\(1\)找后面是否有若干个\(0\)的位置的\(a_i\)与当前位置的异或和相等,用线性基维护一下就好了。代码:#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintN=205;intT;intn;longlong......
  • AtCoder Beginner Contest 318
    AtCoderBeginnerContest318A-FullMoon(atcoder.jp)以\(M\)为首项,\(P\)为公差,看\(1\simN\)里包含了多少项的个数#include<bits/stdc++.h>usingi64=longlong;usingnamespacestd;typedefpair<i64,i64>PII;intmain(){ios::sync_with_stdio......
  • AtCoder Regular Contest 165
    Preface这场前三题是上周四写的,今天课有点多本来想着把最近两场CF的博客先写下的但后面发现还有CCLCC的杂谈没写,写完发现由于晚上要上课没时间了,只能先把这场先写一下A-SumequalsLCM设\(n=\prod_{i=1}^kp_i^{c_i}\),不难发现令\(A_1=p_1^{c_1},A_2=p_2^{c_2},\cdots\),然......
  • The 2023 ICPC Asia Regionals Online Contest (2) MDIELK
    The2023ICPCAsiaRegionalsOnlineContest(2)MDIELKMDirtyWork题意:总共有\(n\)个问题,对于第\(i\)个问题需要\(a_i\)分钟。你可以随便选择一个没过的题去写,写完以后马上交,你有\(p_i\)的概率会错,错了不能跳题,你要花额外\(b_i\)的时间去\(debug\)。问你以最佳策略的最小罚......
  • The 2023 ICPC Asia Regionals Online Contest (2)
    Preface这场打的有点捞说实话,两个小时出头的时候写完6个题就开始坐牢了K题由于我习惯性地不写数论就扔给徐神了,徐神也是很有思路写了个看着就很对的东西,但不知道为什么过不去赛后发现K其实是个很傻逼的题,类似的思路我最近补CF的时候还遇到过,但就是没细想虽然当时下机的时候和......
  • AtCoder Beginner Contest 321
    A-321-likeChecker(abc321A)题目大意给定一个数,问从高位到低位,数字是不是递减的。解题思路可以以字符串读入,然后依次判断即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);......
  • 题解 AtCoder Beginner Contest 267 A~H
    ABC267solutionhttps://atcoder.jp/contests/abc267/ProblemA.Saturday题目描述输入一个表示星期的英文字符串,输出:还有多少天到星期六?solution依题意模拟。\(O(1)\)。ProblemB.Split?题目描述Robin有十个小球,如图排列成这样,然后Robin将一些球击飞了,他告诉你哪些......
  • AtCoder Beginner Contest 318 ABCDE
    AtCoderBeginnerContest318A-FullMoon思路:等差数列求项数//AConemoretimes//nndbk#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmod=1e9+7;constintN=2e5+10;intmain(){ios::sync_with_stdio(false);......