RDC
2013, Samara SAU ACM ICPC Quarterfinal Qualification Contest
G
思路卡成智障呀！
Round 1：对着这个魔法阵找了半天规律，效果很辣鸡。
Round 2：打表，效果辣鸡。
Round 3：找映射关系 + Pick定理
对于某种颜色的点来讲，必须形成一个网格状方阵的！
设总共有\(s\)种颜色。方阵中相邻两点连线向量为\((x,y)\)
观察网格，注意“一个格子”与“这个格子的左上角”是一一对应的。
因此，由皮克定理：\(x^2+y^2=s+1\)
I
日常不会贪心..........
贪心是不可能贪心的，这辈子都不可能会贪心!
搞DP又不会搞.........
我发现自己一碰到这种什么序列，区间上的贪心DP就直接炸毛。
研究下自己的魔术回路：
- 倒着做【前面对后面有影响，可以睡觉了。】
- 能过挡住第i个石头，那么
PreDamege<=t[i]-d[i]，然后就想维护前缀最大值什么的，效果很辣鸡。 - DP：要记录前i个石头吸收了多少伤害，可以睡觉了。
做法：从前往后扫，拿个堆了维护石头，如果要被砸死了，那就丢掉一个伤害值最大的石头。
2013, VI Samara Regional Intercollegiate Programming Contest
A
魔术回路
- 完全在乱搞一气....WAWAWAWAAC，太弱。
注意，找到第一只存活的兔几后，接下来最多也只要牺牲一只小兔几。
慢慢分类讨论.
- 首先是n=1或者k=1这些。
- n%k=1, 最坏的情况：前n/k次，全部失败，剩下那瓶药肯定就是想要的啦!
- n%k>1, 最坏的情况：前n/k次，全部失败，因为现在还有>=2瓶的药没检测，所以还需要再牺牲一只兔几。
- n%k=0, 最坏的情况：前n/k-1次，全部失败，接下来就和上一场情况类似了。
C
看到完美匹配，直接想到Hall定理。然而效果极度辣鸡。
正解：贪心+线段树
写得好凌乱吖！！！
emmm...碰键盘一定一定先把思路整理好吖！！！！
写了半天不知道自己在写什么东西就比较喜了.......
做法：
- 把区间按左端点从小到大排序。对于点P，匹配他的区间，右端点当然越靠左越好！根据这个规律就可以判断是否存在完美匹配。
- 问题的关键是第二步，判断完美匹配是否唯一！对于点P，设与他匹配的区间是S。然后我们判断点P是否能与点Q互换位置，不妨设Q在P左边，那么
S.left <= Q < P，设Q对应的区间为T，PQ能互换的条件是T.right >= P，因此我们使用线段树维护点对应的区间的右端点MAX就好了。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
#define rd(x) scanf("%d",&x)
#define prt(x) printf("%d\n", x);
#define prtvec(v) for(int i=0;i<v.size();i++) printf("%d%c", v[i], i==(v.size()-1)?'\n':' ');
#define sz(x) (int)x.size()
#define pb(x) push_back(x)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,y,x) for(int i=y;i>=x;i--)
const int N=200000+10;
const double EPS = 1e-8;
int n,ret[N],ans[N],now[N];
struct Nod {
int l,r,id;
Nod(){}
Nod(int l_,int r_,int id_) {l=l_,r=r_,id=id_;}
bool operator < (const Nod & o) const {
if(r==o.r) return l == o.l ? id < o.id : l < o.l;
return r < o.r;
}
} nod[N];
struct Interval {
int l, r;
} interval[N];
struct Room {
int id, x;
bool operator < (const Room & o) const {
return x < o.x;
}
} a[N]; int p[N];
set<Nod> st;
bool cmp(Nod a, Nod b) {
return a.l < b.l;
}
int s[N<<2];
void build(int l,int r,int rt){
if(l==r){
s[rt]=interval[ret[l]].r;
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
s[rt]=max(s[rt<<1],s[rt<<1|1]);
}
int queryMax(int l,int r,int rt,int L,int R){
if(L<=l&&r<=R){
return s[rt];
}
int mid=(l+r)>>1;
int ans=0;
if(L<=mid) ans=queryMax(l,mid,rt<<1,L,R);
if(R >mid) ans=max(ans,queryMax(mid+1,r,rt<<1|1,L,R));
return ans;
}
int main(){
rd(n);
rep(i,1,n) rd(a[i].x), a[i].id=i;
sort(a+1,a+1+n);
rep(i,1,n) p[i]=a[i].x;
rep(i,1,n) now[i]=a[i].id;
rep(i,1,n) rd(nod[i].l), rd(nod[i].r), nod[i].id=i;
sort(nod+1,nod+1+n,cmp);
int las=1;
rep(i,1,n) {
while(las<=n && nod[las].l <= a[i].x) {
st.insert(nod[las]);
las ++;
}
Nod tmp = *st.lower_bound(Nod(-1,a[i].x,0));
ret[i]=tmp.id;
ans[tmp.id]=i;
interval[ret[i]].l = tmp.l;
interval[ret[i]].r = tmp.r;
if (ret[i]==0) return !printf("Let's search for another office.\n");
st.erase(tmp);
}
build(1,n,1);
rep(i,1,n){
int Lb = lower_bound(p+1,p+1+n,interval[ret[i]].l) - p;
int Rb = i-1;
if (Lb > Rb) continue;
int mx = queryMax(1,n,1,Lb,Rb);
if (mx >= a[i].x) {
return !printf("Ask Shiftman for help.\n");
}
}
printf("Perfect!\n");
rep(i,1,n){
printf("%d ", now[ans[i]]);
}
}
F
贪心怕是有完杀效果吧。
对于区间按左端点排序。对于每个点，去左端点尽可能靠左的区间。lower_bound一下就好了。
K
构造长度为n，逆序对为k的排列。
智障的做法1：像[a,...1][b....a+1][c....b+1]....[n....c+1]这样，长度为len的区间对逆序的贡献为len*(len-1)/2,每次都拿出尽可能长的一段。然后惊喜地发现总长度有可能凑不出n.
智障的做法2：BIT + 二分【还被边界杀】，虽然能够，但是....好沙比啊。
不智障的做法：先[a,....1][a+1,.....n]然后把n往左边扯。