Codeforces Round 239

Posted on By 二价氢

#Div2.

##A

##B

#Div1.

##A Triangle

###Task

给定直角边,问是否存在满足以下条件的直角三角形

  1. 顶点为整点
  2. 边不平行于坐标轴

###Solution

枚举

则存在

三个顶点分别为

###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这组数据上,这很可能是由于,判断的缺失而造成

我们似乎能证明

  1. 这不会满足
  2. 题目的不合法

但是,根据证明,存在一组,能满足以上两点,这时可以为

非常好地满足了以上两点,并且,有趣的是,20 15这组数据挂了的人,15 20却能通过,好像15 20没过的人,20 15又能过,真是奇怪

##B Long Path

###Task

给一个图,第奇数次访问时走到处,第偶数次访问时走到处,询问从走到需要多少步

同时有

###Solution

注意,我们走到处时,肯定不会走到编号大于的结点处,所以,这样走下来,最终肯定是走回到号结点,然后走到号结点,继续

于是有递推方程

解释如下:从,首先走一步到处,然后从走到,接着,走一步到,然后从走到

同时,加上记忆化搜索即可

###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

一个数列,下标从,现在有次修改,给定三个数,表示对区间,区间内每一个数加上,输出最终的数列

###Solution

万万没想到,这题居然是暴力,所以它看起来是个数据结构题,实际上是道数学题

我们预处理组合数等等,然后对每一次操作用前缀和的方式,修改一个影子序列,最后将这个影子序列加到原序列里即可

时间复杂度

###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