当前位置:网站首页>Niuke novice monthly race 40
Niuke novice monthly race 40
2022-07-06 11:25:00 【%xiao Q】
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;
}
边栏推荐
- Ansible实战系列三 _ task常用命令
- Solve the problem of installing failed building wheel for pilot
- The virtual machine Ping is connected to the host, and the host Ping is not connected to the virtual machine
- QT creator design user interface
- Why can't STM32 download the program
- ES6 Promise 对象
- Unable to call numpy in pycharm, with an error modulenotfounderror: no module named 'numpy‘
- 02-项目实战之后台员工信息管理
- 记一次某公司面试题:合并有序数组
- Knowledge Q & A based on Apache Jena
猜你喜欢
error C4996: ‘strcpy‘: This function or variable may be unsafe. Consider using strcpy_s instead
Swagger, Yapi interface management service_ SE
软件测试与质量学习笔记3--白盒测试
MySQL主从复制、读写分离
QT creator create button
Integration test practice (1) theoretical basis
Image recognition - pyteseract TesseractNotFoundError: tesseract is not installed or it‘s not in your path
Dotnet replaces asp Net core's underlying communication is the IPC Library of named pipes
Summary of numpy installation problems
[download app for free]ineukernel OCR image data recognition and acquisition principle and product application
随机推荐
Learn winpwn (2) -- GS protection from scratch
QT creator uses Valgrind code analysis tool
解决安装Failed building wheel for pillow
JDBC原理
In the era of DFI dividends, can TGP become a new benchmark for future DFI?
Case analysis of data inconsistency caused by Pt OSC table change
vs2019 第一个MFC应用程序
Use dapr to shorten software development cycle and improve production efficiency
图像识别问题 — pytesseract.TesseractNotFoundError: tesseract is not installed or it‘s not in your path
PHP - whether the setting error displays -php xxx When PHP executes, there is no code exception prompt
Principes JDBC
Request object and response object analysis
Valentine's Day flirting with girls to force a small way, one can learn
保姆级出题教程
[蓝桥杯2020初赛] 平面切分
Base de données Advanced Learning Notes - - SQL statements
The virtual machine Ping is connected to the host, and the host Ping is not connected to the virtual machine
Redis的基础使用
What does BSP mean
ES6 Promise 对象