高橋・直樹's Blog

http://ctf.idf.cn/index.php?g=game&m=article&a=index&id=59

题目：红与黑

描述：

解决方案：

通过stegsolve.jar，获取不同通道的图像数据。一种常见的JPG隐写方式，参见：

http://blog.csdn.net/program_think/article/details/6462625

获得图像：

获得flag.

FLAG：

wctf{h0w_Can_Make_A_steg}

http://www.lydsy.com/JudgeOnline/problem.php?id=3203

题意

题目很复杂0.0

对于每一关，会加一个血量为a[i]的僵尸在队首，每个僵尸之间间隔d，

队首的坐标为x[i]，僵尸移动速度1单位长度/s

每次求一个植物的最小攻击力y[i]点血/s，使得出题人不被吃掉的情况下，打死所有僵尸。

注意：如果某次植物攻击，大于当前僵尸的血量，超出的攻击力会打到下一个僵尸。

题解

设s[i]=sigm(a[i])

则y[i]=max{(s[i]-s[j-1])/(x[i]+（i-j）*d)}  (i≥j);

于是对于每个僵尸j我们设点（j*d，s[j-1]），

那么答案就相当于每次给定一个点（x[i]+i*d，s[i]），

在当前僵尸中求一个点使得这两个点的斜率最大。

这样维护下凸壳，再二分就可以了。

#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=100010;
const double eps=1e-8;
struct point
{
    ld x,y;
}p[N],c;
int n,q[N],top;
ld s[N],x[N],d,ans;
 
ld cross(point c,point a,point b)
{
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
 
int find()
{
    int tmp=1,l=2,r=top,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(cross(c,p[q[mid]],p[q[mid-1]])<-eps)
            tmp=max(tmp,mid),l=mid+1;
        else r=mid-1;
    }
    return tmp;
}
  
int main()
{
    double o1,o2;
    scanf("%d%lf",&n,&o1);d=o1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&o1,&o2);s[i]=o1,x[i]=o2,s[i]+=s[i-1];
        p[i].x=i*d;p[i].y=s[i-1];
    }
    int j;
    for(int i=1;i<=n;i++)
    {
        while(top>1 && cross(p[q[top-1]],p[q[top]],p[i])<-eps) top--;
        q[++top]=i;c.x=x[i]+i*d;c.y=s[i];j=q[find()];
        ans+=(c.y-p[j].y)/(c.x-p[j].x);//printf("%.5lf\n",(double)ans);
    }
    printf("%.0lf\n",(double)ans);
}

http://www.lydsy.com/JudgeOnline/problem.php?id=3144

题意

一个n*m*k的立方体，从侧面切过去，切出一个N*M的切面（不是一个面，是崎岖的0.0），切到的每个点都有一个权值v（x,y,z）。

且切到的每个点与四周被切点的高度差（即z轴坐标的差）不能超过给定的D（切面要平滑0.0）。

最小化∑v(x,y,z){(x,y,z)∈切面}

题解

首先做k+1层n*m的点，对于第i层的每个点向i+1层的该点连容量为v（x,y,i)的边。

s向最下层的每个点连+∞的边，最上层连t，容量为+∞

这样之后就把点权转到了边上，做最小割。

然后处理高度差D的限制，

把第i层（x,y）的每个点向它处在i-D层的周围的点连+∞的边。

转换成割来考虑的话，就是如果把第i层（x,y）到i+1层的（x,y）割掉的话，

那么它周围的点必须割在差在D以内的边，画个图就很明显啦~~

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;
const int N=100001,M=6000000;
const int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
int u[M],v[M],w[M],next[M],head[N],k=1;
int d[N],pre[N],low[N],vd[N],cur[N];
int p,q,r,D,s,t;
 
int num(int x,int y,int z)
{   
    if(x<1||y<1||z<1||x>p||y>q||z>(r+1)) return N-1;
    return (z-1)*(p*q)+(x-1)*q+y;
}
 
int solve(int s,int t) 
{ 
    int now=s,i,ans=0; 
    low[s]=INT_MAX;vd[0]=t; 
    while(d[s]<t) 
    { 
        for(i=cur[now];i;i=next[i]) 
            if(w[i]>0 && d[now]==d[v[i]]+1) 
                break; 
        cur[now]=i; 
        if(i) 
        { 
            low[v[i]]=min(low[now],w[i]);pre[v[i]]=i;now=v[i]; 
            if(now==t) 
            { 
                for(;now!=s;now=u[pre[now]]) 
                    w[pre[now]]-=low[t],w[pre[now]^1]+=low[t]; 
                low[s]=INT_MAX;ans+=low[t]; 
            } 
        } 
        else
        { 
            if(!--vd[d[now]]) break; 
            d[now]=t; 
            for(i=head[now];i;i=next[i]) 
                if(w[i]>0 && d[now]>d[v[i]]+1) 
                    d[now]=d[v[i]]+1,cur[now]=i; 
            vd[d[now]]++; 
            if(now!=s)  now=u[pre[now]]; 
        } 
    } 
    return ans; 
}
void add(int x,int y,int z)
{
    u[++k]=x;v[k]=y;w[k]=z;next[k]=head[x];head[x]=k;
    u[++k]=y;v[k]=x;w[k]=0;next[k]=head[y];head[y]=k;
}
int main()
{
    scanf("%d%d%d",&p,&q,&r);
    scanf("%d",&D);
    s=p*q*(r+2)+1;t=s+1;
    for(int i=1;i<=p;i++)
        for(int j=1;j<=q;j++)
        {
            add(num(i,j,r+1),t,INT_MAX);add(s,num(i,j,1),INT_MAX);
            for(int o=0;o<4;o++)
                add(num(i,j,r+1),num(i+dx[o],j+dy[o],r+1-D),INT_MAX);
        }
    int x;
    for(int k=1;k<=r;k++)
        for(int i=1;i<=p;i++)
            for(int j=1;j<=q;j++)
            {
                scanf("%d",&x);
                add(num(i,j,k),num(i,j,k+1),x);
                for(int o=0;o<4;o++)
                    add(num(i,j,k),num(i+dx[o],j+dy[o],k-D),INT_MAX);
            }
    printf("%d\n",solve(s,t));
}

http://www.lydsy.com/JudgeOnline/problem.php?id=3119

题意

要求构造一个序列，

满足，长度为N，和为M，第一个数是X，

从第二项开始一定比前一项大A或比前一项小B；

保证有解。

题解

如果在第i个位置上+A，他会对所有i以后（N-i+1）个数造成影响，

即对和造成的影响是+(N-i+1）*A

那么设+A操作总共对x个数造成影响，-B操作总共对y个数造成影响。

列得：

     xA-yB=M-N*X;

     x+y=n*(n-1)/2;

可以把x、y解出来。

问题就变成了用1..n-1之间的数去凑x或者y。

就从n-1开始，不断减小x就可以了。

#include<cstdio>
#include<cstring>
using namespace std;
long long N,M,n,m,x,y,X,A,B;
bool f[100011];
int main()
{
	scanf("%lld%lld%lld%lld%lld",&N,&X,&A,&B,&M);
	m=M-N*X;n=N*(N-1)/2;
	x=(m+B*n)/(A+B);y=n-x;
	int now=N-1;
	while(x)
	{
		if (x-now>=0)
			f[now]=1,x-=now;
		now--;
	}
	printf("%lld",X);
	for(int i=N-1;i>=1;i--)
	{
		if(f[i]) X+=A;else X-=B;
		printf(" %lld",X);
	}
	puts("");
}

http://www.lydsy.com/JudgeOnline/problem.php?id=3106

题意

一个n*n（n>=2）棋盘上有黑白棋子各一枚。游戏者A和B轮流移动棋子，A先走。

        A：移动白棋子。可以往上下左右四个方向之一移动一格。

        B：移动黑棋子。可以往上下左右四个方向之一移动一格或者两格。

当某游戏者把自己的棋子移动到对方棋子所在的格子时就赢了。两个游戏者都很聪明，当可以获胜时会尽快获胜，只能输掉的时候会尽量拖延时间。判断谁会赢，需要多少回合。

题解

不看题解不会- =

然后找到一种很奇怪的做法。。

首先没有平局- =，

如果黑色不在白色的旁边，黑色一定赢（因为白色永远吃不到它0.0）。

接下来的问题是求需要多少步

暴力，然后，其实是卡时。。

我们猜测答案不超过3n步。。。。

记忆化搜索，f[a][b][c][d][x][y]表示白(a,b)，黑(c,d)，x步，y表示当前游戏者是谁。

于是就过了，不明真相。

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