CodeVS第三次月赛 day1 解题报告

一开始是陈江伦拉我来做的

做完第一题 第二题不会做了 就拉了顾霆枫来做

然后比赛结束了GTF还没做完第二题 我第三题写了70分

最终得分 第一题90分+第三题40分=130分 CodeVS排名第81

Cww的作业 内存限制: 128.0MB 时间限制: 1s 测试数据: 10 * 10pts

题目描述 Description

师傅给cww布置了道题,cww看到题目就不想写,请你帮忙了:

QQ截图20151004225127

QQ截图20151004225134

注:∑是累加符号 。上述的公式的意思从( for k = 2 ;k <= 2n+1 ; k++) ans+=f(k)^2 最后的答案要 % 10007

输入描述 Input Description

仅一行,一个整数 n;

输出描述 Output Description

仅一行,所求整数(%10007);(结果必须取过模后输出)

样例输入 Sample Input样例输入1: 3

样例输入2: 10

样例输出 Sample Output样例输出1: 28

样例输出2: 770

数据范围及提示 Data Size & Hint10% : n ≤ 10.

20% : n ≤ 100.

40% : n ≤ 1000.

60% : n ≤ 10000.

80% : n ≤ 1000000.

100% : n ≤ 10^9.

 

这道题一开始坑了我好久 看不懂题 因为我没看到注释(其实比赛完了我都没看到)

然后我和陈江伦都看成了输入3输出10 于是一直想不明白

想清楚之后 很容易可以想出来的是

f(n)=max[f(n-1),n的最大非n因数]

 

于是我先递推求每个f(n)

得到

QQ图片20151004230118

(f(1)其实并不存在 请无视)

可以发现规律 f(n)=(n/2)^2

想了想也的确如此 因为偶数除以二所得的肯定是最大非n因数 奇数肯定是前一个偶数的结果

(n-1)/2-n/3=n/6-1/2=(n-3)/6

因为这里的n是奇数且大于1

所以n≥3

(n-3)/6≥0

所以可以得到 答案为1243

—————————————————————

补证明:假设存在一个数k=f(n)

则在1~n中有两个数x,y为k的倍数

则x,y的最小值为k,2k

而y的最大值为n

则k=n/2

即f(n)=n/2

—————————————————————

但是即使是O(n),10^9的数据还是会爆

于是我去百度了一下公式

发现1到n的平方和就等于n(n+1)(2n+1)/6

于是就很简单了

cout<<(n*(n+1)%10007*(2*n+1)/3)%10007;

不过这样也只有90分 因为不能保证3能整除n(n+1)%10007(2n+1)

所以我的最终代码:

#include <iostream>
using namespace std;
int main()
{
long long n,n1,n2;
cin>>n;
n1=n+1ll;
n2=2ll*n+1ll;
if(!n%3)n/=3;
else if(!n1%3)n1/=3;
else n2/=3;
cout<<(n*n1%10007*n2)%10007;
return 0;
}

 

逃离异次元杀阵 内存限制: 128.0MB 时间限制: 1s 测试数据: 10 * 10pts

题目描述 Description

一天你突然醒来,发现自己被关在一个魔方格里,你很快联想到异次元杀阵里的情景,觉得有必要逃出去。所幸,身上的无线电没有坏,还可以与外界取得联系。但是由外界反馈的信息来看,你并不是处于三维世界里(准确的说是超立方体,第四维并不是时间)。幸运的是你知道了魔方格之间的距离。你物理学地很棒,通过计算魔方格之间的距离的三维关系便可以弄懂了四维的概念逃出生天,你需要通过q(q<=5W)次查询魔方格之间的距离。因为超立方体很不稳定,所以你只有1秒钟时间。

因为超立方体很神奇,就像超时空传送一样,所以这样的魔方格个数n与边数m 满足 绝对值(n-m)<=1.

输入描述 Input Description

第一行三个数n,m,q

接下来m行每行三个数a,b,c表示a、b之间有条长度为c的通道

接下来q行每行询问x到y的距离

输出描述 Output Description

一共q行,每行输出x到y的最短距离 结果在int范围内

样例输入 Sample Input

2 1 1 1 2 8 1 2

样例输出 Sample Output

8

数据范围及提示 Data Size & Hint

此处输入图片的描述

对于100%的数据,n<=50000

 

这道题表示根本不会做

用Floyd稳稳的超时了(不过也许有分)

M=N-1时是一棵树 可以用LCA做

M=N,M=N+1就是一棵树加了1~2条边 不会做了

 

破坏 内存限制: 128.0MB 时间限制: 1s 测试数据: 10 * 10pts

题目描述 Description

有一个n行m列的方阵,从某个方格可以通向上下左右(如果存在)的任一方格。Alice的任务是从第一行中找一个方格开始,经过某些方格,到最后一行的某个方格结束。有k个方格已经被破坏,不能作为出发点,结束点,或者被经过。Bob想要再破坏几个点从而让Alice无法完成任务,他想知道至少要破坏几个。

输入描述 Input Description

第一行为三个整数n,m,k。 接下来k行,每行一对整数x,y,表示第x行第y列的方格已经被破坏(被破坏的方格可能重复给出)。

输出描述 Output Description

仅一行,一个非负整数,表示Bob最少需要再破坏的方格数。

样例输入 Sample Input

5 5 3 4 1 2 3 4 5

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

对于样例,只要将第3行第2列,第3行第4列的两个方格再进行破坏即可。

对于全部的数据

0<x<=n<=1000000000

0<y<=m<=1000000000

0<=k<=500000。

对于某些数据点:

此处输入图片的描述

这道题

我小的时候做某些类脑筋急转弯的题目也用到了其中的方法

就是一个迷宫 如果有一条墙贯穿迷宫中央 那么这个迷宫是无解的

所以要让他走不到终点 只要一条线上的点都被破坏就可以了

直接dp

用a[i][o]表示(i,o)点已被破坏

dp[i][o]表示dp[i][o]表示到第o列为止经过(i,o)的线中已被破坏的点最多的数

于是dp[i][o]=max(dp[i-1][o-1],dp[i][o-1],dp[i+1][o-1])+a[i][o]

最后选出最后一列里最大的 用列数减去它即为最终答案

代码:

#include <iostream>
using namespace std;
bool a[1005][1005];
int dp[1005][1005];
int main()
{
int n,m,k,ans=0;
cin>>n>>m>>k;
for(int i=0;i<k;i++){
int x,y;
cin>>x>>y;
a[x][y]=1;
}
for(int o=1;o<=m;o++)for(int i=1;i<=n;i++)dp[i][o]=max(max(dp[i-1][o-1],dp[i][o-1]),dp[i+1][o-1])+a[i][o];
for(int i=1;i<=n;i++)ans=max(ans,dp[i][m]);
cout<<m-ans;
return 0;
}

 

ok完结撒花XD

说点什么

您将是第一位评论人!

提醒
wpDiscuz