分类：题解

关于基地校day 4的蒟蒻日常——2019.07.28

Begin

T1总统先生，一路走好！

这题

貌似

好像

要开long long？？

附上代码：

#include<bits/stdc++.h>
using namespace std;
long long n,m,ans,l,r;
int main()
{
freopen("president.in","r",stdin);
freopen("president.out","w",stdout);
scanf("%lld%lld",&n,&m);
ans+=n;
n++;
while(n>=m)
{
l=n%m;
r=n/m;
n=l+r;
ans+=r;
}
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}

 

话说总统喝这么多咖啡真的不会得胃溃疡吗……

T2 圣女

这题真的

纯粹是

闲得慌、、

交了一下

运行时错误

我：（？？？）

T3 睡美人航班 

没做、

不想做、、

T4 占梦人

这题我连题目都没看懂……

今天又是听不懂的一天！！

奶思

然后

哇哦欧拉你真的好棒棒哦

费马好nb哦

哇塞欧几里德好厉害喔

神他妈OI中的数学知识

自行理解

nice

THE END.

关于基地校day 3的懵逼日常——2019.07.27

Start

第一题，Kled 。

在打了半个多小时之后

依旧一脸懵逼……

第二题，Darius。

我也不知道……

第三题，Twisted Fate。

这题我在比赛的时候就没看懂题目意思……

第四题，Pantheon。

我按我的理解balabala打了一堆

然后

比赛的时候交上去55分

后来在学校OJ上交了

一样的代码

就

100了？！

重要的是我在编译器上无论怎么输入

输出都是0？！

我：（一脸懵逼）？？！

总而言之

今天的题

看着就是一脸懵逼……

最后

奉上并查集的三种操作。

三种操作：

1.Init（x）:集合初始化：

father[xi]=xi（或者0）；

每个结点都是一棵独立的树，是该树的代表元素。

2.Find（x）：查找：

查找x所在集合si的代表root[si].

即：查找x所在树的树根结点（代表元素）。

3.Unian（x，y）合并x，y所在的不同集合

p=find（x）;

q=find（y）;

if（p!=q）

father[p]=q;或者father[q]=p;

今天又是没有代码的一天！！

奶思

THE END.

 

关于基地校day 2的打卡——2019.07.26

Begin

今天的第一题，奴隶阿飞的励志人生。

简单来说，不会......

第二题，王老菊教你冰原求生。

奉上某位大佬的代码（我是不会承认我懒得打的）。

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[1001],b[1001],i,j,l,f[1001][1001],t;
int main()
{
freopen("manage.in","r",stdin);
freopen("manage.out","w",stdout);
cin>>n>>m>>k;    //n=工作点数,m=工头数,k=每人管的点数
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=b[i-1]+a[i];    //此工作点（i）及前面工作点人数和
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
for(l=1;l<=k;l++)
{
if(i-l<0)   break;    //工作点
f[i][j]=max(f[i][j],max(f[i-l][j],f[i-l][j-1]+b[i]-b[i-l]     //前i个工作点被j个工头管理的最大人数/*此区间最大人数*/));

}
cout<<f[n][m];
return 0;
}

第三题，王老菊教你当典狱长。

后来听学长讲觉得挺水的，但是比赛的时候就是没打23333。

#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("shlqsh.in","r",stdin);
freopen("shlqsh.out","w",stdout);
int t1,t2,i,ans;
cin>>t1>>t2;
for(int i=1;i<=t2;++i)
{
ans+=(t2/i-(t1-1)/i);
}
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}

核心代码：

ans+=(t2/i-(t1-1)/i);

（这里用一下大佬的解释）

t2/i的循环中的i是在1到t2中有倍数的数；

t1-1/i同理

接下来谈谈释义

以样例（2，6）为例

假设i=1,

1的倍数出现了6次，

即约数为1的数出现了6次

假如i=4，

4的倍数出现了一次，

而6/4=1;

所以还是出现了一次

接着算出2的（同理）

6里面的/i从1到6循环的值/约数全部出现的次数/全部加起来

再减去

2里面的/i从1到6循环的值/约数全部出现的次数/全部加起来

接着算出答案

最后一题，王老菊教你言出法随/当断剑奇侠。

#include<bits/stdc++.h>
using namespace std;
int i,j;
long long sum=1,ans=1e8;
int k[]={0,0,1,2,2,3,4,3,2,3,4,5,6,5,4,3,2,3,4,5,6};
int main()
{
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
int n;
cin>>n;
for(i=1;i<=10;i++)
{
for(j=1;j<=10;j++)
{
sum=sum*i;
if(j==1)
ans=min(ans,abs(n-sum)+k[i]);
else
ans=min(ans,abs(n-sum)+k[i]+1);
}
sum=1;
}
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}

最后，奉上回溯法的框架：

（一）

int search(int k)
{
if(到目的地）
输出解
else
for(int i=1;i<=算符种数；i++)
if(满足条件）
{
保存结果；
search(k+1);
恢复：保存结果之前的状态（回溯）
}

（二）

int Search（int k）

{

for（i=1;i<=算符种数；i++）

if(满足条件）
{
保存结果；

if(到目的地）
输出解；

else

search(k+1);

恢复：保存结果之前的状态（回溯）

｝

｝

注意：搜索范围和递归的层数

今天依然是懵逼的蒟蒻！！

The End.

关于基地校day 1的日常懵逼——2019.07.25

基地校懵逼系列day 2

Begin

首先，失恋巧克力职人。

不会做！！

据说是用回溯？反正也没学过（小声说一句学了也不会）。

好的来下一题。

第二题，如龙。

好的来我们关门放宽搜。

貌似是一个类似猴群的玩意儿？？

第三题，有钱男与贫穷女。

嗯......balabala打了一半

然后

不会了......

最后一题，非自然死亡。

我......

总之

今天没有代码！！（等做完了再写上去哈）

最后

吐槽部分

1.失恋巧克力职人

话说吃那么多巧克力真的不会得糖尿病吗？！

2.如龙

桐生会组员好吃亏喔......

3.有钱男与贫穷女

她真的好闲喔……

4.非自然死亡

嗯......

今日份懵逼蒟蒻

@-@

——End

数的计算




1
 






1
 

题目描述

我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
1.          不作任何处理;
2.          在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3.          加上数后,继续按此规则进行处理,直到不能再加自然数为止.

输入

一个数n

输出

　一个数表示答案

样例输入

6

样例输出

6



1
2
3
4
其实，不需要存下排出的数，只要递归，大于0小于等于n/2就ans++





核心函数如下：





1
2
<span class="hljs-keyword">

//int</span>





1
2
3
4
5
6
7
8
9
10
11
12
13
14
 ans=<span class="hljs-number">1</span>;

<span class="hljs-keyword">//int</span> jis(<span class="hljs-keyword">int</span> n)

//{

//  <span class="hljs-keyword">int</span> i;

//  <span class="hljs-keyword">for</span>(i=<span class="hljs-number">1</span>;i&lt;=n/<span class="hljs-number">2</span>;i++)

//  {       

//      ans++;    //只要可以放就++  

//      <span class="hljs-keyword">if</span>(i/<span class="hljs-number">2</span>==<span class="hljs-number">0</span>) <span class="hljs-keyword">continue</span>;   //判断是否还可以放

//      <span class="hljs-keyword">else</span> jis(i);    //递归

//  }

//  <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;

//}



//有时候不需要把


题目想的太复杂.......

守望者的逃离——关于好惨一守望者

守望者的逃离

#include<bits/stdc++.h>     //使用万能头文件
using namespace std;
int a[300001];
int main()
{
int m,s,t,i;
cin>>m>>s>>t;     //m表示魔法初值，s表示初始位置与岛的出口之间的距离，t表示岛沉没的时间
for(i=1;i<=t;i++)    //使用闪烁法术
{
if(m>=10)     //如果魔法初值大于等于10（表示可以使用）
{
a[i]=a[i-1]+60;     //距离往前加上使用法术后每秒钟可以移动的60米
m-=10;     //魔法值减去用掉的10点
}
else     //如果魔法初值小于10 
{
a[i]=a[i-1];    //原地休息
m+=4;    //每秒钟恢复4点魔法值
}
}
for(i=1;i<=t;i++)
{
a[i]=max(a[i],a[i-1]+17);    //比较，选取最优方案（两个方案之间比较能走的距离）
if(a[i]>=s)    //如果在循环过程中守望者走的距离大于初始位置与岛的出口之间的距离
{
cout<<"Yes"<<endl<<i;      //输出Yes,并输出时间
return 0;
}
}
cout<<"No"<<endl<<a[t];      //否则（在岛沉没时仍未到达岛的出口），输出No，并输出最远能到达的距离
return 0;
}

样例真的笑到我了hhh好惨一守望者

 

2018赛前集训Day6

今天也是满满水题的一天。

T1：【加密编码】（传送门）

嗯，很简单的。

给你每个大写字母对应的另一个大写字母。给你一个包含空格和大写字母的字符串，把其中的大写字母转换成对应的密母（空格原样输出）。

这题算得上难点的就是输入时空格的问题。scanf不行，还有一个输入方法fgets，它以换行判断字符串的读完，所以在用strlen求长度时会多算换行“\n”，枚举时注意一下这个点就没什么问题了（好像有些人因为这个WA了）。像我这种蒟蒻，当然是不会用这种高端操作啦，所以也可以一个一个读字符，直到读到的不是大写字母也不是空格就跳出就可以了。

T2：【质数统计】（传送门）

统计a到b之间有多少个质数。

因为b<=1e6，所以随便打个埃氏筛就可以了。

T3：【卫星照片】（传送门）

给你一个由“#”和“.”组成的图，由“#”组成的联通块可以是帐篷或者羊群。帐篷：联通块为矩形且不包含“.”。不是帐篷的联通块都是羊群。问给出的图中有多少个帐篷和羊群。

啦啦啦，很久没打搜索了。时隔多日不打依旧宝刀未老啊

输入完之后，枚举字符，找到“#”后搜索包含它的联通块，搜索过程中求出联通块中有多少个“#”，并找到这个联通块最小的x、最大的x、最小的y、最大的y，如果这个联通块是个矩形，那么(max_x-min_x+1)*(max_y-min_y)=“#”的个数，判断是否为帐篷。可以再开一个变量存羊群的个数（因为不是帐篷的联通块就是羊群），也可以存联通块的个数，输出答案时再减掉帐篷的个数，也是可以的。

T4：【课题选择】（传送门）

题意：n篇论文，m个课题，可重复选择课题。对于某个课题i，写 x 篇论文， 需要花费 Ai*x^Bi 个单位时间， 给定与每一个课题相对应的 Ai 和 Bi 的值， 请计算出如何选择论文的课题使得完成这 n 篇论文的时间最少。

emmmm，看着就像DP但贪心就能过的题。（好难过啊）

当前我们要写i篇论文，那么当前的最少时间是写i-1篇论文+从m个课题中再选一篇的时间。然后可以求出i篇论文与i-1篇论文最小的时间差（因为有乘方不能直接加），在加上i-1篇论文的最少时间。



1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=n;i++)

    {

        f[i]=1e9;

        for(int j=1;j<=m;j++)

        {

            d1=1;d2=1;

            for(int r=1;r<=b[j];r++)

                {d1*=(k[j]+1);d2*=k[j];}

            if((long long)a[j]*(d1-d2)<f[i]) {f[i]=(long long)a[j]*(d1-d2);w=j;}

        }

        k[w]++;f[i]+=f[i-1];

    }

找到多写一篇论文的最少时间对应的课题，然后将其写的篇数++（k数组），后面的才会是对的。注意要开long long啦。

继续阅读2018赛前集训Day6

2018CZ夏令营Day14

这是集训的倒数第二天了，明明水的一匹，却炸了。

不要问我为什么，我也不知道为什么······

T1：【深渊】

题意：不想讲有n个数，每个数都有一个价值v，取若干个数使他们的和是m的倍数又尽可能的大。

先吐槽一下，给的题解有点偏差，真是害死人，改半天改不出来。

正解动规。

f[i][j]表示前i个取到的价值和再%m余j的情况下，能取到最大价值和。

每个物品只有两种状态，取或不取。不取的话，就等于上个物品%m余j的最大价值和，所以：

f[i][(j+v[i])%m]=f[i-1][(j+v[i])%m];

如果取的话，就等于本身（也就是不取的情况）和上一个物品再%m余j的情况下，加上v[i]。注意第二维j+v[i]可能会超过m，所以要取余。

if(h[i-1][j])  f[i][(j+v[i])%m]=max(f[i-1][j]+v[i],f[i][(j+v[i])%m]),h[i][(j+v[i])%m]=1;

h数组则是维护某个状态是否到达过。如果你当前这个状态需要有上一个状态转移，而上一个状态却不曾到达过，也是不可行的。

最后要输出的便是前n个数%m=0的最大价值和了，也就是f[n][0]；

感谢烨神尽一个小时的教导，还帮我调代码。

T2：【勇士】

这是我来到常州这么多天遇到的最最最最最水的一题，没有之一。

就是给你n个数，找到最大的数，并找一下最大的数值有几个。

简！单！不！简！单！

不需要任何算法，你自己爱怎么来怎么来，反正我没有用到快排，直接在读入时，如果这个数大于maxx，maxx=当前这个数，g（计数器）清为1。如果等于，g++。

注意每个数的范围，此题需要long long。

T3：【战斗】

题意：好复杂不想讲

其实最后的正解也就是贪心。

每次把所有的数从小到大排，然后对于最大的数，只能和前面的数连，也就是从前a[n]个数都要减一，而最后一个数变成零，重复此步骤知道所有的数都变成零。如果大于零的数不够减了，那便是矛盾的。

嗯，就这样。考场上我写的代码也很接近了，少个排序断送满分。

T4：【堕落】

不是很会，也不是很想去理解 。送你们题解：

看到x坐标范围较小，考虑将一个矩形拆成若干个以行单位的线段，最多1000*1000条，然后双关键字排序，统计每一行的线段覆盖。

继续阅读2018CZ夏令营Day14

11.7 普及

T1    圆国旅行

这题我乍一看感觉还挺难的，后来发现只要算出起点和终点到每个圆心的距离，如果距离小于直径，那么说明两个点在圆内，要穿越一次边境，注意判断两点是否在同一个圆内即可。

T2    A-B

法一：首先，对数据进行快排，再数据进行预处理，将相同的数字归到同一集合，记录下每个数字的个数，对于每一个 A[I]，用二分在它之前找与它相差 C 的数字，若可找到，则将该数字的个数累加到 ans中。

法二：用哈希的思想，构造一个桶（用map），判断每个a[i]+c是否有数存在，如果有数存在，则说明这存在A-B=C的数对，ans++。

mistake：暴力，二重for90分。

T3    Couple Number

法一：数论，可推导得出, s = a^2-b^2 = (a-b)*(a+b)，显然 a-b 和 a+b 同奇偶, 所以 s 必定是’奇数’或’4 的倍数’，枚举 n1 和 n2 中的每一个数, 判断是不是 couple number。

法二：打表发现4n-2的数不是couple number。

T4    混乱队列

DP，设 f[i,j]为, 已选前 i 个人, 逆序对数为 j的总方案数。可推得：如果现在已选 i-1 个人, 逆序对数为 j, 则方案数为 f[i-1,j]。当前要放入第 i 个人, 可以插入 i-1 个人的任意位置, 放在 i-1 个人后不会出现逆序对, 放在第 1 个人后会出现 i-1 个逆序对。这样我们可以得到 f[i,j]=sum(f[i-1,j-i+1..j])。由于普通转移需要 n*m^2 的复杂度,所以我们可以把方程改为 f[i,j]=f[i,j-1]+f[i-1,j]-f[i-1,j-i]，复杂度为 O（nm）。

mistake：我先打了个10以内的暴搜，然后打了个表，有发现当j<i时f[i][j]=(f[i-1][j]+f[i][j-1])%Mod，但后来时间紧没能继续看出i<=j<=c时的规律，就直接交了，40。

今天发现，暴搜和打表真是个好东西（仅限于数学方法、递推和DP）。