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

ydc的博客

 
 
 

日志

 
 

cqoi2013 (bzoj3105~bzoj3109)  

2013-04-09 21:58:25|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
今天学校的模拟测试考了这套题,写下题解吧
题目暂时还看不到
看有没有办法贴一下
方法不是最优方法,但是都能过
cqoi2013 (bzoj3105~bzoj3109) - ydc - ydc的博客
 新NIM
NIM 游戏大家都知道吧,所以这道题就是问你取走若干堆,使得无论别人在剩下的石子里如何取,剩下的异或和恒不等于0
首先是贪心:
最小化取走的,就是最大化取走后剩下来的。题目转变为选取若干堆,不存在异或和为0的子集,最大化其石子数目之和
从大到小排序,如果这一堆可以选就选,否则就一定不选。至于正确性我暂时还不会证明,只不过这种贪心似乎挺常见的(算上这道我已经第四次看到了)
是否可以选的判定,等价于在判断这几堆里是否存在异或和为0的子集
我们对于每一位分开处理,把选不选某一堆石子看作是一个0 or 1的变量,于是这就成了一个异或方程组了
详细地说,对于第i位,以第j堆石子的第i位为(i,j)列的系数,以当前枚举到的石子选不选为变量,常数项为0,用高斯消元法求解
当且仅当异或方程组有且只有每个变量全为0这一组解的情况下此状态合法。也就转化为求解自由元个数问题了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 110
using namespace std;
typedef long long LL;
int n,stone[MAXN];
void read()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&stone[i]);
sort(stone+1,stone+n+1);
}
bool check(int p[],int m)
{
static int a[40][MAXN];
int n=30,h=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=p[j]>>(i-1)&1;
for(int i=1;i<=m;i++)
{
int j=h;
for(;j<=n&&a[j][i]==0;j++);
if(j>n) return false;
if(j!=h)
for(int k=i;k<=m;k++)
swap(a[j][k],a[h][k]);
for(int j=h+1;j<=n;j++)
if(a[j][i])
for(int k=i;k<=m;k++)
a[j][k]^=a[h][k];
h++;
}
return true;
}
LL work()
{
int p[MAXN],s=0;
LL sum=0;
for(int i=n;i>=1;i--)
{
p[++s]=stone[i],sum+=stone[i];
if(check(p,s)==false) s--;
}
for(int i=1;i<=s;i++)
sum-=p[i];
return s==0?-1:sum;
}
int main()
{
read();
printf("%lld\n",work());
return 0;
}



棋盘游戏
很显然平局是坑爹的
白子胜只可能是黑白相邻,此刻输出WHITE 1
所以接下来的分析都是建立在黑子胜的前提下的
通过观察数据+yy发现,似乎或许八成可能大概maybe答案不超过3n?
F[a][b][c][d][step][type]表示黑子在(a,b),白子在(c,d),步数为step,当前是黑/白子走(即type)
记忆化搜索即可
转移如下:
当现在是白子时,在他能走到的4个状态+1里取max
当现在是黑子时,在他能走到的8个状态+1里取min
当step>3n时返回INF
当(a,b)==(c,d)时,如果当前是黑子返回INF,否则返回0。这句话很重要,因为转移时就有可能把黑子被白子吃了的情况转移进黑子取胜的状态了
关键是想到答案不会很大

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 22
using namespace std;
int F[MAXN][MAXN][MAXN][MAXN][MAXN*3][2],n,a,b,c,d;
int DFS(int a,int b,int c,int d,int step,int type)
{
if(step>3*n) return 1<<30;
if(a==c&&b==d) return type==1?1<<30:0;
if(F[a][b][c][d][step][type]) return F[a][b][c][d][step][type];
int &ans=F[a][b][c][d][step][type];
if(type==0)
{
if(a>1) ans=max(ans,DFS(a-1,b,c,d,step+1,1)+1);
if(b>1) ans=max(ans,DFS(a,b-1,c,d,step+1,1)+1);
if(a<n) ans=max(ans,DFS(a+1,b,c,d,step+1,1)+1);
if(b<n) ans=max(ans,DFS(a,b+1,c,d,step+1,1)+1);
}
else
{
ans=1<<30;
if(c>1) ans=min(ans,DFS(a,b,c-1,d,step+1,0)+1);
if(d>1) ans=min(ans,DFS(a,b,c,d-1,step+1,0)+1);
if(c<n) ans=min(ans,DFS(a,b,c+1,d,step+1,0)+1);
if(d<n) ans=min(ans,DFS(a,b,c,d+1,step+1,0)+1);
if(c>2) ans=min(ans,DFS(a,b,c-2,d,step+1,0)+1);
if(d>2) ans=min(ans,DFS(a,b,c,d-2,step+1,0)+1);
if(c+2<=n) ans=min(ans,DFS(a,b,c+2,d,step+1,0)+1);
if(d+2<=n) ans=min(ans,DFS(a,b,c,d+2,step+1,0)+1);
}
return ans;
}
int main()
{
scanf("%d %d %d %d %d",&n,&a,&b,&c,&d);
DFS(a,b,c,d,0,0);
if(abs(a-c)+abs(b-d)==1) printf("WHITE 1\n");
else printf("BLACK %d\n",F[a][b][c][d][0][0]);
return 0;
}

二进制a+b
转化题目后模型如下:
要你构造三个二进制数x,y,z,x有a个1,y有b个1,z有c个1,满足x+y=z且最小化z
DP
记录F[i][a][b][c][type]表示第i位,x已经用了a个1,y已经用了b个1,z已经用了c个1,是否进位。
cqoi今年的第二题、第三题的写转移的时候真的感觉好舒服的。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 40
using namespace std;
int Len(int p)
{
int s=0;
for(int i=p;i;i>>=1)
s++;
return s;
}
void work(int p,int &s)
{
while(p)
{
if(p&1) s++;
p>>=1;
}
}
int sa,sb,sc,sd,n;
void read()
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
int p=max(max(a,b),c);
n=Len(p),work(a,sa),work(b,sb),work(c,sc);
}
void update(int &a,int b)
{
if(a==-1) a=b;
a=min(a,b);
}
int Dp()
{
static int F[2][MAXN][MAXN][MAXN][2];
int cur=0;
memset(F,-1,sizeof(F));
F[cur][0][0][0][0]=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<=min(i,sa);j++)
for(int k=0;k<=min(i,sb);k++)
for(int r=0;r<=min(i,sc);r++)
{
if(F[cur][j][k][r][0]!=-1)
{
update(F[cur^1][j][k][r][0],F[cur][j][k][r][0]);
if(j+1<=sa&&r+1<=sc) update(F[cur^1][j+1][k][r+1][0],F[cur][j][k][r][0]+(1<<i));
if(j+1<=sa&&k+1<=sb) update(F[cur^1][j+1][k+1][r][1],F[cur][j][k][r][0]);
if(k+1<=sb&&r+1<=sc) update(F[cur^1][j][k+1][r+1][0],F[cur][j][k][r][0]+(1<<i));
}
if(F[cur][j][k][r][1]!=-1)
{
update(F[cur^1][j][k][r+1][0],F[cur][j][k][r][1]+(1<<i));
if(j+1<=sa) update(F[cur^1][j+1][k][r][1],F[cur][j][k][r][1]);
if(k+1<=sb) update(F[cur^1][j][k+1][r][1],F[cur][j][k][r][1]);
if(j+1<=sa&&k+1<=sb&&r+1<=sc) update(F[cur^1][j+1][k+1][r+1][1],F[cur][j][k][r][1]+(1<<i));
}
}
cur^=1;
}
return F[cur][sa][sb][sc][0];
}
int main()
{
read();
printf("%d\n",Dp());
return 0;
}


图的逆变换
刚开始题目没怎么看懂……
注意到这样的一副D图
cqoi2013 (bzoj3105~bzoj3109) - ydc - ydc的博客
那么转化为E图后,左边的两条边转化的点能连到的点一定完全一致
换句话说,对于E图中的(i,j),若存在边i->k,j->k,同时存在t使得i与t和j与t一个有边一个没边,就不合法,时间复杂度N^3*T。不过跑起来还是飞快的
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 310
using namespace std;
int n,graph[MAXN][MAXN];
void read()
{
memset(graph,0,sizeof(graph));
int m,a,b;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d",&a,&b);
graph[++a][++b]=1;
}
}
bool check()
{
bool mark1,mark2;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
mark1=false,mark2=false;
for(int k=1;k<=n;k++)
{
if(graph[i][k]&&graph[j][k]) mark1=true;
if(graph[i][k]!=graph[j][k]) mark2=true;
if(mark1==true&&mark2==true) return false;
}
}
return true;
}
int main()
{
int test;
for(scanf("%d",&test);test;test--)
{
read();
printf("%s\n",check()?"Yes":"No");
}
return 0;
}



新数独
这么裸的爆搜!!
恩,剪枝方法很多。lyy大神用的就是靶形数独的二进制压位法,0MS
不过我当时以为效果不是非常好(完全凭yy,并未实践。其效率已被lyy大神的0MS证明了,把我的1000+虐的飞起)
所以我就预处理每一块内的可行方案数
然后我经过实践发现,先搜中间,在搜上下左右,在搜四角,会快一些。
然后超时了!!!超了一个点!!175分
然后我先搜中间,在搜下上左右,在搜四角,最慢的点0.9s过了
然后听卡扎非说裸搜不会超时,我激动的改成左上、上、右上、左、中、右、左下、下、右下的搜索顺序,也就是最普通的那种……
竟然轻松秒杀了!!!!
还我25分!!!
这什么鬼数据啊!!

还好我不是重庆的……
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#define MAXN 15
#define MAXM 400000
#define N 9
using namespace std;
int mark[MAXN][MAXN][MAXN],sol[MAXN][MAXM],s[MAXN],rank[MAXN];
int F[MAXN],use[MAXN],x_up_left[MAXN],y_up_left[MAXN];
void DFS(int p,int now)
{
if(p>N)
{
for(int i=1;i<=N;i++)
{
if(mark[i][1][2]^(F[1]<F[2])) continue;
if(mark[i][2][3]^(F[2]<F[3])) continue;
if(mark[i][4][5]^(F[4]<F[5])) continue;
if(mark[i][5][6]^(F[5]<F[6])) continue;
if(mark[i][7][8]^(F[7]<F[8])) continue;
if(mark[i][8][9]^(F[8]<F[9])) continue;
if(mark[i][1][4]^(F[1]<F[4])) continue;
if(mark[i][2][5]^(F[2]<F[5])) continue;
if(mark[i][3][6]^(F[3]<F[6])) continue;
if(mark[i][4][7]^(F[4]<F[7])) continue;
if(mark[i][5][8]^(F[5]<F[8])) continue;
if(mark[i][6][9]^(F[6]<F[9])) continue;
sol[i][++s[i]]=now;
}
return ;
}
for(int i=1;i<=N;i++)
if(use[i]==0)
{
F[p]=i,use[i]=1;
DFS(p+1,now*10+i);
use[i]=0;
}
}
void read()
{
char flag[10];
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
int p=(i-1)*3+j;
for(int k=1;k<=2;k++)
{
scanf("%s",flag);
if(flag[0]=='<') mark[p][k][k+1]=1;
}
}
for(int j=1;j<=3;j++)
{
int p=(i-1)*3+j;
for(int k=1;k<=3;k++)
{
scanf("%s",flag);
if(flag[0]=='^') mark[p][k][k+3]=1;
}
}
for(int j=1;j<=3;j++)
{
int p=(i-1)*3+j;
for(int k=1;k<=2;k++)
{
scanf("%s",flag);
if(flag[0]=='<') mark[p][3+k][4+k]=1;
}
}
for(int j=1;j<=3;j++)
{
int p=(i-1)*3+j;
for(int k=1;k<=3;k++)
{
scanf("%s",flag);
if(flag[0]=='^') mark[p][3+k][6+k]=1;
}
}
for(int j=1;j<=3;j++)
{
int p=(i-1)*3+j;
for(int k=1;k<=2;k++)
{
scanf("%s",flag);
if(flag[0]=='<') mark[p][6+k][7+k]=1;
}
}
}
DFS(1,0);
int x=1,y=1;
for(int i=1;i<=9;i++)
{
x_up_left[i]=x,y_up_left[i]=y;
y+=3;
if(y>9) x+=3,y=1;
}
}
int h[MAXN][MAXN],l[MAXN][MAXN],ten[MAXN];
bool check(int p,int x,int y,int i)
{
for(int j=x;j<=x+2;j++)
for(int k=y;k<=y+2;k++)
{
int v=sol[p][i]/ten[9-(j-x)*3-k+y-1]%10;
if(h[j][v]||l[k][v]) return false;
}
return true;
}
void add(int p,int x,int y,int i,int mark)
{
for(int j=x;j<=x+2;j++)
for(int k=y;k<=y+2;k++)
{
int v=sol[p][i]/ten[9-(j-x)*3-k+y-1]%10;
h[j][v]=l[k][v]=mark;
}
}
void DFS(int p)
{
if(p>N)
{
for(int i=1;i<=9;i+=3)
for(int j=1;j<=3;j++)
for(int k=0;k<=2;k++)
for(int r=1;r<=3;r++)
printf("%d%c",sol[i+k][F[i+k]]/ten[9-(j-1)*3-r]%10,k==2&&r==3?'\n':' ');
exit(0);
}
int x=x_up_left[p],y=y_up_left[p];
for(int i=1;i<=s[p];i++)
{
if(check(p,x,y,i)==0) continue;
F[p]=i;
add(p,x,y,i,1);
DFS(p+1);
add(p,x,y,i,0);
}
}
void ptm()
{
ten[0]=1;
for(int i=1;i<=9;i++)
ten[i]=ten[i-1]*10;
}
int main()
{
read();
ptm();
DFS(1);
return 0;
}


  评论这张
 
阅读(1665)| 评论(7)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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