[nk] 牛客练习赛100 C 小红的删数字

前言

t a g : tag : tag: 数论 博弈 能被3整除的数 传送门 :

题意 :

思路 : 首先对于能被 3 3 3整除,我们都知道是各位之和能被 3 3 3整除

因此我们考虑将所有数按照 % 3 \%3 %3进行分类,同一类 本质为等价的

因此我们分为

1. 如果原模 3 3 3为 x x x,那么小红必须删除一个模 3 3 3为 x x x的数。因为只有这样子才可以使得之后的和能被 3 3 3整除
2. 小紫必须删除一个模 3 3 3为 x x x的数, x = = 1 / x = = 2 x==1/x==2 x==1/x==2,之后小红必须删除一个模 3 3 3为 1 − x 1-x 1−x的数

当然我们还要保证最后不能被删除完即 c n t [ 0 ] ≠ 0 cnt[0] \neq 0 cnt[0]​=0

code :

// Problem: 小红的删数字
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11251/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)
#define cer(a) cerr