1. 首页
  2. 文章中心
  3. 题解

AGC047 A,B,E题解。

118 阅读 0 评论
我是靠谱客的博主 甜蜜大船，这篇文章主要介绍AGC047 A,B,E题解。，现在分享给大家，希望可以做个参考。

2020/11/6 update : E题满分做法

A - Integer Product

将两个小数乘上1e9,就看有多少对乘起来模1e18=0.由于1e18只有2个质因子: 18个2，18个5。所以只要看每一个数的2和5的个数就行了。
注意不能直接long long (a')=double(a)，而要long long (a')=llround(double(a))不然会Wa5个点。
code:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*
{

AuThOr Gwj
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
#define int LL
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int n,a[200000+20];
double a_[200000+20];
int all[65][65];
signed main(){
	fastio;
	R(n);
	LL res=0;
	rb(i,1,n){
		R(a_[i]);
		;
		a[i]=llround(a_[i]*=1000000000.0);
		int A,B;
		A=B=0;
		while(a[i]%5==0){
			a[i]/=5;
			A++;
		}
		while(a[i]%2==0){
			a[i]/=2;
			B++;
		}
//		cout<<A<<" "<<B<<endl;
		rb(k,0,64)
			rb(j,0,64){
				if(k+A>=18&&j+B>=18){
					res+=all[k][j];
				}
		}
		all[A][B]++;
	}	
	cout<<res<<endl;
	return 0;
}

B - First Second

一个字符串s可以构成s’当且仅当s’的后(s’.length()-1)位与s的后(s’.length()-1)位完全相同，且s的前(s.length()-(s’.length()-1) )位有s’[0]这个字符。
这样就很直接了:直接放到字典树上搞一下就行了。
时间复杂度 O ( ( ∑ ∣ s i ∣ ) ∗ 26 ) O((sum |s_i|)*26) O((∑∣si​∣)∗26)
Code:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/*
{

AuThOr Gwj
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int n=200000+20;
string s[200000+20];
int son[1000000+1][27],cnt[1000000+1][27],old[1000000+1][27];
int root=0;
int cnt_=0;
int have[27];
void go(int now,int is,int t){
	if(is==s[t].length()) return;
	if(son[now][s[t][is]]){
	if(have[s[t][is]]==1){
		old[son[now][s[t][is]]][s[t][is]]++;
		cnt[son[now][s[t][is]]][s[t][is]]++;
	}
	have[s[t][is]]--;
		go(son[now][s[t][is]],is+1,t);
	}
	else{
		son[now][s[t][is]]=++cnt_;
	if(have[s[t][is]]==1){
		old[son[now][s[t][is]]][s[t][is]]++;
		cnt[son[now][s[t][is]]][s[t][is]]++;
	}
	have[s[t][is]]--;
		go(son[now][s[t][is]],is+1,t);
	}	
}
void calc(int now){
	rb(i,1,26){
		if(son[now][i]){
			calc(son[now][i]);
			rb(k,1,26)
				cnt[now][k]+=cnt[son[now][i]][k];
		}
	}
}
int rest(int now,int is,string& s_,int need){	
	if(is==s_.length()) return cnt[now][need]-old[now][need]-1;
	return rest(son[now][s_[is]],is+1,s_,need);
}
int main(){
	fastio;
	R(n);
	rb(i,1,n){
		rb(j,1,26)
			have[j]=0;
		R(s[i]);
		reverse(ALL(s[i]));
		rep(j,s[i].length()){
			s[i][j]-='a'-1;
		}
		rb(j,0,s[i].length()-1)
			have[s[i][j]]++;
		go(root,0,i);
	}	
	calc(root);
	LL res=0;
	rb(i,1,n){
		string ss="";
		rep(j,s[i].length()){
			if(j!=s[i].length()-1) ss+=s[i][j];
		}
		res+=rest(root,0,ss,s[i][s[i].length()-1]);	
	}
	cout<<res<<endl;
	return 0;
}

E

二进制拆分，然后乘起来。
Code:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
const int MAXN=2e5;
/*}
*/
void op(char c,int i,int j,int k){
	printf("%c %d %d %dn",c,i,j,k);
}
void my_and(int i,int j,int k){//a[k]=a[i] & a[j] 
	op('+',i,j,k);
	op('<',MAXN-1,k,k);
}
void split(int i,int j){//将a[i]在[j,j+59]的区域写成二进制 
	op('+',MAXN-2,MAXN-2,MAXN-3);
	op('+',MAXN-1,i,MAXN-10);//
	//MAXN-5 存储当前是否小于 
	rb(pos,j,j+59)
	{
		if(j==pos)
			op('+',MAXN-1,MAXN-2,pos);
		else{
			op('+',pos-1,pos-1,pos);
		}	
	}		
	rl(pos,j+59,j){
		op('+',pos,MAXN-3,MAXN-4);
		op('<',MAXN-4,MAXN-10,MAXN-5);
		op('+',MAXN-5,MAXN-2,pos);
		rb(ci,1,pos-j){
			op('+',MAXN-5,MAXN-5,MAXN-5);
		}
		op('+',MAXN-5,MAXN-3,MAXN-3);
	}
}
int main(){
	puts("122764");
	op('+',1,0,MAXN-1);
	op('<',2,MAXN-1,MAXN-1);
	rb(i,0,29){//存储2^i * B 
		if(i==0) op('+',1,3,3);
		else op('+',3+i-1,3+i-1,3+i);	
	}
	int st=40;
	split(0,st);
	st+=60;
	rb(i,0,29){
		split(i+3,st);
		rb(j,0,59){
			my_and(40+i,st+j,st+j);
			rb(k,1,j)
				op('+',st+j,st+j,st+j);	
			op('+',2,st+j,2);
		}
		st+=60;
	}	
	return 0;
}
/** 程序框架：
  * 
  *
  *
  *
  **/

最后

以上就是甜蜜大船最近收集整理的关于AGC047 A,B,E题解。的全部内容，更多相关AGC047内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(78)

相关文章

AGC005 D ~K Perm Counting题意题解
AGC005 D ~K Perm Counting题意题解
Atcoder AGC 043 D题解DescriptionSolutionCode
Atcoder AGC 043 D题解DescriptionSolutionCode
AGC 050 D题解AGC 050 D题解
AGC 050 D题解AGC 050 D题解
【题解】[AGC005D] ~K Perm Counting
【题解】[AGC005D] ~K Perm Counting
AGC047 A,B,E题解。
AGC047 A,B,E题解。
AGC 032 D 题解
AGC 032 D 题解
ATcoder-[AGC048B]Bracket Score【结论,贪心】正题
ATcoder-[AGC048B]Bracket Score【结论,贪心】正题
正则检验yyyy-MM-dd格式
正则检验yyyy-MM-dd格式

评论列表共有 0 条评论

立即
投稿
返回
顶部