2018寒假集训 lyh:)

集训才两天半,眨眼间就过去了

昨天没时间写,今天补充一下。

桥牌

题目描述

某星球上有n个人,其中两个人的友谊值可以用这样来计算:先把两个人的名字转化成二进制,然后对于同一位(不足补前导0),如果值相等,对应位的值为0,否则的话就是1,结果最后仍旧转换成十进制。
这个星球的价值就是所有友谊值之和。求这个星球的价值

输入

第一行包含一个整数n(1 <= n <= 1000000),表示这个星球上的总人口。接下来n行,
每行一个正整数(小于1000000),表示每个居民的名字。

输出

只有一行一个整数,表示这个星球的价值。

数据范围限制

对于40%的数据:n <= 100;对于100%的数据:n <= 1000000。

 

这道题,就是找在坐标上固定点形成的中心对称图形,

首先,什么是中心对称图形?

如图,无论顺逆旋转180度后可以和自身完全重合的图形称为中心对称图形,则B不是,其它都是中心对称图形。

然后,我们可以利用一个规律,这个规律的特点是

证明复杂,理论简单

就是在一个中心对称图形中,四个顶点相连交点是两个邻点的和的一半,用数学语言表述,就是在已知四边形ABCD为中心对称图形,其中AC和BD交于四边形ABCD内于一点O,则在平面直角坐标系中,A和C的和为O的一半。

回到正题,面对这么大的数据,暴力做法就是直接找四个点咯。然后超时……

正解就是利用上述的规律,寻找题目提供的点各自个中点,然后将发现重复的点就是答案。每次重复的点N对答案的贡献是

ANS=N*(N-1)/ 2

但是,有一个问题

那就是我们需要寻找两个对称的点。

而当我们找到一个点之后,

如果再开始找另一个点的话肯定会超

所以、

把横竖两个轴划分开来

因为数据不大,只是多

所以我们开long long

然后在第一个坐标计算完后加上一个固定的数

像这样

book[z]=(a[i]+a[j])*1000000000+b[i]+b[j];

解决这个问题后,怎么在茫茫人海中寻找到匹配的那一对呢。

1000*1000?

立刻原地炸,前功尽弃

我们可以用一个特别数组存储发现的点

这样就很容易了——

用一个快排,

酱紫,一个循环,只要判断后面的数和前面是否相等就完成了

if(book[i]==book[i-1]) sum++;if(book[i]==book[i-1]) sum++; else{ans+=sum*(sum-1)/2;sum=1;}

真代码如下

  1. #include<iostream>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. using namespace std;
  6. long long a[1002],b[1002],book[1000005];
  7. int main()
  8. { long long n,i,j,z=0,ans=0,sum=1;
  9. scanf("%lld",&n); for(i=1;i<=n;++i)
  10. scanf("%lld%lld",&a[i],&b[i]);
  11. for(i=1;i<=n;++i)
  12. { for(j=i;j<=n;++j)
  13. { if(i==j) continue; z++;book[z]=(a[i]+a[j])*1000000000+b[i]+b[j]; } } sort(book+1,book+z+1);
  14. for(i=2;i<=z;++i)
  15. { if(book[i]==book[i-1]) sum++; else{ans+=sum*(sum-1)/2;sum=1;} } printf("%lld",ans);return 0;}

对布满灰尘的西洋棋宣告将军

不要问我看不清,友情链接:https://2017.noi.team/oj/#contest/show/95/3

首先看数据

不管数据有多大,首先,暴力。

就循环,找路,递归,向下和向右的两种选择,写起来还是比较容易的。

然后是正解。

逆向思维,题目要求的有二者,一是权值,二是路数

每一格棋都可以看做是由上一步和左边走来的,

它的权值最大值就等于上一步的最大值加这一步的最大值

那么我们就可以递推了。

这里只需要注意一个步数问题,

因为要求的步数是基于取得最大值之上的,所以对于两种路径来源,就有三种情况,即

A>B||A=B||A<B

就很好理解了

在权值相同的情况下,当然两条路都可以选

在权值不同的情况下,就选择权值大的路

所以式子显而易见


1
f[i][j]=f[i][j-<span class="hljs-number">1</span>]+a[i][j];

1
c[i][j]=(c[i-<span class="hljs-number">1</span>][j]+c[i][j-<span class="hljs-number">1</span>])%<span class="hljs-number">1000000007</span>;

最后注意,第一行没有上的情况和第一列没有左的情况且它们都只有一条路的特殊情况

那就特殊处理

然后核心代码i,j从2开始

真代码如下

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,i,j,a[2002][2002],f[2002][2002],c[2002][2002];
int main()
{
	freopen("chess.in","r",stdin);
	freopen("chess.out","w",stdout);

	//初始化第一格是一 
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=n;i++){for(j=1;j<=m;j++){scanf("%lld",&a[i][j]);}}
	c[1][1]=1;f[1][1]=a[1][1];
	
	for(i=2;i<=n;i++){f[i][1]=f[i-1][1]+a[i][1];c[i][1]=1;} 
	for(i=2;i<=m;i++){f[1][i]=f[1][i-1]+a[1][i];c[1][i]=1;}
	//第一行第一列特殊情况包括路径只有一个和上一步只有一种 
	 
	for(i=2;i<=n;i++)
	{
		for(j=2;j<=m;j++)
	//从二行二列开始的一般情况 
		{
		//讨论两种途径相等和不相等的三种情况 
			if(f[i-1][j]==f[i][j-1])
			{
				f[i][j]=f[i][j-1]+a[i][j];
				c[i][j]=(c[i-1][j]+c[i][j-1])%1000000007;
			}
			if(f[i-1][j]<f[i][j-1])
			{
				f[i][j]=f[i][j-1]+a[i][j];
				c[i][j]=c[i][j-1]%1000000007;
			}
			if(f[i-1][j]>f[i][j-1])
			{
				f[i][j]=f[i-1][j]+a[i][j];
				c[i][j]=c[i-1][j]%1000000007;
			}
		}
	}
	printf("%lld\n%lld",f[n][m],c[n][m]);return 0;
}

分割金币

有n枚金币(1  <= n  <= 250),金币有价值(可能相同)。现在希望平均分配这n枚金币成2堆。求2堆金币的最小差值。一枚金币不能进行分割。
例如5枚金币,价值分别为1,2,4,8,16。可以如下分配:1,2,4,8分为一堆,16分为一堆。最小差值为16-15=1。
注意特例:价值相等的金币为不同的金币。假设如果有4枚金币,价值为1,1,1,1。那么分配方法有6种。

输入   第1行:一个整数n。
第2到n+1行:一个整数,表示第i个金币的价值(<=1000)。

输出   第1行:一个整数表示分配时候,2堆金币的最小差值。
第2行:达到这个最小差值的分配方法的数量。由于这个数字可能比较大,输出除以1000000的余数。

40%的数据n <= 20;100%的数据n <= 250

暴力略,

。。。

把所有的金币总和算出来

然后拿拼凑的数量一一的总价的一半比较

越接近越好

重点就是怎么算可以拼凑的数量

就用一个一维数组f[i]

i存储元,整体存储次数

只要某个值可以被求到

那就具体计算它还可以拼成多少数目的金币

f[j+a[i]]+=f[j]; f[j+a[i]]+=f[j]; f[j+a[i]]%=k;

这样答案就很好求了


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
<span class="hljs-preprocessor">#<span class="hljs-keyword">include</span>&lt;iostream&gt;</span>
<span class="hljs-preprocessor">#<span class="hljs-keyword">include</span>&lt;cstdio&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[<span class="hljs-number">255</span>],f[<span class="hljs-number">2500005</span>];
<span class="hljs-keyword">int</span> main()
{
    freopen(<span class="hljs-string">"divgold.in"</span>,<span class="hljs-string">"r"</span>,stdin);
    freopen(<span class="hljs-string">"divgold.out"</span>,<span class="hljs-string">"w"</span>,stdout);
    <span class="hljs-keyword">int</span> n,ans1,ans2,sum=<span class="hljs-number">0</span>,k=<span class="hljs-number">1000000</span>;
    <span class="hljs-built_in">scanf</span>(<span class="hljs-string">"%d"</span>,&amp;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">scanf</span>(<span class="hljs-string">"%d"</span>,&amp;a[i]);
        sum+=a[i];
    }
    f[<span class="hljs-number">0</span>]=<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;=n;++i)
    {
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=sum;j&gt;=<span class="hljs-number">0</span>;--j)
        {
            <span class="hljs-keyword">if</span>(f[j]!=<span class="hljs-number">0</span>)
            {
                f[j+a[i]]+=f[j];
                f[j+a[i]]%=k;
            }
        }
    }
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;=sum/<span class="hljs-number">2</span>;++j)
    {
        <span class="hljs-keyword">if</span>(f[j]!=<span class="hljs-number">0</span>)
        {
            ans1=sum-<span class="hljs-number">2</span>*j;
            ans2=f[j];
        }
    }
    <span class="hljs-built_in">printf</span>(<span class="hljs-string">"%d\n%d"</span>,ans1,ans2);
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}

END

总结

这可以说是第一次写blog,这两天才刚刚来到一中,就被叫过来上信息了,因为之前学过编程,但还是对c++不熟悉,便从题库上开始刷题,刚开始的时候,总是在一些小问题上出差错:变量搞错,数据类型不对,题目理解不够······在老师的帮助下,还是慢慢改正过来,希望能够通过接下来的努力,对c++有更深的了解,能够在竞赛上走得更远!

写题心得

这是我第一次写blog,写的不好请大家见谅

 

我是今年暑假才接触到c++,遇到了很多题,想了很久都想不出来,但在很多大佬和老师的帮助下,我才慢慢的懂得了一些关于c++的知识。

 

希望在接下来,能够理解更多关于c++的知识。

 

废话就不多说了,我先溜了

 

2018福建冬令营Day2

早上讲的图论,下午看到题就想用图论写,结果没有一题是图论的。。

【红绿灯】:考虑过建边跑网络流,而且数据范围和网络流差不多。正解是将问题拆分,预处理每个路口到终点的时间,在用线段树维护第一个等红灯的路口。

【全排列】:正解是用dp求长度为i的排列,逆序对小于E的方案数,再用排列组合算答案。

【点点井井】:30%枚举曼哈顿距离,再从大到小枚举横坐标。正解将曼哈顿距离转换为切比雪夫距离,暴力考虑周围5*5的点即可

2018.2.9集训

题目:https://2017.noi.team/oj/#contest/home/95;

T1:棋牌

不需要用到什么算法,主要还是要懂得推规律;把所有的横坐标,纵坐标两两相加,然后判断有多少组相等就是了。

T2:坦克

依旧是一题数学题,原谅pj的做不出来,就是需要与处理一些数据,目前还没改出来。

T3:联络网

树形dp,不会······

T4:对布满灰尘的西洋棋宣告将军

(据说这是一题特意为我们准备的“水题”,呵呵)

正解就是一个dp很简单,因为只能向右和向下走,,所以每个格子只能从左边或者上边走到,比较谁的权值更大。因为还要求路径数,所以当权值相等时,路径数要相加。

大致就是这样的。

blog真是越来越无聊了呢。

——end。

2018.2.9寒假集训

T1 素数
·=·感觉这题是不用讲的数据不会很坑233 没用筛法也能过
就是先预处理后因为是连续的 所以可以用
for(int i=1;i<=t;++i)//这里的t是40000以内的素数个数前面预算处理
for(int j=i+1;j<=t;++j) 就一次次判断就好啦~

T2 晨练
- -DP其实我不怎么懂来着2333没有推来着
听那个学长讲的比较不一样hhh具体差不多是
f[i][j]=max(f[i][j],f[i-1]j[j-1]+d[i])//这里f[i-1][j-1]是上一次的最优值hhh
还有判断休息的就是
f[i+j][0]=max(f[i][j],f[i+j][0])//记得判断一下i+j有没有越界就差不多
f[i][0]=max(f[i][0],f[i-1][0]);//上一次休息的最优值

End.

2018寒假集训day1

I.素数

先用筛法求素数,然后再暴力枚举就可以了。

II.晨练

小 Y 打算通过锻炼来培养自己的运动细胞,他选择的运动方式是每天进行N分钟的晨跑(1<=N<=10000)。
在每分钟的开始,小 Y 会选择下一分钟是用来跑步还是休息。小 Y 的体力限制了他跑步的距离。更具体地,如果小 Y 选择在第 i 分钟内跑步,他可以在这一分钟内跑 D_i(1<=D_i<=1000)米,并且他的疲劳度会增加1。不过,无论何时小 Y 的疲劳度都不能超过 M(1 <=M<=500)。如果小 Y 选择休息,那么他的疲劳度就会每分钟减少 1,但他必须休息到疲劳度恢复到0为止。在疲劳度为 0 时休息的话,疲劳度不会再变动。晨跑开始时,小 Y 的疲劳度为 0。还有,在N分钟的锻炼结束时,小 Y 的疲劳度也必须恢复到0,否则他将没有足够的精力来对付这一整天中剩下的事情。     
求小 Y 最多能跑多少米。

对于n<=50的数据,可以用爆搜拿30分(虽然我只打了20分)。

对于100%的数据,那一看就是dp了,题解如下:

用f[i][j]表示在第i分钟疲劳度为j时能跑的最大距离,而小Y在每一分钟都有两种选择(准确来说是三种),跑或休息,当然在疲劳度为0时也可以休息,于是便推出以下三个方程:

①f[i][0]=max(f[i][0],f[i-1][0]);(表示疲劳度为0时休息)

②f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]);(表示跑)

③f[i+j][0]=max(f[i+j][0],f[i][j]);(表示休息)

最后输出f[n][0]即可。

III.奇怪的桌子

动规+组合数学?不懂。

IV.学校

最短路径问题,30%可以用SPFA,100%算法依旧不懂。

 

【2018寒假】2-8

By shy

辛(qi)亥(mo)革(kao)命(shi)刚刚结束,就要复(han)辟(jia)帝(ji)制(xun)了。

废话不说了,开讲。

然而还是照例要废话几句的

今天懒得废话了,还是讲吧。

1,素数

题目描述

有一些正整数能够表示为一个或连续多个素数的和。那么给定一些正整数,求有多少种这样的表示。对于100%的数据,所有数<=32767。

Solve

首先,枚举每个数所有的和的表示,然后判断是不是素数是一种方法,但是复杂度太高,得想另一个办法。
很明显的我们可以先用埃氏筛(是的我就是不会线性筛)筛出32767以内的素数,然后注意到题目:一个或连续多个素数的和。这样我们可以直接暴力枚举每一个素数作为起点,每次用原数减去相邻的素数直到原数不大于0。当原数=0时,方案数+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*计算方案数*/
//pr[]为筛出的素数(有序排列)
int dfs(int a)
{
    int sum=0;//方案数
    for(int i=1;i<=t&&pr[i]<=a;i++)//枚举素数"起点"
    {
        int j=i,f=a;
        while(f-pr[j]>=0)//不断减去相邻的素数直到原数不大于0
        {
            f-=pr[j];
            ++j;
        }
        if(f==0) ++sum;
    }
    return sum;
}

2,贝茜的 晨练 计划

题目描述

奶牛们小 Y 打算通过锻炼来培养自己的运动细胞,贝茜他选择的运动方式是每天进行N分钟的晨跑(1<=N<=10000)。在每分钟的开始,贝茜小 Y 会选择下一分钟是用来跑步还是休息。贝茜小 Y 的体力限制了他跑步的距离。更具体地,如果贝茜小 Y 选择在第 i 分钟内跑步,他可以在这一分钟内跑 D_i(1<=D_i<=1000)米,并且他的疲劳度会增加1。不过,无论何时贝茜小 Y 的疲劳度都不能超过 M(1 <=M<=500)。如果贝茜小 Y 选择休息,那么他的疲劳度就会每分钟减少 1,但他必须休息到疲劳度恢复到0为止。在疲劳度为 0 时休息的话,疲劳度不会再变动。晨跑开始时,贝茜小 Y 的疲劳度为 0。还有,在N分钟的锻炼结束时,贝茜小 Y 的疲劳度也必须恢复到0,否则他将没有足够的精力来对付这一整天中剩下的事情。请你计算一下,贝茜小 Y 最多能跑多少米。

Thinking

看到这题就知道是个DP。接着我们要推方程。

首先,用f[i][j]表示在第i分钟j点疲劳度的跑步最远路程。

第i分钟疲劳度为0的最优解是上一分钟疲劳度为1和0中的最优解,于是有:

f[i][0]=max(f[i-1][1],f[i-1][0]);

紧接着,第i分钟疲劳度为j的最优解可以由第i-1分钟疲劳度为j+1的最优解(休息),j-1的最优解+第i分钟跑步的路程(跑步),于是有:

f[i][j]=max(f[i-1][j+1],f[i-1][j-1]+d[i]);

然后就愉快的炸掉了。

Solve

还好我的辛苦没有白费,至少理解正解时轻松了许多。继续为自己的错误赋予意义。

还是用f[i][j]表示在第i分钟j点疲劳度的跑步最远路程(最优解)。

方程如下:

f[i][0] = max(f[i][0],f[i-1][0])。//第i分钟疲劳度为0的最优解可以通过第i-1分钟疲劳度为0的最优解转化。

f[i][j] = max(f[i][j],f[i-1][j-1] + d[i])。//第i分钟疲劳度为j的最优解可以通过第i-1分钟疲劳度为j-1的最优解+第i分钟跑步的路程d[i]转化。

f[i+j][0] = max(f[i+j][0],f[i][j])。//这一条是最重要的,因为结束时疲劳度必须为0,所以是有限制的。那么因为疲劳度为j时需要休息j分钟才能成为0,所以i+j分钟时疲劳度j为0,(目前的)最优值为第i分钟疲劳度为j时的最优值。

链接:

7月17日备战Noip2017暑假集训2(A) 贝茜的晨练计划【动态规划】

2018寒假集训Day1之晨练

第一题素数太简单了,可以直接暴力,就不多讲了。

而三、四两题太难了,尚不在我的能力范围内。所以只有第二题能讲了,虽然也没有很懂······


题目:

小 Y 打算通过锻炼来培养自己的运动细胞,他选择的运动方式是每天进行N分钟的晨跑(1<=N<=10000)。
在每分钟的开始,小 Y 会选择下一分钟是用来跑步还是休息。小 Y 的体力限制了他跑步的距离。更具体地,如果小 Y 选择在第 i 分钟内跑步,他可以在这一分钟内跑 D_i(1<=D_i<=1000)米,并且他的疲劳度会增加1。不过,无论何时小 Y 的疲劳度都不能超过 M(1 <=M<=500)。如果小 Y 选择休息,那么他的疲劳度就会每分钟减少 1,但他必须休息到疲劳度恢复到0为止。在疲劳度为 0 时休息的话,疲劳度不会再变动。晨跑开始时,小 Y 的疲劳度为 0。还有,在N分钟的锻炼结束时,小 Y 的疲劳度也必须恢复到0,否则他将没有足够的精力来对付这一整天中剩下的事情。请你计算一下,小 Y 最多能跑多少米。

正解是动态规划。但这题有三个状态转移方程。

上方程!!!!

1.f[i][0]=max(f[i][0],f[i-1][0]);

2.f[i][j]=max(f[i][j],f[i-1][j-1]+d[i]);

3.f[i+j][0]=max(f[i+j][0],f[i][j]);

i表示分钟,j表示疲劳度。然后进行比较就是了。

就这样吧,没啥好讲的。

——end。