因为我不想用电脑来画图，所以本篇题解大部分都手写。
T1 养花 flower
T2 折射 refract
T3 画作 paint =BZOJ2638 黑白染色
//T1 flower
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=100010,maxm=1100,maxk=100000;
int n,m,len,q,l[maxm],r[maxm],pos[maxn],a[maxn],f[maxm][maxn],b[maxn],ans;
int read()
{
int x=0;
char c=getchar();
while (c<48||c>57)
c=getchar();
while (c>=48&&c<=57)
x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
int max(int a,int b)
{
if (a>b)
return a;
return b;
}
int min(int a,int b)
{
if (a<b)
return a;
return b;
}
int main()
{
freopen("flower.in","r",stdin);
freopen("flower.out","w",stdout);
int i,j,k,L,R,ql,qr;
n=read(),q=read();
len=1000;
m=n/len;
if (m*len<n)
m++;
for (i=1;i<=m;i++)
{
l[i]=r[i-1]+1;
r[i]=i*len;
}
r[m]=n;
for (i=1;i<=n;i++)
{
a[i]=read();
pos[i]=(i-1)/len+1;
}
for (i=1;i<=m;i++)
{
memset(b,0,sizeof(b));
for (j=l[i];j<=r[i];j++)
b[a[j]]=a[j];
for (j=1;j<=maxk;j++)
b[j]=max(b[j],b[j-1]);
for (j=1;j<=maxk;j++)
for (k=0;k<=maxk;k+=j)
f[i][j]=max(f[i][j],b[min(maxk,j+k-1)]-k);
}
while (q--)
{
L=read(),R=read(),k=read();
ql=pos[L],qr=pos[R];
ans=0;
if (ql+1>=qr)
{
for (i=L;i<=R;i++)
ans=max(ans,a[i]%k);
}
else
{
for (i=L;i<=r[ql];i++)
ans=max(ans,a[i]%k);
for (i=l[qr];i<=R;i++)
ans=max(ans,a[i]%k);
for (i=ql+1;i<=qr-1;i++)
ans=max(ans,f[i][k]);
}
printf("%d
",ans);
}
return 0;
}
//T2 refract
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=6010,mod=1000000007;
int n,f[2][maxn],ans;
struct node
{
int x,y;
bool operator <(const node &b)const
{
return x<b.x;
}
}a[maxn];
int inc(int a,int b)
{
a+=b;
if (a>=mod)
return a-mod;
return a;
}
int read()
{
int x=0,f=1;
char c=getchar();
while (c<48||c>57)
f=c=='-'?-1:1,c=getchar();
while (c>=48&&c<=57)
x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int main()
{
freopen("refract.in","r",stdin);
freopen("refract.out","w",stdout);
int i,j;
n=read();
for (i=1;i<=n;i++)
a[i]=(node){read(),read()};
sort(a+1,a+n+1);
for (i=1;i<=n;i++)
{
f[0][i]=f[1][i]=1;
for (j=i-1;j>=1;j--)
{
if (a[i].y>a[j].y)
f[0][i]=inc(f[0][i],f[1][j]);
else
f[1][j]=inc(f[1][j],f[0][i]);
}
}
ans=mod-n;
for (i=1;i<=n;i++)
ans=inc(ans,inc(f[0][i],f[1][i]));
printf("%d
",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
//T3 paint
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=55,inf=0x3f3f3f3f;
int n,m,mx[4]={0,1,0,-1},my[4]={1,0,-1,0},dis[maxn*maxn],id[maxn][maxn],q[maxn*maxn*2],l,r,cnt,ix[maxn*maxn],iy[maxn*maxn],ans;
char ch[maxn];
bool mp[maxn][maxn],vis[maxn*maxn];
int max(int a,int b)
{
if (a>b)
return a;
return b;
}
int min(int a,int b)
{
if (a<b)
return a;
return b;
}
int bfs(int u)
{
int i,v,x,y,tx,ty;
l=maxn*maxn,r=l-1;
q[++r]=u;
vis[u]=1;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[u]=1;
while (l<=r)
{
u=q[l++];
x=ix[u],y=iy[u];
for (i=0;i<=3;i++)
{
tx=x+mx[i],ty=y+my[i];
v=id[tx][ty];
if (tx<1||tx>n||ty<1||ty>m||vis[v])
continue;
if (mp[tx][ty]==mp[x][y])
{
dis[v]=dis[u];
q[--l]=v;
vis[v]=1;
}
else
{
dis[v]=dis[u]+1;
q[++r]=v;
vis[v]=1;
}
if (mp[tx][ty]&&dis[v]>=ans)
return inf;
}
}
int tmp=0;
for (i=1;i<=cnt;i++)
if (mp[ix[i]][iy[i]])
tmp=max(tmp,dis[i]);
return tmp;
}
int main()
{
freopen("paint.in","r",stdin);
freopen("paint.out","w",stdout);
int i,j;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%s",ch+1);
for (j=1;j<=m;j++)
{
mp[i][j]=(ch[j]-48);
id[i][j]=++cnt;
ix[cnt]=i,iy[cnt]=j;
}
}
ans=inf;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
ans=min(ans,bfs(id[i][j]));
printf("%d
",ans);
fclose(stdin);
fclose(stdout);
return 0;
}