cf and at

oj

Codeforces 938.C Constructing Tests

nxn的矩阵，只含有0和1两种元素，要求使每个mxm的矩阵(这个矩阵为nxn矩阵的子矩阵)至少含有一个0，求得最多的1的元素个数。此题并不要求输出最多的1的个数。而要求的是给1的个数，输出对应的n和m。
$n^2+(\frac{n}{m})^2=x$,x为元素1的个数。方程可以转化为$(n+\frac{n}{m})(n-\frac{n}{m})=x$利用筛法对x分解$i$和$\frac{x}{i}$,分别代表$(n+\frac{n}{m})和(n-\frac{n}{m})$,细节问题看代码注释。

#include <bit/stdc++.h>
int t;
int main(){
    scanf("%d",&t);
    while(t--){
        int x; scanf("%d",&x);
        if(!x){
            printf("1 1\n"); continue;
        }
        bool suc=0;
        for(int i=1;i*i<x;++i) if(x%i==0){
            int t=x/i;
            if((t+i)%2) continue;//如果2*n不是偶数求得的n不是正确值。
            int n=(t+i)/2,m=(t-i)/2;
            if(n/(n/m)==m){//判断m是否正确
                suc=1; printf("%d %d\n",n,n/m); break;
            }
        }
        if(!suc) printf("-1\n");
    }
}

Codeforces Round #465(Div2) C. Fifa and Fafa(计算几何+数论)

Fifa想要在公寓使用网络，公寓范围是一个以(x1,y1)为圆心，r为半径的圆，Fifa想要设置一个网络覆盖区域，这个区域也是一个圆。而要求覆盖范围不超出公寓外且不包括Fafa这个点(x2,y2)，且使没覆盖的公寓范围最小。输出设置的网络区域的圆心和半径。
分三种情况讨论，一种Fafa在公寓范围外或上，一种与公寓圆心重合，另一种在公寓内。前2种比较好处理，最后一种看图解。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
double r,x1,y1,x2,y2;
int main()
{
    cin>>r>>x1>>y1>>x2>>y2;
    double d=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    double R=(sqrt(d)+r)/2;
    if(d>=r*r)
        printf("%.7f %.7f %.7f",x1,y1,r);
    else if(d==0)
        printf("%.7f %.7f %.7f",x1,y1+r/2,r/2);
    else{
        double dx=x1-x2;
        double dy=y1-y2;
        printf("%.7f %.7f %.7f",x2+dx*R/sqrt(d),y2+dy*R/sqrt(d),R);
    }
    return 0;
}

bjtu1819 二哥的求和

给一个长度为n的数组，求出公式$\sum\limits_{i=l}^r a_i(i-l+1)$。给出q个查询，查询区间[l,r]的公式的值。

#include <iostream>
#include <cstdio>
#include <cstring> 
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
int t,q,n;
long long mxr[maxn],hyx[maxn],a[maxn];
//https://citel.bjtu.edu.cn/acm/oj/problem/1819
//将图中式子拆分为a[i]*(i+1)-a[i]；
//维护前缀和得到正确答案 
int main()
{
    int cnt=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(long long i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            mxr[i]=mxr[i-1]+a[i];
            hyx[i]=hyx[i-1]+a[i]*(i+1);
        }
        scanf("%d",&q);
        printf("Case %d: \n",cnt++);
        while(q--)
        {
            long long l,r;
            scanf("%lld%lld",&l,&r);
            long long ans=(hyx[r]-hyx[l-1])-(mxr[r]-mxr[l-1])*l;
            printf("%lld\n",ans);
        }
    }
    return 0;
}