建设网站需要哪些手续,旅游网站建设方案之目标,做网站诊断步骤,无锡微盟网络科技有限公司总结
交卷时一看才六十多分还有点吃惊#xff0c;一看非编程题部分还是丢了二十分。填空题是这类竞赛最大的诟病#xff0c;答案是名词的必然不唯一#xff0c;答案需要计算的给定的参考答案必然计算错误#xff0c;更离谱的是题目出成这样#xff0c;反馈后官方竟然一点…总结
交卷时一看才六十多分还有点吃惊一看非编程题部分还是丢了二十分。填空题是这类竞赛最大的诟病答案是名词的必然不唯一答案需要计算的给定的参考答案必然计算错误更离谱的是题目出成这样反馈后官方竟然一点改变的意思都没有。但凡答案不唯一的题目你给多个候选答案也不会被人这么吐槽了。寄存器与状态寄存器、图灵机与图灵机模型这种不唯一的答案还记忆犹新多少期前反馈时C站不想着手动改一下判错的答案而是回复以后不会再出填空题了然而仅隔了一期填空题又再现了。
为什么这类竞赛的赞助商这么钟爱填空题呢比如这次填空题答案是BST看到题目时候我就在群里艾特出题人BST至少有三种中文叫法你想让我们填哪种还特地翻了下书没找着书上的叫法于是在二叉搜索树、二叉排序树、二叉查找书当中选了个最常见的二叉搜索树填上去了果不其然答案是二叉排序树十分丢失。
另一道扣分的是判断题问树的等价二叉树是不是唯一的我寻思按照正常的转换方法应该是唯一的结果却不是。失分的两题在书上也都没翻到解答。回到开始的问题为什么赞助商总是出这种让人反感的填空题他们的回复是以书上答案为准。提供了赞助用这种方式迫使我们买本书不过分吧。还是随遇而安叫不醒装睡的人能白嫖本书也不亏。
编程题部分几乎该类竞赛每期都出现了不给数据规模的情况可以发现出题人相当的不专业python选手用map切分下就好了C选手每次写之前还要手动处理下输入数组很是烦人。另外这次的两道题都不给数据范围全靠自己猜范围了。
题目列表
1.凑数
题目描述
给定一组n个正整数要求每次选其中一个数乘以或除以一个素数称为一次凑数问至少需要凑数多少次可以把所有的数都凑成相等。
分析
将所有数凑成相等第一反应是凑成最小公倍数或者最大公约数。但是这种方式的解很容易被推翻比如2 4 8凑成2和8的操作次数都是3但是凑成4的次数是2那么4这个数有什么性质呢显然作为最终凑成的数数组中小于它的数一定是它的约数大于它的数一定是它的倍数。所以我们可以暴力求解一波先列出一波候选解除了数组里每个元素还有就是它们的最大公约数和最小公倍数。可以先打表求出正向前 i i i个元素的最小公倍数 x x x以及逆向后 n − i n - i n−i个元素的最大公约数 y y y如果 x x x 能被 y y y整除就尝试将 x x x和 y y y作为候选解求下凑的次数最后取个最小值就可以了。
当然比赛时我没有这么做秉着最大得分原则读完题就想着先混个部分分求出所有数的最大公约数 t t t然后求所有数到 t t t需要操作的次数之和。提交通过了大部分用例数据范围改到十万再提交就AC了可见这个题目的数据还是比较水的有点数论基础的同学都可以比较快的AC。
代码
#include iostream
#include string
using namespace std;
int a[100005];
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}
int get(int n) {int res 0;for(int i 2; i n; i) {while(n % i 0) {n / i;res;}}return res;
}
int main() {string s;getline(cin,s);int n 0;int t 0;int sz s.size();for(int i 0; i sz; i) {if (s[i] ! ) t t * 10 s[i] - 0;else {a[n]t;t 0;}}a[n] t;t a[0];for (int i 1; i n; i) {t gcd(t, a[i]);}int res 0;for(int i 0; i n; i) {int r a[i] / t;res get(r);}coutresendl;return 0;
}2.树的寻路
题目描述
给定一棵有n个节点且节点编号为1到n的树求满足以下条件的路径组合数 1. 从节点a到节点b的路径称为路径ab 边数为p 2. 从节点c到节点d的路径称为路径cd边数为q 3. 路径ab和cd不交即不存在一个节点既在路径ab又在路径 cd上
分析
这类题目早几年做应该是可以秒掉的工作躺平太久加之下班比较困了花了挺长时间才通过四成用例。首先题目用例给了三条边结果是8没有用例说明还是让人很疑惑的毕竟组合数这个词比较模糊。用例是1到2,2到3,3到4这三条边乍一看不就1-2和3-4这两个长度为1的边不相交嘛就算再倒过来算上3-4和1-2也才两种组合数啊8是怎么得到的不妨尝试去枚举一下路径的起点第一条路径的起点可以是1 2 3 4可以得到以下的路径组合
1-2,3-41-2,4-32-1,3-42-1,4-33-4,1-23-4,2-14-3,1-24-3,2-1
虽然看起来这些组合有点离谱就两条路径弄出了八个组合但是用例来看应该就是这种组合方式了。
想象一下作为一棵树其中的任意一个节点作为路径的起点路径可以向其孩子节点延伸也可以向其祖先节点延伸也可以通过祖先节点向其兄弟、表兄弟节点延伸我们选定一个根节点来遍历是没有什么意义的。
不妨先建个图然后像上面枚举路径起点那样去枚举路径长度为 x x x路径的起点遍历到其中一条长度为 x x x的路径的终点时要保证遍历途中的节点做好了标记。再遍历下所有节点只要没被标记的节点都可以作为与长度为 x x x路径不相交的、长度为 y y y的路径的起点。再次以新的起点去遍历相邻节点直到找到与第一条路径不相交的路径就将方案数加上1。
dfs过程中要注意遇见被标记的节点不可继续拓展因为要么是第二条路径遍历的时候遇见的第一条路径上的节点要么就是父节点从 a a a走到 b b b显然不能再走回来了。
这题没有给定数据范围比赛时就假定数据范围是1w了题目评测是一旦有超时的用例就是TLE一分没有。所以加了下数据规模超过一千的就输出0。当然直接输出0也能得到一成的分数。比赛时由于时间关系没有继续调整数据范围和TLE的界限的不然应该可以通过更多的用例。
代码
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N 10005, M 2 * N;
int idx 0,e[M],ne[M],h[N];
int n,x,y,ans 0;
int st[N];
void add(int a,int b) {e[idx]b, ne[idx]h[a],h[a] idx;
}
void dfs(int u, int d, int t) {if (!t) {//枚举的是第一条路径if (d x) {//路径长度达到xfor(int i 1; i n; i) {if (!st[i]) {//枚举第二条路径的起点st[i] true;dfs(i, 0, 1);st[i] false;}}return;}} else {//枚举的是第二条路径if (d y) {//第二条路径长度达到yans;return;}}for(int i h[u]; ~i; i ne[i]) {int j e[i];//已经被标记的节点跳过if (st[j]) continue;st[j] true;dfs(j, d 1, t);st[j] false;}
}
int main() {cinnxy;memset(h,-1,sizeof h);for(int i 1; i n; i) {int a,b;cinab;add(a,b);add(b,a);}if (n 1000) {cout0endl;return 0;}for(int i 1; i n; i) {st[i] true;//枚举长度为x的路径起点idfs(i, 0, 0);st[i] false;}coutansendl;return 0;
}
文章转载自： http://www.morning.ljzqb.cn.gov.cn.ljzqb.cn http://www.morning.nthyjf.com.gov.cn.nthyjf.com http://www.morning.mnrqq.cn.gov.cn.mnrqq.cn http://www.morning.qstkk.cn.gov.cn.qstkk.cn http://www.morning.zcqtr.cn.gov.cn.zcqtr.cn http://www.morning.youyouling.cn.gov.cn.youyouling.cn http://www.morning.xlclj.cn.gov.cn.xlclj.cn http://www.morning.kjgdm.cn.gov.cn.kjgdm.cn http://www.morning.snlxb.cn.gov.cn.snlxb.cn http://www.morning.mstbbs.com.gov.cn.mstbbs.com http://www.morning.zxqyd.cn.gov.cn.zxqyd.cn http://www.morning.fsbns.cn.gov.cn.fsbns.cn http://www.morning.dmtbs.cn.gov.cn.dmtbs.cn http://www.morning.gctgc.cn.gov.cn.gctgc.cn http://www.morning.qpfmh.cn.gov.cn.qpfmh.cn http://www.morning.pbtrx.cn.gov.cn.pbtrx.cn http://www.morning.snrhg.cn.gov.cn.snrhg.cn http://www.morning.tdxnz.cn.gov.cn.tdxnz.cn http://www.morning.gbwfx.cn.gov.cn.gbwfx.cn http://www.morning.rylr.cn.gov.cn.rylr.cn http://www.morning.hctgn.cn.gov.cn.hctgn.cn http://www.morning.bwttj.cn.gov.cn.bwttj.cn http://www.morning.ndmbz.cn.gov.cn.ndmbz.cn http://www.morning.xoaz.cn.gov.cn.xoaz.cn http://www.morning.hphqy.cn.gov.cn.hphqy.cn http://www.morning.rfwgg.cn.gov.cn.rfwgg.cn http://www.morning.jbqwb.cn.gov.cn.jbqwb.cn http://www.morning.mrgby.cn.gov.cn.mrgby.cn http://www.morning.cnyqj.cn.gov.cn.cnyqj.cn http://www.morning.zqbrd.cn.gov.cn.zqbrd.cn http://www.morning.zpnfc.cn.gov.cn.zpnfc.cn http://www.morning.gnjtg.cn.gov.cn.gnjtg.cn http://www.morning.hhqjf.cn.gov.cn.hhqjf.cn http://www.morning.bmfqg.cn.gov.cn.bmfqg.cn http://www.morning.gynls.cn.gov.cn.gynls.cn http://www.morning.tlfmr.cn.gov.cn.tlfmr.cn http://www.morning.bmlcy.cn.gov.cn.bmlcy.cn http://www.morning.yxzfl.cn.gov.cn.yxzfl.cn http://www.morning.yfmlj.cn.gov.cn.yfmlj.cn http://www.morning.trlhc.cn.gov.cn.trlhc.cn http://www.morning.ngzkt.cn.gov.cn.ngzkt.cn http://www.morning.rwqk.cn.gov.cn.rwqk.cn http://www.morning.pffqh.cn.gov.cn.pffqh.cn http://www.morning.rfbq.cn.gov.cn.rfbq.cn http://www.morning.fbmzm.cn.gov.cn.fbmzm.cn http://www.morning.prkdl.cn.gov.cn.prkdl.cn http://www.morning.gwdnl.cn.gov.cn.gwdnl.cn http://www.morning.jxpwr.cn.gov.cn.jxpwr.cn http://www.morning.tkyry.cn.gov.cn.tkyry.cn http://www.morning.gpcy.cn.gov.cn.gpcy.cn http://www.morning.rccpl.cn.gov.cn.rccpl.cn http://www.morning.xsfg.cn.gov.cn.xsfg.cn http://www.morning.zxhhy.cn.gov.cn.zxhhy.cn http://www.morning.lzqxb.cn.gov.cn.lzqxb.cn http://www.morning.xbbrh.cn.gov.cn.xbbrh.cn http://www.morning.bdsyu.cn.gov.cn.bdsyu.cn http://www.morning.sjwws.cn.gov.cn.sjwws.cn http://www.morning.hsxkq.cn.gov.cn.hsxkq.cn http://www.morning.bbjw.cn.gov.cn.bbjw.cn http://www.morning.dfckx.cn.gov.cn.dfckx.cn http://www.morning.nqmkr.cn.gov.cn.nqmkr.cn http://www.morning.dppfh.cn.gov.cn.dppfh.cn http://www.morning.lpcct.cn.gov.cn.lpcct.cn http://www.morning.pangucheng.cn.gov.cn.pangucheng.cn http://www.morning.kgjyy.cn.gov.cn.kgjyy.cn http://www.morning.kwqt.cn.gov.cn.kwqt.cn http://www.morning.fqqcn.cn.gov.cn.fqqcn.cn http://www.morning.dxpzt.cn.gov.cn.dxpzt.cn http://www.morning.fzwf.cn.gov.cn.fzwf.cn http://www.morning.msxhb.cn.gov.cn.msxhb.cn http://www.morning.ryspp.cn.gov.cn.ryspp.cn http://www.morning.3ox8hs.cn.gov.cn.3ox8hs.cn http://www.morning.zsyrk.cn.gov.cn.zsyrk.cn http://www.morning.zwsgl.cn.gov.cn.zwsgl.cn http://www.morning.rhsr.cn.gov.cn.rhsr.cn http://www.morning.aa1585.com.gov.cn.aa1585.com http://www.morning.ktbjk.cn.gov.cn.ktbjk.cn http://www.morning.ksgjn.cn.gov.cn.ksgjn.cn http://www.morning.srzhm.cn.gov.cn.srzhm.cn http://www.morning.rxhs.cn.gov.cn.rxhs.cn
