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

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

Fudan University Local Contest 2012  

2012-06-14 22:18:56|  分类: 比赛总结 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       上个星期六在VJ上做的一场训练赛,被卡成狗了。现场榜的A和B,K和L的顺序反了。然后我一刷榜L题2分钟被秒了,A题6分钟被秒了,顿时吓尿了,瞎写了个暴力水A,然后就悲剧了......明明是一道有点小蛋疼的搜索,结果被我当成水题来乱搞,直到最后才AC,惨不忍睹......在标程+数据+神牛blog的帮助下,今天终于finish了最后一道题,写个小结吧。

       这题直接搜会超时,我们需要一点小优化。因为每次选一架飞机起飞的过程中,其它的飞机都不能动,所以我们只能选和起飞点直接连通的飞机。先进行这样的预处理,定义一个状态s,表示飞机场上对应的格子有无飞机(不管颜色),总共有2^9种状态,如果对与s,我们选择一个和起飞点直接连通的有飞机的格子,并把其置0,得到状态ss,那么s和ss连一条有向边。然后就可以利用这个状态转移图直接dfs了。

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
struct edge{
int v,p;
edge(){}
edge(int v,int p):v(v),p(p){}
};
vector<edge> G[256];

int dx[]={0,1,0,-1},
dy[]={1,0,-1,0};

int mat[5][5],vis[5][5],flag[1<<8],ans;

void predfs(int s,int x,int y){
vis[x][y]=1;
if(mat[x][y]==2){
int v=s,p=(x-1)*3+y-1;
v^=(1<<(8-p));
G[s].push_back(edge(v,p));
return;
}
for(int i=0;i<4;i++){
int tx=x+dx[i],ty=y+dy[i];
if(mat[tx][ty]&&!vis[tx][ty])
predfs(s,tx,ty);
}
}
void dfs(int s,int color){
if(!s){if(!flag[color]) flag[color]=1,ans++;return;}
for(int i=0;i<G[s].size();i++){
int ts=G[s][i].v,p=G[s][i].p;
int tmp=mat[p/3+1][p%3+1];
mat[p/3+1][p%3+1]=1;
dfs(ts,color*2+tmp-2);
mat[p/3+1][p%3+1]=tmp;
}
}
int main(){
for(int s=1;s<256;s++)
{
for(int t=s,i=3;i;i--)
for(int j=3;j;j--)
mat[i][j]=(t&1)+1,t>>=1;
memset(vis,0,sizeof(vis));
predfs(s,1,1);
}
int cas=0;
char str[3][5];
while(scanf("%s%s%s",str[0],str[1],str[2])+1){
int s=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++){
mat[i+1][j+1]=(str[i][j]=='*'?1:(str[i][j]=='B'?2:3));
s=s*2+(str[i][j]!='*');
}
ans=0;
memset(flag,0,sizeof(flag));
dfs(s,0);
printf("Case %d: %d\n",++cas,ans);
}
return 0;
}




       DP,dp[i][j]表示用前j个石头组成长度为i的模式的方式一共有多少种,dp[i][j]=sum{dp[i-k][j-1]*C[i][k],1<=k<=a[i]}。可以用滚动数组,使空间达到O(len)。

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define ll long long
#define mod 1000000007
using namespace std;
int n,a[109];
int dp[10009],C[10009][109];
int main(){
int cas=0;
for(int i=0;i<10009;i++){
C[i][0]=1;
for(int j=1;j<109&&j<=i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
while(scanf("%d",&n)+1){
for(int i=0;i<n;i++) scanf("%d",a+i);
int cnt=0;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=0;i<n;i++){
cnt+=a[i];
for(int j=cnt;j>=1;j--)
for(int k=1;k<=a[i]&&k<=j;k++)
dp[j]=(dp[j]+1ll*dp[j-k]*C[j][k])%mod;
}
int ans=0;
for(int i=1;i<=cnt;i++) ans=(ans+dp[i])%mod;
printf("Case %d: %d\n",++cas,ans);
}
return 0;
}



       还是DP,只不过写起来有点繁琐,先预处理一下会好很多。把每一位都预处理出min和max,表示这一位的数只能从min到max,比如问号就是0-9。并且对于位数不够字符串,把高位补成0。然后dp[i][j]表示从低到高至第i位并进位为j的时候的方案数。最后答案为dp[n][0]。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;
int n;
int d[3][20],u[3][20];
ll dp[20][2];

void init(string s){
string a,b,c;
int i,j;
memset(d,0,sizeof(d));
memset(u,0,sizeof(u));
for(i=0;s[i]!='+';i++);
for(j=0;s[j]!='=';j++);
a=s.substr(0,i);
b=s.substr(i+1,j-i-1);
c=s.substr(j+1,s.size()-j-1);
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
reverse(c.begin(),c.end());
n=max(a.size(),max(b.size(),c.size()));
for(i=0;i<a.size();i++){
if(a[i]=='?') d[0][i]=0,u[0][i]=9;
else d[0][i]=u[0][i]=a[i]-'0';
}
if(a.size()>1&&a[a.size()-1]=='?') d[0][a.size()-1]=1;
for(i=0;i<b.size();i++){
if(b[i]=='?') d[1][i]=0,u[1][i]=9;
else d[1][i]=u[1][i]=b[i]-'0';
}
if(b.size()>1&&b[b.size()-1]=='?') d[1][b.size()-1]=1;
for(i=0;i<c.size();i++){
if(c[i]=='?') d[2][i]=0,u[2][i]=9;
else d[2][i]=u[2][i]=c[i]-'0';
}
if(c.size()>1&&c[c.size()-1]=='?') d[2][c.size()-1]=1;
}
void gao(){
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=0;i<n;i++)
for(int j=0;j<2;j++){
if(!dp[i][j]) continue;
for(int x=d[0][i];x<=u[0][i];x++)
for(int y=d[1][i];y<=u[1][i];y++){
int t=(x+y+j)%10,tt=(x+y+j)/10;
if(t>=d[2][i]&&t<=u[2][i]) dp[i+1][tt]+=dp[i][j];
}
}
}
int main(){
int cas=0;
string s;
while(cin>>s){
init(s);
gao();
printf("Case %d: %lld\n",++cas,dp[n][0]);
}
return 0;
}


       神题,给一个图,删除两条边使得这个图连通且存在欧拉回路。先统计度数为奇数的点的个数,如果不为2或者4,那么肯定无解。先考虑4个点的情况,直接枚举删除的两条边O(3)然后并查集check。2个点的情况就不好搞了,设两个点为u、v。首先我们找出所有的x,满足x-u,x-v。那么满足条件的方案必然是选某一个x,然后删除x-u和x-v。但x的个数可能会非常的多,直接暴力是不行的。然后我就蛋疼了.....想了好久都没想到一种好的解决方案,只好看标程怎么搞,结果发现标程居然是直接暴力的- -|||,无语了,稍微吐嘈一下fudan的出题人,这也太懒了,居然写个暴力做标程。难道这题就没有优美做法吗?答案是NO,传送门7k+神牛的神做法。先把所有的x-u、x-v都删除,得到一个新的图GG。假设存在一组解(y->u,y->v)。那么对于任意的x,只要满足下面两种情况之一,那么(x->u,x->v)也是一组满足条件的解。
(1)在GG上和u或者v连通。
(2)和某一个满足条件的非自身的x连通。
于是我们就可以先找出满足条件的字典序最优对,然后check()一下是否能够使得原图变成连通且存在欧拉回路的图。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define N 200009
using namespace std;
int n,m;
int a[N],b[N],d[N];
int tf[N],vis[N],fa[N];
typedef pair<int,int > PII;
typedef pair<pair<int,int>,int > PPI;
int find(int a){return fa[a]==a?a:fa[a]=find(fa[a]);}
bool union_set(int a,int b){
a=find(a),b=find(b);
if(a==b) return false;
fa[a]=b;
return true;
}
bool check(){
int c=n-1;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=m;i;i--)
if(!tf[i])
c-=union_set(a[i],b[i]);
return !c;
}
int main(){
int cas=0;
while(scanf("%d%d",&n,&m)+1){
printf("Case %d: ",++cas);
memset(tf,0,sizeof(tf));
memset(d,0,sizeof(d));
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++){
scanf("%d%d",a+i,b+i);
d[a[i]]^=1;
d[b[i]]^=1;
}
if(!check()){puts("NO");continue;}
vector<int> odd;
for(int i=1;i<=n;i++)
if(d[i])
odd.push_back(i);
if(!odd.size()||odd.size()>4){puts("NO");continue;}
if(odd.size()==2)
{
int u=odd[0],v=odd[1];
for(int i=1;i<=m;i++){
if(a[i]==u) vis[b[i]]=i;
else if(b[i]==u) vis[a[i]]=i;
}
vector<PPI> del;
for(int i=1;i<=m;i++){
if(a[i]==v&&vis[b[i]]){
tf[i]=tf[vis[b[i]]]=1;
del.push_back(PPI(PII(min(i,vis[b[i]]),max(i,vis[b[i]])),b[i]));
}
else if(b[i]==v&&vis[a[i]]){
tf[i]=tf[vis[a[i]]]=1;
del.push_back(PPI(PII(min(i,vis[a[i]]),max(i,vis[a[i]])),a[i]));
}
}
check();
sort(del.begin(),del.end());
memset(vis,0,sizeof(vis));
for(int i=0;i<del.size();i++)
vis[find(del[i].second)]=del[i].second;
PPI ans;
int ok=0;
for(int i=0;i<del.size();i++){
int t=find(del[i].second);
if(t==find(u)||t==find(v)||vis[t]!=del[i].second){
ok=1;
ans=del[i];
break;
}
}
if(ok){
memset(tf,0,sizeof(tf));
tf[ans.first.first]=tf[ans.first.second]=1;
if(!check()) ok=0;
}
if(ok) printf("YES\n%d %d\n",ans.first.first,ans.first.second);
else puts("NO");
}
else
{
vector<int> v;
for(int i=1;i<=m;i++)
if(d[a[i]]&&d[b[i]])
v.push_back(i);
sort(v.begin(),v.end());
int ok=0,e1,e2;
for(int i=0;!ok&&i<v.size();i++)
for(int j=i+1;!ok&&j<v.size();j++){
e1=v[i],e2=v[j];
d[a[e1]]^=1,d[b[e1]]^=1;
d[a[e2]]^=1,d[b[e2]]^=1;
if(!d[odd[0]]&&!d[odd[1]]&&!d[odd[2]]&&!d[odd[3]]){
tf[e1]=1,tf[e2]=1;
if(check()) ok=1;
tf[e1]=0,tf[e2]=0;
}
d[a[e1]]^=1,d[b[e1]]^=1;
d[a[e2]]^=1,d[b[e2]]^=1;
}
if(ok) printf("YES\n%d %d\n",e1,e2);
else puts("NO");
}
}
}




       裸划分树,正好趁这个机会学习了一下这个神奇的数据结构。

#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#define N 100009
using namespace std;
int n;
int a[N],od[N];
int left[20][N],val[20][N];
bool cmp(const int &x,const int &y){return a[x]<a[y];}
void build(int l,int r,int d){
if(l==r) return;
int mid=(l+r)>>1,p=0;
for(int i=l;i<=r;i++){
if(val[d][i]<=mid){
val[d+1][l+p]=val[d][i];
left[d][i]=++p;
}
else
{
left[d][i]=p;
val[d+1][mid+i+1-l-p]=val[d][i];
}
}
build(l,mid,d+1);
build(mid+1,r,d+1);
}
int query(int s,int e,int k,int l,int r,int d){
if(l==r) return l;
int mid=(l+r)>>1,ss,ee;
ss=(s==l?0:left[d][s-1]);
ee=left[d][e];
if(ee-ss>=k) return query(l+ss,l+ee-1,k,l,mid,d+1);
return query(mid+1+(s-l-ss),mid+1+(e-l-ee),k-(ee-ss),mid+1,r,d+1);
}
int main(){
int cas=0,m,l,r;
while(scanf("%d",&n)+1){
printf("Case %d:\n",++cas);
for(int i=1;i<=n;i++) scanf("%d",a+i),od[i]=i;
sort(od+1,od+n+1,cmp);
for(int i=1;i<=n;i++) val[0][od[i]]=i;
build(1,n,0);
scanf("%d",&m);
while(m--){
scanf("%d%d",&l,&r);
printf("%d\n",a[od[query(l,r,(r-l)/2+1,1,n,0)]]);
}
}
}



       神题,这是CLJ神牛的互测题,弱菜看完一点想法都没有,找到解题报告后才明白怎么做,解体报告传送门

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,K;
struct edge{
int a,b,c,x;
}E[100009];
int fa[50009];

bool cmp(const edge &a,const edge &b){if(a.c==b.c) return a.x<b.x;return a.c<b.c;}
int find(int a){return a==fa[a]?a:fa[a]=find(fa[a]);}
bool union_set(int a,int b){a=find(a),b=find(b);if(a==b) return false;fa[a]=b;return true;}

int cal(int &cnt,int x){
int ret=0;
cnt=0;
for(int i=0;i<m;i++) if(!E[i].x) E[i].c+=x;
for(int i=0;i<n;i++) fa[i]=i;
sort(E,E+m,cmp);
for(int i=0,c=n-1;c;i++)
if(union_set(E[i].a,E[i].b))
c--,ret+=E[i].c,cnt+=!E[i].x;
for(int i=0;i<m;i++) if(!E[i].x) E[i].c-=x;
return ret;
}

int main(){
int cas=0;
while(scanf("%d%d%d",&n,&m,&K)+1)
{
for(int i=0;i<m;i++)
scanf("%d%d%d%d",&E[i].a,&E[i].b,&E[i].c,&E[i].x);
int cnt,s=-100,e=100,mid,res;
while(s<=e){
mid=(s+e)/2;
cal(cnt,mid);
if(cnt>=K) res=mid,s=mid+1;
else e=mid-1;
}
printf("Case %d: %d\n",++cas,cal(cnt,res)-K*res);
}
}





        又一道神题,直接输出答案=(Q+1)/(P+2),解体报告见7k+大神。PS:那个组合数学上的公式的证明实在是太巧妙了!!!!!!
  评论这张
 
阅读(354)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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