题解 | #数字游戏#
数字游戏
https://ac.nowcoder.com/acm/contest/11217/A
数字游戏
题目描述：
一个x ，当x不为零时进行如下操作
- 如果二进制x中有奇数个1，则x二进制形式下最低位取反
- 如果二进制xxx中有偶数个1，则x二进制形式下非前导零最高位取反
询问对于一个x，操作几次后变为零
思路1：
对于奇数的情况，其实就对x异或了1
对于偶数的情况，其实就是把第一个的1去掉了，这里可以使用lowbit，一个数减去p次lowbit后等于0，就说明他有p个1，且可以获得第一个1对应的值，这样就可以实现判断与去掉第一个1
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 300000 + 10
int n, m, k;
int x, y, z;
int a, b, c;
void work(){
x = IntRead();
int ans = 0;
while (x) {
int p = x;
int len = 0;
while (p) {
if(p == lowbit(p))a = p;
p -= lowbit(p);
++len;
}
if(len % 2)x ^= 1;
else x -= a;
++ans;
}
pd(ans);
}
int main(){
// io;
int tt;cin>>tt;
for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
}
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
思路2:
找规律，根据这个数二进制下的1的个数和他本身的奇偶性来分类讨论即可
可以用bitset的一个函数，直接统计出二进制下1的个数
假设x二进制下1的个数
- y&1=1
- x&1=1，输出2 * y - 1
- x&1=0，输出2 * y + 1
- y&1=0
- x&1=1，输出2 * y - 2
- x&1=0，输出2 * y
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 300000 + 10
int n, m, k;
int x, y, z;
int a, b, c;
void work(){
x = IntRead();
bitset<32>b(x);
y = (int)b.count();
if(y & 1){
if(x & 1)cout<<2 * y - 1<<endl;
else cout<<2 * y + 1<<endl;
}
else{
if(x & 1)cout<<2 * y - 2<<endl;
else cout<<2 * y<<endl;
}
}
int main(){
// io;
int tt;cin>>tt;
for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
}
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
跳跳跳
题目描述：
n个格子呈环形分布，顺时针方向分别标号为1∼n，其中1和n相邻，每个格子上都有一个正整数a[i]，玩家可以选择一个点作为起点开始跳n下，第i次跳跃，玩家只可以选择当前位置左边或右边最近且尚未被跳跃过的位置进行一次跳跃，并获得i×a[p]的得分，其中p为第 i 次跳跃的位置。
问能得到的最高分
思路：
区间dp
dp[i] [j] 表示左边的第一个未选择的点为i，最右边的第一个为选择的点为j，能得到的最大价值
dp[i] [j] = max(dp[i - 1] [j] + len * tr[i], dp[i] [j - 1] + len * tr[j])
len是此区间的长度
和区间dp一样，先枚举区间长度len，再枚举 i ，这样可以直接得到 j
还有一点就是这是一个环，搞成2倍的数组去跑，最后取max
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 300000 + 10
int n, m, k;
int x, y, z;
int a, b, c;
ll tr[MAX];
ll dp[4005][4005];
void work(){
cin>>n;
for(int i = 1; i <= n; ++i){
cin>>tr[i];
tr[i + n] = tr[i];
}
for(int i = 1; i <= n * 2; ++i)dp[i][i] = tr[i];
for(int len = 2;len <= n; ++len){
for(int i = 1; i <= 2 * n - len + 1; ++i){
int j = i + len - 1;
dp[i][j] = max(dp[i + 1][j] + len * tr[i], dp[i][j - 1] + len * tr[j]);
}
}
ll ans = 0;
for(int i = 1; i <= n + 1; ++i){
ans = max(ans, dp[i][i + n - 1]);
}
cout<<ans<<endl;
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
数字匹配
题目描述：
x和y在二进制下最大连续重合长度大于等于k的数量（1<=x<y<=n）
思路：
先预处理，搞一个vector数组，将这个数二进制下长度为k的二进制的十进制数塞进去
暴力枚举 i 和 j，暴力枚举这个两个的vector中的数有没有重合
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 300000 + 10
int n, m, k;
int x, y, z;
int a, b, c;
vector<int>tr[2005];
int C_H(string s){
int ans = 0;
for(int i = 0; i < s.size(); ++i){
ans *= 2;
ans += s[i] - '0';
}
return ans;
}
void cal(){
for(int i = 1; i <= n; ++i){
set<int>se;
x = i;
string s;
while (x) {
s += x % 2 + '0';
x /= 2;
}
reverse(s.begin(), s.end());
s = " " + s;
for(int j = 1; j + k <= s.size(); ++j){
int num = C_H(s.substr(j, k));
if(se.count(num))continue;
se.insert(num);
tr[i].push_back(num);
}
}
}
bool judge(int a, int b){
for(auto u : tr[a]){
for(auto v : tr[b]){
if(u == v)return true;
}
}
return false;
}
void work(){
cin>>n>>k;
cal();
int ans = 0;
for(int i = 1; i <= n; ++i){
for(int j = i + 1; j <= n; ++j){
if(judge(i, j))++ans;
}
}
cout<<ans<<endl;
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
优美字符串
题目描述：
一个字符串，给定字符串变成一个任意相邻字符都不相等的字符串最少需要插入多少个字符
思路：
记录相邻的相等字符的数量，输出原串的长度+该数量
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 300000 + 10
int n, m, k;
int x, y, z;
string s;
void work()
{
cin>>s;
k = 0;
for(int i = 0; i < s.size() - 1; ++i){
if(s[i] == s[i + 1])++k;
}
cout<<s.size() + k<<endl;
}
int main(){
// io;
int tt;cin>>tt;
for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
}
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
分组
题目描述：
n个人，分成m组，每个人都有一个价值，每个组的人的价值必须相等，要求人数最多的组的人数尽可能少，问能不能成功安排
思路：
最小的最大值，显然是二分答案
二分组的最大数量，check的时候就判断需要的最少组的数量与m的关系即可
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 300000 + 10
int n, m, k;
int x, y, z;
string s;
int tr[MAX];
vector<int>v;
bool judge(int x){
int num = 0;//组的数量
for(int i = 0; i < v.size(); ++i){
num += (v[i] + x - 1) / x;
}
if(num > m)return false;
return true;
}
void work()
{
cin>>n>>m;
for(int i= 1; i <= n; ++i){
cin>>tr[i];
}
sort(tr + 1, tr + 1 + n);
k = 1;
for(int i = 1; i < n; ++i){
if(tr[i] == tr[i + 1])++k;
else {
v.push_back(k);
k = 1;
}
}
v.push_back(k);
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if(!judge(mid))l = mid + 1;
else r = mid - 1;
}
if(l >= 1 && l <= n)cout<<l<<endl;
else cout<<-1<<endl;
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
过桥
题目描述：
问从1到n的最短时间，每个点有一个价值a
i，如果ai>0，那这1秒可以从i走到[i + 1, i + ai]的任意一个位置，如果ai<0,那这1秒会可以走到[1, ai+i]的任意一个位置
思路1：
简单dp，dp[i] 表示从1走到 i 的最短时间，如果ar[i]都大于0，那就可以更新[i+1, i+ar[i]]的dp值，显然1到n的dp值肯定是非递减的，所以对于ar[i]<0的情况，说明从i会跳到[1, a
i+1]的位置，这就会更新这些点的值，但是这更新是肯定不会更新最小值，所以对于ai<0的就跳过就行，最后输出dp[n]，如果dp[n]是初始值就说明更新不到n，就输出-1
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 300000 + 10
int n, m, k;
int x, y, z;
int a, b, c;
int tr[MAX];
int dp[MAX];
void work(){
cin>>n;
for(int i = 1; i <= n; ++i)cin>>tr[i];
mem(dp, inf);
dp[1] = 0;
for(int i = 1; i <= n; ++i){
if(tr[i] <= 0)continue;
for(int j = i; j <= i + tr[i]; ++j){
dp[j] = min(dp[j], dp[i] + 1);
}
}
if(dp[n] == inf)cout<<-1<<endl;
else cout<<dp[n]<<endl;
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
思路2：
暴力建图跑最短路
虽然很愚蠢，但是确实能过
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 4000000 + 10
int n, m, k;
int x, y, z, s;
int a, b, c;
int tot;
int head[MAX];
struct ran{
int to, nex, val;
}tr[MAX];
ran now, nex;
void add(int u, int v, int c){
tr[++tot].to = v;
tr[tot].nex = head[u];
tr[tot].val = c;
head[u] = tot;
}
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q;
int dis[MAX];
bool vis[MAX];
void dijkstra(){
s = 1;
q.push(make_pair(0, s));
dis[s] = 0;
while (!q.empty()) {
int u = q.top().second;q.pop();
if(vis[u])continue;
vis[u] = 1;
for(int i = head[u]; i; i = tr[i].nex){
int v = tr[i].to;
if(dis[v] > dis[u] + tr[i].val){
dis[v] = dis[u] + tr[i].val;
q.push(make_pair(dis[v], v));
}
}
}
if(dis[n] == inf)cout<<-1<<endl;
else cout<<dis[n]<<endl;
}
void work()
{
cin>>n;
for(int i = 1; i <= n; ++i){
cin>>x;
if(i == n)continue;
if(x > 0){
for(int j = i + 1; j <= i + x; ++j)add(i, j, 1);
}
else{
for(int j = 1; j <= i + x - 1; ++j)add(i, j, 1);
}
}
mem(dis, inf);
dijkstra();
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
空调遥控器
题目描述：
n个人，每个人有一个温度诉求a
i,当室内温度为k时，当且仅当｜a[i]−K｜≤p，这个人才能正常进入训练状态，问如何调整温度才能使的更多的队员同时进入状态，输出最大的队员数
思路1:
每个人都有一个范围a[i]-k<= t <= a[i] + k, 对每个这个区间的每个值进行加1，从头扫一遍找最大值
当然肯定不能暴力进行区间更新，可以用差分前缀和来优化
有个问题就是温度可能是负数，那我们就给每个温度+1000000
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 2000000 + 10
int n, m, k;
int x, y, z;
int tr[MAX];
void work()
{
cin>>n>>m;
for(int i = 1; i <= n; ++i){
cin>>x;
x += 1000000;
tr[x - m]++;
tr[x + m + 1]--;
}
int ans = 0;
for(int i = 1; i < MAX; ++i){
tr[i] += tr[i - 1];
ans = max(ans, tr[i]);
}
cout<<ans<<endl;
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
思路2:
排序后使用双指针来获得最长区间的长度
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 1000000 + 10
int n, m, k;
int x, y, z;
int a, b, c;
int tr[MAX];
void work(){
cin>>n>>k;
for(int i = 1; i <= n; ++i)cin>>tr[i];
sort(tr + 1, tr + 1 + n);
int l = 1, r = 1;
int ans = 0;
while (l <= n && r <= n) {
// cout<<l<<' '<<r<<endl;
ans = max(ans, r - l + 1);
if(tr[r + 1] - tr[l] <= 2 * k)++r;
else ++l;
}
cout<<ans<<endl;
}
int main(){
io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
思路3:
二分答案
写chekc函数的时候只要有一个tr[i + len - 1] - tr[i] <= 2 * k就行
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 1000000 + 10
int n, m, k;
int x, y, z;
int a, b, c;
int tr[MAX];
bool judge(int len){
for(int i = 1; i + len - 1 <= n; ++i){
if(tr[i + len - 1] - tr[i] <= 2 * k)return true;
}
return false;
}
void work(){
cin>>n>>k;
for(int i = 1; i <= n; ++i)cin>>tr[i];
sort(tr + 1, tr + 1 + n);
int l = 1, r = n + 1;
while (l <= r) {
int mid = (l + r) / 2;
if(judge(mid))l = mid + 1;
else r = mid - 1;
}
cout<<l - 1<<endl;
}
int main(){
io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
来点gcd
题目描述：
n个数，m个询问，每次询问一个数x，问能不能从这n个数中选出任意数量个数，使的这些数的gcd等于x
思路：
注意数据范围，a
i不超过n如果这p个数gcd=x，说明这p个数肯定是x的倍数
但如果p个数是x的倍数，这p个数不一定gcd=x，因为可能是x的倍数
所以我们对于每个数x，我们去枚举他的倍数，看看存不存在，如果存在就求gcd，看看最后能不能等于x即可
用个标记数组来标记每个询问过的数的答案
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 1000000 + 10
int n, m, k;
int x, y, z;
int a, b, c;
bool vis[MAX];
int f[MAX];
int gcd(int a, int b){
if(b) return gcd(b, a % b);
else return a;
}
bool judge(int x){
int gg = 0;
for(int i = x; i <= n; i += x){
if(vis[i]){
gg = gcd(gg, i);
if(gg == x){
return true;
}
}
}
return false;
}
void work(){
cin>>n>>m;
for(int i = 1; i <= n; ++i)vis[i] = f[i] = 0;
for(int i = 1; i <= n; ++i){
cin>>x;
vis[x] = 1;
}
for(int i = 1; i <= m; ++i){
cin>>x;
if(!f[x]){
if(judge(x)){
f[x] = 1;
}
else f[x] = -1;
}
cout<<(f[x] == 1 ? "YES\n" : "NO\n");
}
}
int main(){
io;
int tt;cin>>tt;
for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
}
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
体操队形
题目描述：
n个人，标号1到n，每个人都希望排在a
i的前面，当ai=i时则不用管，问有多少种排队方式可以满足所有队员
思路：
全排列暴力判断就行
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 300000 + 10
int n, m, k;
int x, y, z;
string s;
int tr[100];
int ar[100];
int pos[100];
bool judge(){
for(int i = 1; i <= n; ++i){
if(tr[ar[i]] == ar[i])continue;
if(pos[ar[i]] >= pos[tr[ar[i]]])return false;
}
return true;
}
void work()
{
cin>>n;
for(int i = 1; i <= n; ++i)cin>>tr[i];//i在tr[i]前面
for(int i = 1; i <= n; ++i)ar[i] = i;
do {
for(int i = 1; i <= n; ++i)pos[ar[i]] = i;//ar[i]的位置是i
if(judge())++k;
} while (next_permutation(ar + 1, ar + 1 + n));
cout<<k<<endl;
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
