目录

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;}