C++算法算法训练第十一天
以下为牛客挑战
今日收获
学到了状态压缩dp,这个是选或者不选两种情况所有数的情况。
for(int i=0;i<(1LL<<n);i++){}
__builtin__popcount(i);统计i中二进制的个数，可以用于判断有没有选到这么多。
if(i>>j&1)continue;这个是第被选了就下一个，这个是右移移动到最后一个看看是不是1
牛客练习赛148
签到题
A-签到题_牛客练习赛148 (nowcoder.com)
2
1 2
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;for(int i=1;i<=n;i++){cout<<i<<" ";}return 0;
}
Bob的蛋糕店
状态压缩 DP
B-Bob的蛋糕店_牛客练习赛148 (nowcoder.com)
2 1
1 1
No
这个题我不会一开始，但是我看了大佬的怎么解。
这个题用是数轴，我们可以假设给数轴的点全部搞成0，选了的搞成1；
这样的话一个位置就有两个可能，选或者不选，那一共有2的n次方的选择
也就是1LL<<n,1向右移动n个单位1<<31000-->2的3次方。
所以我们可以去枚举所有的方法，比如枚举到i，---》这个也相当于一个状态。，相当于把1的选完了，剩下的枚举长度，
if(i>>j&1)continue;//遇到1的直接不要加上
这里一个很关键的函数
__builtin_popcount(i),统计i中y1的个数，是一个数二进制1的个数
我们可以用这个来判断到底选了多少。
先统计
∑m ×i--》x
∑mi---》y
最后只要X/Y==x/y-->X*y==Y*x;
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,k;cin>>n>>k;int X=0,Y=0;vector<int>a(n+9);for(int i=0;i<n;i++){cin>>a[i];X+=a[i]*(i+1);Y+=a[i];}for(int i=0;i<(1ll<<n);i++){if(__builtin_popcount(i)!=k)continue;int x=0,y=0;for(int j=0;j<n;j++){if(i>>j&1)continue;x+=a[j]*(j+1);//用来算改变之后的xy+=a[j];}if(X*y==Y*x){cout<<"Yes";return 0;}}cout<<"No";return 0;
}
修复排列
BFS+ 单调性优化
C-修复排列_牛客练习赛148 (nowcoder.com)
4
1 2 3 4
1 2 3 4
2 1 3 4
2 2 3 4
我们可以知道，答案肯定是单调递增。因为前面的最优值，可以为后面的提供保障。我们可以使用bfs去搜索答案。
a[i]-->数据
b[i]-->第i次的修改的位置b[i]
c[i]-->第i个为位置可以换的c[i]ia[i]-->这个是a[i]数组第的位置
当这个!vis(b[i]时候，加入队列,加入后，必须进行交换，然后交换后我们可以知道要么存在两个一样的数组，要么就刚好是原来的数组。我们就去找这个数（c[i]）替换的a[i],这个c[i]原来的位置，找到位置后，看起有没有改过，如果改过就直接下一个，相当于已经不好重复了。
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;vector<int>a(n+1),b(n+1),c(n+1),ia(n+1);for(int i=1;i<=n;i++){cin>>a[i];ia[a[i]]=i;}for(int i=1;i<=n;i++){cin>>b[i];}for(int i=1;i<=n;i++){cin>>c[i];}int ans=0;queue<int>q;vector<bool>vis(n+1);for(int i=1;i<=n;i++){if(!vis[b[i]]){q.push(b[i]);}while(q.size()){auto u=q.front();ans++;vis[u]=1;q.pop();auto v=ia[c[u]];if(vis[v])continue;q.push(v);}cout<<ans<<" ";}return 0;
}
牛客周赛 Round 128
小红的双层夹心
A-小红的双层夹心_牛客周赛 Round 128 (nowcoder.com)
abba
Yes
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);string s;cin>>s;if(s[1]==s[2]){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}return 0;
}
小红的马卡龙定位
B-小红的马卡龙定位_牛客周赛 Round 128 (nowcoder.com)
0 0
10 10
5 5
3
这个简单先判断x是不是相同的，如果相同比较y的大小，如果不相同就直接去比较x就行了
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int x1,y1,x2,y2,x3,y3;cin>>x1>>y1>>x2>>y2>>x3>>y3;if((x1+x2)>x3){cout<<3;}else if((x1+x3)>x2){cout<<2;}else{cout<<1;}return 0;
}
小红的奶油蛋糕工坊
C-小红的奶油蛋糕工坊_牛客周赛 Round 128 (nowcoder.com)
4
1 3 2 4
1 3 1 4
主要是数组里面的构成排列，没一个数值都出现一次，所以我们只需要另一半变成其中的中位数就行了
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;vector<int>v(n);for(int i=0;i<n;i++){cin>>v[i];}int m=(n+1)/2;for(int i=0;i<n;i++){if(v[i]<=m)v[i]=(m+1)/2;cout<<v[i]<<" ";}return 0;
}
小红的奇数奶油球
D-小红的奇数奶油球_牛客周赛 Round 128 (nowcoder.com)
3
3
1 2
2 3
5
1 2
1 3
3 4
3 5
4
1 2
1 3
1 4
1
1
4
这个题目就是要我们树中有多少个节点，满足以该节点为根的子树大小为奇数，且删除该节点后每个连通分量的大小都为奇数（或者说，该节点的所有子树大小都是奇数，且剩余部分 n - ans[u] 也是奇数或为零）。
我们就去遍历这些节点，找出根，然后统计出是不是奇数。
ok &= ans[v] & 1;
- 只要有一个子树是偶数大小，
ok变成false - 所有子树必须都是奇数，
ok才能保持true
ok &= (n - ans[u] == 0) || ((n - ans[u]) & 1);
| 部分 | 含义 |
|---|---|
n |
整棵树的总节点数 |
ans[u] |
以 u 为根的子树大小 |
n - ans[u] |
删除节点 u 后，上方连通分量的大小（父节点方向的树） |
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];
void solve(){int n;cin>>n;vector<vector<int>>g(n+1);for(int i=0,u,v;i<n-1;i++){cin>>u>>v;g[u].emplace_back(v);g[v].emplace_back(u);}if(n==1){cout<<1<<endl;return;}int sum=0;vector<int>ans(n+1,1);auto dfs=[&](auto self,int u,int p)->void{bool ok=true;for(auto v:g[u]){if(v==p)continue;self(self,v,u);ans[u]+=ans[v];//自底向上累加子树大小的ok &= ans[v] & 1;}ok &= (n - ans[u] == 0) || ((n - ans[u]) & 1);if (ok) sum++;};dfs(dfs,1,-1);cout<<sum<<endl;
};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}