8,20考试是哪一天进行的？

本文共计1700个文字，预计阅读时间需要7分钟。

项目名称 + 鸽子（pigeon） + 莉莉莉（come） + 神话和葛根（konjac） + 时间限制 + 空间限制 + 源文件名 + 输入文件名项目名称 + 鸽子（pigeon） + 来了（come） + 神话与魔芋（konjac） + 时间限制 + 空间限制 + 源代码文件 + 输入文件

题目名称 赶鸽子(pigeon) 莱都莱了(come) 神犇和蒟蒻(konjac) 时间限制 1.0s 1.0s 2.0s 空间限制 512MB 512MB 512MB 源文件名 pigeon.c/cpp/pas come.c/cpp/pas konjac.c/cpp/pas 输入文件名 pigeon.in come.in konjac.in 输出文件名 pigeon.out come.out konjac.out

    

A赶鸽子

时间限制 :-MS空间限制 :-KB 评测说明 :1s,512m

问题描述

众所周知，机房里有n只鸽子。有一天，nudgd闲得发慌突发奇想，决定把这些鸽子全部赶到一起。已知，将数量分别为a只和b只的两群鸽子赶到一起，需要花费[emailprotected]的时间，其中@为c与c++中的位异或（^）运算符，或pascal中的xor运算符。由于nudgd不想做PPT很闲，所以他想用尽可能多的时间来把所有鸽子赶到一起。他想知道最多需要多少时间，才能把所有鸽子都赶到一起。开始时，可以看作有n群鸽子，每群仅有一只。

输入格式

输入一行，第一行一个正整数n(2<=n<=2^32)，表示鸽子的总数。

输出格式

输出一行，第一行一个正整数，表示把所有鸽子赶到一起所需要的最多时间。

样例输入 1

2

样例输出 1

0

样例输入 2

3

样例输出 2

3

样例输入 3

233

样例输出 3

27028

提示

样例2说明

设三只鸽子的编号分别为1,2,3，先把1和2赶到一起，需要的时间为0，剩下两群鸽子（1,2），（3）再把（1,2）和（3）赶到一起，需要时间为3，剩下一群鸽子（1,2,3）。

数据范围与约定

对于的数据50%，保证n<=2^10

对于的数据100%，保证 n<=2^32

提示

数据无梯度。

n会超出int的范围。

分析

设合并n只鸽子的最大时间为f(n)

50分算法：f(n)=max{f(i)+f(n-i)+(i^(n-i))}(1<i<=n/2)，直接dp

打表f(1)~f(11)={0,0,3,5,10,14,21,27,36,44,55}

差分一下，设d(i)=f(i+1)-f(i)，d(1)~d(10)={0,3,2,5,4,7,6,9,8,11}，发现d(i)=i^1。

90分算法：利用结论:当鸽子的总数为n时，合并的最大时间为n*(n-1)/2-[n为偶数]

证明：

引理：i>=1,j>=1,则(i^j)<=i+j

证：i^j=(i|j)-(i&j)，又i+j=(i|j)+(i&j)，所以(i^j)<=(i|j)<=i+j。

当n<=4时，可以手动算出结论成立。
当n>4时，设对任意k<n，结论成立，
则对于任意2<i<n，
f(i)-f(i-1)=i-1±1
所以对于任意2<i<=n/2，
f(i-1)+f(n-i+1)>=f(i)+f(n-i)+n-i*2+1>=f(i)+f(n-i)
又对于任意1<=i<n，
i^(n-i)<=n，
1^(n-1)=1+n-1+(1&(n-1))*2>=n-2
所以对于任意2<i<=n/2，
f(1)+f(n-1)+(1^(n-1))
>=f(2)+f(n-2)+n-2*2+1+n-2
=f(2)+f(n-2)+n*2-5
>=f(2)+f(n-2)+n
>=f(i)+f(n-i)+(i^(n-i))

100分算法：注意到提示，n可能爆int，所以n*n<=pow(2,64)，会爆long long，所以需要先除2，再乘。

上代码

#include<stdio.h> #include<bits/stdc++.h> using namespace std; long long n; int main() { //freopen("pigeon.in","r",stdin); //freopen("pigeon.out","w",stdout); cin>>n; if(n%2==0)cout<<n/2*(n-1)-1; else cout<< n*(n-1)/2; }

B莱都莱了

时间限制 :-MS空间限制 :-KB 评测说明 :1s,512m

问题描述

题目背景

"nidgd总是在过年期间做坏事，要是被别人发现了就说‘这大过年的，就别计较了‘。如果别人真的不计较了，nidgd还会顺便给他拜个晚年，祝他晚年幸福。"

题目描述

nidgd终于像祝福中的那样，安度晚年去了。

晚年的nidgd闲来无事，玩起了卡牌游戏。

nidgd有n张卡牌，第i张卡牌上写有数字Ai。

nidgd会魔法，他有k种魔法，但是每种魔法只能用一次，并且只能使用其中m种魔法。

每种魔法有3个参数ty,x,y。

若ty=1，则使用魔法后第x张卡牌上的数字变为y。 若ty=2，则使用魔法后第x张卡牌上的数字增加y。 若ty=3，则使用魔法后第x张卡牌上的数字乘上y。

现在nidgd想求一种方案，使得使用完毕后所有卡牌的乘积最大。

乘积可能很大，请你输出排序后字典序最小的方案。关于最小字典序，见输出格式。

输入格式

第一行3个数n,k,m，意义见题目描述。$1\leq n\leq 105,1\leq m\leq k\leq 105$

接下来一行n个数，第i个数为Ai。1<=Ai<=10^6

接下来k行，每行3个数ty,x,y。1<=ky<=3,1<=x<=n,1<=y<=10^6。

输出格式

第一行一个数num表示实际使用的魔法个数。

接下来1行num个数，表示选取的魔法的编号。

如果有多种方案，优先选num小的，再优先选第1 个魔法编号尽量小的，再优先第2个……

样例输入 1

243
1320
1114
1230
216
322

样例输出 1

3
234

样例输入 2

1074
5281331257
284
347
344
243
353
155
258

样例输出 2

4
2347

提示

对于40%的数据，1<=n<=10,1<=k<=10。

对于剩下60%的数据，没有限制。