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

### 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;
}


## 【Codeforces 734F】Anton and School

### Code

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

const int N = 200009;

int n, a[N], b[N], c[N];

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 check() {
static int cnt[100];
for (int i = 1; i <= n; i++) {
for (int t = 0, v = a[i]; v; v >>= 1, ++t) {
cnt[t] += v & 1;
}
}
for (int i = 1; i <= n; i++) {
int tb = 0, tc = 0;
for (int j = 0, cur = 1; j <= 30; j++, cur <<= 1) {
tb += (a[i] & cur)? cnt[j] * cur: 0;
tc += (a[i] & cur)? n * cur: cnt[j] * cur;
}
if (tb != b[i] || tc != c[i]) {
return false;
}
}
return true;
}

int main() {
for (int i = 1; i <= n; i++) {
}
LL sum = 0;
for (int i = 1; i <= n; i++) {
sum += a[i];
}
if (sum % (n << 1)) {
puts("-1");
exit(0);
}
sum /= n << 1;
for (int i = 1; i <= n; i++) {
if ((a[i] -= sum) % n) {
puts("-1");
exit(0);
} else {
a[i] /= n;
}
}
if (!check()) {
puts("-1");
exit(0);
}
for (int i = 1; i <= n; i++) {
printf("%d ", a[i]);
}
return 0;
}


## 【POJ 3922】A simple stone game

### Code

#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;

const int N = 10000000;

int n,k,x,y,a[N],b[N];

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 main() {
for (int t = 1, T = read(); t <= T; ++t) {
a[0] = b[0] = x = y = 0;
while (a[x] < n) {
a[x + 1] = b[x] + 1;
for (++x; (LL)a[y + 1] * k < a[x]; ++y);
b[x] = y? b[y] + a[x]: a[x];
}
if (a[x] == n) {
printf("Case %d: lose\n", t);
} else {
int ans = 0;
for (; n && x; --x) {
if (n >= a[x]) {
n -= a[x];
ans = a[x];
}
}
printf("Case %d: %d\n", t, ans);
}
}
return 0;
}


## 【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;
}


## 【Codeforces 715A】Plus and Square Root

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

int main(){
int n; cin>>n; cout<<2<<endl;
for (LL i=2;i<=n;i++) cout<<i*(i+1)*(i+1)-i+1<<endl;
return 0;
}


## 【Codeforces 708B】Recover the String

《论何为血wa》

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int MAXN = 1000000+9;

LL a00,a01,a10,a11,tag,n;
char pat[MAXN];

char c=getchar(); LL 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 int solve(LL w) {
w *= 2; LL tmp = sqrt(w);
if (tmp*(tmp+1) != w) {tag++;return 0;}
else return tmp+1;
}

int main(){
if (!a00 && !a11 && !a01 && !a10) cout<<0<<endl, exit(0);
else if (a11 && !a00 && !a10 && !a01) {
if(solve(a11)) {
a11 = solve(a11);
for (LL i=1;i<=a11;i++) pat[i] = '1';
cout<<pat+1;
} else cout<<"Impossible";
} else if (!a11 && a00 && !a10 && !a01) {
if(solve(a00)){
a00 = solve(a00);
for (LL i=1;i<=a00;i++) pat[i] = '0';
cout<<pat+1;
} else cout<<"Impossible";
} else {
a00 = solve(a00); a11 = solve(a11);
if (tag) cout<<"Impossible";
else if (a00*a11 != a01 + a10) cout<<"Impossible";
else {
n = a00+a11; int l1 = a10/a00, l2 = a01/a00;
if (l1*a00 < a10) pat[n-l2-(a10-l1*a00)] = '1';
if (l2*a00 < a01) pat[l1+(a01-l2*a00)+1] = '1';
for (int i=1;i<=l1;i++) pat[i] = '1';
for (int i=1;i<=l2;i++) pat[n-i+1] = '1';
for (int i=1;i<=n;i++) if (!pat[i]) pat[i] = '0';
printf("%s",pat+1);
}
}
return 0;
}