首页 > 其他分享 >AtCoder Regular Contest 172

AtCoder Regular Contest 172

时间：2024-02-29 20:15:38浏览次数：29  
标签：AtCoder typedef Hasher int long Regular include 172 define

Preface

开学了小溜一下之前没打的ARC，结果这场后面没有计数改成数论了又给我创飞了

这场的DE都太玄学了，属于是自己想半天一点屌思路没有然后看一眼题解就顿悟的类型

总结就是菜得发昏

A - Chocolate

挺有意思的签到题

考虑从大到小依次切，对于一个原来\(H'\times W'\)的块，为了尽量不浪费肯定是把它切下一个角来

不难发现剩余的部分可以分出三个更小的块，暴力模拟一下这个过程即可

至于为什么不是分两个块，因为我们是从大到小考虑的，如果分三块无解那么分两块肯定也无解

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1005;
int H,W,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d%d",&H,&W,&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	sort(a+1,a+n+1,greater <int>()); vector <pi> vec; vec.push_back(pi(H,W));
	for (i=1;i<=n;++i)
	{
		int len=1<<a[i]; bool flag=0;
		for (j=0;j<vec.size();++j)
		{
			auto [x,y]=vec[j];
			if (x>=len&&y>=len)
			{
				if (x-len>0) vec.push_back(pi(x-len,len));
				if (y-len>0) vec.push_back(pi(len,y-len));
				if (x-len>0&&y-len>0) vec.push_back(pi(x-len,y-len));
				vec.erase(vec.begin()+j); flag=1; break;	
			}
		}
		if (!flag) return puts("No"),0;
	}
	return puts("Yes"),0;
}

B - AtCoder Language

真·签到计数题，属于是连我看一眼都会做的程度了

不难发现一个合法的串需要满足，对于任意两个颜色相同的位置\(i,j(i<j)\)，必须有\(n-(j-i+1)<k-1\)

因为若不满足上面的条件我们就可以在区间外部选出\(k-1\)个位置，然后最后\(1\)个位置就有至少两种选法了

不妨考虑从前往后确定，第一位的放法有\(L\)种，第二位的放法有\(L-1\)种，一直到第\(n-(k-1)\)位及之后的放法有\(L-[n-(k-1)]+1\)​种，很容易直接计算答案

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int mod=998244353;
int n,k,l;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; scanf("%d%d%d",&n,&k,&l); int ans=1;
	for (i=0;i<n-(k-1);++i) ans=1LL*ans*(l-i)%mod;
	for (i=1;i<=k-1;++i) ans=1LL*ans*(l-(n-(k-1))+1)%mod;
	return printf("%d",ans),0;
}

C - Election

考虑找一个相对好统计的特征来刻画一个串，首先不难想到将A看作\(1\)，将B看作\(-1\)，然后求出前缀和数组\(pfx_i\)

不难发现最后\(pfx_i\)为\(0\)的地方就是C，否则根据\(pfx_i\)的正负绝对其是A还是B

观察到C的处境很特别，考虑用一个二元组\((pos_i,tp_i)\)来刻画某一个C的特征，其中\(pos_i\)表示其出现的位置，\(tp_i\)表示其之前这一段（到上个C为止是A还是B）

不难发现一个串和某个关于C的二元组的集合唯一对应，因此我们不妨用Hash来维护所有的二元组的Hash值，接下来考虑移动第一个字符的位置带来的影响

不妨假设第一个字符初始时就在开头，每次将其往后交换，首先若这次交换的两个字符相同则不会有任何影响

否则若\(s_i=A,s_{i+1}=B\)，不难发现交换后带来的影响就是\(pfx_i-=2\)；同理若\(s_i=B,s_{i+1}=A\)，交换后带来的影响就是\(pfx_i+=2\)

一边枚举一边动态维护整个序列的Hash值即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1e6+5;
int n,pfx[N]; char s[N];
const int mod1=998244353,mod2=1e9+7;
struct Hasher
{
	int x,y;
	inline Hasher(CI X=0,CI Y=0)
	{
		x=X; y=Y;
	}
	inline LL get_val(void)
	{
		return ((1LL*x)<<31LL)|(1LL*y);
	}
	friend inline bool operator == (const Hasher& A,const Hasher& B)
	{
		return A.x==B.x&&A.y==B.y;
	}
	friend inline Hasher operator + (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x+B.x)%mod1,(A.y+B.y)%mod2);
	}
	friend inline Hasher operator - (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x-B.x+mod1)%mod1,(A.y-B.y+mod2)%mod2);
	}
	friend inline Hasher operator * (const Hasher& A,const Hasher& B)
	{
		return Hasher(1LL*A.x*B.x%mod1,1LL*A.y*B.y%mod2);
	}
}pw[N]; unordered_set <LL> rst;
const Hasher seed=Hasher(31,131);
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%s",&n,s+1),pw[0]=Hasher(1,1),i=1;i<=n;++i)
	pw[i]=pw[i-1]*seed,pfx[i]=pfx[i-1]+(s[i]=='A'?1:-1);
	Hasher cur; for (i=1;i<=n;++i) if (pfx[i]==0) cur=cur+pw[i]*(pfx[i-1]>0?Hasher(1,1):Hasher(2,2));
	for (rst.insert(cur.get_val()),i=1;i<n;++i)
	{
		if (s[i]==s[i+1]) continue;
		if (s[i]=='A'&&s[i+1]=='B')
		{
			if (pfx[i]==0) cur=cur-pw[i]*(pfx[i-1]>0?Hasher(1,1):Hasher(2,2));
			if (pfx[i+1]==0) cur=cur-pw[i+1]*(pfx[i]>0?Hasher(1,1):Hasher(2,2));
			if ((pfx[i]-=2)==0) cur=cur+pw[i]*(pfx[i-1]>0?Hasher(1,1):Hasher(2,2));
			if (pfx[i+1]==0) cur=cur+pw[i+1]*(pfx[i]>0?Hasher(1,1):Hasher(2,2));
		} else
		{
			if (pfx[i]==0) cur=cur-pw[i]*(pfx[i-1]>0?Hasher(1,1):Hasher(2,2));
			if (pfx[i+1]==0) cur=cur-pw[i+1]*(pfx[i]>0?Hasher(1,1):Hasher(2,2));
			if ((pfx[i]+=2)==0) cur=cur+pw[i]*(pfx[i-1]>0?Hasher(1,1):Hasher(2,2));
			if (pfx[i+1]==0) cur=cur+pw[i+1]*(pfx[i]>0?Hasher(1,1):Hasher(2,2));
		}
		swap(s[i],s[i+1]); rst.insert(cur.get_val());
	}
	return printf("%d",rst.size()),0;
}

D - Distance Ranking

这题比赛场上过的贼少（比E少了一个数量级），后面想了半天也想不出个所以然，然后看了题解发现我是个傻逼

首先考虑构造一个所有点对间距离全相等的Case，这个也很简单，我们设\(V_{i,j}\)表示点\(i\)第\(j\)维的坐标，则\(V_{i,j}=[i==j]\times S\)即可满足上述要求，其中\(S\)为任意常数

此时任意两点间距离都是\(2S^2\)，考虑如果我们令\(V_{i,j}=c\ \ (i\ne j)\)会有什么影响，即点\(i\)和点\(j\)的距离变为了\(2S^2-2\times cS+c^2\)

由于所有点之间的距离都有\(2S^2\)因此不妨扔掉不管，如果我们令\(S\)为一个极大值（比如\(10^8\)），而\(c\)的数量级相比于\(S\)定的很小（不妨令\(c\in[1,\frac{N(N-1)}{2}]\)），则\(2S^2-2\times cS+c^2\)的值就变得只和\(c\)有关了

因此我们按照题目要求的排名顺序来确定\(V_{i,j}\)的值即可，代码非常简单

（PS：据说由于这题点数很少，还有很多奇怪的随机化乱搞做法，但由于时间所限就没有去尝试了）

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=25,INF=1e8;
int n,ans[N][N],x,y;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) ans[i][i]=INF;
	for (i=1;i<=n*(n-1)/2;++i) scanf("%d%d",&x,&y),ans[x][y]+=(n*(n-1)/2-i+1);
	for (i=1;i<=n;++i) for (j=1;j<=n;++j) printf("%d%c",ans[i][j]," \n"[j==n]);
	return 0;
}

E - Last 9 Digits

我只能说第一反应是打表找规律，但这题的规律有点小逆天

首先你要搞出以下两个猜想：

  • 当模数为\(10^k\)时，满足\(n^n\equiv x\pmod {10^k}\)的解\(n\)在\([1,10^k]\)的范围内有且仅有一个，且它们构成双射关系
  • 当模数为\(10^{k+1}\)时，设满足\(n^n\equiv x\pmod {10^k}\)的在\([1,10^{k}]\)内的解为\(n'\)，则满足\(n^n\equiv x\pmod {10^{k+1}}\)的在\([1,10^{k+1}]\)内的解为\(n=n'+t\times 10^k\ \ (t\in [0,9])\)

例如当\(k=3,x=16\)时，有\(514^{514}\equiv1514^{1514}\equiv2514^{2514}\equiv 16\pmod {10^3}\)

上述结论的具体证明可以看官方题解，大致思路就是先暴力验证当\(k=2\)时成立，然后后面用归纳法证明\(k\ge 2\)亦成立

有了这个结论后就很简单了，我们先大力在\([1,100)\)内找出某个数\(n_0\)满足\(n_0^{n_0}\equiv x\pmod {100}\)，然后不停往上递推即可

单组数据复杂度为\(100+9^2\)，可以通过此题

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
int t,x,pw[10];
inline int quick_pow(int x,int p,int mod,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(void)
{
	pw[0]=1; for (RI i=1;i<=9;++i) pw[i]=pw[i-1]*10;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t),init();t;--t)
	{
		RI i,j; scanf("%d",&x); int lst;
		for (i=1;i<100;++i) if (quick_pow(i,i,100)==x%100) { lst=i; break; }
		for (i=3;i<=9;++i) for (j=0;j<10;++j)
		{
			int tmp=lst+pw[i-1]*j;
			if (quick_pow(tmp,tmp,pw[i])==x%pw[i]) { lst=tmp; break; }
		}
		printf("%d\n",lst);
	}
	return 0;
}

Postscript

ARC还是太玄妙了，我还是滚回去写CF吧

标签：AtCoder,typedef,Hasher,int,long,Regular,include,172,define
From： https://www.cnblogs.com/cjjsb/p/18045337

相关文章

  • Codeforces 1830C Hyperregular Bracket Strings
    考虑到区间的限制\([l,r]\)就是要求\([l,r]\)里的字符会在\([l,r]\)里找到匹配。假设还有个区间\([l',r']\)满足\(l\lel'\ler\ler'\)，能够发现限制变成了\([l,l'),[l',r],(r,r']\)这\(3\)个区间内的字符能在对应区间内找到匹配。继续，假设\(l\lel'\le......
  • AtCoder Beginner Contest 342
    AtCoderBeginnerContest342比赛链接开学了，以后codeforces大概率只能补题了，但是atcoder还是可以做的A-Yay!思路找出只出现一次的字符就可以Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){ strings; cin>>s; std::map<ch......
  • AtCoder Beginner Contest 342
    D.SquarePair给你一个数组,最多2e5个元素,每个元素的范围是0到2e5问选出两个元素,乘积为完全平方数的情况有多少?(任选a[i]a[j],且满足i<j)一种思路是用map记录数组的元素,选出一个元素x后,枚举所有完全平方数,如果完全平方数可以整除选出的这个元素且整除的结果y在map......
  • Toyota Programming Contest 2024#2（AtCoder Beginner Contest 341）D - Only one of two
    目录链接题面题意题解代码总结链接D-Onlyoneoftwo题面题意求第\(k\)个只能被\(N\)或\(M\)整除的数题解\([1，x]\)中的能被\(n\)整除的数有\(\lfloor\frac{x}{n}\rfloor\)个\([1，x]\)中的能被\(m\)整除的数有\(\lfloor\frac{x}{m}\rfloor\)个\([1，x]\)中的能被\(n\)......
  • HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）
    HUAWEIProgrammingContest2024（AtCoderBeginnerContest342）A-Yay!代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingi128=__int128_t;usingpiii=p......
  • Atcoder Beginner Contest 342 全题解
    A-Yay!题意给定字符串\(s\)已知该字符串中只有一个字符与其他字符不同求这个字符思想开一个数组\(cnt_i\)来记录\(s\)中每个字符出现的次数，一个数组\(first_i\)来记录\(s\)中每个字符第一次出现的下标。选择\(cnt_i=1\)的\(i\)输出\(first_i\)......
  • AtCoder Beginner Contest 342
    A-Yay!(abc342A)题目大意给定一个字符串，两个字符，其中一个只出现一次，找出它的下标。解题思路看第一个字符出现次数，如果是\(1\)则就是它，否则就是不是它的字符。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){io......
  • Atcoder ABC 342 全题解
    闲话当我还是一个只会AB的小蒟蒻时，由于不会C又看不懂官方题解，只好看网上的题解。结果：ABC签到题不讲AB对着题意模拟即可。A有个好玩的做法，先看前两个，如果不同跟第三个比较，如果相同看后面哪个字母跟第一个不一样。C由于是将所有的$c_i$替换，所以可得同一个字母最......
  • AtCoder WTF 2019 B Multiple of Nine/南外集训 2024.2.23 T1
    给定\(q\)个区间\(\{[l_i,r_i]\}\)，计算满足条件的长度为\(n\)的十进制数码串\(S\)的个数\(\bmod10^9+7\)：\(\foralli\in[1,q],num(S[l_i,r_i])\equiv0\pmod9\)。其中\(num(T)\)表示数码串\(T\)代表的整数，\(T[a,b]\)表示子串\(T_aT_{a+1}\dotsT_b\)......
  • 山海经&&Atcoder Alternating String (线段树)
    前言:为什么把他们放在一起?因为我发现把pushup向上回溯放结构体类型函数里比较方便并且这两题确实也有相同思想山海经这题分三种情况左子树前缀和+右子树前缀和2.右子树后缀和与右总区间+左子树3.左区间最大子段与右区间最大子段与左后缀与右前缀特别要注意......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99