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

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

2012 Multi-University Training Contest 3  

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

  下载LOFTER 我的照片书  |
       这场多校又做挫了,水题出的慢,难题没搞出来,最后6题靠后,怨念啊~!最近老是不在状态,每道题都要先SB一下才能过,导致Godot每次都是同题罚时垫底,过几天开始刷比赛,希望能找到一点手感。

1001. Arcane Numbers 1

       看完题目我马上就想到了这题等价与判断找一个x,使得B^x mod A=0。结果实现的时候我突发奇想,YY了一个类似于求gcd的算法来判断,WA了N次还没找到原因,在yh的提醒下改成判质因数包含才过,此时我们的罚时已经成翔了。

1002. Arcane Numbers 2

       这题比赛的时候没做出来,赛后看了题解,感觉挺神的。首先我们按位枚举进行计数,暴力的算法复杂度是O(64*N)的。这里就需要第一个优化了:假如现在统计到了B+A*x项的第K位,我们可以知道B+A*x的第K位和B+A*(x+2^(1+K))的第K位是相同的,这相当于一个周期为2^(K+1)的循环节,所以我们只需要枚举计算0~2^(K+1)-1项就行了。
       
       接下来考虑计算循环节中1的个数,假设统计的是第K位,我们会发现B+A,B+2*A,B+3*A……的第K位是连续的一段0,接着连续的一段1,这样反复交替的。因为相邻两项每次加上A,当且仅当加了2^(K)/A次A时,第K位才可能受到影响,所以我们可以分段来统计,这样复杂度就变成了O(64*2^(K)/(2^(K)/A))=O(64*A)。

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll a,b,n;
ll cal(ll K,ll N){
ll T=(1ll<<K),s=0,ret=0;
while(s<N){
ll x=b+s*a;
ll d=max(1ll,min((T-(x%T))/a,N-s));
ret+=d*((x&T)>0);
s+=d;
}
return ret;
}
ll solve(){
ll ret=0;
for(int i=0;i<63;i++){
ll T=1ll<<(i+1);
if(n/T) ret+=n/T*cal(i,T);
ret+=cal(i,n%T);
}
return ret;
}
int main(){
int T,cas=0;
cin>>T;
while(T--){
cin>>a>>b>>n;
b+=a;
cout<<"Case #"<<++cas<<": "<<solve()<<endl;
}
}




1003. Candy

       封榜后开始做这题,想到了一个n*(2^m)状态,O(m)转移的DP方程,算了一下复杂度,感觉用short数组+一些优化应该是可以过的,结果交上去后返回的不是TLE,竟然是WA。然后就纠结了,一直到比赛结束也没发现哪里错了,后来收到数据后才发现自己的代码没错,数据有问题,输入里少了一个Case,把这个一改就过了,真是坑爹!
       
       我的做法大概是这样:dp[i][j]表示,在已分配了状态j表示的糖果的情况下,0~i-1的小朋友已经达到了欢乐值的下界,第i个小朋友能获得的最大欢乐值,转移分两种,一种是枚举每一颗还没分配的糖果,更新最大值;另一种是当dp[i][j]>=b[i]时,dp[i+1][j]=0。由于K<=10,m<=13,所以用short就行了,最后17xxms AC。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 14
using namespace std;
int n,m,c;
short dp[N][1<<13],like[N][N],b[N];
int main(){
int T,cas=0;
scanf("%d",&T);
T=451; //坑爹的地方,输入T=452
while(T--){
memset(dp,-1,sizeof(dp));
memset(like,0,sizeof(like));
memset(b,0,sizeof(b));
scanf("%d%d%d",&m,&n,&c);
for(int i=0,t;i<n;i++) scanf("%d",&t),b[i]=t;
for(int i=0;i<n;i++)
for(int j=0,t;j<m;j++){
scanf("%d",&t);
like[i][j]=(t?c:1);
}
dp[0][0]=0;
int mask=(1<<m);
for(int i=0;i<n;i++){
for(int j=0;j<mask;j++){
if(dp[i][j]==-1) continue;
if(dp[i][j]>=b[i]) dp[i+1][j]=0;
for(int k=0,t=1;k<m;k++,t*=2)
if(~j&t)
dp[i][j+t]=max((int)dp[i][j+t],dp[i][j]+like[i][k]);
}
}
bool flag=0;
flag=(dp[n][mask-1]!=-1);
printf("Case #%d: ",++cas);
flag?puts("YES"):puts("NO");
}
puts("Case #452: YES"); //最后一组输出YES.
}



1004. Magic Number

       数据有点大,所以没敢直接DP判断,写了一颗Trie树,然后在上面DFS进行统计,貌似做麻烦了,直接DP就能水过。

1005. Triangle LOVE

       hx29分钟2Y了,我们队过的第一道题= =。题意是在一个竞赛图中找一个长度为3的环,这题是CF117C的原题,貌似那次是我第二次参加CF?总之当时不会捉= =。赛后问hx,他表示毫无印象......

1006. Flowers

       yh做的,貌似是个排序神马的,这是我们队过的第二题,此时的我还在苦思冥想为啥我的A的WA了.......

1009. Cut the cake

       不错的DP题,有点类似于Cut the Sequence,用队列维护再加个map就OK了。这题又SB了,一开始想到了正确的解法,结果大脑短路,又把这个解法否定了,绕了半天的圈子终于又回到了起点,此时已经过了20分钟= =

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#define ll long long
#define mod 1000000007ll
#define N 1009
#define inf 1000000000ll;
using namespace std;
typedef pair<int,int> II;
int n,m;
char s[N][N];
short r[N][N],b[N][N],f[N][N],g[N][N],dp[N][N];
map<int,int> t;
map<int,int>::iterator it;
int Q[N],qs,qe;
int main(){
//freopen("in.in","r",stdin);
int T,cas=0;
scanf("%d",&T);
while(T--){
int ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(s[i][j]=='R'){
r[i][j]=1+r[i-1][j];
b[i][j]=0;
if(s[i-1][j]=='B') g[i][j]=1+g[i-1][j];
else g[i][j]=1;
if(s[i][j-1]=='B') f[i][j]=1+f[i][j-1];
else f[i][j]=1;
}
else{
b[i][j]=1+b[i-1][j];
r[i][j]=0;
if(s[i-1][j]=='R') g[i][j]=1+g[i-1][j];
else g[i][j]=1;
if(s[i][j-1]=='R') f[i][j]=1+f[i][j-1];
else f[i][j]=1;
}
if(s[i-1][j-1]==s[i][j]) dp[i][j]=min((int)min(f[i][j],g[i][j]),dp[i-1][j-1]+1);
else dp[i][j]=1;
ans=max(ans,2*dp[i][j]);
//printf("i:%d j:%d dp:%d\n",i,j,dp[i][j]);
//printf("i:%d j:%d r:%d b:%d rb:%d\n",i,j,r[i][j],b[i][j],rb[i][j]);
}
for(int i=1;i<=n;i++){
t.clear();
qs=qe=0;Q[qe++]=0;
for(int j=1;j<=m;j++){
while(qs<qe&&r[i][j]<=r[i][Q[qe-1]]){
qe--;
if(qs!=qe){
int tmp=r[i][Q[qe]]-Q[qe-1];
it=t.find(tmp);
if(it->second==1) t.erase(tmp);
else it->second--;
}
}
Q[qe++]=j;
if(qs+1!=qe) t[r[i][j]-Q[qe-2]]++;
if(t.size()) ans=max(ans,j+(--t.end())->first);
}
t.clear();
qs=qe=0;Q[qe++]=0;
for(int j=1;j<=m;j++){
while(qs<qe&&b[i][j]<=b[i][Q[qe-1]]){
qe--;
if(qs!=qe){
int tmp=b[i][Q[qe]]-Q[qe-1];
it=t.find(tmp);
if(it->second==1) t.erase(tmp);
else it->second--;
}
}
Q[qe++]=j;
if(qs+1!=qe) t[b[i][j]-Q[qe-2]]++;
if(t.size()) ans=max(ans,j+(--t.end())->first);
}
}
printf("Case #%d: %d\n",++cas,2*ans);
}
}



1010. MAP

       坑爹的阅读题+模拟题,题意各种蛋疼,WA了7次后hx终于发现了BUG,把这题过掉了。此时Godot的罚时已经逆天了。。。。
  评论这张
 
阅读(188)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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