欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #512 (Div. 2, based on Technocup 2019 Elimination Round 1)(ABCD总结)

程序员文章站 2022-05-09 22:00:15
...

GG,又是掉分场,几乎没啥hack点,拼题量和手速。

第二次一分钟秒出A题。(但是没有什么用,因为赛场上几乎不可能出这么简单的题)

B题做的时候就有点思维僵化了。直接用四条边的方程判断点是否在内部就行了。其实这道题可以拓展到五、六边形甚至更多边形。(作为一个数学系的人居然没有第一时间想到,真是惭愧。。。)

C题一看就是爆搜啊。n才100,直接枚举0到所有位的和,然后爆搜判断能不能有一组合法解即可。注意,要判断能否分成两组以上。(不然会WA on test 3)

D题。。。其实并不难,但是比赛干了1小时没做出来。

给你n,m,k(<=1e9),让你构造三个点,使得三个点构成三角形的面积恰好等于n*m/k。三个点的横坐标在范围[0,n],纵坐标范围在[0,m]。

很容易想到固定一点(0,0),然后构造剩下的两个点。

由三角形面积公式我们可以想到,如果n*m*2能整除k,则一定存在合法情况,否则一定不存在。

那合法的时候怎么构造呢?

注意题目中的一个关键条件:k>=2

也就是说,固定x2=0,y3=0 ,则一定存在合法情况,使0<=x3<=n,0<=y2<=m,使x3*y2==2*n*m/k。

怎么构造x3和y2呢?

利用GCD。

上式可化成2*n*m/((k/x)*x)

分成两项 2*n/x    m/(k/x)

像不像正好是x3和y2?

显然需要2*n%x==0&&k%x==0

我们已经知道n*m*2能整除k。显然满足上式以后,m一定能整除(k/x)。因此我们取x=gcd(2*n,k)。

这样的答案虽然合法,但是由于n*2了,所以当x==1也就是2*n和k互质时,x3>n。

那就x3/=2;y2*=2啊。

因为总存在一种合法情况,所以这个2总要分给n或m。既然n不行,那肯定就是m了呗。

这样代码就有了:

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=200010;
ll n,m,k,d;
int a[maxn],sum[maxn];
int c[maxn];
ll ans,ct,cnt,tmp,flag;
ll s,x,y,xx,yy,xxx,yyy;
ll gcd(ll x,ll y)
{
    return y?gcd(y,x%y):x;
}
int main()
{
    int T,cas=1;
    while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF)
    {
        if((n*m%k)!=0&&(n*m*2)%k!=0) {puts("NO");continue;}
        ll x=gcd(n<<1,k);
        ll y=k/x;
        x=(n<<1)/x;
        y=m/y;
        if(x>n){x>>=1;y<<=1;}
        puts("YES");
        puts("0 0");
        printf("0 %lld\n",y);
        printf("%lld 0\n",x);
    }
    return 0;
}

仔细想想,其实不是很难,但完全可以说是一个思维题了。

不是第一次做这种题了。放在博客里来提醒自己。

 

 

相关标签: ACM