| 题目名称 | 赶鸽子(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赶鸽子 |
||
|
问题描述
众所周知，机房里有n只鸽子。有一天，nudgd闲得发慌突发奇想，决定把这些鸽子全部赶到一起。已知，将数量分别为a只和b只的两群鸽子赶到一起，需要花费a@b的时间，其中@为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莱都莱了 |
||
|
问题描述
题目背景
"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，意义见题目描述。$1leq nleq 105,1leq mleq kleq 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
2 4 3
13 20
1 1 14
1 2 30
2 1 6
3 2 2
样例输出 1
3
2 3 4
样例输入 2
10 7 4
5 2 8 1 3 3 1 2 5 7
2 8 4
3 4 7
3 4 4
2 4 3
3 5 3
1 5 5
2 5 8
样例输出 2
4
2 3 4 7
提示
对于40%的数据，1<=n<=10,1<=k<=10 。
对于剩下60%的数据，没有限制。