#Div2.
##A
##B
#Div1.
##A Triangle
###Task
给定直角边，问是否存在满足以下条件的直角三角形
- 顶点为整点
- 边不平行于坐标轴
###Solution
枚举\(x_1,y_1\)和\(x_2,y_2\)，\(x_1^2+y_1^2=a^2,x_2^2+y_2^2=b^2\)
若\(\frac{x_1}{y_1}=\frac{x_2}{y_2}\)且\(x_1\neq x_2,y_1\neq y_2\)则存在
三个顶点分别为\((-y_1,x_1),(x_2,y_2),(0,0)\)
###Code
最长耗时30 MS
最多内存4 KB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
using namespace std;
vector<pair<int,int> > A,B;
int a,b,c,d,e;
int la,lb;
int lc,ld,le,lf;
double aa,bb;
const double eps=1e-8;
int main()
{
scanf("%d%d",&a,&b);
for (int i=1;i<=1000;i++)
{
for (int j=1;j<=1000;j++)
{
if (i*i+j*j==a*a)
A.push_back(make_pair(i,j));
if (i*i+j*j==b*b)
B.push_back(make_pair(i,j));
}
}
la=A.size();lb=B.size();
for (int i=0;i<la;i++)
{
for (int j=0;j<lb;j++)
{
lc=A[i].first;ld=A[i].second;
le=B[j].first;lf=B[j].second;
if ((lc!=ld)&&(le!=lf)&&(lc!=lf)&&(lc*lf==ld*le))
{
printf("YES\n");
printf("%d %d\n",-ld,lc);
printf("%d %d\n",le,lf);
printf("0 0\n");
return 0;
}
}
}
printf("NO\n");
return 0;
}
###Tips
很多人跪在20 15这组数据上，这很可能是由于\(x_1\neq x_2,y_1\neq y_2\)，判断的缺失而造成
我们似乎能证明
若\(x_1=x_2,y_1=y_2\)
- 这不会满足\(\frac{x_1}{y_1}=\frac{x_2}{y_2}\)
- 题目的\(a,b\)不合法
但是，根据证明，存在一组\((x_1,x_2,y_1,y_2)\)，能满足以上两点，这时可以为\((16,12,12,9)\)
非常好地满足了以上两点，并且，有趣的是，20 15这组数据挂了的人，15 20却能通过，好像15 20没过的人，20 15又能过，真是奇怪
##B Long Path
###Task
给一个图，第奇数次访问时走到\(p_i\)处，第偶数次访问时走到\(i+1\)处，询问从\(1\)走到\(n\)需要多少步
同时有\(1\le p_i \le i\)
###Solution
注意，我们走到\(p_i\)处时，肯定不会走到编号大于\(i\)的结点处，所以，这样走下来，最终肯定是走回到\(i\)号结点，然后走到\(i+1\)号结点，继续
于是有递推方程\(f(i,j)=1+f(p_i,i)+1+f(i+1,j)\)
解释如下：从\(i\)到\(j\)，首先走一步到\(p_i\)处，然后从\(p_i\)走到\(i\)，接着，走一步到\(i+1\)，然后从\(i+1\)走到\(j\)
同时，加上记忆化搜索即可
###Code
最长耗时31 MS
最多内存3964 KB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1005,mod=1e9+7;
int f[maxn][maxn],p[maxn],n;
int dp(int s,int t)
{
if (s==t)
return 0;
if (~f[s][t])
return f[s][t];
return f[s][t]=(1+dp(p[s],s)+1+dp(s+1,t))%mod;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&p[i]);
memset(f,-1,sizeof(f));
printf("%d\n",dp(1,n+1));
return 0;
}
##C Curious Array
###Task
一个数列\(\{a_i\}\)，下标从\(1\)到\(10^5\)，现在有\(m\)次修改，给定三个数\(l,r,k\)，表示对区间\((l,r)\)，区间内每一个数\(a_j\)加上\(\left(\begin{array}{c} j-l+k\\k\end{array}\right)\)，输出最终的数列\(\{a_i\}\)
###Solution
万万没想到，这题居然是暴力，所以它看起来是个数据结构题，实际上是道数学题
我们预处理组合数等等，然后对每一次操作用前缀和的方式，修改一个影子序列，最后将这个影子序列加到原序列里即可
时间复杂度\(O(mk)\)
###Code
最长耗时1357 MS
最多内存84156 KB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <numeric>
using namespace std;
const int maxmn=100005,maxk=105;
const long long mod=1000000007;
struct Int{
long long a;
Int (){a=0;}
Int (long long _a){a=_a%mod;if (a<0)a+=mod;}
Int operator + (Int b){return Int(a+b.a);}
Int operator - (Int b){return Int(a-b.a);}
Int operator * (Int b){return Int(a*b.a);}
Int operator ^ (long long b)
{
Int ret(1),k(a);
while (b)
{
if (b&1)
ret=ret*k;
k=k*k;
b>>=1;
}
return Int(ret);
}
Int operator ~ (void){return Int(a)^(mod-2);}
Int operator / (Int b){return (*this)*Int(~b);}
};
int a[maxmn],m,n,l,r,k;
Int fact[maxmn],ifact[maxmn];
Int sum[maxk][maxmn];
Int Fact(int l,int r) //Pi_{i=l}^{r} i
{
if (l<=0 && r>=0)
return 0;
if (l>0)
return fact[r]*ifact[l-1];
else
{
int num=r-l+1;
Int ret=Fact(-r,-l);
if (num%2)
return Int(0)-ret;
else
return ret;
}
}
Int C(long long n,long long m)
{
return Fact(n-m+1,n)*ifact[m];
}
int main()
{
fact[0]=1;
for (int i=1;i<maxmn;i++)
fact[i]=fact[i-1]*i;
for (int i=0;i<maxmn;i++)
ifact[i]=~fact[i];
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++)
scanf("%d",&a[i]);
for (int i=0;i<m;i++)
{
scanf("%d%d%d",&l,&r,&k);
l--;r--;
int A=k-l;
for (int a=0;a<=k;a++)
{
Int t=C(A,k-a);
sum[a][l]=sum[a][l]+t;
sum[a][r+1]=sum[a][r+1]-t;
}
}
for (int i=0;i<maxk;i++)
partial_sum(&sum[i][0],&sum[i][n],&sum[i][0]);
for (int i=0;i<n;i++)
{
Int ret=a[i];
for (int j=0;j<maxk;j++)
ret=ret+C(i,j)*sum[j][i];
printf("%lld ",ret.a);
}
printf("\n");
return 0;
}
##D
##E