当前位置:网站首页>AcWing 2022 每日一题
AcWing 2022 每日一题
2022-07-04 20:47:00 【.Ashy.】
Week 1 星期五 性感素数(选择结构+素数判断)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
bool judge(int n)
{
if(n<2) return 0;
for(int i=2;i*i<=n;i++)
if(n%i==0)
return 0;
return 1;
}//素数判断
int main()
{
cin>>n;
if(judge(n)&&judge(n-6))
{
puts("Yes");
cout<<n-6;
return 0;
}//先找小的匹配性感素数
if(judge(n)&&judge(n+6))
{
puts("Yes");
cout<<n+6;
return 0;
}//找不到小的找大的匹配性感素数
for(int i=n+1;;i++)
{
if(judge(i)&&judge(i+6)||judge(i)&&judge(i-6))
{
cout<<"No"<<endl<<i;
break;
}
}//都找不到往后搜索找一个性感素数
}
Week 4 星期日 倒水问题(暴力搜索)
原题链接:
倒水问题
思路:
一开始读理所当然的想到了贝祖定理和扩展欧几里得,但是仔细读题后发现并不是那回事,仔细看了题解后回来补题。
是一个搜索题,暴力搜索所有的状态即可;
A,B,C 的范围都是 0 ~ 4000 看起来状态数好像有 40013 那么多(必爆),但其实不然,因为每次转移必须保证 一个杯子是空的或者一个杯子是满的,这样最坏复杂度就降低到 3 ∗ 2 ∗ 4000 ∗ 4000 3*2*4000*4000 3∗2∗4000∗4000 大约是 9.6*107 也就是 1e8
一开始三杯水的状态为 (0,0,C)
开始倒水即状态开始转移后,转移方向是
a - b
a - c
b - a
b - c
c - a
c - b
这六个方向,我们根据题意进行转移即可
注意不计算重复的状态,每次的状态为(a,b,c),a,b,c 满足 a+b==c 因此我们只要记下其中两个数的状态就相当于表示出了这三个数的状态,我们用 set 来存状态,状态不同的时候 C 有可能相同, 我们用另一个 set 来存 所有不同的的C,统计C的答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int A,B,C;
typedef pair<int,int> PII;
set<PII>st;
set<int>ans;
/* a - b a - c b - a b - c c - a c - b */
void dfs(int a,int b,int c)
{
if(st.count({
a,b})) return ;
st.insert({
a,b});//记录状态
ans.insert(c);//记录当前状态下的答案
int x;
x=min(a,B-b);
dfs(a-x,b+x,c);//a - b
x=min(a,C-c);
dfs(a-x,b,c+x);//a - c
x=min(b,A-a);
dfs(a+x,b-x,c);//b - a
x=min(b,C-c);
dfs(a,b-x,c+x);//b - c
x=min(c,A-a);
dfs(a+x,b,c-x);//c - a
x=min(c,B-b);
dfs(a,b+x,c-x);//c - b
}
int main()
{
while(cin>>A>>B>>C)
{
ans.clear();
st.clear();
dfs(0,0,C);
cout<<ans.size()<<endl;
}
}
总结
以后看题要好好读题,不能看着像就用某种思路,这题的各种小细节都特别巧妙,包括它搜索的方法(状态的转移),记录的方法,应当好好学习这个题。
Week 5 星期一 树查找(选择结构)
思路:
第k层的左侧序号 l 是 2k-1 右侧序号 r 是 2k-1
判断是否为空 即判断 n 与 l 的 大小关系
而当不为空的时候,也要注意这一层是否完全
注意格式
左移 k 即为 × 2k
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4+10;
int n,k;
int a[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
cin>>k;
int r=(1<<k)-1;
int l=1<<(k-1);
if(n<l)
{
cout<<"EMPTY";
}
else
{
r=min(r,n);
for(int i=l;i<=r;i++)
{
if(i!=r) cout<<a[i]<<" ";
else cout<<a[i];
}
}
}
边栏推荐
- Kubeadm初始化报错:[ERROR CRI]: container runtime is not running
- 偷窃他人漏洞报告变卖成副业,漏洞赏金平台出“内鬼”
- [ 每周译Go ] 《How to Code in Go》系列文章上线了!!
- 【公开课预告】:视频质量评价基础与实践
- OMS系统实战的三两事
- ArcGIS 10.2.2 | solution to the failure of ArcGIS license server to start
- 解析steam教育中蕴含的众创空间
- Jerry's ad series MIDI function description [chapter]
- Flutter WebView示例
- flink1.13 sql基础语法(一)DDL、DML
猜你喜欢
【活动早知道】LiveVideoStack近期活动一览
Word文档中标题前面的黑点如何去掉
Arcgis 10.2.2 | arcgis license server无法启动的解决办法
超详细教程,一文入门Istio架构原理及实战应用
杰理之增加进关机前把触摸模块关闭流程【篇】
Redis 排查大 key 的3种方法,优化必备
Flutter TextField示例
【LeetCode】17、电话号码的字母组合
MP3是如何诞生的?
Billions of citizens' information has been leaked! Is there any "rescue" for data security on the public cloud?
随机推荐
Numpy vstack and column_ stack
Redis bloom filter
Interpreting the development of various intelligent organizations in maker Education
如何使用ConcurrentLinkedQueue做一个缓存队列
Shutter textfield example
旋变串判断
B站视频 声音很小——解决办法
华为ensp模拟器 实现多个路由器的设备可以相互访问
Enlightenment of maker thinking in Higher Education
LambdaQueryWrapper用法
__init__() missing 2 required positional arguments 不易查明的继承错误
IIC (STM32)
maya灯建模
如何借助自动化工具落地DevOps
Rotary transformer string judgment
At the right time, the Guangzhou station of the city chain science and Technology Strategy Summit was successfully held
迈动互联中标北京人寿保险
Huawei ENSP simulator enables devices of multiple routers to access each other
2021 CCPC 哈尔滨 B. Magical Subsequence(思维题)
In the release version, the random white screen does not display the content after opening the shutter