当前位置:网站首页>Codeworks round 639 (Div. 2) cute new problem solution
Codeworks round 639 (Div. 2) cute new problem solution
2022-07-05 08:51:00 【Qizi K】
Codeforces Round #639 (Div. 2) Cute new problem solution
Because of the long queue, the round is unrated. I’m trying to investigate it. Just solve problems for fun. I hope you liked them. Mike. Unfortunately, because the server is not rating 了
A. Puzzle Pieces
The question : Give several similar puzzles . Ask if you can use these puzzles to make n * m The block .
tips: obviously 1 OK or 1 Column can definitely .
2 * 2 It's fine too .
and 3 * 2 No way. :
And all greater than 3 * 2 The block of must contain 3 * 2 Sub block of . So none of them .
The code is incredibly simple :( Afraid of mistakes, I also checked for a long time hhh)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, m, t;
void solve(){
scanf("%d%d", &n, &m);
if(n == 1 || m == 1) printf("YES\n");
else if(n == 2 && m == 2) printf("YES\n");
else printf("NO\n");
}
int main(){
scanf("%d",&t);
while(t--){
solve();
}
return 0;
}
B. Card Constructions
The question : use poker Build a poker tower , As shown in the figure below . ask : give n A playing card , Try to put the biggest tower you can every time , How many can be placed completely at most .
tips:
I practice : Looking for a regular .
The second is two more sharp than the first (cards standing up) And a flat card (horizontal cards).2 * 2 + 1
The third one is three more sharp than the third one (cards standing up) And two flat cards (horizontal cards).3 * 2 + 2
And so on , You can play the table to find the number of cards needed by all towers .( because n No more than 1e9, about 30000 That's about it ).
Since the array is incremental , It can be calculated by two points (30000 The amount of data can be equal ).
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,t, book[100005] = {
0, 2};
void makebook(){
for(int i = 2; i <= 30005; ++i)
book[i] = book[i - 1] + 3 * i - 1;
}
void solve(){
// Linear look , No two points
scanf("%d",&n);
int cnt = 0;
for(int i = 30005; i >= 1;){
if(book[i] > n) --i;
else{
cnt++;
n -= book[i];
}
if(n <= 1) break;
}
printf("%d\n",cnt);
}
void solve2(){
// Two point search
scanf("%d",&n);
int cnt = 0, right = 30005;
while(n >= 2){
int pos = upper_bound(book + 1, book + 1 + right, n) - book - 1;
right = pos;
n -= book[pos];
if(n >= 0) cnt++;
}
printf("%d\n",cnt);
}
int main(){
scanf("%d",&t);
makebook();
while(t--){
solve2();
}
return 0;
}
Pay attention to the array from small to large ,upper_bound() What we found was The first one is greater than n The location of , Location -1 Is the last less than or equal to n The location of .
{ Review the : If the array is in order from large to small , Use greater() Realization ~}
P.S. It's fine too Direct push A formula ~
Let’s count the number of cards in a pyramid of height h. There are 2(1+2+3+⋯+h) cards standing up, and there are 0+1+2+⋯+(h−1) horizontal cards. So, there are 3/2h * h + 1/2 h cards total.
C. Hilbert’s Hotel
The question : Hilbert Hotel problem ~ Classical discrete mathematical problems . Original k Guest No. 1 lives in k Room number , Now give me a n An array of lengths , After moving according to certain rules , Whether there is still one room for each guest .
tips:1.“More formally, r = k mod n is the smallest non-negative integer such that k−r is divisible by n.”
e.g. (−1337) mod 3 = 1 , instead of -2.
2. The rules :Then for each integer k, the guest in room k is moved to room number k+a【k mod n】
3. The set of integers is a Countable sets with infinite elements , model n Equivalence class share n individual (0,1,……n-1). Just look 0-(n-1) Whether these numbers meet the conditions after moving ~ namely :Checked with a boolean array to make sure each number from 0 to n−1 is included.( Whether it can be allocated to 0-(n-1) In the equivalence class of )
#include<bits/stdc++.h>
using namespace std;
int n, t, book[200005];
void solve(){
scanf("%d",&n);
int flag[n + 5] = {
0}; // Tag array
for(int i = 0; i < n; ++i)
scanf("%d", &book[i]);
for(int i = 0; i < n; ++i){
int tmp = (i + book[i]) % n;
if(tmp < 0) tmp += n; // By definition , If the remainder is negative, it should be converted to positive
flag[tmp] = 1;
}
for(int i = 0; i < n; ++i)
if(!flag[i]){
printf("NO\n");
return ;
}
printf("YES\n");
}
int main(){
scanf("%d",&t);
while(t--){
solve();
}
return 0;
}
To be continued ing……
边栏推荐
- Wheel 1:qcustomplot initialization template
- MPSoC QSPI flash upgrade method
- 696. Count binary substring
- [matlab] matlab reads and writes Excel
- golang 基础 ——map、数组、切片 存放不同类型的数据
- Halcon color recognition_ fuses. hdev:classify fuses by color
- AdaBoost use
- [daily training -- Tencent selected 50] 557 Reverse word III in string
- Halcon shape_ trans
- Xrosstools tool installation for X-Series
猜你喜欢
随机推荐
Wechat H5 official account to get openid climbing account
It cold knowledge (updating ing~)
ORACLE进阶(三)数据字典详解
The location search property gets the login user name
MPSoC QSPI Flash 升级办法
RT-Thread内核快速入门,内核实现与应用开发学习随笔记
Illustrated network: what is gateway load balancing protocol GLBP?
C#图像差异对比:图像相减(指针法、高速)
696. Count binary substring
Meta标签详解
猜谜语啦(5)
ECMAScript6介绍及环境搭建
[matlab] matlab reads and writes Excel
Halcon: check of blob analysis_ Blister capsule detection
猜谜语啦(6)
Guess riddles (9)
IT冷知识(更新ing~)
Reasons for the insecurity of C language standard function scanf
Ros-10 roslaunch summary
Beautiful soup parsing and extracting data