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

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

2011 Asia Regional Daejeon  

2012-08-10 00:29:50|  分类: 比赛总结 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       
       棒子国的区域赛题,一共12道,感觉相对其他赛区还是较简单一些,除了K题是个大坑,其他的最长1.7KB搞定,DP题略多,做的时候我这种DP傻逼感到压力灰常大,刷完之后还是收获不小的。

A - Block Compaction

       给你一些长宽平行XY轴的矩形,先把矩形向下压缩至X轴,然后再向右压缩至Y轴,求最小的能完全覆盖所有矩形的矩形。一开始还以为是几何什么的,果断无视之,后来发现这题其实是个水题。考虑向左压缩的情况,先把所有的矩形按左端点的x左边排序,那么矩形左移的过程中肯定只会和排序后在它前面的矩形相交,暴力枚举判相交,取相交矩形中最大的右端点x坐标,即为矩形左移后的坐标。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct rec{int x,y,p,q;}a[509];
int n;
bool cmp(const rec &a,const rec &b){
return a.x<b.x;
}
void gao(){
for(int i=0;i<n;i++){
int t=0;
for(int j=0;j<i;j++)
if(a[j].y<a[i].q&&a[j].q>a[i].y)
t=max(t,a[j].p);
a[i].p-=a[i].x-t;
a[i].x=t;
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0;i<n;i++) cin>>a[i].y>>a[i].x>>a[i].q>>a[i].p;
sort(a,a+n,cmp);
gao();
int w=0;
for(int i=0;i<n;i++) w=max(w,a[i].p);
for(int i=0;i<n;i++) swap(a[i].x,a[i].y),swap(a[i].p,a[i].q);
sort(a,a+n,cmp);
gao();
int d=0;
for(int i=0;i<n;i++) d=max(d,a[i].p);
cout<<d<<' '<<w<<endl;
}
}



B - Chemical Products

       水题一枚,直接暴力枚举就行了。

C - Color Length

       很赞的一道DP题,模型不是很明显,需要仔细观察题目的性质。膜拜UESTC神队的代码后才明白怎么做。可以发现有这么一个性质,Color Length的计算只和同种颜色最两端的车的坐标有关,于是我们可以处理成i-j的形式,当第一次遇见某颜色的车时,权值减去当前坐标,当遇见的车的颜色是最后一次出现时,权值加上当前坐标。这个判断可以通过预处理达到O(1),计算f[2][N],g[2][N],f[i]表示1-i的车的颜色的出现情况,g[i]表示i-n的车的颜色出现情况。dp[i][j]表示第一车道合并了前i辆车,第二车道合并了前j辆车时所得的最小权值。更新的时候只有两种情况,选第一车道的第i+1辆车合并或者选第二车道的第j+1辆车合并。当选进来的车的颜色第一次出现的时候,权值减去当前坐标(i+j),当这种颜色在剩下未选的车中不会再出现时,权值加上(i+j)。然后更新最小值,复杂度为O(n*m)。写的时候最好用个滚动数组神马的,不然还是有压力的。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 5009
#define two(x) (1<<(x))
using namespace std;
int n,m,dp[2][N];
int f[N][2],g[N][2];
char s1[N],s2[N];
int main(){
int T;
cin>>T;
while(T--){
scanf("%s%s",s1,s2);
n=strlen(s1);
m=strlen(s2);
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
memset(dp,0x7f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++){
f[i][0]=f[i-1][0]|two(s1[i-1]-'A');
g[n-i+1][0]=g[n-i+2][0]|two(s1[n-i]-'A');
}
for(int i=1;i<=m;i++){
f[i][1]=f[i-1][1]|two(s2[i-1]-'A');
g[m-i+1][1]=g[m-i+2][1]|two(s2[m-i]-'A');
}
int now=1,nxt=0;
for(int i=0;i<=n;i++){
now^=1,nxt^=1;
memset(dp[nxt],0x7f,sizeof(dp[nxt]));
for(int j=0;j<=m;j++){
if(i<n){
int t=dp[now][j];
if(~(f[i][0]|f[j][1])&two(s1[i]-'A')) t-=i+j;
if(~(g[i+2][0]|g[j+1][1])&two(s1[i]-'A')) t+=i+j;
dp[nxt][j]=min(dp[nxt][j],t);
}
if(j<m){
int t=dp[now][j];
if(~(f[i][0]|f[j][1])&two(s2[j]-'A')) t-=i+j;
if(~(g[i+1][0]|g[j+2][1])&two(s2[j]-'A')) t+=i+j;
dp[now][j+1]=min(dp[now][j+1],t);
}
}
}
printf("%d\n",dp[now][m]);
}
}



D - Equipment
       
       当K>=5的时候直接分别选五件对五个属性加成最大的装备即可。K<5的时候可以状态压缩DP,dp[i][j]表示选了i件装备,且j对应的属性已经确定了最大值时能获得的最大加成,转移的时候只要枚举子集和加入的新装备进行更新就行了,这里装备可以重复使用,因为一件装备可以提供5个属性。写的时候用位运算枚举子集,还是很方便的= =

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define N 10009
using namespace std;
int n,m;
int r[N][5];
int dp[6][1<<5];
int main() {
int T;
cin>>T;
int mask=(1<<5);
while(T--){
cin>>n>>m;
for(int i=0;i<n;i++) for(int j=0;j<5;j++) scanf("%d",&r[i][j]);
m=min(5,m);
memset(dp,0,sizeof(dp));
for(int l=0;l<m;l++)
for(int i=0;i<n;i++)
for(int j=0;j<mask;j++){
int t=mask-1-j;
for(int y=t;y;y=(y-1)&t){
int tmp=dp[l][j];
for(int x=0;x<5;x++) if(y&(1<<x)) tmp+=r[i][x];
dp[l+1][j+y]=max(dp[l+1][j+y],tmp);
}
}
printf("%d\n",dp[m][(1<<5)-1]);
}
return 0;
}



E - Furniture Factory

       一秒一秒的模拟,把任务按(截止时间-当前时间-还需要的时间)排序,优先选最小的m个分配。如果模拟的过错中出现负数,表明无解。感觉有点像个弹簧。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define N 109
using namespace std;
typedef pair<int,int> II;
int n,m;
struct order{
int s,w,d,p;
}a[109];
struct node{
int d,w,p;
node(){}
node(int d,int w,int p):d(d),w(w),p(p){}
};
bool f[N][509];
bool cmp1(const order &a,const order &b){return a.s<b.s;}
bool cmp2(const node &a,const node &b){
if(a.d-a.w!=b.d-b.w) return a.d-a.w<b.d-b.w;
return a.w<b.w;
}
int main(){
int T;
cin>>T;
while(T--){
cin>>m>>n;
memset(f,0,sizeof(f));
for(int i=0;i<n;i++) cin>>a[i].s>>a[i].w>>a[i].d,a[i].p=i+1;
sort(a,a+n,cmp1);
vector<node> v;
int t=1,p=0,flag=0;
while(1){
if(p==n&&!v.size()) break;
for(;p<n&&a[p].s<=t;p++) v.push_back(node(a[p].d,a[p].w,a[p].p));
sort(v.begin(),v.end(),cmp2);
if(v.size()&&t+v[0].w>v[0].d){flag=1;break;}
for(int i=0;i<m&&i<v.size();i++)
v[i].w--,f[v[i].p][t]=1;
for(int i=0;i<v.size();i++)
if(v[i].w==0)
v.erase(v.begin()+i),i--;
t++;
}
if(flag){puts("0");continue;}
for(int i=1;i<=n;i++){
vector<II> seg;
int x;
for(int j=1;j<=t;j++){
if(f[i][j]&&!f[i][j-1]) x=j;
if(!f[i][j]&&f[i][j-1]) seg.push_back(II(x,j));
}
printf("%d",seg.size());
for(int i=0;i<seg.size();i++) printf(" %d %d",seg[i].first,seg[i].second);
puts("");
}
}
}


F - Leet

       直接DFS,用map<string,char>记录转换关系,999B搞定,时限3s,27xxms水过,还是有点小压力。

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
int n;
map<char,string> h;
string a,b;
int dfs(int x,int y){
if(!a[x]&&!b[y]) return 1;
if(!a[x]||!b[y]) return 0;
if(h[a[x]]!="")
{
string t=h[a[x]];
int i;
for(i=0;t[i]&&b[y+i]&&t[i]==b[y+i];i++);
if(t[i]) return 0;
return dfs(x+1,y+i);
}
else
{
string t="";
for(int i=0;i<n&&b[y+i];i++){
t.append(1,b[y+i]);
h[a[x]]=t;
if(dfs(x+1,y+i+1)) return 1;
h[a[x]]="";
}
}
return 0;
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n>>a>>b;
h.clear();
cout<<dfs(0,0)<<endl;
}
}



G - Laptop

       因为时间区间满足si<=sj且ei<=ej。任务的安排顺序就可以被确定下来了,按start排序,可以证明任务按这个顺序安排肯定不会比最优解差,调整法什么的搞一搞就行了。那么怎么求最小的间隙个数呢?我们可以这样贪心,从左边开始向右边遍历,对所有的任务进行处理,记录已经安排的任务所能达到的最右边的时间戳x,初始x=end1。处理到第i个任务时,如果满足start_i<=x,说明第i个任务可以紧接着前面的任务安排,x=min(x+1,end_i);否则说明出现了间隙,ans++,x=end_i。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 100009
using namespace std;
struct task{int s,e;}a[N];
int n;
bool flag[N*10];
bool cmp(const task &a,const task &b){
if(a.s!=b.s) return a.s<b.s;
return a.e<b.e;
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n;
memset(flag,0,sizeof(flag));
for(int i=0;i<n;i++) scanf("%d%d",&a[i].s,&a[i].e),a[i].e--;
sort(a,a+n,cmp);
int x=a[0].e,ans=0;
for(int i=1;i<n;i++){
if(a[i].s>x+1) ans++,x=a[i].e;
else x=min(x+1,a[i].e);
}
cout<<ans<<endl;
}
}



H - Neon Sign

       反着考虑,一个三角形边颜色不同时只有两种情况:红红蓝、蓝蓝红。枚举一个点,计算和它相连颜色为蓝色的边的数量c1和颜色为红色的边的数量c2,cnt+=c1*c2。最后答案为总三角形数-cnt/2,因为每个三角形都被计算了两次,所以要除以2。

#include<cstdio>
#include<iostream>
#define N 1009
using namespace std;
int n,a[N][N];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
scanf("%d",&a[i][j]),a[j][i]=a[i][j];
int cnt=0;
for(int i=0;i<n;i++){
int c1=0,c2=0;
for(int j=0;j<n;j++){
if(i==j) continue;
if(a[i][j]) c1++;
else c2++;
}
cnt+=c1*c2;
}
cout<<n*(n-1)*(n-2)/6-cnt/2<<endl;
}
}


I - Pizza Delivery

       可以发现最优的路径肯定是一条左右反复前进的路径,向左走一段路程后再向右走这样交替进行。一个批萨的收益=初始的收益-到达的时间。这个式子的第二项不怎么好维护,我们可以把它转化成其它的形式。考虑我们已经把i~j的批萨都送完了,当前的位置为i,假设我们还要送k个批萨。第k个批萨肯定是1~i-1或者是j+1~n中的某一个,假设为h,那么i~h的这段时间在后面的k个批萨收益计算的第二项中都出现了,所以直接减去dis[i][h]*k的收益,这样式子的第二项就转化成了满足最优子结构的式子。设方程dp[n][n][n][2],dp[i][j][k][0|1]表示已经送完了i~j的批萨,还剩下k个批萨未送,位置在i|j(0|1)时的最大收益。转移有四种,移至左边i-1处送批萨或者不送,移至右边j+1处送批萨或者不送。具体方程如下:

dp[i][j][k][0]=max{dp[i][j+1][k][1]-k*dis[j+1][i],dp[i][j+1][k-1][1]-k*dis[j+1][i]+w[j+1],dp[i-1][j][k][0]-k*dis[i-1][i],dp[i-1][j][k-1][0]-k*dis[i-1][j]+w[i-1]}

最后总的复杂度为O(n^3),用记忆化搜索实现会很方便。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define N 109
#define inf 1000000000
using namespace std;
int n;
int p[N],c[N];
int dp[N][N][N][2];
int go(int l,int r,int k,int t){
int &f=dp[l][r][k][t];
if(f!=-1) return f;
f=0;
if((l==0&&r==n-1)||k==0) return f;
int v1=-inf,v2=-inf;
if(t){
if(r<n-1) v1=max(go(l,r+1,k,1)-k*(p[r+1]-p[r]),go(l,r+1,k-1,1)-k*(p[r+1]-p[r])+c[r+1]);
if(l>0) v2=max(go(l-1,r,k,0)-k*(p[r]-p[l-1]),go(l-1,r,k-1,0)-k*(p[r]-p[l-1])+c[l-1]);
}
else{
if(r<n-1) v1=max(go(l,r+1,k,1)-k*(p[r+1]-p[l]),go(l,r+1,k-1,1)-k*(p[r+1]-p[l])+c[r+1]);
if(l>0) v2=max(go(l-1,r,k,0)-k*(p[l]-p[l-1]),go(l-1,r,k-1,0)-k*(p[l]-p[l-1])+c[l-1]);
}
f=max(v1,v2);
return f;
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=0;i<n;i++) cin>>p[i];
for(int i=0;i<n;i++) cin>>c[i];
int x;
for(x=0;x<n;x++)
if(p[x]>0){
for(int i=n;i>x;i--) p[i]=p[i-1],c[i]=c[i-1];
p[x]=0,c[x]=0;
n++;
break;
}
if(x==n) p[n]=0,c[n++]=0;
memset(dp,-1,sizeof(dp));
int ans=0;
for(int i=1;i<n;i++)
ans=max(ans,go(x,x,i,0));
cout<<ans<<endl;
}
}



J - Soju

       这题我的做法是n*log(n)的,代码又长又搓,正解为O(n)的算法。n*log(n)的做法:把所有的点按y坐标排序,A集合的点标记为0,B集合的点标记为1。模拟一条平行于x轴从底向上扫描的直线,这样平面就被分割成了两个区域。扫描到一个B集合的点P时,所有在直线下面的点R和P的曼哈顿距离为P.x+P.y-R.x-R.y,在直线上面的点S和P的曼哈顿距离为P.x-P.y+S.x-S.y。于是我们开两个map,分别维护直线上面的点的x-y值,和直线下面的点的x+y值。扫描到A集合的点时更新map,扫描到B集合的点时更新答案。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
#define N 100009
using namespace std;
typedef pair<int,int> II;
struct point{
int x,y,t;
}P[N<<1];
int n,m;
multiset<int> U,D;
bool cmp(const point &a,const point &b){
return a.y<b.y;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
D.clear(),U.clear();
cin>>n;
for(int i=0;i<n;i++){
scanf("%d%d",&P[i].x,&P[i].y),P[i].t=0;
U.insert(P[i].y-P[i].x);
}
cin>>m;
for(int i=n;i<n+m;i++) scanf("%d%d",&P[i].x,&P[i].y),P[i].t=1;
sort(P,P+n+m,cmp);
int ans=1000000000;
for(int i=0;i<n+m;i++){
if(P[i].t)
{
int t;
if(D.size()){
t=*(--D.end());
ans=min(ans,P[i].x+P[i].y-t);
}
if(U.size()){
t=*(U.begin());
ans=min(ans,P[i].x-P[i].y+t);
}
}
else
{
U.erase(U.find(P[i].y-P[i].x));
D.insert(P[i].x+P[i].y);
}
}
cout<<ans<<endl;
}
}



L - Turtle

       水题一枚,直接模拟就行了,连数组都不用开。

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

历史上的今天

评论

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

页脚

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