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

AtCoder Grand Contest 044

时间：2023-09-27 18:55:17浏览次数：34  
标签：AtCoder include return Contest int long ge frac 044

A - Pay to Win

不妨将操作倒过来考虑，问题就变成了每次除以 \(2,3,5\) 或者 \(+1,-1\)，令 \(f_n\) 表示将 \(n\) 变成 \(0\) 的最小花费，然后记忆化搜索即可，可以证明复杂度是对的。

代码：

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int T;
long long n;
int a,b,c,d;
map<long long,long long>f;
long long dfs(long long n)
{
	if(n==0) return 0;
	if(n==1) return d;
	if(f[n]) return f[n];
	long long x=n/2*2,y=(n+1)/2*2;
	f[n]=min(dfs(x/2)+1LL*(n-x)*d+a,dfs(y/2)+1LL*(y-n)*d+a);
	x=n/3*3,y=(n+2)/3*3;
	f[n]=min(f[n],min(dfs(x/3)+1LL*(n-x)*d+b,dfs(y/3)+1LL*(y-n)*d+b));
	x=n/5*5,y=(n+4)/5*5;
	f[n]=min(f[n],min(dfs(x/5)+1LL*(n-x)*d+c,dfs(y/5)+1LL*(y-n)*d+c));
	f[n]=min((__int128)f[n],(__int128)n*d);
	return f[n];
}
void solve()
{
	scanf("%lld%d%d%d%d",&n,&a,&b,&c,&d);
	f.clear();
	printf("%lld\n",dfs(n));
	return;
}
int main()
{
	scanf("%d",&T);
	while(T--)
		solve();
	return 0;
}

B - Joker

当位于 \((x,y)\) 离开时我们将这个点的最短路加进答案里，将这个点标记为离开，然后用这个点去暴力更新每个点的最短路。可以发现最短路的权值之和为 \(O(n^3)\) 的级别，每次至少使得最短路 \(-1\)，时间复杂度为 \(O(n^3)\)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=505;
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n;
int p[N*N];
pair<int,int> pos[N*N];
int dis[N][N];
bool vis[N][N];
void dfs(int x,int y)
{
	for(int i=0;i<4;i++)
	{
		int tx=x+dir[i][0],ty=y+dir[i][1];
		if(tx<0||tx>n||ty<0||ty>n) continue;
		int d=dis[x][y];
		if(!vis[tx][ty]) d++;
		if(dis[tx][ty]>d)
		{
			dis[tx][ty]=d;
			dfs(tx,ty);
		}
	}
	return;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n*n;i++)
	{
		scanf("%d",&p[i]);
		pos[i]=make_pair((p[i]-1)/n+1,p[i]%n==0?n:p[i]%n);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dis[i][j]=min({j-1,n-j,i-1,n-i});
	long long ans=0;
	for(int i=1;i<=n*n;i++)
	{
		int x=pos[i].first,y=pos[i].second;
		vis[x][y]=true;
		ans+=dis[x][y];
		dis[x][y]--;
		for(int i=0;i<4;i++)
		{
			int tx=x+dir[i][0],ty=y+dir[i][1];
			dis[x][y]=min(dis[x][y],dis[tx][ty]);
		}
		dfs(x,y);
	}
	printf("%lld",ans);
	return 0;
}

C - Strange Dance

从高位到低位插入 Trie 很难处理，考虑从低位到高位插入 Trie，每个叶子节点记录一下当前的数为多少。S 操作就可以在节点上打上翻转标记。R 操作可以将子树 \(0\to 1,1\to 2,2\to 0\) 其中 \(2\) 中可能会对下一位进位，递归下去就好了，最后将每个点的位置在 Trie 上找出来就是了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int M=15,N=600005;
int n,m,Q;
char s[N];
int Pw[M];
struct Trie
{
	struct Node
	{
		int ch[3];
		int val;
		int tag;
		Node()
		{
			ch[0]=ch[1]=ch[2]=0;
			val=-1;
			tag=0;
			return;
		}
	}trie[N*3];
	int tot=1;
	void insert(int x)
	{
		vector<int>v;
		int t=x;
		while(t)
			v.push_back(t%3),t/=3;
		while(v.size()<m)
			v.push_back(0);
		int u=1;
		for(int c:v)
		{
			if(!trie[u].ch[c]) trie[u].ch[c]=++tot;
			u=trie[u].ch[c];
		}
		trie[u].val=x;
		return;
	}
	void push_down(int u)
	{
		if(!trie[u].tag) return;
		swap(trie[u].ch[1],trie[u].ch[2]);
		for(int i=0;i<3;i++)
			trie[trie[u].ch[i]].tag^=1;
		trie[u].tag=0;
		return;
	}
	void reverse(int u)
	{
		trie[u].tag^=1;
		return;
	}
	void add(int u)
	{
		if(!u) return;
		push_down(u);
		int t=trie[u].ch[2];
		trie[u].ch[2]=trie[u].ch[1];
		trie[u].ch[1]=trie[u].ch[0];
		trie[u].ch[0]=t;
		add(trie[u].ch[0]);
		return;
	}
	void query(int u,int sum,int dep,vector<int>&res)
	{
		if(!u) return;
		push_down(u);
		if(trie[u].val!=-1) res[trie[u].val]=sum;
		for(int i=0;i<3;i++)
			query(trie[u].ch[i],sum+i*Pw[dep],dep+1,res);
		return;
	}
}T;
int main()
{
	scanf("%d",&m);
	Pw[0]=1;
	for(int i=1;i<=m;i++)
		Pw[i]=Pw[i-1]*3;
	n=Pw[m];
	scanf("%s",s+1);
	Q=strlen(s+1);
	for(int i=0;i<n;i++)
		T.insert(i);
	for(int i=1;i<=Q;i++)
		if(s[i]=='S') T.reverse(1);
		else if(s[i]=='R') T.add(1);
	vector<int>res;
	res.resize(n);
	T.query(1,0,0,res);
	for(int u:res)
		printf("%d ",u);
	return 0;
}

D - Guess the Password

我们可以用构造出一个长度为 \(L\)，字符为 \(c\) 的字符串，询问之后就可以得出每个字符在串中的出现次数 \(cnt_c\)，将他们的和相加即可得到字符串的长度 \(len\)。

可以发现，我们可以用一次操作判断一个串是否是原串的子序列。

考虑如果字符集只有 \(0,1\) 的时候怎么做。考虑从左到右确定每个位置的字符。考虑判断当前位是否为 \(0\)，我们可以构造一个 \(011\ldots 1\) 将目前可以填的所有 \(1\) 填成一个串，在前面加入一个 \(0\)。如果这是原串的一个子序列，则当前位为 \(0\)，否则当前位为 \(1\)。

仔细思考上面的过程，可以发现同样适合于两个无交的字符集合的情况。那么就可以得出了，用归并的方法，每次将两个字符集合并成原串的一个子序列，询问次数为 \(O(L\log 62)\)。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int L=128,N=65;
const char ch[]={"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"};
int len;
int cnt[N];
int query(const string &s)
{
	cout<<"? "<<s<<endl; 
	int ans;
	cin>>ans;
	return ans;
}
bool check(const string &s)
{
	return query(s)==len-s.size();
}
string merge(int l,int r)
{
	if(l==r) return string(cnt[l],ch[l]);
	int mid=(l+r)/2;
	string a=merge(l,mid),b=merge(mid+1,r);
	string t;
	int i=0,j=0;
	while(i<a.size()&&j<b.size())
	{
		if(check(t+a[i]+b.substr(j))) t+=a[i],i++;
		else t+=b[j],j++;
	}
	while(i<a.size())
		t+=a[i],i++;
	while(j<b.size())
		t+=b[j],j++;
	return t;
}
int main()
{
	for(int i=0;i<62;i++)
		cnt[i]=L-query(string(L,ch[i])),len+=cnt[i];
	string ans=merge(0,62);
	cout<<"! "<<ans<<endl;
	return 0;
}

E - Random Pawn

可以发现，可以在最大值那里肯定会停止，我们可以将环断成两段，问题变成了序列上的问题。

考虑如果没有 \(b_i\) 的代价的时候怎么做。可以发现一个结论：

在长度为 \(L\) 的数轴上的位置 \(x\) 处，每次可以等概率的向左或者向右走一步，只有当到达 \(0,L\) 的时候才停止，则到达 \(L\) 停止的概率为\(\frac {x}{L}\)，到达 \(0\) 停止的概率为 \(\frac {L-x}{L}\)。

证明：

令 \(f_i\) 表示当前位于 \(i\) 到达 \(L\) 的概率，则 \(f_0=0,f_L=1\)，可以得出 \(f_i=\frac{f_{i-1}+f_{i+1}}{2}\)，那么解出的 \(f_i=\frac{i}{L}\)，原命题得证。

我们称一个点为停止点当且仅当这个点移动的收益比当前点停止的收益低。

可以发现，如果当前点为 \(i\)，移动的期望收益一定是由 \(i\) 前面第一个停止点 \(a\) 和后面第一个停止点 \(b\) 贡献的。到达 \(a\) 停止的概率为\(\frac {b-i}{b-a}\)，到达 \(b\) 停止的概率为 \(\frac {i-a}{b-a}\)，那么 \(i\) 移动的期望收益为 \(A_a\cdot \frac {b-i}{b-a}+A_b\cdot \frac {i-a}{b-a}\)。

考虑如何求出所有的停止点，令第 \(i\) 个点的坐标为 \((i,A_i)\)，可以发现，第 \(i\) 个点移动的期望即为 \(x=i\) 时 \(a-b\) 这条线段的 \(y\) 值，停止点的条件即为 \(A_i\) 需要比这条线段高。那么停止点显然在一个凸包内，维护一个上凸壳即可。

考虑如果 \(b_i\) 的代价的时候，式子就变成了 \(f_i=\max(A_i, \frac{f_{i-1}+f_{i+1}}{2}-b_i)\)，我们需要将它变换成 \(g_i=\max(A_i',\frac{g_{i-1}+g_{i+1}}{2})\) 的形式，令 \(c_i=f_i-g_i\)，那么

\[\begin{aligned}g_i&=f_i-c_i \\ &=\max(A_i-c_i, \frac{f_{i-1}+f_{i+1}}{2}-b_i-c_i) \\ &=\max(A_i-c_i, \frac{g_{i-1}+c_{i-1}+g_{i+1}+c_{i+1}}{2}-b_i-c_i) \\ &=\max(A_i-c_i,\frac{g_{i-1}+g_{i+1}}{2}+\frac{c_{i-1}+c_{i+1}}{2}-b_i-c_i)\end{aligned} \]

我们可以构造出一种 \(c_i\)，使得 \(\frac{c_{i-1}+c_{i+1}}{2}-b_i-c_i=0\)，令 \(A_i'=A_i-c_i\)，则式子变成了 \(g_i=\max(A_i',\frac{g_{i-1}+g_{i+1}}{2})\) 的形式，维护一个上凸壳即可。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200005;
int n;
long long A[N];
int b[N];
long long c[N];
long long a[N];
struct Point
{
	int x;
	long long y;
};
double slope(Point a,Point b)
{
	return (double)(b.y-a.y)/(b.x-a.x);
}
Point p[N];
Point s[N];
int top;
int pos[N];
bool book[N];
long long ans[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&A[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	int Max=max_element(A+1,A+n+1)-A;
	rotate(A+1,A+Max,A+n+1);
	rotate(b+1,b+Max,b+n+1);
	n++;
	A[n]=A[1],b[n]=b[1];
	c[1]=c[2]=0;
	for(int i=2;i<=n;i++)
		c[i+1]=2*b[i]+2*c[i]-c[i-1];
	for(int i=1;i<=n;i++)
		a[i]=A[i]-c[i];
	for(int i=1;i<=n;i++)
	{
		p[i]=(Point){i,a[i]};
		while(top>=2&&slope(s[top-1],s[top])<=slope(s[top-1],p[i])) top--;
		s[++top]=p[i];
	}
	for(int i=1;i<=top;i++)
		pos[i]=s[i].x,book[pos[i]]=true;
	long double ans=0;
	for(int i=2;i<=n;i++)
		ans+=c[i];
	for(int i=2;i<=n;i++)
		if(book[i]) ans+=p[i].y;
		else
		{
			int a=lower_bound(pos+1,pos+top+1,i)-pos-1,b=upper_bound(pos+1,pos+top+1,i)-pos;
			a=pos[a],b=pos[b];
			ans+=(long double)(p[a].y*(b-i)+p[b].y*(i-a))/(b-a);
		}
	printf("%.12Lf",ans/(n-1));
	return 0;
}

F - Name-Preserving Clubs

考虑建一个 \(k\times n\) 的 \(01\) 矩阵，每个位置表示这个集合中是否包含这个元素。

考虑任意两个集合都不同的情况。

称一个矩阵是好的，当且仅当任意打乱它的列，不存在一种方式使得打乱行和最初的矩阵相同。可以发现，一个好的矩阵的条件任意两列都不同。

假设一个矩阵 \(A\) 是好的，可以注意到下面两个性质：

  • \(A\) 的转置 \(A^T\) 是好的。
  • 考虑 \(2^k\) 种不同的列，由其中所有不存在于 \(A\) 的列构成的矩阵 \(A^C\) 也是好的。

注意到行列操作是独立的，因此先打乱行，再打乱列是等价的。

根据上面的讨论，我们可以得出以下结论：

设 \(c(k,n)\) 表示本质不同的 \(k\times n\) 的好的矩阵的数量，那么有 \(c(k,n)=c(n,k),c(k,n)=c(k,2^k-n)\)。

设 \(g(n)\) 表示最小的 \(k\) 使得 \(c(k,n)> 0\)，那么有：

\(2^{g(n)}-n\ge g(g(n))\)

证明：

\(c(g(n),n)=c(g(n),2^{g(n)}−n)=c(2^{g(n)}−n,g(n))> 0\)。则根据 \(g\) 的定义有 \(2^{g(n)}-n\ge g(g(n))\)。

令 \(G(n)\) 满足 \(G(1)=0\)，\(G(n)\) 是最小的 \(k\) 满足 \(2^k-n\ge G(k)\)。

引理 1：\(G(i)< i\)。

证明：

考虑证明 \(2^{i-1}-i\ge G(i-1)\)

  • 对于 \(i=1\) 显然；
  • 对于 \(i> 1\) 的情况，\(G(i-1)\leq i-2\leq 2^{i-1}-i\)，得证。

引理 2：对于 \(n> 1\)，有 \(G(i)\ge G(i−1)\)。

证明：

因为满足 \(2^{G(i)}-G(i)\ge i\) 的 \(G(i)\) 必然满足 \(2^{G(i)}-G(i)\ge i-1\)，故 \(G(i)\ge G(i−1)\)。

引理 3：对于 \(n> 1\)，\(0\leq G(i)-G(i-1)\leq 1\)。

证明：

  • 当 \(n=2,3\) 时显然；
  • 对于 \(i> 3\) 的情况，\(2^{G(i−1)}-(i-1)\ge G(G(i−1))\)，\(2^{G(i-1)}\ge 2\)，所以有 \(2^{G(i - 1) + 1} - i \ge 2^{G(i - 1)} + 1 - (i - 1) \ge G(G(i - 1)) + 1 \ge G(G(i - 1) + 1)\)。

引理 4：对于 \(k\ge G(n)\)，有 \(2^k-n\ge G(k)\)。

证明：

  • 当 \(k=G(n)\) 显然；
  • 对于 \(k> G(n)\) 的情况，有 \(2^k-n\ge 2^{k−1}+1−n\ge G(k−1)+1\ge G(k)\)。

引理 5：当且仅当 \(G(n)\leq k\leq 2^n−G(n)\) 时，\(c(k,n)> 0\)。

证明：

考虑证明充分性。

当 \(k=1\) 显然；

考虑 \(k> 1\) 的情况。

  • \(G(n)-k< n\)，不妨令 \(k> n\)。

由 \(k\ge G(n)\) 可得 \(2^k−n\ge G(k)\)，所以有 \(n\leq 2^n-G(k)\)。

由 \(k\le 2^n- G(n)\) 可得 \(2^n−k\ge G(n)\)，故 \(n\geq G(k)\)，得证。

  • \(k> 2^{n−1}\)。

考虑证明 \(G(n)-2n−k\)。又 \(2^n−G(n)\ge k\) 得证。

  • \(k< 2^{n−1}\) 时同理。

  • \(n \leq k \leq 2^{n - 1}\)。

考虑构造一个集合 \(\{(1),(1,2),(2,3),\cdots ,(n−1,n)\}\)。剩下的填 \(k−n\) 个大小 \(\ge 3\) 的集合。

可以得出 \(n=2,3\) 合法；当 \(n\ge 4\) 的时候，大小 \(\ge 3\) 的集合的个数大于一半，得证。

引理 4：当 \(6 \leq k \leq n \leq 2^{k - 1}\) 时，$ c(k,n)> 1000$

考虑先构造一个大小为 \(k−2\) 的集合，包含 \(\{(1,2),(2,3),\cdots ,(n−1,n)\}\)，然后将其中一个或者其中 \(k−3\) 个取补集。剩下的 \(n−k+2\) 个集合任意放大小不为 \(2\) 或者 \(k−2\) 的集合。

结论是 \(n=4\) 的时候答案加上 \(1\)，\(n=7\) 的时候答案加上 \(2\).

剩下的情况就是 \(k\leq 5,n\leq 2^{k−1}\)，暴搜后打表即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int res[6][20]={{},
{1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,4,6,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,36,108,220,334,384,0,0,0,0,0,0,0,0},
{0,0,0,0,0,976,1001,1001,1001,1001,1001,1001,1001,1001,1001,1001,1001}};
const int N=1005;
int G[N];
void init()
{
	G[1]=0;
	for(int n=2;n<=1000;n++)
	{
		for(int k=1;k<n;k++)
			if((1LL<<k)>=n&&((1LL<<k)-n)>=G[k])
			{
				G[n]=k;
				break;
			}
		if(G[n]==0) G[n]=-1;
	}
	return;
}
int g(long long n)
{
	if(n<=1000) return G[n];
	for(int k=1;;k++)
		if((1LL<<k)>=n&&((1LL<<k)-n)>=g(k)) return k;
	return -1;
}
int solve(long long n,long long k)
{
	if(n<k) swap(n,k);
	if(k<63&&(1LL<<k)-n<n) return solve((1LL<<k)-n,k);
	if(k>5) return 1001;
	if(k==0) return 1;
	return res[k][n];
}
long long n;
int main()
{
	init();
	scanf("%lld",&n);
	int ans=solve(n,g(n));
	if(n==4) ans++;
	if(n==7) ans+=2;
	if(ans>1000) printf("-1");
	else printf("%d",ans);
	return 0;
}

标签：AtCoder,include,return,Contest,int,long,ge,frac,044
From： https://www.cnblogs.com/zhou-jk/p/17733447.html

相关文章

  • 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);......
  • AtCoder Beginner Contest 320 ABCDE
    AtCoderBeginnerContest320A-LeylandNumber思路：直接快速幂//AConemoretimes//nndbk#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmod=1e9+7;constintN=2e5+10;llqmi(lla,llb){llans=1;whil......
  • AtCoder Beginner Contest 253 E
    AtCoderBeginnerContest253E-DistanceSequence思路：前缀和优化DP要求$|a[i]-a[i+1]|>=k\(定于\)dp[i][j]:\(前\)i\(个数以\)j\(结尾的合法序列数列\)dp[i][j]+=dp[i-1][1～(j-k)]+dp[i-1][(j+k)～m]$直接写的话复杂度是\(O(nm^2)\)的会TLE，我们发现可以做一个前缀和优化......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99