- 2024-08-162024年7月上海月赛乙组
幂的运算题目:给定a,b,c,求\(a^{b}\)modc。分析:快速幂板子题代码:#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+10;longlongn,m,k;longlongksm(longlonga,longlongb,longlongp){ longlongans=1; while(b){ if(b&1)
- 2024-08-02上海计算机学会2022年5月月赛C++乙组T3狼人游戏(二)
狼人游戏(二)内存限制: 256 Mb时间限制: 1000 ms题目描述有 n 名玩家在玩狼人游戏,有一些玩家的身份是狼人。其余玩家的身份是预言家。游戏的进程中,陆续出现了 m 句发言,每句发言来自于某个玩家,发言的信息是声称另一个玩家的身份是狼人或者是预言家。小爱猜想,狼人的发
- 2023-08-21YACS 2023年8月月赛 乙组 T3 香槟塔 题解
题目链接乙组中比较好的一道思维题。首先考虑暴力,如果没满就倒满了就往下继续倒,直到倒完或溢出为止,但如果开始就全满然后每次都从最上面倒那么$O(n^2)$就超时了。我们希望找到一个数据结构(当然不是也行)能够快速得到从某个位置向下(包括当前位置)第一个没满的香槟塔,显然并查集。
- 2023-08-21YACS 2023年8月月赛 乙组 T1 最长回文 题解
题目链接小清新的区间DP题。看到数据范围以及回文一眼盯真得到是区间DP。设$f[i][j]$为区间$[i,j]$成为回文串最少要经过几次操作,转移一个个看。首先可以删掉第$j$个,$f[i][j]=\min(f[i][j],f[i][j-1]+1)$,同理也可以删掉第$i$个,$f[i][j]=\min(f[i][j],f[i+1][j]+1)$
- 2023-08-21YACS 2023年6月月赛 乙组 T3 工作安排 题解
这道题是乙组里比较新奇的一题,本来一眼看下来不会,后来蒙了个按照单位时间内收到罚款排序居然对了,十分意外。简单的证明一下:假设有两个工作,时间分别为$t_1$$f_1$$t_2$$f_2$,假设把第一个放在前面更优,前面的罚款不变。则有$t_1\timesf_1+(t_1+t_2)\timesf_2<t_2\timesf_2+(
- 2023-08-09YACS2023年6月乙组
T1:两数归零\(a_i+a_j=0\Leftrightarrowa_j=-a_i\),用std::map<int,int>来统计即可代码实现#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<(n);++i)usingnamespacestd;usingll=longlong;intmain(){intn;cin&
- 2023-08-09YACS2023年7月乙组
T1:树的计数注意到,深度为\(2\)的点一定是深度为\(1\)的点的儿子节点,深度为\(3\)的点一定是深度为\(2\)的点的儿子节点.....那么深度为\(i\)的点可以是深度为\(i-1\)的儿子节点,对于此题是一个经典的分步乘法计数原理,把深度为\(2\)的儿子节点确定下来是第一步,深度为
- 2023-04-11YACS2022年10月乙组
T1:录制节目可以将原题转化成有\(n\)条线段,可以保留若干条线段,并且可以分成两部分,使得每部分的线段互不相交先将所有线段按右端点做升序排序,且按左端点做降序排序然后维护两个变量last1和last2last1:第一个部分的最后的端点last2:第二个部分的最后的端点尽量让\(\min(
- 2023-02-23YACS2023年2月乙组
T3:最大子集本题是01背包的变种题记dp[i]表示选到的奶牛的智商总和为\(i\)时对应的情商总和的最大值这里由于\(x\)可能是负数,所以需要将\(i\)向后偏移\(3e5\)
- 2023-02-17YACS 2023年1月月赛 乙组 T4 加与乘(二) 题解
题目链接应大家的要求,早上起来更一下乙组T4。这一道题目我们发现不仅会加元素了,还会重复执行任务。很容易想到用两个树状数组来维护每个任务的执行次数,以及每个单元格
- 2023-02-02YACS2023年1月乙组
T1:无限延展见P3612[USACO17JAN]SecretCowCodeS代码实现#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;intmain(){ strings;llk;
- 2023-01-12 YACS 2022年12月月赛 乙组 T1 拼接单词 题解
一道结论题,代码相当的短。我们先来考虑会拼出重复的情况:那必定是第一个字符串里有一个$a$(其他的也行),第二个也有一个$a$。那么我们就可以选择拿第一个字符串$a$前面的
- 2023-01-12YACS 2022年12月月赛 乙组 T2 八进制小数 题解
纪念一下,两件事。$1.$打$YACS$一年了,时间过得好快啊。$2.$第一次$AK$乙组。高精板子。$8$进制转十进制,很简单。小数部分第一位的数字乘上$8^{-1}$,第二位就乘上
- 2022-12-03YACS 2022年11月月赛 乙组 T3 菜单设计 题解
题目链接上完编程课回来的深夜,更一篇吧。这一题一看数据范围$:18$,阶乘暴力打不了,就是状压。其实我还是比较喜欢状压的,不过这几个月怎么这么多状压?首先:设计状态不难发
- 2022-11-22YACS 2022年11月月赛 乙组 T1 数对统计 题解
好久没更了,闲话一句,我的初赛成绩只有$71.5$,$76$才能进$NOIP$,所以就更一篇吧首先先考虑暴力算法,枚举两个数,设这两个数为$x$和$y$,如果$f[x][y]=false$,那就标记为$t
- 2022-11-02YACS2021年7月乙组
T1:牛奶供应(三)站在提前生产的角度来思考,为了缩小总成本,如果某天足够便宜就多生产一些牛奶。但这样的想法会遇到一个困难,也就是现在生产牛奶到底要生产多少箱,它是由之后的若
- 2022-10-11YACS2022年9月乙组
T1:区间交集(二)这种统计有多少对满足题意,首先想下暴力\(O(n^2)\)复杂度正解:判断区间是否有交集,其实比较麻烦,怎么简单判断?如果已知左端点的大小顺序,那么判断是否有交集
- 2022-08-212020年9月乙组 最大圆弧
首先,如果将题目的“圆环”改成“数组”,相信大家都会做,就是如下intsum=0,maxn=0;//sum更新最大值for(inti=1;i<=n;i++){ scanf("%d",&a); if(sum<0)sum=0;//