[考试反思]0918csp-s模拟测试46:残存
我。。。
行吧大概说说。
T1打的n2dp,什么随机化什么改变读入顺序都能AC。
没想优化。打了个链表优化dp。不知为何WA了。
T2读错题,死了。
T3的50分暴力没来得及优化感觉思路很神仙(然而并没有特别神仙)
打了3个对拍,T1还是一个spj对拍。然后各种AC。。。
T2读错了题对拍显然也是错的。。
呃啊。。。
T2子任务测试点放错了,然后这次要重测。
每次重测的题我都爆零(3次了),每次数据出锅导致我丢AC的都没有重测(2次)。
Update:这次重测我的0分读错题代码变成了10分!!!
T1:Set
我曾经在想鸽巢原理会怎么考。
这题挺好的,出题人的想法很好,但是他并没有尝试去卡那些乱搞的人。
为什么模数是n呢。。。肯定有值得利用的地方。
因为一共有n+1个位置的前缀和的值,而只有n种不同的取值。
那么一定有重复的值,那么对应的两个位置做差就能被整除,所以这一段区间就是合法的。
思路很棒!
#include<cstdio>
int n,x[],lst[],sum;
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%d",&x[i]);
lst[]=;
for(int i=;i<=n;++i){
sum=(sum+x[i])%n;
if(lst[sum]){printf("%d\n",i-lst[sum]+);for(int j=lst[sum];j<=i;++j)printf("%d ",j);return ;}
lst[sum]=i+;
}
}
思路积累:
- 鸽巢原理
- 前缀和同余等价于区间和整除
T2:Read
书是可以换顺序的啊。。。。
卡空间的情况下求众数出现次数是否大于一半。
先求出现最多的数。
那么出现这个数就是目前位置次数最多的就cnt++,否则--,cnt=0时更新这个值。
这样的话如果它的数量超过一半的话就一定会有盈余。
所以你最后记录下的数要么就是出现了超过一半次数的数(众数),要么就是一个没有意义的数。
再跑一遍,判断这个数出现了几次就好了。
#include<cstdio>
int m,k,c[],X[],Y[],Z[],ans,id=,cnt,tms,N;long long lst;
int main(){
scanf("%d%d",&m,&k);const int K=(<<k)-;
for(int i=;i<=m;++i)scanf("%d",&c[i]),N+=c[i];
for(int i=;i<=m;++i)scanf("%d",&X[i]);
for(int i=;i<=m;++i)scanf("%d",&Y[i]);
for(int i=;i<=m;++i)scanf("%d",&Z[i]);
for(int i=;i<=m;++i){
lst=X[i];
if(!cnt)id=lst,cnt++;else if(lst==id)cnt++;else cnt--;
for(int j=;j<=c[i];++j){
lst=(lst*Y[i]+Z[i])&K;
if(!cnt)id=lst,cnt++;else if(lst==id)cnt++;else cnt--;
}
}
for(int i=;i<=m;++i){
lst=X[i];tms+=lst==id;
for(int j=;j<=c[i];++j)lst=(lst*Y[i]+Z[i])&K,tms+=lst==id;
}
if(tms>N-tms-)printf("%d\n",tms-(N-tms)-);else puts("");
}
思路积累:
- 模拟法求众数?
- hash_map。(非正解)
T3:Race
遇到异或容易想到trie。
可以发现,建出trie后,对于一个特定的数,我们把它的路径上的兄弟节点(m个)的权值记下来。
设为st数组,那么其含义就是在一半的场次中,有st[i]个人的数同时比他大。(研究一下二进制然后看看trie就明白了)
而st的每一位是自由组合的。
暴力就是跑一边背包,记录每种排名的方案数,st就相当与物品,最后把排名与最终得分相乘。
但是我们并没有利用题目中平方的性质。
那个式子其实就是$ \sum (st[i]+st[j]+st[k]+...+st[p])^2 $
st在一半的情况中会出现在和式里。
那么对于特定的i在一半的和式里会出现项$ st[i]^2 $
对于特定的i和j,在一半的一半即1/4的情况里会同时在和式里出现,它们的贡献就是$ 2\times st[i] \times st[j] $
可以再合并合并式子也可以就此打住。
反正把上面的答案加起来(可以m2枚举,也可以前缀和优化到m)之后乘上总方案数就是了。
总方案数不要用快速幂,kxT90了(我也感觉不正常),直接左移就行了啊。。。
代码实现极其简单。
#include<cstdio>
#define mod 1000000007
int t[][],w[],n,cnt,st[],m,x[],rt,tot;
void insert(int &p,int num,int al){
if(!p)p=++cnt;
w[p]++;
if(al==-)return;
insert(t[p][(num&<<al)?:],num,al-);
}
void ask(int p,int num,int al){
if(al==-)return;
st[al]=w[t[p][(num&<<al)?:]];
ask(t[p][(num&<<al)?:],num,al-);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)scanf("%d",&x[i]),insert(rt,x[i],m-);
for(int i=;i<=n;++i){
ask(rt,x[i],m-);
long long ans=;
for(int i=;i<m;++i)for(int j=i;j<m;++j)ans=(ans+1ll*st[i]*st[j])%mod;
(ans<<=m-)%=mod;
tot^=ans;
}printf("%d\n",tot);
}
思路积累:
- 二进制与trie
- 平方式的特点:拆开后每一项都是2次所以枚举是n2的
- 卡常是一种习惯:用位运算
最新文章
- sujection重构
- 如何解决Selenium中"Cannot find function addEventListener in object [object HTMLDocument]"的错误
- Parameter index out of range (2 >; number of parameters, which is 1)
- vs2010配置boost编程环境(照抄并简化)
- 18.中介者模式(Mediator Pattern)
- EntityFramework Code First 添加唯一键
- ios游戏开发--cocos2d学习(2)
- Schtasks 命令详解
- 初学redux笔记,及一个最简单的redux实例
- rpm包制作
- POJ 3111 K Best(最大化平均值)
- layoutSubview触发时机
- mybatis注解@Param对JavaBean的作用
- Nagios监控配置文件及监控流程
- SQL问题+知识点总结总
- bootstrapTable使用场景及方式
- Windows下Apache服务器搭建
- Android进阶AIDL - 2018年4月14日
- Android学习路-UI控件
- Oozie-自定义实现WorkFlow中shell action
热门文章
- centos7.x 部署主、从DNS服务器
- WebSocket协议与抓包
- [Swoole] 在Ubuntu下安装、快速开始
- 引入flask_cache时出现ModuleNotFoundError: No module named &#39;flask.ext&#39;
- 第一天 hello world 启程
- DataStructure之线性表以及其实现
- SQLMAP SSI注入错误解决
- 单调队列与DP
- [LUOGU3413] SAC#1 - 萌数
- opencv::凸包-Convex Hull