改程序之前，写程序之前，确保自己理解了，不然效率会很低。
写程序少用复制黏贴，容易细节出错，不好调试。
T1：
题意：
给定两字符串，判断B串是否是A串的字串且输出B串每个字母的匹配位置字典序最大的匹配方案。
分析：
典型贪心，特别是“字典序最大”，不过好久没写贪心了有点迟钝233.
从后向前遍历B串和A串，找到B串单词的第一个匹配位置即可比较下一个。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define ll long long
#define inf 2e8
#define modd 1e9+7
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define minus(x) memset(x,-1,sizeof(x))
#define each(i,n) for(int i=1;i<=n;i++)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "door"
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=1e6+5;
int lena,lenb,cur,ans[Maxn];
char a[Maxn],b[Maxn],tmp;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void init()
{
scanf("%s",a);lena=strlen(a);
if(!lena){printf("No");return;}
scanf("%s",b);lenb=strlen(b);
cur=lena-1;
}
void work()
{
if(lenb>lena){
printf("No");return;
}
for(int i=lenb-1;i>=0;i--){
for(cur;cur>=0;cur--)
if(a[cur]==b[i]){
ans[i]=cur+1;cur--;break;
}
}
if(ans[0]){
printf("Yes\n");
for(int i=0;i<lenb;i++)
printf("%d\n",ans[i]);
}
else printf("No");
}
void debug()
{
//
}
int main()
{
freopen(PROC".in","r",stdin);
freopen(PROC".out","w",stdout);
init();
work();
//debug();
return 0;
}T2：
题意：
给定一地图，偶数行相连的0看做一权值为0的个数的点，求从第一行走到第n行的最大权值和。
分析：
显然可以DP，数据范围简直是为DP设计的，f[i][j]表示i行j列及以下的最大权值和，判断能不能走到就对无法到达下一层且不是最后一层的位置f值直接置0即可。
图论做法：缩点，拓扑排序避免多次修改以后直接走SPFA；适用宽度更大的情况。
拓展：
读错题了以为只取经过的位置的权值，那么就要加一维表示来的方向，再在同一行从左向右，从右向左各扫一遍记录从左来或从右来的值。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define ll long long
#define inf 2e8
#define modd 1e9+7
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define minus(x) memset(x,-1,sizeof(x))
#define each(i,n) for(int i=1;i<=n;i++)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "ant"
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=1e3+5;
int n,m,ans,idx;
int a[5*Maxn][2*Maxn],f[5*Maxn][2*Maxn];
int maxn[Maxn*2],num[Maxn*2];
char tmp;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void init()
{
n=read();m=read();
if((!n)||(!m))return;
each(i,n){
while(tmp>'1'||tmp<'0')tmp=getchar();
each(j,m){
a[i][j]=tmp-'0';
tmp=getchar();
}
}
}
void work()
{
for(int i=n;i>0;i--){
int lll=!(i%2);
num[0]=maxn[0]=0;
idx=0;
for(int j=1;j<=m;j++)
if(!a[i][j]){
maxn[idx]=max(maxn[idx],f[i+1][j]);
num[idx]+=lll;
}
else ++idx,maxn[idx]=num[idx]=0;
idx=0;
for(int j=1;j<=m;j++)
if(!a[i][j]){
if(maxn[idx]||i==n)
f[i][j]=maxn[idx]+num[idx];
}
else ++idx;
}
each(j,m)ans=max(ans,f[1][j]);
if(ans)printf("%d",ans);
else printf("-1");
}
void debug()
{
//
}
int main()
{
freopen(PROC".in","r",stdin);
freopen(PROC".out","w",stdout);
init();
work();
//debug();
return 0;
}T3：
题意：
在矩阵里求长度为wi的线段的条数（可连点）；
分析：
显然知道若该线段“长”为x,“宽”为y，则条数为(n-x)*(m-y)*2；那么重点是求x^2+y^2=wi^2的整数解。
考虑剪枝，但若用暴力不好剪枝，继续分析发现，可以用gcd来将方程变为求完全平方数（如下：
x^2+y^2=wi^2;
y=sqrt((wi-x)(wi+x));
那么此时提出两式的gcd，根号内内容互质又能开出正整数，则只能是两个完全平方数，但这里直接求满足完全平方数的两式还是不方便，考虑变形：
令 a*a=wi-x,/gcdb*b=wi+x/gcd;
则a*a+b*b=2*wi/gcd；
至此就缩小了数据范围。
不过引入了一个变量，所以我们要枚举两个变量，由于右式是除法，则只用枚举sqrt(2*wi)，再在下面讨论两种情况即可。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define ll long long
#define inf 2e8
#define modd 1e9+7
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define minus(x) memset(x,-1,sizeof(x))
#define each(i,n) for(int i=1;i<=n;i++)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "amount"
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
int t;
long long n,m,w,ans,a,b,ww;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void init()
{
n=read();m=read();t=read();
}
ll _gcd(ll xxx,ll yyy)
{
return yyy==0?xxx:_gcd(yyy,xxx%yyy);
}
void work()
{
w=read();ans=0;
if(w<n)ans+=(n-w)*m;
if(w<m)ans+=(m-w)*n;
ww=w*w;w<<=1;
for(ll i=1;i*i<=w;i++)
if(!(w%i)){
for(ll j=1;j*j<=w/i/2LL;j++){
long long k=floor((double)sqrt((double)w/(double)i-(double)j*(double)j));
//if(j>=k)continue;
if(k*k!=w/i-j*j)continue;
if(k==j||_gcd(k,j)!=1ll)continue;
//if(k<=0||j<=0)continue;
a=k*k*i-j*j*i;a/=2ll;
b=i*k*j;
//if(a*a+b*b!=ww)continue;
//if(i!=_gcd(w/2-a,w/2+a))continue;
if(a<n&&b<m)ans+=(n-a)*(m-b);
if(b<n&&a<m)ans+=(m-a)*(n-b);
}
if(i*i!=w)
for(int j=1;j*j<=i/2LL;j++){
long long k=floor((double)sqrt((double)i-(double)j*(double)j));
// if(j>=k)continue;
if(k*k!=i-j*j)continue;
if(k==j||_gcd(k,j)!=1ll)continue;
//if(k<=0||j<=0)continue;
a=k*k*w/i-j*j*w/i;a/=2ll;
b=k*j*w/i;
//if(a*a+b*b!=ww)continue;
//if(w/i!=_gcd(w/2-a,w/2+a))continue;
if(a<n&&b<m)ans+=(n-a)*(m-b);
if(b<n&&a<m)ans+=(m-a)*(n-b);
}
}
printf("%I64d ",ans);
}
void debug()
{
//
}
int main()
{
freopen(PROC".in","r",stdin);
freopen(PROC".out","w",stdout);
init();
each(i,t)
work();
//debug();
return 0;
}