报告)"/>
牛客月赛40(解题报告)
目录
A-数字游戏
题目：
思路分析：
代码实现：
B-跳跳跳
题目：
思路分析：
代码实现：
C-数字匹配
题目：
思路分析：
代码实现：
D-优美的字符串
题目：
思路分析：
代码实现：
E-分组
题目：
思路分析：
代码实现：
F-过桥
题目：
思路分析：
代码实现：
G-空调遥控
题目：
思路分析：
代码实现：
I- 体操队形
题目：
思路分析：
代码实现：
A-数字游戏
题目：
思路分析：
这道题好玄学！（原来是我眼瞎了 要用快读和cout别用小心！
然后计算位运算的模拟操作了
最后一位取反直接^就行
然后计数1的个数可以拿lowbit来操作 lowbit的功能是取这个数二进制下最后一个1以及后面0的全部
在计数的同时可以找到第一位1方便之后为偶数的操作
代码实现：
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/** __----~~~~~~~~~~~------___* . . ~~//====...... __--~ ~~* -. \_|// |||\\ ~~~~~~::::... /~* ___-==_ _-~o~ \/ ||| \\ _/~~-* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~* _-~~ .=~ | \\-_ '-~7 /- / || \ /* .~ .~ | \\ -_ / /- / || \ /* / ____ / | \\ ~-_/ /|- _/ .|| \ /* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\* ' ~-| /| |-~\~~ __--~~* |-~~-_/ | | ~\_ _-~ /\* / \ \__ \/~ \__* _--~ _/ | .-~~____--~-/ ~~==.* ((->/~ '.|||' -_| ~~-/ , . _||* -_ ~\ ~~---l__i__i__i--~~_/* _-~-__ ~) \--______________--~~* //.-~~~-~_--~- |-------~~~~~~~~* //.-~~~--\* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~** 神兽保佑 永无BUG*/int lowbit(int x){return x&-x;
}
int x,n;
int main(){scanf("%d",&n);while (n--) {scanf("%d",&x);int ans=0;while (x) {int a1=x;int num=0;int a2=0;while (a1) {if(a1==lowbit(a1)) a2=lowbit(a1);num++;a1-=lowbit(a1);}if(num&1) {x^=1;}else{x-=a2;}ans++;}printf("%d\n", ans);}
}
B-跳跳跳
题目：
思路分析：
一个区间DP的题目：
状态转移方程是: f[l][r]=max(dp(l+1,r)+len*a[l],dp(l,r-1)+len*a[r]);
len是区间长度 通过记忆化好实现
然后枚举起点计算最大值就行
代码实现：
const int MAX=4010;
int n;
int a[MAX];
ll f[MAX][MAX];
int dp(int l,int r){if(f[l][r]) return f[l][r];if(l==r) return a[l];int len=r-l+1;return f[l][r]=max(dp(l+1,r)+len*a[l],dp(l,r-1)+len*a[r]);
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];a[i+n]=a[i];}ll ans=0;for(int i=1;i<=n;i++){ans=max(ans,dp(i,i+n-1));}cout<<ans;
}
C-数字匹配
题目：
思路分析：
用了类似hash的思想
i和j有>=k的重合位那么就一定存在k位的重合
我们枚举i的每k位的数字放入桶中
然后枚举j的每k位数字在桶中查找
如果找到的话++
代码实现：
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/** __----~~~~~~~~~~~------___* . . ~~//====...... __--~ ~~* -. \_|// |||\\ ~~~~~~::::... /~* ___-==_ _-~o~ \/ ||| \\ _/~~-* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~* _-~~ .=~ | \\-_ '-~7 /- / || \ /* .~ .~ | \\ -_ / /- / || \ /* / ____ / | \\ ~-_/ /|- _/ .|| \ /* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\* ' ~-| /| |-~\~~ __--~~* |-~~-_/ | | ~\_ _-~ /\* / \ \__ \/~ \__* _--~ _/ | .-~~____--~-/ ~~==.* ((->/~ '.|||' -_| ~~-/ , . _||* -_ ~\ ~~---l__i__i__i--~~_/* _-~-__ ~) \--______________--~~* //.-~~~-~_--~- |-------~~~~~~~~* //.-~~~--\* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~** 神兽保佑 永无BUG*/int n,k;
const int MAX=114514;
int Hash[MAX];
int ans;
int a[MAX];
void insert(int x){int pos=0;while (x) {a[++pos]=x&1;x>>=1;}int s=0;for(int i=1;i<=k;i++){s=s*2+a[i];}Hash[s]=1;for(int i=k+1;i<=pos;i++){
// s=2*(s-a[i-k]*(1ll<<(k-1)))+a[i];s=2*(s-(1ll<<(k-1))*a[i-k])+a[i];Hash[s]=1;}
}
void query(int x){int pos=0;while (x) {a[++pos]=x&1;x>>=1;}int s=0;for(int i=1;i<=k;i++){s=s*2+a[i];}if(Hash[s]){ans++;return;}for(int i=k+1;i<=pos;i++){s=2*(s-(1ll<<(k-1))*a[i-k])+a[i];if(Hash[s]){ans++;return;}}
}
void clear(int x) {int pos=0;while (x) {a[++pos]=x&1;x>>=1;}int s=0;for(int i=1;i<=k;i++){s=s*2+a[i];}Hash[s]=0;for(int i =k+1;i<=pos;i++) {s=2*(s-(1ll<<(k-1))*a[i-k])+a[i];Hash[s] = 0;}
// mms(Hash,0);
}
int main(){cin>>n>>k;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){int ws1 = log2(i) + 1, ws2 = log2(j) + 1;if(ws1 < k || ws2 < k) {continue;}insert(i);query(j);clear(i);}}cout<<ans;
}
D-优美的字符串
题目：
思路分析：
就是找相邻不同的间隔数
代码实现：
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/** __----~~~~~~~~~~~------___* . . ~~//====...... __--~ ~~* -. \_|// |||\\ ~~~~~~::::... /~* ___-==_ _-~o~ \/ ||| \\ _/~~-* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~* _-~~ .=~ | \\-_ '-~7 /- / || \ /* .~ .~ | \\ -_ / /- / || \ /* / ____ / | \\ ~-_/ /|- _/ .|| \ /* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\* ' ~-| /| |-~\~~ __--~~* |-~~-_/ | | ~\_ _-~ /\* / \ \__ \/~ \__* _--~ _/ | .-~~____--~-/ ~~==.* ((->/~ '.|||' -_| ~~-/ , . _||* -_ ~\ ~~---l__i__i__i--~~_/* _-~-__ ~) \--______________--~~* //.-~~~-~_--~- |-------~~~~~~~~* //.-~~~--\* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~** 神兽保佑 永无BUG*/const int MAX=10001;
int w(string s){int ans=0;for(int i=0;i<s.length()-1;i++){if(s[i]==s[i+1]){ans++;}}return ans;
}
int main(){int n;cin>>n;while (n--) {string s;cin>>s;cout<<s.length()+w(s)<<endl;}
}
E-分组
题目：
思路分析：
最大的最小很容易想到二分
但是题目数据很小
直接枚举check也行
代码实现：
代码1:
const int MAX=100010;
int n,m;
int a[MAX];
map<int,int>mp;
vector<int>v;
int ch(int x){int ans=0;for(int i=0;i<v.size();i++){double y=x;ans+=ceil(mp[v[i]]/y);}
// cout<<"ans= "<<ans<<endl;if(ans>m) return 0;return 1;
}
int main(){cin>>n>>m;set<int>st;for(int i=1;i<=n;i++){cin>>a[i];if(st.count(a[i])==0){st.insert(a[i]);v.push_back(a[i]);}mp[a[i]]++;}
// cout<<mp[2]<<endl;
// cout<<mp[3]<<endl;if(st.size()>m){cout<<-1;return 0;}for(int i=1;i<=n;i++){if(ch(i)){cout<<i;return 0;}}cout<<-1;
}
代码2（二分）
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/** __----~~~~~~~~~~~------___* . . ~~//====...... __--~ ~~* -. \_|// |||\\ ~~~~~~::::... /~* ___-==_ _-~o~ \/ ||| \\ _/~~-* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~* _-~~ .=~ | \\-_ '-~7 /- / || \ /* .~ .~ | \\ -_ / /- / || \ /* / ____ / | \\ ~-_/ /|- _/ .|| \ /* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\* ' ~-| /| |-~\~~ __--~~* |-~~-_/ | | ~\_ _-~ /\* / \ \__ \/~ \__* _--~ _/ | .-~~____--~-/ ~~==.* ((->/~ '.|||' -_| ~~-/ , . _||* -_ ~\ ~~---l__i__i__i--~~_/* _-~-__ ~) \--______________--~~* //.-~~~-~_--~- |-------~~~~~~~~* //.-~~~--\* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~** 神兽保佑 永无BUG*/const int MAX=100010;
int n,m;
int a[MAX];
int ch(int x){int ans=0;for(int i=1;i<=MAX;i++){if(a[i]){ans+=(a[i]-1)/x+1;}}return ans<=m;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){int x;cin>>x;a[x]++;}int l=1;int r=n;while (l+1<r) {int mid=(l+r)>>1;if(ch(mid)){r=mid;}else l=mid;}if(!ch(r)) r=-1;cout<<r;
}
F-过桥
题目：
思路分析：
这道题可以理解为dp模型也可以理解为最短路模型
代码实现：
代码1dp
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/** __----~~~~~~~~~~~------___* . . ~~//====...... __--~ ~~* -. \_|// |||\\ ~~~~~~::::... /~* ___-==_ _-~o~ \/ ||| \\ _/~~-* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~* _-~~ .=~ | \\-_ '-~7 /- / || \ /* .~ .~ | \\ -_ / /- / || \ /* / ____ / | \\ ~-_/ /|- _/ .|| \ /* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\* ' ~-| /| |-~\~~ __--~~* |-~~-_/ | | ~\_ _-~ /\* / \ \__ \/~ \__* _--~ _/ | .-~~____--~-/ ~~==.* ((->/~ '.|||' -_| ~~-/ , . _||* -_ ~\ ~~---l__i__i__i--~~_/* _-~-__ ~) \--______________--~~* //.-~~~-~_--~- |-------~~~~~~~~* //.-~~~--\* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~** 神兽保佑 永无BUG*/const int MAX=100001;
int n,m;
int a[MAX];
int dp[MAX];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}mms(dp,INF);dp[1]=0;for(int i=1;i<=n;i++){if(a[i]>0){for(int j=i+1;j<=a[i]+i;j++){dp[j]=min(dp[j],dp[i]+1);}}else{for(int j=i+a[i];j<=i-1;j++){dp[j]=min(dp[j],dp[i]+1);}}}if(dp[n]>=INF) cout<<-1;else cout<<dp[n];}
代码2最短路
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/** __----~~~~~~~~~~~------___* . . ~~//====...... __--~ ~~* -. \_|// |||\\ ~~~~~~::::... /~* ___-==_ _-~o~ \/ ||| \\ _/~~-* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~* _-~~ .=~ | \\-_ '-~7 /- / || \ /* .~ .~ | \\ -_ / /- / || \ /* / ____ / | \\ ~-_/ /|- _/ .|| \ /* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\* ' ~-| /| |-~\~~ __--~~* |-~~-_/ | | ~\_ _-~ /\* / \ \__ \/~ \__* _--~ _/ | .-~~____--~-/ ~~==.* ((->/~ '.|||' -_| ~~-/ , . _||* -_ ~\ ~~---l__i__i__i--~~_/* _-~-__ ~) \--______________--~~* //.-~~~-~_--~- |-------~~~~~~~~* //.-~~~--\* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~** 神兽保佑 永无BUG*/#define N 2005
using namespace std;
struct edge {int v, nxt;
} e[N * N << 1];
int p[N], eid;
void init() {memset(p, -1, sizeof p);eid = 0;
}
void insert(int u, int v) {e[eid].v = v;e[eid].nxt = p[u];p[u] = eid ++;
}
int dis[N], n, a[N];
queue<int> q;
void bfs(int S) {memset(dis, -1, sizeof dis);dis[S] = 0; q.push(S);while(q.size()) {int u = q.front(); q.pop();for(int i = p[u]; i + 1; i = e[i].nxt) {int v = e[i].v;if(dis[v] == -1) {dis[v] = dis[u] + 1;q.push(v);}}}
}
int main() {init();scanf("%d", &n);for(int i = 1; i <= n; i ++) {scanf("%d", &a[i]);if(a[i] > 0) {for(int j = i + 1; j <= min(n, a[i] + i); j ++) {insert(j, i);}}if(a[i] < 0) {for(int j = 1; j <= max(1, i + a[i]); j ++) {insert(j, i);}}}bfs(n);printf("%d", dis[1]);return 0;
}
G-空调遥控
题目：
思路分析：
数据范围比较小 我们直接枚举k 然后预处理前缀和 找最大值就行
或者用差分思想解决
代码实现：
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/** __----~~~~~~~~~~~------___* . . ~~//====...... __--~ ~~* -. \_|// |||\\ ~~~~~~::::... /~* ___-==_ _-~o~ \/ ||| \\ _/~~-* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~* _-~~ .=~ | \\-_ '-~7 /- / || \ /* .~ .~ | \\ -_ / /- / || \ /* / ____ / | \\ ~-_/ /|- _/ .|| \ /* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\* ' ~-| /| |-~\~~ __--~~* |-~~-_/ | | ~\_ _-~ /\* / \ \__ \/~ \__* _--~ _/ | .-~~____--~-/ ~~==.* ((->/~ '.|||' -_| ~~-/ , . _||* -_ ~\ ~~---l__i__i__i--~~_/* _-~-__ ~) \--______________--~~* //.-~~~-~_--~- |-------~~~~~~~~* //.-~~~--\* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~** 神兽保佑 永无BUG*/const int MAX=1000000;
int a[MAX+10];
int n,p;
int main(){n=read();p=read();for(int i=1;i<=n;i++){int x;x=read();a[x]++;}for(int i=1;i<=MAX;i++){a[i]+=a[i-1];}int ans=0;for(int i=1;i<=MAX;i++){ans=max(ans,a[min(MAX,p+i)]-a[max(0,i-p-1)]);}cout<<ans;
}代码2
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/** __----~~~~~~~~~~~------___* . . ~~//====...... __--~ ~~* -. \_|// |||\\ ~~~~~~::::... /~* ___-==_ _-~o~ \/ ||| \\ _/~~-* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~* _-~~ .=~ | \\-_ '-~7 /- / || \ /* .~ .~ | \\ -_ / /- / || \ /* / ____ / | \\ ~-_/ /|- _/ .|| \ /* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\* ' ~-| /| |-~\~~ __--~~* |-~~-_/ | | ~\_ _-~ /\* / \ \__ \/~ \__* _--~ _/ | .-~~____--~-/ ~~==.* ((->/~ '.|||' -_| ~~-/ , . _||* -_ ~\ ~~---l__i__i__i--~~_/* _-~-__ ~) \--______________--~~* //.-~~~-~_--~- |-------~~~~~~~~* //.-~~~--\* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~** 神兽保佑 永无BUG*/const int MAX=2000210;
int n,p;
int a[MAX];
int main(){cin>>n>>p;for(int i=1;i<=n;i++){int x;cin>>x;a[max(1,x-p)]++;a[x+p+1]--;}int ans=0;int now=0;for(int i=1;i<=MAX;i++){now+=a[i];ans=max(ans,now);}cout<<ans<<endl;}
I- 体操队形
题目：
思路分析：
数据很小 我们可以直接枚举所有状态（全排列就行n!的复杂度
然后check就行
思路2.状态压缩dp
思路3.暴搜
代码实现：
枚举：
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/** __----~~~~~~~~~~~------___* . . ~~//====...... __--~ ~~* -. \_|// |||\\ ~~~~~~::::... /~* ___-==_ _-~o~ \/ ||| \\ _/~~-* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~* _-~~ .=~ | \\-_ '-~7 /- / || \ /* .~ .~ | \\ -_ / /- / || \ /* / ____ / | \\ ~-_/ /|- _/ .|| \ /* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\* ' ~-| /| |-~\~~ __--~~* |-~~-_/ | | ~\_ _-~ /\* / \ \__ \/~ \__* _--~ _/ | .-~~____--~-/ ~~==.* ((->/~ '.|||' -_| ~~-/ , . _||* -_ ~\ ~~---l__i__i__i--~~_/* _-~-__ ~) \--______________--~~* //.-~~~-~_--~- |-------~~~~~~~~* //.-~~~--\* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~** 神兽保佑 永无BUG*/const int MAX=12;
int a[MAX];
map<char,int>mp;
int ans;
void permutation(char *str,int length)
{sort(str,str+length);do{
// for(int i=0; i<length; i++)
// {
// printf("%c ",str[i]);
// }
// printf("\n");for(int i=0;i<length;i++){mp[str[i]]=i;}
// for(int i=0;i<length;i++){
// cout<<str[i]<<"--"<<mp[str[i]]<<endl;
// }int flag=1;for(int i=0;i<length;i++){if(a[i]!=i+1){if(mp[i+1+'0']>mp[a[i]+'0'])flag=0;}}if(flag) ans++;}while(next_permutation(str,str+length));}
int main()
{int n;cin>>n;for(int i=0;i<n;i++)cin>>a[i];char str[10];for(int i=0;i<n;i++){str[i]='1'+i;}permutation(str,n);cout<<ans;return 0;
}爆搜
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/** __----~~~~~~~~~~~------___* . . ~~//====...... __--~ ~~* -. \_|// |||\\ ~~~~~~::::... /~* ___-==_ _-~o~ \/ ||| \\ _/~~-* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~* _-~~ .=~ | \\-_ '-~7 /- / || \ /* .~ .~ | \\ -_ / /- / || \ /* / ____ / | \\ ~-_/ /|- _/ .|| \ /* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\* ' ~-| /| |-~\~~ __--~~* |-~~-_/ | | ~\_ _-~ /\* / \ \__ \/~ \__* _--~ _/ | .-~~____--~-/ ~~==.* ((->/~ '.|||' -_| ~~-/ , . _||* -_ ~\ ~~---l__i__i__i--~~_/* _-~-__ ~) \--______________--~~* //.-~~~-~_--~- |-------~~~~~~~~* //.-~~~--\* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~** 神兽保佑 永无BUG*/const int MAX=15;
int vis[MAX];
int n;
int a[MAX];
int in[MAX];
int ans;
void dfs(int pos){if(pos==n){ans++;return;}for(int i=1;i<=n;i++){if(!vis[i]&&!in[i]){vis[i]=1;if(a[i]!=i) in[a[i]]--;dfs(pos+1);vis[i]=0;if(a[i]!=i) in[a[i]]++;}}
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]!=i) in[a[i]]++;}dfs(1);cout<<ans<<endl;}
更多推荐
牛客月赛40(解题报告)
发布评论