## 【日常小测】仰望星空

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1009;
const int M = 1000009;
const int INF = 1e9;
const double PI = acos(-1);

int n, R, D, S, T;
int in[N], ot[N], cnt_in, cnt_ot;
int head[N], nxt[M], to[M], mth[N], vis[N];
pair<double, int> arr[N];
struct Point{
int x, y, ty;
inline int dis(const Point &P) {
return (x - P.x) * (x - P.x) + (y - P.y) * (y - P.y);
}
}p[N];

inline void AddEdge(int u, int v) {
static int E = 1;
}

char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

inline bool DFS(int w) {
vis[w] = 1;
for (int i = head[w]; i; i = nxt[i]) {
if (!mth[to[i]] || (!vis[mth[to[i]]] && DFS(mth[to[i]]))) {
mth[to[i]] = w;
mth[w] = to[i];
return 1;
}
}
return 0;
}

inline int solve() {
int ret = 0;
for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
if (!mth[i]) {
memset(vis, 0, sizeof(vis));
ret += DFS(i);
}
}
return ret;
}

inline void print(int w) {
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] == mth[w]) {
vis[w] = vis[to[i]] = 1;
printf("%d %d\n", w, mth[w]);
return;
} else if (!vis[to[i]]){
print(mth[to[i]]);
}
}
}

int main() {
R = read(); R *= R;
D = read(); D *= D;
S = 0; T = N - 1;
for (int i = 1; i <= n; i++) {
if (p[i].ty = p[i].dis(p[1]) > R) {
in[++cnt_in] = i;
} else {
ot[++cnt_ot] = i;
}
}
for (int ii = 1; ii <= cnt_in; ii++) {
int i = in[ii], cnt_arr = 0;
double mx = -PI, mn = PI;
for (int jj = 1; jj <= cnt_ot; jj++) {
int j = ot[jj];
if (p[i].dis(p[j]) <= D) {
double agl = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
mx = max(mx, agl);
mn = min(mn, agl);
arr[++cnt_arr] = make_pair(agl, j);
}
}
if (mx - mn >= PI) {
for (int j = 1; j <= cnt_arr; j++) {
arr[j].first += arr[j].first < 0? PI * 2: 0;
}
}
sort(arr + 1, arr + 1 + cnt_arr);
for (int j = 1; j <= cnt_arr; j++) {
}
}
printf("%d\n", solve() << 1);
memset(vis, 0, sizeof(vis));
for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
if (mth[i] && !vis[i]) {
print(i);
}
}
return 0;
}


## 【BZOJ 4886】[Lydsy2017年5月月赛] 叠塔游戏

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;

int n,tot,u[N],v[N],fa[N],val[N],cir[N],sz[N];
LL ans;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int find(int x) {
return x == fa[x]? x: fa[x] = find(fa[x]);
}

int main() {
for (int i=1;i<=n;i++) {
ans += u[i];
ans += v[i];
}
sort(val+1, val+1+tot);
tot = unique(val+1, val+1+tot) - val - 1;
for (int i=1;i<=tot;i++) {
fa[i] = i;
sz[i] = 1;
}
for (int i=1;i<=n;i++) {
int x = lower_bound(val+1, val+1+tot, u[i]) - val;
int y = lower_bound(val+1, val+1+tot, v[i]) - val;
if (find(x) != find(y)) {
sz[fa[y]] += sz[fa[x]];
if (cir[fa[x]]) {
cir[fa[y]] = 1;
}
fa[fa[x]] = fa[y];
} else {
cir[fa[x]] = 1;
}
}
for (int i=1;i<=tot;i++) {
if (find(i) == i) {
sz[i] -= (cir[i] ^ 1);
}
}
for (int i=1,w=1;i<=n;i++,w++) {
while (sz[find(w)] == 0) ++w;
ans -= val[w];
sz[fa[w]]--;
}
printf("%lld\n",ans);
return 0;
}


## 【TopCoder SRM714】Salesman

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int INF = 1e9;
const int N = 1e4;

int pfx[N],delta[N],pos[N],nxt[N];

class Salesman {
public:
int minMoves(vector<int> ppos, vector<int> ddelta) {
int n = ppos.size();
for (int i=1;i<=n;i++) {
pos[i] = ppos[i - 1];
delta[i] = ddelta[i - 1];
}
int ans = INF;
ans = min(ans, solve(n));
for (int l=1,r=n;l<r;l++,r--) {
swap(pos[l], pos[r]);
swap(delta[l], delta[r]);
}
for (int i=1;i<=n;i++) {
pos[i] = -pos[i];
}
ans = min(ans, solve(n));
return ans;
}
private:
inline int solve(int n) {
int mn = INF, mx = -INF, ret = INF;
for (int i=1;i<=n;i++) {
pfx[i] = pfx[i-1] + delta[i];
if (delta[i] < 0) {
mx = max(mx, i);
mn = min(mn, i);
}
}
for (int i=n,j=n;i;i--) {
if (delta[i] < 0) {
j = i;
}
nxt[i] = j;
}
if (mn == INF) {
return 0;
}
for (int l=1;l<=mn;l++) {
for (int r=mx;r<=n;r++) {
if (pfx[r] - pfx[l - 1] >= 0) {
ret = min(ret, cal(l, r));
break;
}
}
}
return ret;
}
inline int cal(int l, int r) {
int ret = pos[r] - pos[l] + abs(pos[l]), ans = INF;
int cry = 0, ned = 0, ptn = 0;
for (int i=l;i<=r;i++) {
if (delta[i] >= 0) {
cry += delta[i];
if (cry >= ned && ned) {
cry -= ned;
ret += max(0, pos[i] - ptn) << 1;
ned = 0;
}
} else if (delta[i] < 0) {
if (!ned && cry >= -delta[i]) {
cry += delta[i];
} else {
if (!ned) {
ptn = max(ptn, pos[i]);
}
ned -= delta[i];
}
}

ans = min(ans, ret + max(0, pos[r] - (ned? ptn: pos[nxt[i+1]])));
}
return ans;
}
};


## 【LA 5524】[EC2015 Final] Suffixes and Palindromes

### 背景

Claris给我安利的题，似乎子问题都会的样子

## 【BZOJ 4319】[CERC2008] Suffix Reconstruction

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;

int n,sa[N],rak[N];
char ans[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main() {
ans[sa[1]] = 'a';
for (int i=1,w='a';i<n;i++) (rak[sa[i]+1]>rak[sa[i+1]+1])? ans[sa[i+1]]=++w: ans[sa[i+1]]=w;
if (ans[n] <= 'z') printf("%s",ans+1);
else puts("-1");
return 0;
}


## 【BZOJ 4700】适者

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

class WellTimedSearch {
public:
double getProbability(int n, int A, int B) {
int vout = 0;
for (int i=1,up,down;i<=n;i++) {
if (A > 1) up = Get_Top(i+1>>1, A-1);
else {if (i == 1) up = 0; else up = 1e9;}
if (n - up - i < 0) break;
down = Get_Down(B-A, n - up - i, i<<1);
vout = max(vout, i + down);
}
return (double)vout / n;
}
private:
int Get_Top(int len, int t) {
if (t > 1) return min((int)1e9, len + (len>1? Get_Top(len+1>>1, t-1): t-1));
if (t == 1 && len > 1) return 1e9;
return 1;
}
int Get_Down(int t, int num_node, int cur) {
if (!t) return 0;
if (cur >= num_node) return num_node;
return cur + Get_Down(t-1, num_node - cur, cur<<1);
}
};


## 【UVa 11134】Fabled Rooks

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000+9;

int xl[N],xr[N],yr[N],yl[N],X[N],Y[N],n;
deque<pair<int,int> > beg[N]; deque<int> End[N];
priority_queue<pair<int,int> ,vector<pair<int,int> >, greater<pair<int,int> > > que;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline bool solve(int *l, int *r, int *ret) {
memset(ret,0,sizeof(X));
while (!que.empty()) que.pop();
for (int i=1;i<=n;i++) {
beg[i].clear();
End[i].clear();
}
for (int i=1;i<=n;i++) {
beg[l[i]].push_back(make_pair(r[i],i));
End[r[i]].push_back(i);
}

for (int i=1;i<=n;i++) {
while (!beg[i].empty()) {
pair<int,int> w = beg[i].front();
beg[i].pop_front();
que.push(make_pair(w.first,w.second));
}

if (que.empty()) return false;
ret[que.top().second] = i;
que.pop();

while (!End[i].empty()) {
if (!ret[End[i].front()])
return false;
End[i].pop_front();
}
}
return true;
}

int main(){
for (int i=1;i<=n;i++) {
}

if (!solve(xl,xr,X)) {puts("IMPOSSIBLE"); continue;}
if (!solve(yl,yr,Y)) {puts("IMPOSSIBLE"); continue;}

for (int i=1;i<=n;i++)
printf("%d %d\n",X[i],Y[i]);
}
return 0;
}


## 【POJ 3514】[NEERC2006] Graveyard

##### 证明：

1)|A|==|B|：显然将距离最终雕塑位置最小的点移动过去不会使答案变劣
2)|A|<|B|：显然逆时针转动尽量小的距离，使得有一个原雕塑与最终雕塑位置重叠会使答案变优
3)|A|>|B|：同理可得：应顺时针转动最小距离

## 【BZOJ 4404】[Neerc2015] Binary vs Decimal

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int M = 200+9;
const int N = 200000+9;
const int Q = 200;
const int SEED = 233;
const int MOD = 9999971;

int n,top,bot;
bitset<M> BIN[M];
struct Data{
int dec,len;
bitset<M> bin;
}que[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void Add_BIN(bitset<M> &A, bitset<M> B) {
static short tmp[M];
memset(tmp,0,sizeof(tmp));
for (int i=1;i<Q;i++) {
tmp[i] += (short)A[i] + B[i];
tmp[i+1] += tmp[i] / 2;
tmp[i] &= 1;
}
for (int i=1;i<Q;i++) A[i] = tmp[i];
}

inline int Get_Hash(bitset<M> &A, const int len) {
int ret = 0;
for (int i=1;i<=len;i++)
ret = (LL)(ret + A[i]) * SEED % MOD;
return ret;
}

inline bool Extend(Data w, bool v) {
w.dec = (LL)(w.dec+v)*SEED % MOD;

if (w.dec != Get_Hash(w.bin, w.len)) return 0;
else return que[++top] = w, 1;
}

int main(){

BIN[1][1] = 1;
for (int i=2;i<Q;i++) {
BIN[i] = BIN[i-1]<<1;
}

que[1].len = que[2].len = 1;
que[2].dec = SEED;
que[2].bin[1] = 1;
bot = 1; top = 2;

for (int tmp=top;n;bot=tmp+1,tmp=top) {
for (int i=bot;i<=tmp && n;i++)
Extend(que[i],0);
for (int i=bot;i<=tmp && n;i++)
if (Extend(que[i],1)) n--;
}
for (int i=que[top].len;i;i--)
putchar(que[top].bin[i]?'1':'0');
return 0;
}


## 【Codeforces 732E】Sockets

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;
const double EPS = 1e-8;

struct Socks{
int id,val;
inline bool operator < (const Socks &tmp) const {
return val < tmp.val;
}
}s[N];
int p[N],n,m,nxt[N],num[N],v1[N],v2[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void insert(int w, int v) {
static int T = 0;
nxt[++T] = head[w]; num[T] = v;
}

int main(){
for (int i=1;i<=n;i++) p[i] = read();
for (int i=1;i<=m;i++) s[i].val = read(), s[i].id = i;
for (int i=1;i<=n;i++) insert(p[i],i);
sort(s+1,s+1+m);
for (int i=1;i<=m;i++) {
for (int w=0,cur=s[i].val;;cur=(int)(ceil((double)cur/2)+EPS),w++) {
v1[s[i].id] = w;
break;
}
if (cur == 1) break;
}
}
int vout1 = 0, vout2 = 0;
for (int i=1;i<=m;i++) vout1 += v1[i];
for (int i=1;i<=n;i++) vout2 += (v2[i] > 0);
cout<<vout2<<' '<<vout1<<endl;
for (int i=1;i<=m;i++) printf("%d ",v1[i]); cout<<endl;
for (int i=1;i<=n;i++) printf("%d ",v2[i]);
return 0;
}


## 【BZOJ 3829】[POI2014] FarmCraft

#include<bits/stdc++.h>
using namespace std;

const int N = 500000+9;
const int M = 1000000+9;

int n,tmp[N],beg[N],end[N],tot,C1;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void Add_Edge(int u, int v) {
static int T = 0;
}

inline bool CMP(const int &a, const int &b) {
return max(f[a],g[a]+2+f[b]) < (f[b],g[b]+2+f[a]);
}

void DP(int w, int fa) {
int cnt = 0;
if (to[i] != fa) cnt++;
}
beg[w] = tot + 1;
end[w] = (tot += cnt); cnt = -1;
for (int i=head[w];i;i=nxt[i]) if (to[i] != fa) {
DP(to[i],w);
g[w] += g[to[i]] + 2;
tmp[beg[w]+(++cnt)] = to[i];
}
if (beg[w] <= end[w]) {
sort(tmp+beg[w],tmp+end[w]+1,CMP);
}
for (int i=beg[w],sum=0;i<=end[w];i++) {
f[w] = max(f[w], f[tmp[i]] + sum + 1);
sum += g[tmp[i]] + 2;
}
}

int main(){
for (int i=1;i<=n;i++) {
}
C1 = f[1];
for (int i=1;i<n;i++) {
}
DP(1,1);
printf("%d\n",max(g[1]+C1,f[1]));
return 0;
}


## 【Codeforces 712C】Memory and De-Evolution

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main(){