首页 > 代码库 > 多校第一场 费马小定理+模拟+组合数学

多校第一场 费马小定理+模拟+组合数学

A题:Couple doubi

链接:http://acm.hdu.edu.cn/showproblem.php?pid=4861

这题逗逼了,刚开始根本就没什么思路,刚开始看题的时候有点像费马小定理,但是这个定理我只知道,然后没用过。看了下定义,有点不一样的是反着的,然后反着的我又不会转化,尼玛,就这样错过了最好的解题方法。然后队友又理解错题意了。WA了多发,然后我重新看了下题意,然后队友才发觉理解错题意了,然后找了规律才A。

代码比较短,就不贴了,真的写吧。

if(k/(p-1)&1) puts("YES");
else puts("NO");

D题: Task

链接:http://acm.hdu.edu.cn/showproblem.php?pid=4864

这题刚开始想的时候想对了。就是把机器和任务放到同一个数组里,然后根据时间和等级从大到小排序,但是时间知道怎么取,但是等级的时候就不太知道了。所以不太敢敲,也不知道怎么处理那些时间都大,然后等级也大的时候取哪个。然后……然后刚刚知道怎么处理,但是又T了。看了琦神的,用multiset处理真是太机智了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<bitset>
#define INF 100007
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct abc
{
    int ti,le,ty;
}a[200005];
bool cmp(abc a,abc b)
{
    if(a.ti!=b.ti) return a.ti>b.ti;
    if(a.le!=b.le) return a.le>b.le;
    return a.ty>b.ty;
}
multiset<int>s;
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        int i,j,cnt=0;
        ll sum=0,sum1=0;
        s.clear();
        for(i=0;i<n;i++)
            scanf("%d%d",&a[cnt].ti,&a[cnt].le),
            a[cnt++].ty=1;
        for(i=0;i<m;i++)
            scanf("%d%d",&a[cnt].ti,&a[cnt].le),
            a[cnt++].ty=0;
        sort(a,a+cnt,cmp);
        for(i=0;i<cnt;i++)
        {
            if(a[i].ty) s.insert(a[i].le);
            else
            {
                multiset<int>::iterator it=s.lower_bound(a[i].le);
                if(it!=s.end())
                    sum1++,sum+=500*a[i].ti+2*a[i].le,s.erase(it);
            }
        }
        printf("%I64d %I64d\n",sum1,sum);
    }
    return 0;
}