8,20考试
问题描述 众所周知，机房里有n只鸽子。有一天，nudgd 输入格式 输入一行，第一行一个正整数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,3）??。 数据范围与约定 对于的数据50%，保证n<=2^10 对于的数据100%，保证 n<=2^32 提示 数据无梯度。 n会超出 分析设合并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,3,5,10,14,21,27,36,44,55} 差分一下，设d(i)=f(i+1)-f(i)，d(1)~d(10)={0,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时，可以手动算出结论成立。 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; } ?
问题描述 题目背景 "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,y。1<=ky<=3,1<=x<=n,1<=y<=10^6。 输出格式 第一行一个数num表示实际使用的魔法个数。 接下来1行num个数，表示选取的魔法的编号。 如果有多种方案，优先选num小的，再优先选第1 个魔法编号尽量小的，再优先第2个…… 样例输入 1 2?4?3 样例输出 1 3 样例输入 2 10?7?4 样例输出 2 4 提示 对于40%的数据，1<=n<=10,1<=k<=10??。 对于剩下60%的数据，没有限制。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
