第一题：
LGTB 得到了一个序列，他想在这个序列中选择一个最长的连续子序列，使得这个子序列的最大公约数等于1。请告诉他他能得到的最大长度，如果没有这样的序列，输出-1.
对于50% 的数据，1 <=n <= 1000
对于100% 的数据，1 <=n <= 10^5 1 <= ai <= 10^9
解：首先，读题。。这个序列的公约数，是公共约数，所以，只要这个序列中有两个数的最大公约数为1，那么无论这个序列有多长，只要符合这个条件，那么它们所有的最大公约数，为1。所以答案为-1，或者，n。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100005
using namespace std;
int n,v[maxn],f[maxn],ans;
int gcd(int a,int b)
{
return b==?a:gcd(b,a%b);
}
int main()
{
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%d",&v[i]);
for (int i=;i<=n;i++)
{
if (gcd(v[i],v[i-])==){
printf("%d",n);
return ;
}
}
if (n==&&v[n]==) printf("");
else printf("-1");
return ;
}
第二题：
LGTB 新买了一张n * m 的矩(桌) 阵(子)，他想给某些1 * 1 的小矩形染色，使得染色之后，原矩阵的每个n * n 的子矩阵中都包含恰好k 个被染色了的小矩形。他想知道有多少种染色方案能让他满足上述要求。因为答案可能很大，请输出方案数模1000000007 (10^9 + 7) 后的值.
对于15% 的数据，1 <=n *m <= 20, n <= m
对于40% 的数据，1 <=n <= 10, n <= m <= 1000
对于100% 的数据，1 <= n <= 100, n <= m <= 10^18, 0 <= k<= n^2
解： 这道题，考试的时候没怎么仔细想。因为不知道为什么考试的时候根本没有心情思考，一直很浮躁，不在状态。
首先，要先找到：对于每n列中的第 i 列中的被染色数等于第n+i 列的染色数。以下为证明：
| i (1,2,3,......)对应当前列有第 i 个矩阵经过 n=4,m=9 | ||||||||
| 1,2 | 1,2,3 | 1,2,3,4 | 2,3,4,5 | 3,4,5,6 | 4,5,6 | 5,6 | ||
|
每列的染色数 |
||||||||
|
a |
b | c | d | a | b | c | d | a |
注意到，红色部分，都是染色为a，因为1矩阵染了a，那2,3,4,5矩阵也该染a个，6矩阵也该染a个，才满足所有矩阵染的数相等。
所以我们可以直接只算n列为一块，就可以了。但是最后一块不一定为n列。
那么用dp[i][j]表示n列中的第 i 列染 j 个的方案数。dp[i][j]=∑(dp[i-1][j-p]*C(n,p)^T[i])%P。T[i]表示 i 这一列(在n列中的位置)在m中重复了几次。如红色部分所在列，重复了3次，而剩下部分所在列只重复了2次，也就是“最后一块不一定为n列”的解释。对于所有第 i 列而言，j<=i*n&&j<=k，染 p (p=min(n,j)) 个有C(n,p)中组合，有T[i]个第 i 列，所以方案数相乘（乘法原理：这是T[i]列同时满足），而对于所有的p，是加法∑，(加法原理：有p中不同的填法并列)。
注意 i， j，p都可以从0 开始。乘方用快速幂。
还有T[i]不一定是一个数组，可以改为判断当前 i 列是否小于m%n,如果小于则T[i]=m/n+1，否则为m/n。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 105
#define ll long long
#define P 1000000007//打错了mod数
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
ll n,m,k;
ll dp[maxn][maxn*maxn],c[][maxn][maxn];//组合--i 中取 j -- 0: m/n,1:m/n+1
ll ksm(ll cur,ll ki)
{
ll t=,tmp=cur,kk=ki;
while (kk)
{
if (kk%) t=(t*tmp)%P;
kk>>=;
tmp=(tmp*tmp)%P;
}
return t;
}
void pre()
{
for (int i=;i<=;i++)
{
c[][i][]=c[][i][i]=c[][i][]=c[][i][i]=;
for(int j=;j<i;j++)
{
c[][i][j]=c[][i][j]=c[][i-][j-]+c[][i-][j];//***
c[][i][j]%=P;
}
}
ll xi=m/n;
for (int i=;i<=;i++)
for (int j=;j<=i;j++)//<=i
{
c[][i][j]=ksm(c[][i][j],xi);
c[][i][j]=ksm(c[][i][j],xi+);
}
}
int main()
{
freopen("table.in","r",stdin);
freopen("table.out","w",stdout);
scanf(AUTO AUTO AUTO,&n,&m,&k);
pre();
int cur=(<=m%n);// choose 0 or 1
for (int i=;i<=min(n,k);i++)//pre work ,from 0可以不选
dp[][i]=c[cur][n][i];
for (int i=;i<=n;i++)
{
int cu=(i<=m%n);// >=i choose 1
for (int j=;j<=i*n&&j<=k;j++)// from 0
for (int t=;t<=min(n,(ll)j);t++)//min(n,j) from 0
{
// dp[i][j]+=(dp[i-1][j-t]*c[cu][n][t])%P;
dp[i][j]=(dp[i][j]+(dp[i-][j-t]*c[cu][n][t])%P)%P;//注意加法原理和乘法原理
}
}
printf(AUTO,dp[n][k]);
return ;
}
第三题：
LGTB 最近迷上了正方形，现在他有n 个在二维平面上的点，请你告诉他在这些点中选4 个点能组成四条边都平行于坐标轴的正方形的方案数有多少
对于10% 的数据，1 <= n<= 50
对于30% 的数据，1 <=n <= 1000
对于100% 的数据，1 <=n <=10^5，0 <= xi, yi <= 10^5
解：
这套题怎么两道都是相似的。。然后我就写了一个大暴力。判断每个点向它的左下方找长度依次为:1,2,3,..min(xi,yi)的满不满足正方形。居然还得了50。。意料之外。
50分代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1005
using namespace std;
int n,ans;
struct pp{
int x,y;
};
pp v[maxn*maxn];
bool mp[maxn][maxn];
int main()
{
freopen("square.in","r",stdin);
freopen("square.out","w",stdout);
scanf("%d",&n);
for (int i=;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
v[i].x=a;v[i].y=b;
mp[a][b]=true;
}
for (int i=;i<=n;i++)
{
int xi=v[i].x,yi=v[i].y;
if (xi==||yi==) continue;
int ma=min(xi,yi);
for (int j=;j<=ma;j++)
if (mp[xi-j][yi]&&mp[xi][yi-j]&&mp[xi-j][yi-j]){
ans++;
}
}
printf("%d",ans);
return ;
}
还有两天。不准备写正解了，还不如我自己复习呢。
��--1-1-11