CSP-J题目总结(退役博客)

总感觉时间过得好快,初三比完赛信息马上就要告一段落了。

T1:水题。但我还是检查了好几遍文件读写(由于我最近模拟赛的文件读写连错)。

T2:一道要用队列优化的模拟,一开始还以为跟海港一样,还好后来的样例比较良心,让我这个不认真看题的发现漏洞。顺利的就过了大数据。

吸取了去年的经验,我T1T2花了1个多小时。

T3:考试的时候一眼看出DP,但是看到一堆变量就不想推了,索性连贪心都不打(那时候好像忘了有这东西了。。。)傻傻地扔了个空代码上去。。。

T4:我磕了2个小时的正解(显然学长发言都没听),找出了大部分规律——最短路+判断回环,但细节处理不好,民间数据也才30。。。

总结:T1T2AC了,吸取了去年的教训,但时间安排不妥当。省一也由于T3T4(乱打一通)不是很稳。

CSP-J题目总结(退役博客)

不得不说时间过得快呀,转眼就要面对中考了,只能暂时跟信息说Bye了。

T1:一如既往的水题,比去年还水,长度都规定好了,没AC的可以退组了(手动滑稽)。

T2:典型海港题,要加队列优化,另外可能还要搞点别的东西(比如标记)。考试本来想打队列优化,但是又感觉时间复杂度应该差不多,然后就没打,估计全都是TLE。

T3:对于dp蒟蒻的我来说dp是不可能打的,只能打贪心,反正也不是正解,就不细说了。小样例可以过,大样例就过不了了,希望CCF数据水一点,贪心的数据多一点吧。

T4:第一眼没看懂题目,后面看懂了,就是一层层找关系,看最后一次有没有找到1。这道题良心,20%数据就是为蒟蒻准备的,后面觉得不甘心,就打了个dfs,预计20吧。

总结:省一可能不是很稳,跟去年一样第二题炸裂,希望CCF数据下留人,让我好好退役吧!

Day bb

 

 

第一题  score

这一题只要根据题目所给的公式编写程序就好了。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
<span class="hljs-preprocessor">#<span class="hljs-keyword">include</span>&lt;bits/stdc++.h&gt;</span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">int</span> a,b,c,ans;
<span class="hljs-keyword">int</span> main(){
    freopen(<span class="hljs-string">"score.in"</span>,<span class="hljs-string">"r"</span>,stdin);
    freopen(<span class="hljs-string">"score.out"</span>,<span class="hljs-string">"w"</span>,stdout);
    <span class="hljs-built_in">cin</span>&gt;&gt;a&gt;&gt;b&gt;&gt;c;
    a/=<span class="hljs-number">10</span>;
    b/=<span class="hljs-number">10</span>;
    c/=<span class="hljs-number">10</span>;
    ans=a*<span class="hljs-number">2</span>+b*<span class="hljs-number">3</span>+c*<span class="hljs-number">5</span>;
    <span class="hljs-built_in">cout</span>&lt;&lt;ans&lt;&lt;endl;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}

 

第二题  libarian

图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个
正整数。
每位借书的读者手中有一个需求码,这个需求码也是一个正整数。如果一本书的图
书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。
小 D 刚刚当上图书馆的管理员,她知道图书馆里所有书的图书编码,她请你帮她写
一个程序,对于每一位读者,求出他所需要的书中图书编码最小的那本书,如果没有他
需要的书,请输出 -1 。

这一题就是要拿需求码和图书编码进行对比,如果需求码与图书编码的后半部分或全部一样的话那么这本书就是读者需要的,一边判断一边筛选最小的就好了。需求码用数字再进行取余就好了不需要使用字符。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<span class="hljs-preprocessor">#<span class="hljs-keyword">include</span>&lt;bits/stdc++.h&gt;</span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">int</span> n,q,c[<span class="hljs-number">1010</span>],m,w,b,p,ans;
<span class="hljs-keyword">int</span> main(){
    freopen(<span class="hljs-string">"librarian.in"</span>,<span class="hljs-string">"r"</span>,stdin);
    freopen(<span class="hljs-string">"librarian.out"</span>,<span class="hljs-string">"w"</span>,stdout);
    <span class="hljs-built_in">cin</span>&gt;&gt;n&gt;&gt;q;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;++i)
        <span class="hljs-built_in">cin</span>&gt;&gt;c[i];
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=q;++i){
        <span class="hljs-built_in">cin</span>&gt;&gt;m&gt;&gt;w;
        b=<span class="hljs-number">10</span>;
        p=<span class="hljs-number">0</span>;
        ans=<span class="hljs-number">10000001</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">1</span>;j&lt;m;++j)
            b*=<span class="hljs-number">10</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">1</span>;j&lt;=n;++j){
            <span class="hljs-keyword">if</span>(c[j]%b==w&amp;&amp;c[j]&lt;ans){
                ans=c[j];
                p=<span class="hljs-number">1</span>;
            }
        }
        <span class="hljs-keyword">if</span>(p) <span class="hljs-built_in">cout</span>&lt;&lt;ans&lt;&lt;endl;
        <span class="hljs-keyword">else</span>  <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">"-1"</span>&lt;&lt;endl;
    }
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}

第三题  chess

有一个m × m的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在
要从棋盘的最左上角走到棋盘的最右下角。任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的),你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时,如果两个格子的颜色相同,那你不需要花费金币;如果不同,则你需要花费 1 个金币。另外,你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用,而且这个魔法的持续时间很短,也就是说,如果你使用了这个魔法,走到了这个暂时有颜色的格子上,你就不能继续使用魔法;只有当你离开这个位置,走到一个本来就有颜色的格子上的时候,你才能继续使用这个魔法,而当你离开了这个位置(施展魔法使得变为有颜色的格子)时,这个格子恢复为无色。现在你要从棋盘的最左上角,走到棋盘的最右下角,求花费的最少金币是多少?

这道题要用到深搜,代码如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
<span class="hljs-preprocessor">#<span class="hljs-keyword">include</span>&lt;bits/stdc++.h&gt;</span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">int</span> fx[<span class="hljs-number">4</span>]={-<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,<span class="hljs-number">1</span>,<span class="hljs-number">0</span>};
<span class="hljs-keyword">int</span> fy[<span class="hljs-number">4</span>]={<span class="hljs-number">0</span>,-<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,<span class="hljs-number">1</span>};
<span class="hljs-keyword">int</span> f[<span class="hljs-number">110</span>][<span class="hljs-number">110</span>];
<span class="hljs-keyword">int</span> mp[<span class="hljs-number">110</span>][<span class="hljs-number">110</span>];
<span class="hljs-keyword">int</span> m,n,ans=<span class="hljs-number">9999999</span>,x,y,c;
<span class="hljs-keyword">void</span> dfs(<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> y,<span class="hljs-keyword">int</span> sum,<span class="hljs-keyword">bool</span> t){
    <span class="hljs-keyword">int</span> xx,yy;
    <span class="hljs-keyword">if</span>(x&lt;<span class="hljs-number">1</span>||y&lt;<span class="hljs-number">1</span>||x&gt;m||y&gt;m) <span class="hljs-keyword">return</span>;
    <span class="hljs-keyword">if</span>(sum&gt;=f[x][y]) <span class="hljs-keyword">return</span>;
    f[x][y]=sum;
    <span class="hljs-keyword">if</span>(x==m&amp;&amp;y==m&amp;&amp;sum&lt;ans){
        ans=sum;
        <span class="hljs-keyword">return</span>;
    }
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;<span class="hljs-number">4</span>;++i){
        xx=x+fx[i];
        yy=y+fy[i];
        <span class="hljs-keyword">if</span>(mp[xx][yy]){
            <span class="hljs-keyword">if</span>(mp[xx][yy]==mp[x][y])
                 dfs(xx,yy,sum,<span class="hljs-keyword">false</span>);
            <span class="hljs-keyword">else</span> dfs(xx,yy,sum+<span class="hljs-number">1</span>,<span class="hljs-keyword">false</span>);
        }
        <span class="hljs-keyword">else</span>
            <span class="hljs-keyword">if</span>(!t){
                mp[xx][yy]=mp[x][y];
                dfs(xx,yy,sum+<span class="hljs-number">2</span>,<span class="hljs-keyword">true</span>);
                mp[xx][yy]=<span class="hljs-number">0</span>;
            }
    }
}
<span class="hljs-keyword">int</span> main(){
    freopen(<span class="hljs-string">"chess.in"</span>,<span class="hljs-string">"r"</span>,stdin);
    freopen(<span class="hljs-string">"chess.out"</span>,<span class="hljs-string">"w"</span>,stdout);
    <span class="hljs-built_in">cin</span>&gt;&gt;m&gt;&gt;n;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;++i){
        <span class="hljs-built_in">cin</span>&gt;&gt;x&gt;&gt;y&gt;&gt;c;
        mp[x][y]=c+<span class="hljs-number">1</span>;
    }
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=m;++i)
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">1</span>;j&lt;=n;++j)
            f[i][j]=<span class="hljs-number">9999999</span>;
    dfs(<span class="hljs-number">1</span>,<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,<span class="hljs-keyword">false</span>);
    <span class="hljs-keyword">if</span>(ans==<span class="hljs-number">9999999</span>)
        <span class="hljs-built_in">printf</span>(<span class="hljs-string">"-1"</span>);
    <span class="hljs-keyword">else</span>
        <span class="hljs-built_in">printf</span>(<span class="hljs-string">"%d\n"</span>,ans);
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}

这道题实在不会的话,考试的时候还是可以输出“-1”,骗点分的。

第四题  jump

跳房子,也叫跳飞机,是一种世界性的儿童游戏,也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下:在地面上确定一个起点,然后在起点右侧画 n 个格子,这些格子都在同一条直线上。每个格子内有一个数字(整数),表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳,跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳,依此类推。规则规定:玩家每次都必须跳到当前位置右侧的一个格子内 。玩家可以在任意时刻结束游戏,获得的分数为曾经到达过的格子中的数字之和。现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷,它每次向右弹跳的距离只能为固定的 d。小 R 希望改进他的机器人,如果他花 g 个金币改进他的机器人,那么他的机器人灵活性就能增加 g,但是需要注意的是,每次弹跳的距
离至少为 1。具体而言,当g < d时,他的机器人每次可以选择向右弹跳的距离为 d-g, d-g+1,d-g+2,…,d+g-2,d+g-1,d+g;否则(当g ≥ d时),他的机器人每次可以选择向右弹跳的距离为 1,2,3,…,d+g-2,d+g-1,d+g。现在小 R 希望获得至少 k 分,请问他至少要花多少金币来改造他的机器人 。

这道题还未想出……

20191114

T1成绩
题意:给出作业成绩、小测成绩和期末考试成绩,算总成绩。总成绩=作业成绩×20%+小测成绩×30%+期末考试成绩×50%
考场思路(正解):这貌似没什么好思路的,直接算就好了,为了不用到浮点数,我先乘了20再除以100,类推。

T2图书管理员
题意:有一些编码,是正整数,查询一些需求码(也是正整数)是不是这些编码中一个数的后缀,如果是,输出满足条件最小的一个编码。
考场思路(正解):输入很好,我连位数都用不着算。给编码排序,在每次询问时枚举所有编码,需求码有几位就给编码模10的几次方,若模后
的编码和需求码相等,就直接输出。

T3棋盘
题意:一个棋盘,格子可能是红、黄或无色的。从棋盘的左上角走到最右下角,求最小花费。可以向上、下、左、右四个方向前进。当你从一个
格子走向另一个格子时,如果两个格子的颜色相同,那你不需要花费金币;如果不同,则你需要花费 1 个金币。如果要走到无色的格子,必须花
费两个金币让它变成黄或红的,但走到变色的格子时不能再让其他格子变色。
考场思路(正解):宽搜,每次分情况入队,但是如果在搜索到已经搜索过的点时,如果发现所用金币更少,也要入队,第一次搜到(m, m)时不一
定是答案,必须要搜到队空为止。

T4跳房子
题意:一条直线中有一些格子有分数,一个机器从第0格跳起,每次可以向右跳d格,每花g个金币能让它跳跃一次最小距离为max(1,d-g),最大距
离为d+g。要使机器人至少得到k分,求最少花的金币数。
考场思路:先把所有正数的分数加起来,若小于k就输出-1(竟然没有-1的点?!),前两个测试点n<=10,不错,就从0开始从小到大枚举用g个
金币能不能得k分,暴搜判断是否可以得k分。20分。
修改:把枚举改成二分,把暴搜判断改成DP(如果从第j个点可以跳到第i个点则用f[j]+s[i]更新f[i])。50分。

冲刺11.12

隔天补写。。。。。

T1 sheep

面积恰好为n的、长和宽都是正整数的矩形羊圈,这个羊圈的周长最短要是多少。。。

AC。。。把面积开方,一个一个递减判断。。。简单粗暴。。。

T2 carry

只用技能秀死他。。。。。3个技能,一技能造成物攻值10倍的伤害,二技能造成法强值10倍的伤害,三技能造成物攻值6倍和法强值6倍的伤害。。。

另外的,当她使用3次任意技能后,下一次技能将获得强化。。

!!!!重点是这个任意技能也包括强化后的,所以第四次技能后每使用2次普通技能就可以再用强化后的技能了!!!!!

死在这里。。。竟然还有35分???

强化后,一技能造成物攻值20倍的伤害,二技能造成法强值15倍的伤害,三技能造成攻值9倍和法强值9倍的伤害。。。。简单粗暴。。。

T3 game

4个玩家,牌有"2,3,4,5,6,7,8,9,10,J,Q,K,A"自小到大的点数;黑桃(S),红桃(H),梅花(C),方块(D)的花色,一张牌由一种花色和一种点数组成。。。。

在每一回合中,每个玩家出一张牌,点数最大的牌中最先出牌的人为该轮的赢家,四张牌被置入赢家的弃牌堆中。。。所有回合结束后,每个玩家弃牌堆中的牌独立进行结算。。。。

第一步,玩家拿出所有种类红桃牌各一张和一张黑桃Q,丢弃它们并且给其他玩家各加26分,重复以上过程直到不能作出这个操作。。。一定要种类齐全。。

第二步,一张一张丢弃剩下的牌,如果是红桃则给自己加1分,如果是黑桃Q则给自己加13分,其他牌分数不变。。。所以其他牌就别统计了。。。

求每人的分数。。。

直接模拟,注意样例中有点数为1的牌????要处理掉。。。善于用数组,避免太过冗长。。。。。

T4 plan

听说用二分,但是我不知道如何实现。。。

215分的一天ヾ(・ω・`。)(虽然是隔天补写的。。)

20191112_冲刺DAY4

今天是真的没时间写博客~~~~~~~~~~~

改题改了很久啊——————

①羊圈(sheep)

设长为x,宽为y
xy=n
所以只需要搜索x, y使得xy = n即可
o(n2 )河以过60分
显然,因为x, y到超过Vn时,会重复
所以只需保证x*x<= n,
当n是x倍数时,y= n/x;
o开根n可以过100分
注意要开longlong

我是设一个数l=1,l<r,l++

然后用n不断除以l,统计sum=(s+l)*2

然后不断比较sum的最小值

这样复杂度就最多只有n的一半

two:

这题有点坑

放大招也算是积攒大招3次中的一次

只要把第一次的三个小招做处理就行了

举个例子:小小小大小小大小小大小小大......

把第一个小单独加,再小小大的乘以组数,最后再加上余数就行了


1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
    read();
    scanf("%lld%lld%lld",&n,&a,&b);
    if(n<=3){
        printf("%lld",max(a*10,max(b*10,(a*6)+(b*6)))*n);
        return 0;
    }
    p=n/3;
    if(n%3==0) p--;
    printf("%lld",p*max(a*20,max(b*15,(a*9)+(b*9)))+(n-p)*max(a*10,max(b*10,(a*6)+(b*6))));
return 0;
}

第三第四还没理解透~~~