[牛客练习赛65]补题

https://ac.nowcoder.com/acm/contest/5961

A 贪心

瞎猜,小的用来加，大数用来乘

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5+5;
const int MOD = 998244353;
ll b[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;++i) cin>>b[i];
    sort(b,b+n);
    ll ans=0;
    for(int i=0;i<n/2;++i){
        ans = (ans+b[i])%MOD;
    }
    for(int i=0;i<n/2;++i){
        ans = (ans*b[i+n/2])%MOD;
    }
    cout<<ans%MOD;
}

B 快速幂

把每个数表示成k的多少次方,k^a*k^b=a+b 比较a+b的大小即可,本来想用log函数。。结果超时
pow函数用inline才能过....还不如for循环快

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define MYINTMAX 0x3f3f3f3f
const int N = 5e5+5;
const int MOD = 998244353;
int mod;
inline ll myPow(ll a,ll b){
    ll base=a;ll ans=1;
    while(b>0){
        if(b&1) ans=ans*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ans%mod;
}
//把每个数表示成k的多少次方,k^a*k^b=a+b 比较a+b的大小即可,本来想用log函数。。结果超时
ll a[2001][2001];
signed main()
{
    int n,m,k;
    cin>>n>>m>>k>>mod;
    int ans=0;ll x;
    for(int i=0;i<n;++i){
        int tmp=0;
        for(int j=0;j<m;++j){
            scanf("%lld",&x);
            int exponent=0;
            while (x!=1){
                exponent++;
                x/=k;
            }
            tmp+=exponent;
        }
        ans=max(tmp,ans);
    }
    int sum=myPow(k,ans)%mod;
    cout<<sum<<endl;
    return 0;
}

C 极角排序,计算几何

我们平常所使用的坐标系都是直角坐标系，而极角排序是在极坐标系下进行的。
这里首先要选取一个点，然后其它点根据与参考点的连线与x轴所成的夹角的大小进行排序的。
这里我们可以简单理解为绕着一个点逆时针转圈访问。
夹角排序，可以理解为斜率排序,这个题是以(0,0)为中心则(x,y)斜率为y/x; 斜率比较则为 $y1/x1 > y2/x2$
做的时候想到了答案只有-1,0,1,2,3 0,1很好判断，1就是存在斜率相同的点，但没想到是按斜率排序然后二分查找
2，3并没有想到好办法去判断 = =
看题解才会系列:
画图可以发现如果n > 2一定输出2
如果n=2，只有当询问点，(0,0)和两个点构成了一个平行四边形时会输出3，否则输出2

#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
int n,q;

struct point{
    ll x,y;
    point(){}
    point(ll x,ll y):x(x),y(y){}
    point operator +(const point&a)const { return point(x+a.x,y+a.y);}
    point operator -(const point&a)const { return point(x-a.x,y-a.y);}
    ll operator ^(const point&a)const {return x*a.y-y*a.x;}// 斜率比较
    bool operator == (const point &a)const {return (x==a.x)&&(y==a.y);}
    bool operator <(const point &a)const { return (x * a.y - y * a.x)>0;}
}pt[N];
bool same(point a,point b) { return ((a ^ b) == 0); }

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld%lld",&pt[i].x,&pt[i].y);
        if(pt[i].x == 0 && pt[i].y == 0) --i,--n;
    }
    sort(pt + 1,pt + n + 1);
    bool line = same(pt[1],pt[n]);//所有的点都在同一条线上

    while(q--)
    {
        point a; scanf("%lld%lld",&a.x,&a.y);
        if(a.x == 0 && a.y == 0) { printf("0\n"); continue; }

        int it = lower_bound(pt + 1,pt + n + 1,a) - pt; // 二分找斜率相同的点
        if(1 <= it && it <= n && same(pt[it] , a)) { printf("1\n"); continue; }

        if(line) { printf("-1\n"); continue; }

        if(n > 2) { printf("2\n"); continue; }

        if(a == (pt[1] + pt[2])) printf("3\n");//构成了一个平行四边形时输出3
        else printf("2\n");
    }
    return 0;
}