首页 > 其他分享 >freee Programming Contest 2023（AtCoder Beginner Contest 310）

freee Programming Contest 2023（AtCoder Beginner Contest 310）

时间：2023-07-17 21:01:09浏览次数：42  
标签：AtCoder CI const Beginner Contest int include RI define

Preface

打的就是依托答辩，当时看一眼D感觉是个爆搜不想写就先跳了去想F，结果傻逼了没想出来

最后30min了赶紧溜回去把D爆搜写了，但是已经罚时爆炸了，其实如果正常正序做的话排名会挺稳的

后面一问包大爷发现F是个傻逼题，只能说计数水平实在是低下

A - Order Something Else

签到题

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=1005;
int t,n,a[N],P,Q,mi=1e9;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d%d",&n,&P,&Q),i=1;i<=n;++i)
	scanf("%d",&a[i]),mi=min(mi,a[i]);
	return printf("%d",min(P,Q+mi)),0;
}

B - Strictly Superior

签到题，重在阅读题意

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=105;
int t,n,m,p[N],c[N],x,f[N][N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
	{
		for (scanf("%d%d",&p[i],&c[i]),j=1;j<=c[i];++j)
		scanf("%d",&x),f[i][x]=1;
	}
	for (i=1;i<=n;++i) for (j=1;j<=n;++j) if (i!=j)
	{
		if (p[i]<p[j]) continue;
		bool flag=1; for (k=1;k<=m;++k)
		if (f[i][k]&&!f[j][k]) { flag=0; break; }
		if (!flag) continue;
		if (p[i]>p[j]||c[i]<c[j]) return puts("Yes"),0;
	}
	return puts("No"),0;
}

C - Reversible

以后我再写自然溢出的Hash我就是傻逼好吧

Hash被卡了一发后有点急了就直接Rush了棵字典树上去，后面发现可以直接用set <string>艹过去

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=200005;
int n,m,ans; char s[N],t[N];
class Trie
{
	private:
		int ch[N][26],tot; bool ed[N];
	public:
		inline void insert(char *s,CI n)
		{
			int now=0; for (RI i=1;i<=n;++i)
			{
				if (!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++tot;
				now=ch[now][s[i]-'a'];
			}
			ed[now]=1;
		}
		inline bool find(char *s,CI n)
		{
			int now=0; for (RI i=1;i<=n;++i)
			{
				if (!ch[now][s[i]-'a']) return 0;
				now=ch[now][s[i]-'a'];
			}
			return ed[now];
		}
}T;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
	{
		scanf("%s",s+1); m=strlen(s+1); for (j=1;j<=m;++j) t[j]=s[m-j+1];
		int flag=0; for (j=1;j<=m;++j) if (s[j]!=t[j]) { flag=s[j]<t[j]; break; }
		if (flag==0) for (j=1;j<=m;++j) s[j]=t[j];
		if (!T.find(s,m)) T.insert(s,m),++ans;
	}
	return printf("%d",ans),0;
}

D - Peaceful Teams

感觉还是要一定技巧的爆搜题，如果纯搜的话可能会T（据包大爷所说）

不妨设\((now,num)\)表示当前搜索到第\(now\)个点，已经划分了\(num\)个组

考虑大力枚举这个数在前面的哪一组里，顺带维护下每个组的限制关系

当然还有一种操作就是新增一个组，这个也很好处理

这种写法的一个好处就是限制了每个组中最小的元素的标号递增，因此比起纯爆搜要少一个最后除以排列数的东西，因此跑的飞快

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=15,mod=998244353;
int n,t,m,x,y,ans,vis[N],f[N][N],c[N]; vector <int> v[N];
inline void DFS(CI now,CI num)
{
	if (num>t) return;
	if (now>n) return (void)(ans+=num==t);
	for (RI i=1;i<=num;++i)
	if (!f[i][now])
	{
		c[now]=i; for (int to:v[now]) ++f[i][to];
		DFS(now+1,num); for (int to:v[now]) --f[i][to];
	}
	c[now]=num+1; for (int to:v[now]) ++f[num+1][to];
	DFS(now+1,num+1); for (int to:v[now]) --f[num+1][to];
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d%d",&n,&t,&m),i=1;i<=m;++i)
	scanf("%d%d",&x,&y),v[x].push_back(y);
	return DFS(1,0),printf("%d",ans),0;
}

E - NAND repeatedly

考虑把所有右端点为\(i\)的区间一起考虑，设\(x_i\)表示这些区间中值为\(0\)的区间个数，\(y_i\)表示值为\(1\)的区间个数

根据新加入的一个点的权值可以很容易的写出递推关系，就很容易维护答案了

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=1000005;
int n,x[N],y[N]; char s[N]; long long ans;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i)
	{
		if (s[i]=='1') x[i]=y[i-1],y[i]=x[i-1],++y[i];
		else x[i]=1,y[i]=x[i-1]+y[i-1]; ans+=y[i];
	}
	return printf("%lld",ans),0;
}

F - Make 10 Again

其实很trivial的一道题，但想的思路可能有点问题，应该看到\(10\)第一反应就是状压的

由于这里有一个任取的要求，所有朴素的DP都不太好维护状态，不过由于要求的范围很小，所以考虑状压

设\(f_{i,S}\)表示处理了前\(i\)个骰子，其中能表示的数的状态为\(S\)的概率，不难发现\(S\)只要存储\(\le 10\)的信息即可，多余的部分没有意义

那么我们转移的时候先把\(\min(10,a_i)\)的数的选法转移了，然后考虑若\(a_i>10\)，只要把数组的值原封不动地乘上\(\frac{a_i-10}{a_i}\)即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=105,M=1<<11,mod=998244353;
int n,a[N],f[N][M],ans;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (f[0][1]=i=1;i<=n;++i)
	{
		int div=quick_pow(a[i]);
		for (j=0;j<M;++j) for (k=1;k<=min(10,a[i]);++k)
		inc(f[i][j|((j<<k)&(M-1))],1LL*f[i-1][j]*div%mod);
		if (a[i]>10) for (j=0;j<M;++j)
		inc(f[i][j],1LL*f[i-1][j]*(a[i]-10)%mod*div%mod);
	}
	for (i=0;i<M;++i) if ((i>>10)&1) inc(ans,f[n][i]);
	return printf("%d",ans),0;
}

G - Takahashi And Pass-The-Ball Game

考虑先把传球的过程做一遍，然后接下来考虑求出再做了\([0,K-1]\)遍的情况，全部累计后最后除以\(K\)即可

然后这题有一个关键的性质，就是大的操作可以拆分为若干个小的操作，而操作次数多的贡献可以向前累计到次数小的地方

直接讲有点抽象，可以看下下面这个Tutorial里的图片理解下：

因此考虑倍增求解，先预处理出\(go_{i,j}\)表示从\(i\)开始向后跳\(j\)次到达的位置，这样我们可以先把球放在对应的次数上，然后向前累计即可

具体实现可以看代码，复杂度\(O(n\log K)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<unordered_set>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair <int,int> pi;
const int N=200005,mod=998244353;
int n,a[N],b[N],go[N][60],f[N][60],ans[N]; long long k;
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%lld",&n,&k),i=1;i<=n;++i)
	scanf("%d",&a[i]),go[i][0]=a[i];
	for (i=1;i<=n;++i) scanf("%d",&b[i]);
	for (j=1;j<60;++j) for (i=1;i<=n;++i) go[i][j]=go[go[i][j-1]][j-1];
	for (i=1;i<=n;++i)
	{
		int x=i; for (j=0;j<60;++j) if ((k>>j)&1)
		inc(f[x][j],b[i]),x=go[x][j];
	}
	for (j=59;j>=0;--j) for (i=1;i<=n;++i)
	inc(f[i][j-1],f[i][j]),inc(f[go[i][j-1]][j-1],f[i][j]);
	for (i=1;i<=n;++i) inc(ans[a[i]],f[i][0]);
	int inv=quick_pow(k%mod);
	for (i=1;i<=n;++i) printf("%d ",1LL*ans[i]*inv%mod);
	return 0;
}

Postscript

寄寄寄寄，摆摆摆摆摆

标签：AtCoder,CI,const,Beginner,Contest,int,include,RI,define
From： https://www.cnblogs.com/cjjsb/p/17561213.html

相关文章

  • SMU Summer 2023 Contest Round 4
    SMUSummer2023ContestRound4A-TelephoneNumber思路：满足有8，且8后有大于等于11个数#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongtypedefpair<int,int>PII;typedefpair<string,int>PSI;typedefpair<char,int>PCI;type......
  • SMU Summer 2023 Contest Round 4
    SMUSummer2023ContestRound4A.TelephoneNumber满足第一个8后面存在10个字符即可#include<bits/stdc++.h>#defineendl'\n'#defineintlonglongusingnamespacestd;intn,m;voidsolve(){cin>>n;strings;cin>>s;......
  • AtCoder Beginner Contest 310
    PeacefulTeams\(n\)个运动员，要分成\(t\)个队伍，一共有\(m\)对人不能放在一支队伍里，求方案数，每支队伍至少需要有一个人\(1\leqt\leqn\leq10\)题解：DFS搜索通过数据范围考虑爆搜我们考虑枚举的顺序\(O(n!)\)我们对每个人\(c\)枚举将其加到当前的\(d\)支队伍中新开一......
  • AtCoder Regular Contest 092 E Both Sides Merger
    洛谷传送门AtCoder传送门Keyobservation：每个元素的下标奇偶性不改变。于是讨论最后一个数是下标为奇数还是偶数加起来的数。将下标奇偶性相同的元素分开考虑。对于下标奇偶性相同的元素，不难发现答案的上界是所有\(>0\)的元素之和（没有\(>0\)的元素时选一个最大的），并且一......
  • freee Programming Contest 2023（AtCoder Beginner Contest 310）
    freeeProgrammingContest2023（AtCoderBeginnerContest310）-AtCoderA-OrderSomethingElse(atcoder.jp)题意是在买一道菜的情况下可以将原为\(P\)元的饮料优惠到\(Q\)元,否则就按原价买#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signed......
  • AtCoder Beginner Contest 310
    （AtCoderBeginnerContest310） A-OrderSomethingElse思路：比较下打折和不打折的情况#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongtypedefpair<int,int>PII;typedefpair<string,int>PSI;typedefpair<string,string>PSS;c......
  • 近期 AtCoder Beginner Contest 题目选做
    AtCoderBeginnerContest310Ehttps://atcoder.jp/contests/abc310/tasks/abc310_e我们要求所有区间的NAND之和，发现NAND最后只可能是\(0\)或\(1\)，所以我们只需要计数区间NAND为\(1\)的即可。考虑dp，设\(f_{i,0/1}\)表示以\(i\)结尾的区间最后NAND和为\(0/......
  • freee Programming Contest 2023（AtCoder Beginner Contest 310）题解
    点我看题A-OrderSomethingElse直接比较\(P\)和\(Q+min(D_i)\)，输出较小值即可。点击查看代码#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<n;++i)#definerepn(i,n)for(inti=1;i<=n;++i)#defineLLlonglong#definefifirst#definesesecond#defi......
  • AtCoder Beginner Contest 310
    目录题目传送门：abc310比赛摘记：B题没读懂题意。。。如此简单题卡了好久继续加油哈......
  • Atcoder Regular Contest 118 F - Growth Rate
    想到插值其实就挺套路的了吧……设\(dp_{i,j}\)表示有多少种方法确定\(a_i\sima_n\)使得\(a_i=j\)。那么有\(dp_{i,j}=\sum\limits_{k\geja_i}dp_{i+1,k}\)。边界条件是\(dp_{n+1,1\simm}=1\)。不难发现复杂度与值域有关，一眼过不去的样子。考虑优化，记\(lim_i\)满足......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99