Niuke novice monthly race 40

A. Digital games

A sign in question , Just imitate the meaning of the question , Pay attention to input and output , Card input , Output , It is best to scanf,printf, Do not use cin,cout
Reference code ;

#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;
            //  use lowbit Calculate how many 1, And find the highest one 1 Number expressed in decimal system of , use t Record 
			while(dx)
			{
    
				if(dx == lowbit(dx)) t = dx;
				cnt++;
				dx -= lowbit(dx);
			}
			
			if(cnt % 2) x ^= 1; // Take the last digit in reverse 
			else x -= t; //  Because the highest position must be 1, So just subtract t
			ans++;
		}
		
		printf("%d\n", ans);
	}
	
	return 0;
} 

B. Jump, jump, jump

Algorithm ： Circular interval dp
First we have to deal with a ring , We can drive 2 Double space , Make the first half the same as the second half , And then in the interval dp, See the code

#include <iostream>
using namespace std;

const int N = 2010;

int a[2 * N];
int f[2 * N][2 * N];  //f[i][j] From i Jump to the j Need to consume 

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]); //  Jump right 
			f[i][j] = max(f[i][j], f[i + 1][j] + len * a[i]); //  Jump left 
		}
		
	int ans = 0;
	for(int i = 1; i <= n; i++)
		ans = max(ans, f[i][i + n - 1]);
	cout << ans << endl;
} 

C. Number matching

This question , We can drive 2 Layer cycle to violence , In judging this 2 Number x, y Whether the conditions are met , The key is how we have to judge ？
here , We can find out x,y The length of binary expression is k Number of numbers , Convert to decimal , And write it down , see x,y Whether there is the same , Of course, the length is greater than k It must be possible , Because the length is greater than k The existence of , So the length is k It must exist .
Reference code ：

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

const int N = 2010;

int n, k;
bool st[N];

//  Used to calculate the length k The decimal system of numbers 
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);
	//  Less than t It must be impossible to match successfully 
	while(x >= t)
	{
    
		st[f(x)] = true;  //  Make a mark 
		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. Beautiful string

A water problem , It's not specific , See the code
Reference code ：

#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. grouping

A question with a two point answer , See code for details .
Reference code ：

#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. cross the bridge

A linear dp topic , It's easy to write the state transition equation , See the code

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

const int N = 2010;

int a[N];
int f[N]; // f[i] Means to transfer to i Minimum time for floating blocks 

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. Air conditioning remote control

Algorithm ： Double pointer + greedy

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

There is also a way to write the prefix and , I won't write

H. Have some gcd

This question , We need to judge x Compliance , We can find out that all in the set are x The number of multiples of , And take them gcd, See if it's on x equal , Because we need to find out the relationship with x equal gcd(a1, a2, a3, …), These numbers must be x Multiple ,
Reference code ：

#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] Deposit is 1~n Each number in the set exists i Multiple of 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. Gymnastics formation

Algorithm ：dfs
A full permutation problem , Just one more limitation ,
Reference code ：

#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]] Express a[i] Has this number ever appeared before , It's true , There have been , For false , Has never appeared 
		{
    
			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;
	
}