牛客周赛 Round 32
目录
A.小红的01背包
B.小红的 dfs
C.小红的排列生成
D.小红的二进制树
E.小红的回文数
F.小红的矩阵修改
A.小红的01背包
思路： 看到标题就用动规做了hhhh，实则就是个小学题。。
int f[205];int main()
{int m,x,y;cin>>m>>x>>y;for(int i=x;i<=m;i++)f[i]=max(f[i],f[i-x]+y);cout<<f[m];
}B.小红的 dfs
思路：由题意可知只有三种情况符合，所以我们只需条件判断满足这三种状态需要修改的最少次数
1d f s
f
s2d
d f ss3df
d f sconst int N=4;
char a[N][N];int main()
{for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)cin>>a[i][j];int ans1=(a[1][1]!='d')+(a[1][2]!='f')+(a[1][3]!='s')+(a[2][1]!='f')+(a[3][1]!='s');int ans2=(a[2][1]!='d')+(a[2][2]!='f')+(a[2][3]!='s')+(a[1][2]!='d')+(a[3][2]!='s');int ans3=(a[3][1]!='d')+(a[3][2]!='f')+(a[3][3]!='s')+(a[1][3]!='d')+(a[2][3]!='f');cout<<min(min(ans1,ans2),ans3);
}C.小红的排列生成
思路：贪心，我们先将1~n中的数用set存一遍，输入的时候如果set中含有这个数，则在set中删去，否则就是要修改的数，用map存储，输入完以后set中剩余的数就是map中的数要修改达到的数，为了使修改次数尽可能小，我们要将map中小的数修改成set中小的数
此题要开long long!!!
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int N=1e5+5;int a[N];int32_t main()
{int n;cin>>n;set<int> s;map<int,int> mp;for(int i=1;i<=n;i++) s.insert(i);for(int i=1;i<=n;i++){cin>>a[i];if(s.count(a[i])) s.erase(a[i]);else mp[a[i]]++;}int sum=0;for(auto t:mp){for(int i=0;i<t.second;i++){sum+=abs(t.first-(*s.begin()));s.erase(*s.begin());}}cout<<sum;
}D.小红的二进制树
思路：树形dp，题目要求一个节点能到达由二进制数组成的数为奇数的路径，也就是只要这条路径上的节点为1，那么路径数就要加1，遇到叶子节点时，判断其实是否为1，为1，则向上返回1，否则返回0
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;const int N=1e5+5;
string s;
vector<int> g[N];
int n;
int f[N];int dfs(int u)
{if(g[u].size()==0&&s[u]=='1') return 1;int sum=0;for(auto t:g[u]){// if(t==fa) continue;sum+=dfs(t);//返回子节点的路径数if(s[t]=='1'&&g[t].size()) sum++;//如果子节点为1，且不是叶子节点，说明当前节点走到子节点也是一条路径}f[u]=sum;return f[u];
}int32_t main()
{cin>>n;cin>>s;s=" "+s;for(int i=1;i<n;i++){int a,b;cin>>a>>b;g[a].push_back(b);//因为题目只沿着子节点走，所以建有向边就行了// g[b].push_back(a);}dfs(1);for(int i=1;i<=n;i++)cout<<f[i]<<endl;
}E.小红的回文数
思路： 数字回文数有根据其长度分为两种情况，（1）长度为偶数时，在这个区间中的0~9的个数必须是偶数个，eg.1919 、001199 （2）长度为奇数时，这个区间中的数只有一个数的个数为奇数，其余均为偶数，eg.13331、3999993，用map<vector<int>,int> 存储前面0~9每个数的奇偶性。
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#define int long long
using namespace std;const int N = 1e5+5;map<vector<int>,int> mp;
vector<int> t;int32_t main()
{string s;cin>>s;for(int i=0;i<10;i++)t.push_back(0);mp[t]++;int sum=0;for(int i=0;i<s.size();i++){t[s[i]-'0']^=1;sum+=mp[t];for(int j=0;j<10;j++){vector<int> temp=t;temp[j]^=1;sum+=mp[temp];}mp[t]++;}cout<<sum;
}F.小红的矩阵修改
思路： 状态压缩dp，行数为4，有3个字符，我们可以用三进制中的0 1 2来表示每个字符，通过枚举每一列，再枚举这一列所有三进制组成的数，是否符合相邻的数不相等，如果是第一列且满足相邻两个数不相等，则计算原来的状态与我们现在枚举的状态有多少个数不同，然后用状态转移方程dp[i][j]=min(dp[i][j],res),dp[i][j]表示前i列以状态为j结尾的最少修改次数，这如果非第一列，还要枚举前面一列的状态与当前这一列的状态是否有相同的数字，若没有则进行状态转移dp[i][j]=min(dp[i][j],dp[i-1][k]+res)。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>using namespace std;const int N =1005;int p[5]={1,3,9,27,81};
int n,m,dp[N][105],b[N];
string s[5];
map<char,int> mp;bool check(int x)
{for(int i=0;i<n;i++){b[i]=x%3;x/=3;}for(int i=1;i<n;i++)if(b[i-1]==b[i]) return false;return true;
}bool check(int pre,int now)
{for(int i=0;i<n;i++){if(pre%3==now%3) return false;pre/=3,now/=3;}return true;
}
int main()
{cin>>n>>m;for(int i=0;i<n;i++)cin>>s[i];mp['r']=1;mp['e']=2;mp['d']=0;memset(dp,0x3f,sizeof dp);//dp[0][0]=0;int ans=0x3f3f3f3f;for(int i=0;i<m;i++){for(int j=0;j<p[n];j++){if(check(j)){int res=0,x=j;if(!i){for(int k=0;k<n;k++){if(mp[s[k][i]]!=b[k]) res++;}dp[i][j]=min(dp[i][j],res);}else{for(int k1=0;k1<n;k1++){if(mp[s[k1][i]]!=b[k1]) res++;}for(int k=0;k<p[n];k++){// res=0,x=j;if(check(k,j)){dp[i][j]=min(dp[i][j],dp[i-1][k]+res);}}if(i==m-1)ans=min(ans,dp[i][j]);}}}}cout<<ans;
}