当前位置:网站首页>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;
}
边栏推荐
- Introduction to LVS [unfinished (semi-finished products)]
- Leetcode-556: the next larger element III
- Simple selection sort of selection sort
- One question per day 1020 Number of enclaves
- Leetcode-31: next spread
- Leetcode stack related
- Data visualization chart summary (II)
- Sum of three terms (construction)
- Applicable to Net free barcode API [off] - free barcode API for NET [closed]
- 博弈论 AcWing 894. 拆分-Nim游戏
猜你喜欢
Navicat连接Oracle数据库报错ORA-28547或ORA-03135
Leetcode array operation
1.14 - assembly line
RGB LED infinite mirror controlled by Arduino
Data visualization chart summary (II)
博弈论 AcWing 893. 集合-Nim游戏
[2020]GRAF: Generative Radiance Fields for 3D-Aware Image Synthesis
Chapter 6 relational database theory
MySQL advanced part 2: optimizing SQL steps
Gauss Cancellation acwing 884. Solution d'un système d'équations Xor linéaires par élimination gaussienne
随机推荐
Gauss Cancellation acwing 884. Solution d'un système d'équations Xor linéaires par élimination gaussienne
js快速将json数据转换为url参数
What is socket? Basic introduction to socket
C Primer Plus Chapter 15 (bit operation)
Quickly use Amazon memorydb and build your own redis memory database
Simple selection sort of selection sort
可变电阻器概述——结构、工作和不同应用
How to understand the definition of sequence limit?
背包问题 AcWing 9. 分组背包问题
【LeetCode】Day94-重塑矩阵
WordPress switches the page, and the domain name changes back to the IP address
Leetcode divide and conquer / dichotomy
[rust notes] 14 set (Part 1)
Traditional databases are gradually "difficult to adapt", and cloud native databases stand out
Leetcode backtracking method
[2021]GIRAFFE: Representing Scenes as Compositional Generative Neural Feature Fields
Leetcode array operation
Applicable to Net free barcode API [off] - free barcode API for NET [closed]
[rust notes] 14 set (Part 2)
C - XOR to all (binary topic)