注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

Codeforces Round #132 (Div. 2) C,D  

2012-08-11 13:38:36|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
C. Crosses

题目连接:http://codeforces.com/contest/215/problem/C

刚开始想分类讨论,找出计算的公式直接O(1),但是,找公式发现要考虑的情况很多,后来参考了http://www.cppblog.com/hanfei19910905/archive/2012/08/10/186807.html的想法
因为数据量不是很大 ,cross所包含的格子是两个矩形的并集,ab所表示的矩形和cd所表示的矩形的并集,先找到包含这两个矩形并集的最小的矩形n1 * m1,即枚举 n1 = max(a,c,) , m1 = max(b,d) 
对当前的这个n1 * m1的矩形,所包含的cross 面积为s的个数为f(n1,m1,s) ,最后结果加上 f(n1,m1,s ) * (n - n1 + 1) * (m - m1 + 1) ,后面乘的(n - n1 + 1) * ( m - m1 + 1)表示这个n1 * m1 的矩形放在在 n * m 范围内的方法数。

计算f(n1 , m1 ,s ) :
1)如果n1 * m1 == s,f(n1 ,m1 ,s ) = 2 * (n1 / 2 + 1) * (m1 / 2 + 1) - 1,因为是完全填充了n1 * m1的矩形,所以单用ab矩形或者cd矩形就能够确定了,假设ab确定,cd的的选取只要在ab的范围内就ok了,这样有(n1 /2 +1)*(m1/2+1)种方法 ,  乘2因为a,b 和c,d相互交换又是一种方法, -1因为a,b 和c,d相同的情况下,交换不会产生新的corss。
2)如果n1 * m1 > s , 这时候,如果直接找cross的个数就不好找了。这时候,可以换个角度,此时的cross相当于在n1 * m1 的矩形中剪掉4个角,corss的形状的个数就是剪掉4个角的方法数。如何确定剪掉4个角的方法数? 枚举。 因为每个角的面积a =  (n1 * m1 -s ) / 4 ,枚举a的一条边长为i,则另一条边长为a/ i , 这时候注意需要判断一下是否是从n1 * m1上切下来的 ,就是边长的限制。
另外如果 (n1 * m1 -s) % 4 如果不是0表示n1*m1的矩形中不可能包含一个cross 面积为s,且包含cross的最小矩形为n1 * m1。
分别枚举每种且角的方法,对每种切角的方法,ans += 2 * (n - n1 + 1) * ( m - m1 + 1),其中(n - n1 + 1) * ( m - m1 + 1)表示这个n1 * m1 的矩形放在在 n * m 范围内的方法数表示,*2 表示ab和cd呼唤的情况。另外要考虑到如果a为正方形,则表示ab和cd互换不会产生新的cross。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#define LL long long
using namespace std;
int n,m,s;

void init()
{
scanf("%d%d%d",&n,&m,&s);
}

LL cal(int n,int m, int n1, int m1)
{
return 1L * (n - n1 + 1) * (m - m1 + 1);
}


void work()
{
int i,j;
LL ans = 0;
int n1,m1;
for(n1 = 1;n1 <= n; n1 +=2 )
{
for(m1 = 1;m1 <= m; m1 += 2) if (n1 * m1 >= s && (n1 * m1 -s ) % 4 == 0)
{
int dx = n1 / 2;
int dy = m1 / 2;
if(n1 * m1 == s)
{
ans += cal(n,m,n1,m1) * ((dx + 1) * (dy + 1) * 2 - 1) ;
continue;
}
int a = (n1 * m1 - s) / 4;
for(int i = 1;i * i <= a;i ++) if (a % i == 0)
{
if(i * i == a)
{
if(i <= dx && i <= dy ) ans += 2 * cal(n,m,n1,m1);
}
else
{
if(i <= dx && a / i <= dy ) ans += 2 * cal(n,m,n1,m1);
if(i <= dy && a / i <= dx ) ans += 2 * cal(n,m,n1,m1);
}
}
}
}
cout << ans <<endl;

}

int main()
{
init();
work();
return 0;
}



D. Hot Days

看起来很复杂的题目,其实经过分析后,发现是有规律的。
贪心:
假设在第i个region需要用n个车,那么
如果 T[i] - t[i] > m/n 那么在这个region的成本c = cost[i] * n
如果 T[i] - t[i] < m/n 那么在这个region的成本c = cost[i] * n + { m - (T[i] - t[i] ) * ( n-1) } * x[i], 化简c = (cost[i] - (T[i]-t[i] ) *x[i] )  * n + (m + T - t) * x[i] ,只有n是变量,并且是线性的,所以极值一定在端点处取得。
也就是说,极值为n = 1的情况,或者n = m / (T - t) + ( m % (T - t)  == 0  ) 的情况,每隔region取这两者的较小的就ok,
注意T <  t 的情况 

#include <iostream>
#include <cstdlib>
#include <cstdio>


using namespace std;

int n,m;

void init()
{
scanf("%d%d",&n,&m);
}


void work()
{
int t,T,x,cost;
long long ans = 0;
long long t1,t2;
for (int i = 0;i < n;i ++)
{
scanf("%d%d%d%d",&t,&T,&x,&cost);
if(m + t > T) t1 = cost + 1LL* m * x;
else t1 = cost;
if(T <= t )
{
ans += t1;
continue;
}

int nx = m / (T-t);
if (m % (T-t) != 0)
nx += 1;
t2 = 1LL * cost * nx;
ans += t1 < t2 ? t1: t2;

}
cout << ans <<endl;

}


int main()
{
init();
work();

return 0;
}


  评论这张
 
阅读(447)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018