[数据结构与算法]牛客Novice月赛40

A. 数字游戏

一道签到题，模拟题意即可，这题要注意输入输出，会卡输入，输出，最好用scanf，printf，不要用cin，cout
参考代码；

#include <iostream>
#include <cstdio>
using namespace std;
#define lowbit(x) (x & -x)

int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		int x;
		scanf("%d", &x);
		
		int ans = 0;
		while(x)
		{
			int cnt = 0, t, dx = x;
            // 用lowbit运算计算出有多少个1，并求出最高一位1的十进制表达的数,用t记录
			while(dx)
			{
				if(dx == lowbit(dx)) t = dx;
				cnt++;
				dx -= lowbit(dx);
			}
			
			if(cnt % 2) x ^= 1; //取反最后一位
			else x -= t; // 因为最高位一定是1，所以只要减去t
			ans++;
		}
		
		printf("%d\n", ans);
	}
	
	return 0;
} 

B. 跳跳跳

算法：环形区间dp
首先得处理一个环，我们可以开2倍都空间，使前一半与后一半相同，然后在做区间dp，详情看代码

#include <iostream>
using namespace std;

const int N = 2010;

int a[2 * N];
int f[2 * N][2 * N];  //f[i][j]表示从i跳到j需要消耗的

int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], a[i + n] = a[i];
	
	for(int len = 1; len <= n; len++)
		for(int i = 1; i <= 2 * n; i++)
		{
			int j = i + len - 1;
			f[i][j] = max(f[i][j], f[i][j - 1] + len * a[j]); // 往右跳
			f[i][j] = max(f[i][j], f[i + 1][j] + len * a[i]); // 往左跳
		}
		
	int ans = 0;
	for(int i = 1; i <= n; i++)
		ans = max(ans, f[i][i + n - 1]);
	cout << ans << endl;
} 

C. 数字匹配

这题，我们可以开2层循环去暴力，在判断这2个数x, y是否符合条件，关键是我们得怎么判断？
这里，我们可以找出x,y二进制表达的长度为k的数，转化为十进制，并记录下来，看x,y中是否有存在相同，当然长度大于k肯定也是可以的，因为长度大于k的存在，那么长度为k的一定是存在的。
参考代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 2010;

int n, k;
bool st[N];

// 用来计算出长度为k的数的十进制
int f(int x)
{
	return x & ((1 << k) - 1);
}

bool judge(int x, int y)
{
	memset(st, 0, sizeof st);
	int t = 1 << (k - 1);
	// 小于t一定不可能匹配成功的
	while(x >= t)
	{
		st[f(x)] = true;  // 做标记
		x >>= 1;
	}
	
	while(y >= t)
	{
		if(st[f(y)]) return true;
		y >>= 1;
	}
	
	return false;
}

int main()
{
	scanf("%d%d", &n, &k);
	
	int ans = 0;
	for(int i = 1; i < n; i++)
		for(int j = i + 1; j <= n; j++)
			if(judge(i, j)) ans++;
	
	printf("%d\n", ans);
	return 0;
}

D. 优美字符串

一道水题，就不具体展开了，详情看代码
参考代码：

#include <iostream>
using namespace std;

int main()
{
	int T;
	cin >> T;
	
	while(T--)
	{
		string s;
		cin >> s;
		
		int ans = 0, t = 1; char ch = s[0];
		for(int i = 1; i < s.size(); i++)
		{
			if(s[i] == ch) t++;
			else
			{
//				cout << t << ' ';
				ans += t - 1;
				t = 1, ch = s[i];
			}
		}
		ans += t - 1;
		
		cout << ans + s.size() << endl;
	}
	return 0;
} 

E. 分组

一道二分答案的题，详情请看代码。
参考代码：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N];

bool judge(int x)
{
	int sum = 0, t = 1;
	for(int i = 1; i < n; i++)
	{
		if(a[i] != a[i + 1] || t == x)
		{
			t = 1;
			sum++;
		} 
		else t++;
	}
	
	if(sum > m) return false;
	return true;
}

int main()
{
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	
	int ans = -1;
	int l = 1, r = n;
	while(l < r)
	{
		int mid = l + r >> 1;
		if(judge(mid)) 
		{
			r = mid;
			ans = mid;
		}
		else l = mid + 1;
	}
	cout << ans << endl;
	return 0;
}

F. 过桥

一道线性dp题，挺容易写出状态转移方程的，详情看代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 2010;

int a[N];
int f[N]; // f[i]表示转移到第i个浮块的最少时间

int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	memset(f, 0x3f, sizeof f);
	f[1] = 0;
	for(int i = 1; i <= n; i++)
	{
		if(a[i] < 0)
		{
			for(int j = 1; j <= i + a[i]; j++)
				f[j] = min(f[j], f[i] + 1);
		}
		
		else
		{
			for(int j = i + 1; j <= i + a[i]; j++)
				f[j] = min(f[j], f[i] + 1);
		}
	}
	
	if(f[n] == 0x3f3f3f3f) puts("-1");
	else cout << f[n] << endl;
	return 0;
}

G. 空调遥控

算法：双指针 + 贪心

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;

int a[N];

int main()
{
	int n, p;
	cin >> n >> p;
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	
	int ans = -1, l = 0, r = 0;
	for(int i = p + a[0]; i <= a[n - 1] - p; i++)
	{
		while(r < n && a[r] - i < p + 1) r++;
		while(l < r && i - a[l] > p) l++;
		ans = max(ans, r - l);
	}
	
	cout << ans << endl;
	return 0;
}

还有一种前缀和的写法，这就不写了

H. 来点gcd

这道题，我们要判断x是否符合，我们可以找出在集合中所有是x的倍数的数，并取他们gcd，看是否于x相等，因为要找出与x相等的gcd(a1, a2, a3, …)，这些数一定是x的倍数，
参考代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;

int a[N], g[N], cnt[N];  // g[i]存的是1~n中每个数在集合中存在的是i的倍数的gcd

int main()
{
	int T;
	cin >> T;
	
	while(T--)
	{
		int n, m;
		scanf("%d%d", &n, &m);
		for(int i = 1; i <= n; i++) cnt[i] = g[i] = 0;
		
		for(int i = 0; i < n; i++)
		{
			int x;
			scanf("%d", &x);
			cnt[x]++;
		}
		
		for(int i = 1; i <= n; i++)
			for(int j = i; j <= n; j += i)
				if(cnt[j]) g[i] = __gcd(g[i], j);
		
		while(m--)
		{
			int x;
			scanf("%d", &x);
			if(g[x] == x) puts("YES");
			else puts("NO");
		}
	}
	return 0;
}

I.体操队形

算法：dfs
一道全排列问题，只不过多了一个限制，
参考代码：

#include <iostream>
using namespace std;

int n, ans;
int a[20];
bool st[20];

void dfs(int u)
{
	if(u == n + 1)
	{
		ans++;
		return ;
	}
	
	for(int i = 1; i <= n; i++)
	{
		if(!st[i] && !st[a[i]]) // st[a[i]]表示a[i]这个数在前面有没有出现过，为真，则出现过，为假，则没出现过
		{
			st[i] = true;
			dfs(u + 1);
			st[i] = false;
		}
	}
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	dfs(1);
	cout << ans << endl;
	
}