首页 > 其他分享 >ABC268 题解

ABC268 题解

时间：2023-02-12 12:15:13浏览次数：60  
标签：typedef const int 题解 long maxn ABC268 define

比赛链接：https://atcoder.jp/contests/abc268/tasks

题解：
C
对于每个盘子统计一下转那几次（3 种情况）能够满足条件

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5+5;

int n,a[maxn],cnt[maxn];

signed main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	for(int i=0;i<n;i++){
		int now = (a[i]-i+n)%n;
		++ cnt[now%n];
		++ cnt[(now+1)%n];
		++ cnt[(now+n-1)%n];
	}
	int ans = 0;
	for(int i=0;i<n;i++)
		ans = max(ans, cnt[i]);
	cout << ans << '\n';

	return 0;
}

D
\(O(n!)\) 爆搜一下，注意每次下划线的个数和之后单词的个数有关，用 map 判重即可

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;

int n,m;
set<string>S;
string s[12];
int vis[12];

void dfs(int x,int rem,string now=""){
	if(x == n+1){
		if(now.size()<3||now.size()>16)return ;
		if(S.count(now))return ;
		cout << now << '\n';
		exit(0);
	}
	for(int i=1;i<=n;i++)if(!vis[i]){
		vis[i] = 1;
		string nn = now+s[i];
		if(x==n)dfs(x+1,rem,nn);
		else{
			for(int un=1;un<=rem;un++)if(un+n-x-1<=rem){
				nn = nn + '_';
				dfs(x+1,rem-un,nn);
			}
		}
		vis[i] = 0;
	}
}

signed main(){
	scanf("%d%d",&n,&m);
	int sz = 0;
	for(int i=1;i<=n;i++){
		cin >> s[i];
		sz += s[i].size();
	}
	for(int i=0;i<m;i++){
		string t;
		cin >>t;
		S.insert(t);
	}
	dfs(1,16-sz,"");
	puts("-1");

	return 0;
}

E
坑了

F
贪心的交换法，比 E 简单

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn=2e5+5;

int n;
string s[maxn];
int sum[maxn],sum2[maxn],id[maxn];

signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		id[i] = i;
		cin>>s[i];
		for(int j=0;j<s[i].size();j++){
			if(s[i][j]=='X')++sum[i];
			else sum2[i]+=s[i][j]-'0';
		}
	}
	sort(id+1,id+n+1,[&](int x,int y){
		return 1ll*sum[x]*sum2[y]>1ll*sum[y]*sum2[x];
	});
	int cx = 0;
	ll ans=0;
	for(int i=1;i<=n;i++){
		string nt = s[id[i]];
		for(int j=0;j<nt.size();j++){
			if(nt[j] == 'X')++cx;
			else{
				ans += 1ll*cx*(nt[j]-'0');
			}
		}
	}
	cout << ans << '\n';

	return 0;
}

G
“脑筋急转弯”
首先，\(E(rank_i)=1+E(rank_j<rank_i)=1+\sum_jPr(rank_j<rank_i)\)
考虑 \(i,j\) 的关系：如果 \(j\) 是 \(i\) 的前缀，显然 \(Pr=0\)
如果 \(i\) 是 \(j\) 的前缀，显然 \(Pr=1\)
否则，\(Pr=1/2\)，因为考虑第一个 \(i,j\) 不同的位置，显然大于和小于的方案数是对称相等的，因此为 \(1/2\)
写个 trie 判一下前缀关系即可

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 5e5+5, mod = 998244353;
const int inv2 = (mod+1)/2;

int n;
char s[maxn];
struct trie{
	int tr[maxn][27], cnt = 0, pos[maxn*26], sz[maxn*26];
	int mp[maxn * 26];
	void insert(char *s,int id){
		int n=strlen(s+1);
		int p = 0;
		for(int i=1;i<=n;i++){
			int t = s[i] - 'a';
			if(!tr[p][t]){
				tr[p][t] = ++cnt;
			}
			p = tr[p][t];
		}
		++ pos[p];
		mp[p] = id;
	}
	
	int ans[maxn];
	void dfs(int x,int pref=0,int id=0){
//		printf("%d %d %d\n",x,pref,id);
		int p = x;
		sz[p] = pos[p];
		for(int i=0;i<26;i++)if(tr[p][i]){
			dfs(tr[p][i], pref+pos[p], mp[tr[p][i]]?mp[tr[p][i]]:0);
			sz[p] += sz[tr[p][i]];
		}
//		printf("? %d %d %d   %d %d\n",p,id,sz[p],(n-pref-sz[p]),pref);
		if(id)(ans[id] = 1ll*(n-pref-sz[p])*inv2%mod + (pref)%mod + 1) %= mod; 
	}
}tr;

signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",s +1);
		tr.insert(s, i);
	}
	tr.dfs(0);
	for(int i=1;i<=n;i++)printf("%d\n",tr.ans[i]);

	return 0;
}

Ex
建出 AC 自动机之后贪心即可，如果当前位能匹配上而且是末尾，就改成 *

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn=1e6+5;

struct AC{
	int lst[maxn];
	int tr[maxn][27],cnt;
	int val[maxn];	// 多少个以 i 结点结尾的单词 
	int fail[maxn];
	
	AC(){cnt=0;memset(val,0,sizeof val);}
	
	void insert(char *s){
		int p=0;
		int ns = strlen(s + 1);
		for(int i=1;i<=ns;i++){
			int k = s[i] - 'a';
			if(!tr[p][k])tr[p][k] = ++ cnt;
			p = tr[p][k];
		}
		++ val[p];
	}
	
	void build(){
		queue<int>Q;
		Q.push(0);
		while(!Q.empty()){
			int u = Q.front();Q.pop();
			for(int i=0;i<26;i++)
				if(tr[u][i]){
					fail[tr[u][i]] = u ? tr[fail[u]][i] : 0;
					if(val[fail[tr[u][i]]])lst[tr[u][i]] = fail[tr[u][i]];
					else lst[tr[u][i]] = lst[fail[tr[u][i]]];
					
					Q.push(tr[u][i]);
				}else tr[u][i] = tr[fail[u]][i];
		}
	}
	
	void query(char *t){
		int p=0, res=0;
		int nt = strlen(t + 1);
		for(int i=1;i<=nt;i++){
			p = tr[p][t[i] - 'a'];
			int fg = 0;
			if(val[p]){
				fg = 1;
			}
			
			int v = lst[p];
			while(v){	// 沿失配边跳，加上abc bc c这种的匹配 
				if(val[v]){
					fg = 1;
				}
				v = lst[v];
			}
			if(fg){
				++ res;
				p = 0;
			}
		}
		printf("%d\n",res);
	}
}ac;
char s[maxn],t[maxn];
int n;

signed main(){
	scanf("%s",t+1);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",s +1);
		ac.insert(s);
	}
	ac.build();
	ac.query(t);

	return 0;
}

标签：typedef,const,int,题解,long,maxn,ABC268,define
From： https://www.cnblogs.com/SkyRainWind/p/17113576.html

相关文章

  • YACS 2023年1月月赛 甲组 T2 分割数列（二） 题解
    题目链接继上个月的分割数列（一）又出了这道题。首先还是考虑$n^2DP$，设$f[i]$为分到$i$个的最小权重之和。转移枚举上一个在哪里分就行了。显然时间会超限，我们考虑......
  • YACS 2023年1月月赛 甲组 T1 树的独立集 题解
    题目链接半夜12:00我不睡觉来这里更文章来了。。。这次的甲组好简单，第一次$AK$了，这题看上去很难，要求什么不挨边，其实分析一下就是树形$DP$。首先要求不挨边，所以我......
  • 题解 LGP9018【[USACO23JAN] Moo Route G】
    problem现在有一条数轴，\(t\)表示当前时刻。在\(t=0\)时Bessie恰好处在\(x=0\)的位置。接下来，每秒钟Bessie会向左或者向右移动一个单位距离，我们保证Bessie是在......
  • flannel 低版本glog flag redefined error 问题解决
    最近在构建一个老版本的flannel的时候碰到了此问题，记录下，方便使用解决方法glideinstall--strip-vendor--strip-vcs参考资料https://stackoverflo......
  • go: cannot find main module, but found glide.lock 问题解决
    解决方法exportGO111MODULE=auto说明此问题主要是老golang项目构建可能会出现的，新的一般不对有此问题（都基于gomod了）参考资料https://github.co......
  • abc289g题解
    考虑枚举卖出的物品个数\(i\)，把\(b_i\)从大到小排序。题目的某人会买物品的条件转化为\(b_i\geqp_j-c_j\)，这说明卖出的物品的集合是排序后\(b\)的一段前缀，且卖出\(i\)个......
  • CF793G Oleg and chess 题解
    \(\text{类似于主席树优化建图，直接放一张图片。}\)#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<vector>#include<map>#include......
  • 【题解】CF997C Sky Full of Stars
    简记一下高维二项式反演的套路。思路高维二项式反演。首先意识到\(n\leq10^6\)且计数，并且求“至少”，所以考虑用二项式反演处理。这里如果用一维的二项式反演，可能......
  • 【题解】P4464 [国家集训队] JZPKIL
    仙气飘飘莫反题。显现出了很多推式子习惯的问题。思路莫反+伯努利数+Pr。首先根据\(\operatorname{lcm}(x,y)=\frac{xy}{\gcd(x,y)}\)可以化简：\(\sum\limits......
  • P9033题解
    P9033「KDOI-04」XORSum题解题目链接传送门题意简述构造一个长度为\(n\)，值域为\([0,m]\)的异或和为\(k\)的序列，如果不存在则输出\(-1\)。题目分析首先很容易......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99