这是我们第二次组队训练，毕竟经验不足，加上水平不够，导致我们各种被碾压。
A - Couple doubi:
这道题是道比较水的数论。但我们都没想出来要怎么做。后来是potaty提议打个表看看，然后lmz打出表后发现了规律。我还没细看，待研究后再补全。
D - Task：
这道题一看就知道是个贪心（现在只要是有deadline的题我都觉得是贪心了）。虽然想出来了，但还是不会严格证明为什么只要取满足task的且y最小（y相等时x最小）的machine就行了。
我的做法是把所有machine放进第machine_i_y个桶中，这个桶用set来实现。然后按照x的大小顺序从大到小（x相等时y从大到小）依次取task，每次找到满足最合适的machine。最合适的machine条件上面已经给出（貌似先看x最小，再看y最小也行，不过我的for每个machine再for每个y，如果改成for每个x，时间过不去）。但为什么task是从大到小来取呢？
题目中钱的公式是500*xi+2*yi，而yi<=100，xi>1。可以发现，只要xi>xj，即xi>=xj+1，那么无论怎么取yi和yj，500*xi+2*yi始终是大于500*xj+2*yj的。所以这样取task能保证钱是最多的。鉴于每个machine只能取一个task，如果不取x（或y）偏大的task，而去取x（或y）较小的task，这明显是一种对money的浪费，而且也没有完成更多的task，所以不会有上述做法的反例存在。综上，上述做法是对的。
第一次写博客，若有不明白的可以指出，我会尽力解答的。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <set>
#include <utility>
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define FORD(i,r,l) for(int i=(r);i>=(l);i--)
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long LL;
pair<int,int> mac[100001],task[100001];
int n,m;
int main(){
while (~scanf("%d%d",&n,&m))
{
FOR (i,1,n) scanf("%d%d",&mac[i].second,&mac[i].first);
sort(mac+1,mac+1+n);
FOR (i,1,n) swap(mac[i].second,mac[i].first);
FOR (i,1,m) scanf("%d%d",&task[i].first,&task[i].second);
sort(task+1,task+1+m);
multiset<int> q[101];
multiset<int>::iterator it;
FOR (i,1,n) q[mac[i].second].insert(mac[i].first);
LL ans=0; int ansgs=0; int j;
FORD (i,m,1)
{
for (j=task[i].second; j<=100; j++)
{
if (!q[j].empty())
if ((it=q[j].lower_bound(task[i].first)) != q[j].end())
break;
}
if (j==101) continue;
q[j].erase(it);
ansgs++;
ans+=500*task[i].first+2*task[i].second;
}
/*bool vis[100001];
FORD (i,m,1)
{
FOR (j,1,n)
if (mac[j].first>=task[i].first&&mac[j].second>=task[i].second&&!vis[j])
{
vis[j]=1; ansgs++;
ans+=500*task[i].first+2*task[i].second;
break;
}
}*/
cout<<ansgs<<" "<<ans<<endl;
}
return 0;
}
F - Shooting：
这道题苦思良久没想出来，在看了题解之后一下就明白了。说实话，非常佩服出题人，能想出这样的题来。
题目大意：
有n个target，每次站在x处射击，最多可以射击k个target。K是由公式K = ( a * Pre + b ) % c算出的，Pre是上一次shooting的得分。具体可参考下图：
target被射中不会消失。每次的得分是所有被射中的target的距离之和。如果上次的得分大于P，那么这次的得分翻番。求每次的得分。
解题思路：把距离Di（1<=i<=N）离散化，然后将target按距离从小到大加入函数式线段树中（用左区间点+1，右区间点-1的方式）。然后每次二分一下求出第k个target的位置，二分是利用线段树来算出x处有多少个线段(target)。找到位置之后就很好办了。read得分和read线段的个数的操作是一样的。
还有种做法是按照X坐标离散化。两种方法本质是差不多的，所以就不赘写了。
时间复杂度为O(N*logN+2*N*logX+M*(logN*logX+logX)). 感觉3s的时间会不够的样子...
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#define debug(x) cout<<#x<<" = "<<x<<endl
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define rep(i,n) for(int i=0;i<(n);i++)
#define foreach(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define LC(t) ((t)?(t->o[0]):0)
#define RC(t) ((t)?(t->o[1]):0)
using namespace std;
typedef long long LL;
const int maxn=100001;
int X;
struct btree{
btree *o[2];
int cnt;
LL d;
}tbt[maxn*50]; int tpo;
btree *newnode()
{
btree *p=&tbt[tpo++];
p->o[0]=p->o[1]=0;
p->cnt=p->d=0;
return p;
}
btree *sr(btree *t,int l,int r,int x,int v,int d)
{
btree *p=newnode();
if (t) *p=*t;
p->cnt+=v; p->d+=d;
if (l==r) return p;
int mid=l+r>>1;
if (x<=mid) p->o[0]=sr(p->o[0],l,mid,x,v,d);
else p->o[1]=sr(p->o[1],mid+1,r,x,v,d);
return p;
}
int red1(btree *t,int l,int r,int ll,int rr)
{
if (!t) return 0;
if (ll<=l&&r<=rr) return t->cnt;
int mid=l+r>>1,ret=0;
if (ll<=mid) ret+=red1(t->o[0],l,mid,ll,rr);
if (rr>mid) ret+=red1(t->o[1],mid+1,r,ll,rr);
return ret;
}
LL red2(btree *t,int l,int r,int ll,int rr)
{
if (!t) return 0;
if (ll<=l&&r<=rr) return t->d;
int mid=l+r>>1; LL ret=0;
if (ll<=mid) ret+=red2(t->o[0],l,mid,ll,rr);
if (rr>mid) ret+=red2(t->o[1],mid+1,r,ll,rr);
return ret;
}
struct target{
int l,r,d;
bool operator< (const target &a) const { return d<a.d; }
}tar[maxn];
int n,m,P;
btree *bt[maxn];
void init() { tpo=0; X++; }
int ef(int x,int k)
{
int l=1,r=n,mid;
while (l<=r)
{
mid=l+r>>1;
if (red1(bt[mid],1,X,1,x)<=k) l=mid+1;
else r=mid-1;
}
return r;
}
int main(){
for (int x,a,b,c,z;scanf("%d%d%d%d",&n,&m,&X,&P)!=EOF;)
{
init();
FOR (i,1,n) scanf("%d%d%d",&tar[i].l,&tar[i].r,&tar[i].d);
sort(tar+1,tar+1+n);
FOR (i,1,n)
bt[i]=sr(bt[i-1],1,X,tar[i].l,1,tar[i].d),
bt[i]=sr(bt[i],1,X,tar[i].r+1,-1,-tar[i].d);
LL pre=1,ans,k;
for (int i=1;i<=m;i++,pre=ans)
{
scanf("%d%d%d%d",&x,&a,&b,&c);
k=((LL)a*pre+(LL)b)%c;
z=ef(x,k);
ans=red2(bt[z],1,X,1,x);
if (pre>P) ans*=2;
printf("%I64d
",ans);
}
}
return 0;
}