Codeforces Round #799 (Div. 4) F 3SUM

迷南。 2024-03-30 12:24 54阅读 0赞

[Problem - F - Codeforces][]

题意：

给你n和n个整数，问你是否存在三个数使得三个数加起来的数末尾是3

思路：

**哈希表里枚举**（即map里面枚举）

先把数都放到map里面，在map里面枚举key

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    int n;
    int a[mxn],mp[mxn];
    void init(){
    	memset(mp,0,sizeof(mp));
    }
    void solve(){
    	cin>>n;
    	init();
    	for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]%10]++;
    	for(int i=0;i<=9;i++){
    		if(mp[i]) mp[i]--;
    		else continue;
    		for(int j=0;j<=9;j++){
    			if(mp[j]) mp[j]--;
    			else continue;
    			for(int k=0;k<=9;k++){
    				if(mp[k]) mp[k]--;
    				else continue;
    				if((i+j+k)%10==3){
    					cout<<"YES"<<'\n';
    					return;
    				}
    				mp[k]++;
    			}
    			mp[j]++;
    		}
    		mp[i]++;
    	}
    	cout<<"NO"<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

**总结：**

**指针枚举超时：**

**1.枚举其中一个指针，另外两个指针的结果放哈希表**

**2.枚举一个指针，找另一个指针和这个指针的数学关系，推导式子，然后去查找**

**3.更换枚举对象，去枚举数据范围更小的那个**

**4.哈希表里枚举，去枚举哈希表里的key**

[Problem - F - Codeforces]: https://codeforces.com/contest/1692/problem/F

发表评论取消回复

表情：

评论列表（有 0 条评论，54人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #799 (Div. 4) F 3SUM

[Problem - F - Codeforces][] 题意：给你n和n个整数，问你是否存在三个数使得三个数加起来的数末尾是3 思路：哈希表里枚举（即map里面枚

迷南。/ 2024年03月30日 12:24/ 0 赞/ 55 阅读

相关 Codeforces Round #894 (Div.3)

![在这里插入图片描述][f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center] 文章目录前言 A. Gift

朱雀/ 2024年03月24日 21:12/ 0 赞/ 55 阅读

相关 Codeforces Round 895 (Div. 3)F

[Problem - F - Codeforces][] F. Selling a Menagerie 由题意知，一个动物如果其害怕的动物还没有被买出，就可以卖出翻倍的

短命女/ 2024年03月08日 08:42/ 0 赞/ 86 阅读

相关 Codeforces Round 900 (Div. 3)

[Dashboard - Codeforces Round 900 (Div. 3) - Codeforces][Dashboard - Codeforces Round 90

小灰灰/ 2024年02月27日 03:25/ 0 赞/ 44 阅读

相关 Codeforces Round #587 (Div. 3)

Codeforces Round \587 (Div. 3) [\\(E1.Numerical\\ Sequence\\ (easy\\ version)\\)][E

我不是女神ヾ/ 2023年06月01日 15:54/ 0 赞/ 5 阅读

相关 Codeforces Round #479 (Div. 3)

D:[Divide by three, multiply by two][Divide by three_ multiply by two] 除了这种做法还可以通过建图

￡神魔★判官ぃ/ 2022年05月24日 20:59/ 0 赞/ 165 阅读

相关 Codeforces Round #552 (Div. 3)

C. Gourmet Cat 题目：[http://codeforces.com/contest/1154/problem/C][http_codeforces.com_

骑猪看日落/ 2022年04月24日 07:04/ 0 赞/ 142 阅读

相关 Codeforces Round #552 (Div. 3)

题目链接：[https://codeforces.com/contest/1154][https_codeforces.com_contest_1154] 这次比赛通过了三个

骑猪看日落/ 2022年02月17日 05:24/ 0 赞/ 149 阅读

相关 Codeforces Round #552 (Div. 3)

B. Make Them Equal Description 给定一个长度为 nn 的序列，请你选择一个非负整数 DD，然后将序列中的所有元素要么加上 DD，要么减去

偏执的太偏执、/ 2021年11月10日 12:48/ 0 赞/ 227 阅读

相关 Codeforces Round #560 (Div. 3)

[Codeforces Round \560 (Div. 3)][Codeforces Round _560 _Div. 3] E. Two Arrays and

野性酷女/ 2021年11月01日 04:38/ 0 赞/ 220 阅读