首页 > 其他分享 >AtCoder Beginner Contest 380

AtCoder Beginner Contest 380

时间：2024-11-20 12:56:17浏览次数：1  
标签：AtCoder Beginner int ll long 380 void include find

AtCoder Beginner Contest 380 总结

A

用桶统计 \(1\)，\(2\)，\(3\) 出现的次数，判断即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=10;
string s;
int c[N];
void solve()
{
	cin>>s;
	for(auto x:s) c[x-'0']++;
	if(c[1]==1&&c[2]==2&&c[3]==3) cout<<"Yes\n";
	else cout<<"No\n";
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	#endif 
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

B

扫一遍统计即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=105;
string s;
int n;
int a[N];
void solve()
{
	cin>>s;
	int cnt=0;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='|') a[n++]=cnt,cnt=0;
		else cnt++;
	}
	for(int i=1;i<n;i++) cout<<a[i]<<' ';
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	#endif 
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

C

统计每一个连续的 0 或 1 段的大小，找到第 \(k\) 个 1 段和前一个 0 段交换。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=5e5+5;
int n,k;
string s;
int a[N],c[N];
void solve()
{
	cin>>n>>k>>s;
	int cnt=0;
	s=' '+s;
	for(int i=1;i<s.size();i++)
	{
		int x=s[i]-'0';
		if(s[i]!=s[i-1]) a[++cnt]=x,c[cnt]++;
		else c[cnt]++;
	}
	int j=0;
	for(int i=1;i<=cnt;i++) 
	{
		if(a[i]==1) j++;
		if(j==k)
		{
			swap(a[i],a[i-1]);
			swap(c[i],c[i-1]);
            break;
		}
	}
	for(int i=1;i<=cnt;i++)
		for(int j=1;j<=c[i];j++)
			cout<<a[i];
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	#endif 
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

D

可以知道最终的 \(S\) 是由若干个翻转或不变的初始的 \(S\) 拼成，用 \(1\) 表示翻转，\(0\) 表示不变。最终会是 \(\mathtt{0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0, \dots}\)

考虑找 \(k\) 在第几个 \(s\) 中，记为 \(a\)，因为复制的过程是不断加倍，思考一下可以得到 \(a\) 是由 \(a-\text{二进制最高位的一代表的权值}\) 推过来的，且翻转了。考虑倒推发现最终会剩下 \(lowbit(a)=2^c\)，观察下发现对应翻转情况为 c&1，统计 \(a\) 二进制下 \(1\) 的个数为 \(b\)，也就是要翻转 \(b-1\) 次。所以 \(a\) 对应的翻转情况为 (c&1)^((b-1)&1)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5;
string s;
int n,q;
char change(char x)
{
	if(x>='a'&&x<='z') x=x-'a'+'A';
	else x=x-'A'+'a';
	return x;
}
int count(ll x)
{
	ll y=x&-x;
	ll a=1,c=0;
	while(a<y)
	{
		a*=2;
		c++;
	}
	ll b=0;
	while(x) x-=(x&-x),b++;
	b=(b-1)&1;
	return c&1^b;
}
void solve()
{
	cin>>s>>q;
	n=s.size();
	s=s[n-1]+s;
	while(q--)
	{
		ll k;
		cin>>k;
		ll a=k/n,b=k%n;
		if(b==0)
		{
			if(count(a)) cout<<change(s[n])<<' ';
			else cout<<s[n]<<' ';
			continue;
		}
		if(count(a+1)) cout<<change(s[b])<<' ';
		else cout<<s[b]<<' ';

	}
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	#endif 
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

E

显然是用并查集来维护，注意一下改变完某一块后是否与左右块的颜色相同，如果相同则要合并。所以记录集合的颜色，左右端点，大小。要注意答案可能不只是一个集合的大小，所以要另外计算。

只要不看错题目还是挺简单的 qwq。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=5e5+5;
int n,q;
int a[N],l[N],r[N],fa[N],siz[N],ans[N];
int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
	x=find(x),y=find(y);
	if(x==y) return ;
	fa[x]=y;
	siz[y]+=siz[x];
}
void solve()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++) a[i]=l[i]=r[i]=fa[i]=i,siz[i]=ans[i]=1;
	while(q--)
	{
		int op,x,c;
		cin>>op>>x;
		if(op==1)
		{
			cin>>c;
			x=find(x);
			ans[a[x]]-=siz[x];
			a[x]=c;
			ans[a[x]]+=siz[x];
			if(l[x]!=1&&a[find(l[x]-1)]==c) 
			{
				int y=find(l[x]-1);
				merge(y,x),l[x]=l[y];
			}
			if(r[x]!=n&&a[find(r[x]+1)]==c) 
			{
				int y=find(r[x]+1);
				merge(y,x),r[x]=r[y];
			}

		}
		else cout<<ans[x]<<'\n';
	}
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	#endif 
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

F

因为总牌数比较小，所以不妨使用状态压缩，记录每张牌在谁哪，三进制状态，\(0\) 表示在 Takahashi 那，\(1\) 表示在 Aoki 那，\(2\) 表示在桌上。直接按题意模拟，使用记忆化搜索即可。

要注意三进制状态的处理。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=15,M=6e6;
int n,m,l;
int a[N],p[N];
int f[2][M];

int count(int x,int st)
{
	int cnt=0;
	for(int i=0;i<n+m+l;i++)
	{
		if(st%3==x) cnt++;
		st/=3;
	}
	return cnt;
}
int get(int st,int k)
{
	int ret=0;
	for(int i=0;i<=k;i++)
	{
		ret=st%3;
		st/=3;
	}
	return ret;
}
bool dfs(int x,int st)
{
	if(f[x][st]!=-1) return f[x][st];
	if(count(x,st)==0) return f[x][st]=0;
	f[x][st]=0;
	for(int i=0;i<n+m+l;i++)
		if(get(st,i)==x)
		{
			f[x][st]|=!dfs(x^1,st-x*p[i]+2*p[i]);
			for(int j=0;j<n+m+l;j++)
				if(a[j]<a[i]&&get(st,j)==2)
					f[x][st]|=!dfs(x^1,st-x*p[i]+2*p[i]+x*p[j]-2*p[j]);
		}
	return f[x][st];
}
void solve()
{
	cin>>n>>m>>l;
	p[0]=1;
	int st=0;
	for(int i=1;i<n+m+l;i++) p[i]=p[i-1]*3;
	for(int i=n;i<n+m;i++) st+=p[i];
	for(int i=n+m;i<n+m+l;i++) st+=2*p[i];
	for(int i=0;i<n+m+l;i++) cin>>a[i];
	memset(f,-1,sizeof f);
	if(dfs(0,st)) cout<<"Takahashi\n";
	else cout<<"Aoki\n";
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	#endif 
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

G

将序列划分成三个区间 \([1,i-1]\)，\([i,i+k-1]\)，\([i+k,n]\)。

其中 \([i,i+k-1]\) 随机打乱。因为是求逆序对，被影响的只用 \([i,i+k-1]\) 内产生的逆序对。考虑 \(k\) 个数随机打乱产生逆序对数量的期望。总共 \(\frac{k \times (k-1)}{2}\) 对数，每对数是逆序对的概率为 \(\frac{1}{2}\)，所以该区间产生的期望是 \(\frac{k \times (k-1)}{4}\)。

再来计算其他部分。设整个序列的逆序对数为 \(sum\)，\([i,i+k-1]\) 中产生的逆序对数为 \(now\)，所以其他部分的逆序对数为 \(sum-now\)。整个序列的期望就是 \(sum-now+\frac{k \times (k-1)}{4}\)。区间平移后，要减去 \(a_{i-1}\) 加入 \(a_{i+k-1}\)，分别求出该区间小于 \(a_{i-1}\) 的数的个数 \(x\)，和大于 \(a_{i+k-1}\) $的数的个数 \(y\)，将 \(now\) 更新为 \(now-x+y\)。

类似与滑动窗口求逆序对，用树状数组来写。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

#define int long long 
using namespace std;
typedef long long ll;
const int N=2e5+5,mod=998244353;
int n,k;
int a[N];
struct BIT
{
	int c[N];
	int lowbit(int x) {return x&-x;}
	void clear() {memset(c,0,sizeof c);}
	void add(int k,int x) {for(int i=k;i<=n;i+=lowbit(i)) c[i]+=x;}
	int query(int k) {int ret=0;for(int i=k;i;i-=lowbit(i)) ret+=c[i];return ret;}
	int ask(int k) {return query(n)-query(k);}
}T;
int inv(int x)
{
	int ret=1,y=mod-2;
	while(y)
	{
		if(y&1) ret=ret*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ret;
}
void solve()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	int sum=0,ans=0,now=0;
	for(int i=1;i<=n;i++) sum+=T.ask(a[i]),T.add(a[i],1);
	T.clear();
	for(int i=1;i<=k;i++) now+=T.ask(a[i]),T.add(a[i],1);
	ans=sum-now;
	for(int i=2;i<=n-k+1;i++)
	{
		T.add(a[i-1],-1);
		now-=T.query(a[i-1]);
		now+=T.ask(a[i+k-1]);
		T.add(a[i+k-1],1);
		ans=(ans+sum-now)%mod;
	} 
	cout<<(ans*inv(n-k+1)%mod+k*(k-1)%mod*inv(4))%mod;
}
signed main()
{
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	#endif 
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

标签：AtCoder,Beginner,int,ll,long,380,void,include,find
From： https://www.cnblogs.com/zhouruoheng/p/18556506

相关文章

  • AtCoder Beginner Contest 352 - VP记录
    A-AtCoderLine赛时整活想写异或版本的swap写错了还WA了一发。不过现在会写了：x^=y^=x^=y点击查看代码#include<cstdio>#include<algorithm>usingnamespacestd;intmain(){ intn,x,y,z; scanf("%d%d%d%d",&n,&x,&y,&z); if(x>y)swap(x,y); p......
  • ABC380 DEFG 题解
    ABC380题解赛时秒了ABCDE（好吧其实还是略有卡顿，写完大概花了55min），看到F有博弈直接跑了，没注意到数据范围这么小，看到G一下就会了大致思路，但具体细节上搞复杂了，快写完了才发现不用维护这么多（恼），然后因为某些神秘错误现在都还没有调出来。至于F，赛后看见数据范围这么小，自己独立......
  • Atcoder Beginner Contest 367
    老规矩此处略过前三题，不过B值得关注一下。D题 Pedometer思路肥肠煎蛋，只需要搞一个前缀额然后看前面的前缀和是否有跟当前的前缀和同余的情况(%M)暴力求解这步是O(n^2)的，因此需要优化。这里就用到了一个技巧——哈希表消除分支。所谓的哈希表消除分支其实就是mp[pre_s]存一......
  • [ABC380C] Move Segment 题解
    [ABC380C]MoveSegment题解本题主要考察思维能力，其实不难。题目大意给你一个字符串\(s\)，\(s\)由\(0\)和\(1\)构成，将其分为块中只有一种数字的块。将给定的第\(k\)块数字为\(1\)的块与第\(k-1\)块合并，并输出修改后的字符串。思路分析直接按照题意模拟即可。建......
  • AtCoder Beginner Contest 380 （A~E）题解
    A-123233遍历字符串统计出现次数即可。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e6+10;intn,m,k;inta[N];signedmain(){ strings; cin>>s; map<char,int>mp; for(autot:s){ mp[t]++; } if(......
  • [题解]AtCoder Beginner Contest 380(ABC380) A~F
    A-123233照题意统计即可。点击查看代码#include<bits/stdc++.h>usingnamespacestd;strings;map<char,int>ma;signedmain(){ cin>>s; for(chari:s)ma[i]++; if(ma['1']==1&&ma['2']==2&&ma['3']==3)co......
  • abc380 赛后总结
    菜菜菜，不是你怎么这么菜。A-C模拟即可。D正常的方法因为不管怎么粘合总是一个字符串在复制，所以我们只用考虑大小写问题。我们设字符串为\(A\)，被反转大小写的字符串为\(B\)，那么这个字符串会长这样：\(ABBABAABBAABABBA\cdots\)，第一个\(A\)的位置是\(0\)的话，我们可以发现......
  • 【未完结】 AtCoder Beginner Contest 380 题解
    AtCoderBeginnerContest380Rated：\(770\)A-123233简单模拟B-HurdleParsing字符串模拟C-MoveSegment找到第\(k\)个块的下标，模拟。D-StrangeMirroringE-1DBucketToolF-ExchangeGameG-AnotherShuffleWindow......
  • 【AtCoder】Beginner Contest 378-E.Mod Sigma Problem
    题目链接ProblemStatementYouaregivenasequenceA=(A1......
  • 【AtCoder】Beginner Contest 378-F.Add One Edge 2
    [题目链接](F-AddOneEdge2(atcoder.jp))ProblemStatementYouaregivenatreewithNNNvertices.Thei......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99