Codeforces 30题 (July.16~Aug.12,2014)
据说刷CF可以锻炼代码能力……
机房大爷们都开始刷CF了，我一代蒟蒻怎能不跟随大爷们的脚步？
先预订个30题，希望能坚持完成。这里只有>=Div.1 A的题目才算吧~~以题解数量为证~~
ps:我干脆把< Div.1 A的题解也写到这里吧，就算Unofficial……>=Div.1 A的会在左边表明Prob.XX~~
Prob.01——CF 448D Multiplication Table
这题其实非常水=。=我们可以二分答案x，然后O(n)统计<=x的有多少个。显然对于第i行，<=x的数有x/i个。不要忘了对于每一行要和m取一个min！
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
LL L,R,k,n,m;
int main()
{
scanf("%I64d%I64d%I64d",&n,&m,&k);
L=0;R=1LL*n*m;
while (L<R)
{
LL Mid=(L+R)>>1,cnt=0;
for (int i=1;i<=n;i++) cnt+=min(m,Mid/i);
if (cnt<k) L=Mid+1;else R=Mid;
}
printf("%I64d\n",R);
}
Prob.02——CF 332C Students' Revenge
Prob.03——CF 449A Jzzhu and Chocolate
Prob.04——CF 449B Jzzhu and Cities
Prob.05——CF 449D Jzzhu and Numbers
Unofficial.01——CF 342B Xenia and Spies
Prob.06——CF 342C Cupboard and Balloons
Prob.07——CF 342D Xenia and Dominoes
这是一道值得推荐的题目。
题目的意思是用多米诺骨牌去填充，要保证填完的结果可以移动至少一次多米诺骨牌（'O'的位置要空出来，让一块多米诺骨牌移动到'O'的位置），求方案数。
考虑到行数只有3，这么小的常数，所以为何不状压？然后求方案数，那么递推啊，于是就很好想了：Dp[x][now][Flag]表示当前处理到从左往右第x列，当前这一列的障碍情况是now (0<=now<=7)，Flag=1表示已经满足“可以移动至少一次”的条件，=0则尚未满足。用记忆化搜索实现。
显然我们可以枚举这一列放置的情况。可以放第1、2列，也可以放2、3列，也可以和第(x+1)列合起来放横过来的。注意细节问题即可。
#include<cstdio>
#include<cstring>
using namespace std;
const int Maxn=1e4+19,Mod=1e9+7;
char Map[3][Maxn];
int Dp[Maxn][8][2],tmp[Maxn];
int n;
inline int is_0(int x,int Dis) {return ((x>>Dis)&1)==0;}
inline int Get_Dp(int x,int now,int Flag)
{
int &A=Dp[x][now][Flag];
if (A^-1) return A;A=0;
if (x==n) return A=(!now&&Flag);
now|=tmp[x];
if (now==7) return A=Get_Dp(x+1,0,Flag);
if (is_0(now,0)&&is_0(now,1)) A=(A+Get_Dp(x,now|3,Flag||Map[2][x]=='O'))%Mod;
if (is_0(now,1)&&is_0(now,2)) A=(A+Get_Dp(x,now|6,Flag||Map[0][x]=='O'))%Mod;
int can=1,nxt_Flag=0,nxt_now=0;
for (int i=0;i<3;i++)
{
if (is_0(now,i)&&!is_0(tmp[x+1],i)) {can=0;break;}
if (x&&Map[i][x-1]=='O'||Map[i][x+2]=='O') nxt_Flag=1;
if (is_0(now,i)) nxt_now|=(1<<i);
}
if (can) A=(A+Get_Dp(x+1,nxt_now,Flag||nxt_Flag))%Mod;
return A;
}
int main()
{
scanf("%d",&n);
for (int i=0;i<3;i++) scanf("%s",Map[i]);
for (int i=0;i<n;i++)
{
tmp[i]=7;
for (int j=0;j<3;j++)
if (Map[j][i]=='.') tmp[i]-=(1<<j);
}
memset(Dp,-1,sizeof(Dp));
printf("%d\n",Get_Dp(0,0,0));
}
Prob.08——CF 342E Xenia and Tree
Prob.09——CF 449C Jzzhu and Apples
Prob.10——CF 359C Prime Number
Prob.11——CF 448C Painting Fence
Prob.12——CF 448E Divisors
Unofficial.02——CF 361B Levko and Permutation
Prob.13——CF 361C Levko and Array Recovery
Prob.14——CF 361D Levko and Array
Prob.15——CF 354A Vasya and Robot
Prob.16——CF 354C Vasya and Beautiful Arrays
Prob.17——CF 406A Unusual Product
跪烂6分钟切掉这题的SkyDec大爷！
这是一道非常好的题目，下面是蒟蒻的题解~~~
考虑两个点(x,y)和(y,x)。它们相乘对答案的贡献有两次，分别是行向量x点乘列向量x的时候，行向量y点乘列向量y的时候。这两次的结果是一样的。那么他们对答案的贡献显然是0.
所以无论矩阵是怎么样的，对答案有贡献的只有对角线。那么只要统计对角线即可，不管行取反还是列取反，Ans都取反即可。
#include<cstdio>
using namespace std;
int n,m,x,c,Ans;
int main()
{
scanf("%d",&n);
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
{
scanf("%d",&x);
if (i==j) Ans^=x;
}
scanf("%d",&m);
while (m--)
{
scanf("%d",&c);
if (c<=2) scanf("%d",&x),Ans^=1;else printf("%d",Ans);
}
printf("\n");
}
Prob.18——CF 406B Toy Sum
这道题也是SkyDec大爷告诉我方法的……
我刚看题目，背包~~~ 仔细一看范围，算了下效率，10^12~~~你背包个**……
然后我们可以这么想：对于一个x,它对答案的贡献是x-1。与之对应的y是多少？显然是1e6+1-x对吧，因为1e6-(1e6+1-x)=x-1。
那么我们理所当然地会想到对于每个x找出对应的y。可是有些x和对应的y都被选中了，即都∈X，那怎么办呢？这样的话这对x和y对答案的共同贡献是x-1+(1e6+1-x-1)=1e6-1。这怎么处理呢？我们需要找一对x'和y'，使得1e6-x'+1e6-y'==1e6-1。那么显然的，x'+y'=1e6+1。这样就和刚才的条件一样了~~~
最终的算法就是：对于所有数分类，把x和1e6+1-x分到一组，如果一组中一个被选中了，一个没被选中，那么没被选中的那个作为y输出。如果两个都被选中了，就另外找一个两个数都没选中的组，把这两个数输出。
#include<cstdio>
using namespace std;
const int Max=1e6+19,tot=1e6+1;
int use[Max],n,x,sol[Max],Ans,now=1;
int main()
{
scanf("%d",&n);
while (n--) scanf("%d",&x),use[x]=1;
for (int i=1;i<tot;i++)
if (use[i]==1)
if (!use[tot-i])
{
use[tot-i]=-1;
sol[Ans++]=tot-i;
} else
{
while (use[now]||use[tot-now]) now++;
use[now]=use[tot-now]=-1;
sol[Ans++]=now;sol[Ans++]=tot-now;
use[tot-i]=0;
}
printf("%d\n",Ans);
while (--Ans>=0) printf("%d ",sol[Ans]);
}
Prob.19——CF 444A DZY Loves Physics
这里先给出结论：枚举每一条边。答案一定是某一条边。
CF官方有严密证明。不过显然的，就像平均数，a和b的平均值肯定在a与b之间，如果给出很多数要求其中若干数的平均值的最大值，那么答案肯定在某一个数中。因为再加任何一个数都会拉低平均值。这题也是一样的道理。
#include<cstdio>
#include<algorithm>
using namespace std;
int A[500+19];
int n,m,x,y,z;
double Ans=0.;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&A[i]);
while (m--)
{
scanf("%d%d%d",&x,&y,&z);
Ans=max(Ans,(A[x]+A[y])/(1.0*z));
}
printf("%.15lf\n",Ans);
}
Prob.20——CF 444B DZY Loves FFT
Prob.21——CF 392A Blocked Points
Prob.22——CF 392B Tower of Hanoi
Prob.23——CF 383A Milking cows
Prob.24——CF 383C Propagating tree
Prob.25——CF 383D Antimatter
Prob.26——CF 364A Matrix
Prob.27——CF 364B Free Market
Prob.28——CF 256A Almost Arithmetical Progression
Prob.29——CF 256B Mr. Bender and Square
Prob.30——CF 213A Game
评论 (0)
