Noip模拟30 2021.8.4
T1 毛一琛
考场上打的稳定的$O((2^n)^2)$的暴力。其实再回忆一下上次那道用二进制枚举的题$y$
就可以知道一样的道理,使用$\textit{Meet In the Middle}$,
按照暴力枚举的思想(就是枚举两个没有交集的子集判断其和是不是相等)
去考虑将整个集合分为两部分,在每一部分分别找任意两个集合能够凑出的和
为了好操作我们找到$1~n/2$的集合中任意两个子集的和,并将其标记,存入$map$
并使用$vector$对应$sta$及其标记,再在$n/2+1~n$的枚举中
两两配对就行,配对条件有下:
一, 两个集合没有交集
二,两个集合的并集不空
三,两个集合的并集未被标记。
然后就完了
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,m[22],ans,tot;
4 map<int,int>vis;
5 vector<int>S[1100000];
6 bool vv[1100000];
7 inline void dfs(int x,int sta,int l,int r){
8 if(x>n/2){
9 if(!vis[l-r]) vis[l-r]=++tot;
10 int now=vis[l-r]; S[now].push_back(sta);
11 return;
12 }
13 dfs(x+1,sta,l,r);
14 dfs(x+1,sta|(1<<x-1),l+m[x],r);
15 dfs(x+1,sta|(1<<x-1),l,r+m[x]);
16 }
17 inline void sfd(int x,int sta,int l,int r){
18 if(x>n){
19 if(vis.find(r-l)==vis.end()) return;
20 int now=vis[r-l];
21 for(int i=0;i<S[now].size();i++){
22 if(sta&S[now][i]) continue;
23 if(!(sta|S[now][i])) continue;
24 if(vv[sta|S[now][i]]) continue;
25 vv[sta|S[now][i]]=1; ++ans;
26 }
27 return;
28 }
29 sfd(x+1,sta,l,r);
30 sfd(x+1,sta|(1<<x-1),l+m[x],r);
31 sfd(x+1,sta|(1<<x-1),l,r+m[x]);
32 }
33 namespace WSN{
34 inline short main(){
35 scanf("%d",&n);
36 for(int i=1;i<=n;i++) scanf("%d",&m[i]);
37 dfs(1,0,0,0); sfd(n/2+1,0,0,0);
38 printf("%d\n",ans);
39 return 0;
40 }
41 }
42 signed main(){return WSN::main();}
T2 毛二琛
考场上努力思考正解,可是忒弱想不到,
无奈之下甩出一手$\textit{Next Permutation}$(还是按照当时终端给出的编译信息自学的,乐死)
当时还想着可能是数学,不过是我想多了
关于如何从升序排列的连续数字变为给定数列,只需考虑每个位置不同的元素应向左/右移动
然后还有先后次序,且牵连改变,这样
我们记录$pos_i$表示$i$元素在给定序列里的位置,这样就可以知道升序数列中的那个$i$元素如何移动
我们给他打上标记,同时,为了让他移动的数字打上相反标记表示作出牺牲让$i$移动,这些元素是一段区间
$i~pos_i$(当$i<pos_i$时,另一种相反)
这样预处理完之后,就可以进行$dp$,$dp_{i,j}$表示给定序列前$i$个位置,第$i$号元素排名为$j$的方案
我们发现,当$i$元素应向右移动时,他的转移是他后面的$dp_{i-1,j}$的加和
反之是前面的$dp_{i-1,j}$的加和,这样单纯转移是$O(n^3)$的
处理出一个前缀和数组记录前缀即可优化到$O(n^2)$,可过
1 #include<bits/stdc++.h>
2 #define zuo (1)
3 #define you (2)
4 using namespace std;
5 const int NN=5005,mod=1e9+7;
6 int n,a[NN],pos[NN],tot,ans,biao[NN],dp[NN][NN],sum[NN][NN];
7 namespace WSN{
8 inline short main(){
9 scanf("%d",&n);
10 for(int i=1;i<=n;i++) scanf("%d",&a[i]),++a[i],pos[a[i]]=i;
11 for(int i=1;i<=n;i++){
12 if(pos[i]==i){puts("0");return 0;}
13 if(pos[i]<i){biao[i]=zuo;for(int j=pos[i]+1;j<i;j++) biao[j]=you;}
14 if(pos[i]>i){biao[i]=you;for(int j=i+1;j<pos[i];j++) biao[j]=zuo;}
15 }
16 dp[1][1]=sum[1][1]=1;
17 for(int i=2;i<=n;i++)
18 for(int j=1;j<=i;j++){
19 if(biao[i]==you) dp[i][j]=(sum[i-1][i-1]-sum[i-1][j-1]+mod)%mod;
20 if(biao[i]==zuo) dp[i][j]=sum[i-1][j-1];
21 sum[i][j]=(sum[i][j-1]+dp[i][j])%mod;
22 }
23 printf("%d\n",sum[n-1][n-1]);
24 return 0;
25 }
26 }
27 signed main(){return WSN::main();}
T3 毛三琛
复杂度玄学。。。。。。
就是暴力枚举$x$,然后生成新的物品质量,然后二分$check$
然而我们发现,只是这样肯定是过不了的。。。。。
它稳稳的T掉了。。。。
我们需要一步剪枝,他就可以
就是在每次进行真正的二分前对生成的序列进行目前的最优答案$check$,如果目前最优的答案判断不成功,直接跳过就好
正确性显然
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,mod,k,a[10005],wsn=0x7fffffff,b[10005],l,r,ans;
4 inline bool check(int mid,int x){
5 int tmp=0,num=1;
6 for(register int i=1;i<=n&&num<=k;++i){
7 int shu=(a[i]+x)%mod; if(shu>mid) return 0;
8 tmp+shu>mid ? (++num,tmp=shu):(tmp+=shu);
9 } return num<=k;
10 }
11 namespace WSN{
12 inline short main(){
13 scanf("%d%d%d",&n,&mod,&k);
14 for(register int i=1;i<=n;++i) scanf("%d",&a[i]);
15 for(register int x=0;x<mod;++x){
16 if(!check(wsn,x)) continue;
17 l=0,r=wsn; while(l<=r){
18 int mid=l+r>>1;check(mid,x)? (r=mid-1,ans=mid):(l=mid+1);
19 }wsn=min(wsn,ans);
20 }printf("%d\n",wsn);
21 return 0;
22 }
23 }
24 signed main(){return WSN::main();}
最后,附上今天更新的电脑屏幕的壁纸,比较帅。。。。。。
$\textit{Dark Lao: MYC Orz Orz}$
$\textit{Dark Lao: MYC Orz Orz}$
$\textit{Dark Lao: MYC Orz Orz}$
最新文章
- 关于安装AccessDatabaseEngine_x64.exe 的说明
- 北大poj-1011
- java server
- 没人告诉你关于z-index的一些事
- python - socket - server
- JavaWeb前端: JavaScript 简介
- window8配置IIS,搭建应用程序网站。
- HDU4276 The Ghost Blows Light SPFA&;&;树dp
- Oracle的实例占用内存调整
- knn分类算法学习
- centos7服务的管理
- spring boot2.0.4集成druid,用jmeter并发测试工具调用接口,druid查看监控的结果
- SpringBoot配置ActiveMQ
- OSGI命令
- diskcache
- Selenium自动化测试Python六:持续集成
- 简单的Java串口通讯应答示例
- 【柚子木字幕組】【BBC】 Are Our Kids Tough Enough? Chinese School 英國的孩子足夠堅強嗎?中式教學
- 项目管理---git----遇到问题------.gitignore不起作用
- WPF自定义代码启动应用程序启动方式
热门文章
- 【第十篇】- Git 远程仓库(Github)之Spring Cloud直播商城 b2b2c电子商务技术总结
- Java之SpringBoot自定义配置与整合Druid
- javascript / PHP [Design Patterns - Facade Pattern]
- django使用restframework序列化查询集合(querryset)
- django url配置-反向解析-视图函数-HttpRequest对象-HttpResponse对象-cookies-session-redis缓存session
- 鸿蒙内核源码分析(进程镜像篇)|ELF是如何被加载运行的? | 百篇博客分析OpenHarmony源码 | v56.01
- P4233-射命丸文的笔记【NTT,多项式求逆】
- Notepad++离线安装使用Markdown插件
- Python异常代码含义对照表
- redis学习笔记-01 string类型命令