当前位置:网站首页>Winter messenger 2
Winter messenger 2
2022-07-05 06:19:00 【Strezia】
Link
Game theory ,sg function
I didn't understand the solution ,, Violence made a watch , At the beginning, I also operated 2 It's missing .
Looking at the solution means that every operation will make x x x Reduce , After doing several questions, I feel that if there are multiple operations , Then find the common ground of these operations , To write the transfer equation .
Code
int sg[1050];
int mex(vector<int> v) // v It can be vector、set Equal container
{
unordered_set<int> S;
for (auto e : v)
S.insert(e);
for (int i = 0;; ++i)
if (S.find(i) == S.end())
return i;
}
int cal(int x) {
if(sg[x] != -1) return sg[x];
int t = x;
vector<int> v;
if(t & 1) {
v.pb(cal(t - 1));
}
for(int i = 0; i < 10; i++) {
if(!(t >> i)) break;
if((t >> i) & 1) {
int p = x ^ (1<<i);
for(int j = i - 1; j >= 0; j--) {
int q = p ^ (1<<j);
v.pb(cal(q));
}
}
}
int a = mex(v);
return sg[x] = a;
}
void solve() {
int n;
cin >> n;
string s;
cin >> s;
int a = 0;
for(int i = 0; i < n; i++) {
if(s[i] == 'w')
a = a + (1<<i);
}
if(sg[a]) cout << "Yes\n";
else cout << "No\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
memset(sg, -1, sizeof(sg));
sg[0] = 0;
for(int i = 1; i <= 1030; i++)
cal(i);
int T; cin >> T; while(T--)
solve();
return 0;
}
边栏推荐
- How to generate an image from text on fly at runtime
- Record the process of configuring nccl and horovod in these two days (original)
- [rust notes] 17 concurrent (Part 1)
- 927. 三等分 模拟
- Sqlmap tutorial (II) practical skills I
- [2020]GRAF: Generative Radiance Fields for 3D-Aware Image Synthesis
- Open source storage is so popular, why do we insist on self-development?
- Leetcode-3: Longest substring without repeated characters
- 传统数据库逐渐“难适应”,云原生数据库脱颖而出
- LeetCode-61
猜你喜欢
MIT-6874-Deep Learning in the Life Sciences Week 7
可变电阻器概述——结构、工作和不同应用
Leetcode-6108: decrypt messages
阿里巴巴成立企业数智服务公司“瓴羊”,聚焦企业数字化增长
MySQL advanced part 2: MySQL architecture
Network security skills competition in Secondary Vocational Schools -- a tutorial article on middleware penetration testing in Guangxi regional competition
Groupbykey() and reducebykey() and combinebykey() in spark
Traditional databases are gradually "difficult to adapt", and cloud native databases stand out
数据可视化图表总结(二)
Spark中groupByKey() 和 reduceByKey() 和combineByKey()
随机推荐
【Rust 笔记】15-字符串与文本(上)
Doing SQL performance optimization is really eye-catching
Simple selection sort of selection sort
How to understand the definition of sequence limit?
[leetcode] day94 reshape matrix
The difference between CPU core and logical processor
MySQL advanced part 1: View
[rust notes] 16 input and output (Part 2)
Data visualization chart summary (II)
Operator priority, one catch, no doubt
[rust notes] 14 set (Part 2)
Filter the numbers and pick out even numbers from several numbers
C - XOR to all (binary topic)
MIT-6874-Deep Learning in the Life Sciences Week 7
MatrixDB v4.5.0 重磅发布,全新推出 MARS2 存储引擎!
JS quickly converts JSON data into URL parameters
WordPress switches the page, and the domain name changes back to the IP address
Open source storage is so popular, why do we insist on self-development?
SQLMAP使用教程(一)
栈 AcWing 3302. 表达式求值