C语言算法训练第十一天，如何为？
摘要：C++算法算法训练第十一天 以下为牛客挑战 今日收获 学到了状态压缩dp,这个是选或者不选两种情况所有数的情况。 for(int i=0;i<(1LL<&
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<<3
1000-->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);//用来算改变之后的x
y+=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;
}