数论那块不太会,以前应该用过费马小定理但是太长时间没做数论想不起来。比赛的时候找了几组样例,队友推出的结论。
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 100000 #define eps 1e-7 #define INF 0x7FFFFFFF #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 typedef long long ll; int main(){ int p,k; while(scanf("%d%d",&k,&p)!=EOF){ if((k/(p-1))%2==0) cout<<"NO"<<endl; else cout<<"YES"<<endl; } return 0; }HDU 4864
贪心的思想,实际上是按t值排序后找到最小的能匹配的l机器,把任务放进去,因为根据 500*t+2*l 知道t对价值的决定性比l要大。比赛时候逗比了WA了几发之后一度以为是思路有问题。后来再敲我把满足t条件的机器存入新的结构体数组,排序后找最小的匹配的机器,果然T了。然后还是用map映射了满足t条件的l值,找到最小的满足任务的l值#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 1000100 #define eps 1e-7 #define INF 0x7FFFFFFF #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 typedef long long ll; struct node{ int t,l; }task[MAXN],machine[MAXN],temp[MAXN]; int vis[MAXN]; bool cmp(node x,node y){ if(x.t==y.t) return x.l>y.l; else return x.t>y.t; } map<int, int> mp; int main(){ int m,n,i,j,cnt; ll ans; while(scanf("%d%d",&n,&m)!=EOF){ mp.clear(); cnt = 0; ans = 0LL; for(i=0;i<n;i++){ scanf("%d%d",&machine[i].t,&machine[i].l); } for(i=0;i<m;i++){ scanf("%d%d",&task[i].t,&task[i].l); } sort(machine,machine+n,cmp); sort(task,task+m,cmp); j = 0; int tot = 0; for(i=0;i<m;i++){ while(j<n&&machine[j].t>=task[i].t){ mp[machine[j].l]++; j++; } map<int, int>::iterator it = mp.lower_bound(task[i].l); if(it!=mp.end()){ cnt++; ans+=task[i].t*500+task[i].l*2; mp[it->first]--; if(!mp[it->first]) mp.erase(it->first); } } cout<<cnt<<" "<<ans<<endl; } return 0; }HDU 4869
传送门HDU 4870
矩阵&&高斯消元,不会。。。别人博客里有个推导的做法,移步这里:http://blog.csdn.net/a601025382s/article/details/38047905