## 【BZOJ 2296】[POJ Challenge] 随机种子

### Code

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

const LL MX = 9876543201999999;
const LL MN = 9876543201000000;

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 = read(); T; T--) {
if (!x) {
puts("-1");
} else {
LL r = MX / x + 1, l = MN / x;
while (l <= r) {
LL mid = l + r >> 1;
if (x * mid < MN) {
l = mid + 1;
} else if (x * mid > MX) {
r = mid - 1;
} else {
printf("%lld\n", mid * x);
break;
}
}
}
}
return 0;
}


## 【BZOJ 4722】由乃

### 解题报告

More Formally：次数会爆 $long long$

DP的那个函数必须是一个凸包

## 【BZOJ 2654】tree

### Code

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

const int N = 100000+9;

struct Edge{int u,v,val,col;}e[N];
int n,m,STA,fa[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 int find(int w) {
int f = fa[w], tmp;
while (f != fa[f]) f = fa[f];
while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
return f;
}

bool cmp_mx(const Edge &A, const Edge &B) {return A.val < B.val || (A.val == B.val && A.col > B.col);}
bool cmp_mn(const Edge &A, const Edge &B) {return A.val < B.val || (A.val == B.val && A.col < B.col);}

inline bool judge(int delta) {
int cnt = 0;
sort(e+1, e+1+m, cmp_mx);
for (int i=1;i<=n;i++) fa[i] = i;
for (int i=1;i<=m;i++) {
if (find(e[i].u) != find(e[i].v)) {
fa[find(e[i].u)] = find(e[i].v);
cnt += e[i].col;
}
}
if (cnt < STA) return 1;

int cost = 0; cnt = 0;
sort(e+1, e+1+m, cmp_mn);
for (int i=1;i<=n;i++) fa[i] = i;
for (int i=1;i<=m;i++) {
if (find(e[i].u) != find(e[i].v)) {
fa[fa[e[i].u]] = fa[e[i].v];
cnt += e[i].col;
cost += e[i].val;
}
}
if (cnt > STA) return 0;
else {
printf("%d\n",cost-STA*delta);
exit(0);
}
}

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

int l=-100,r=100,mid;
while (l <= r) {
mid = l + r >> 1;
for (int i=1;i<=m;i++) if (e[i].col) e[i].val += mid;
if (judge(mid)) r = mid - 1;
else l = mid + 1;
for (int i=1;i<=m;i++) if (e[i].col) e[i].val -= mid;
}
return 0;
}


## 【BZOJ 4443】[Scoi2015] 小凸玩矩阵

### Code

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

const int N = 500 + 9;
const int M = 500000;
const int INF = 1e9;

int n,m,K,S,T,val[N/2][N/2],tot,TMP[M];
queue<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 void Add_Edge(int u, int v) {
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = 1;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}

inline bool BFS() {
memset(dis,60,sizeof(dis));
dis[S] = 0; que.push(S);

while (!que.empty()) {
int w = que.front(); que.pop();
if (dis[to[i]] > dis[w] + 1 && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}

return dis[T] < 1e8;
}

int DFS(int w, int v) {
if (w == T) {
return v;
} else {
int ret = 0;
for (int &i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
int tmp = DFS(to[i], min(v, flow[i]));
v -= tmp; ret += tmp;
flow[i] -= tmp; flow[i^1] += tmp;
if (!v) break;
}
}
return ret;
}
}

inline int Dinic() {
int ret = 0;
while (BFS()) {
ret += DFS(S,INF);
}
return ret;
}

inline bool judge(int sta) {
TT = 1; S = 0; T = N - 1;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (val[i][j] <= sta) {
}
}
}
for (int i=1;i<=m;i++)
return Dinic() >= n - K + 1;
}

int main(){
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
}
}
sort(TMP+1, TMP+1+tot);
tot = unique(TMP+1, TMP+1+tot) - TMP - 1;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
val[i][j] = lower_bound(TMP+1, TMP+1+tot, val[i][j]) - TMP;
}
}

int l=1, r=tot, mid, vout=0;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid)) r = mid-1, vout = mid;
else l = mid + 1;
}
printf("%d\n",TMP[vout]);
return 0;
}


## 【BZOJ 4326】[NOIP2015] 运输计划

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

const int N = 300000+9;
const int M = N << 1;

int dep[N],fa[N][20],in[N],out[N],dis[N],n,m,div_cnt;
struct Query{int u,v,lca,len;}q[N];

namespace fastIO{
#define BUF_SIZE 100000
#define OUT_SIZE 100000
#define ll long long
bool IOerror=0;
inline char nc(){
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if (p1==pend){
if (pend==p1){IOerror=1;return -1;}
//{printf("IO error!\n");system("pause");for (;;);exit(0);}
}
return *p1++;
}
inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (sign)x=-x;
}
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (sign)x=-x;
}
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (ch=='.'){
double tmp=1; ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
}
if (sign)x=-x;
}
char ch=nc();
for (;blank(ch);ch=nc());
if (IOerror)return;
for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
*s=0;
}
for (c=nc();blank(c);c=nc());
if (IOerror){c=-1;return;}
}
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (bo)x=-x;
}
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (bo)x=-x;
}
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (ch=='.'){
double tmp=1;
for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
}
if (bo)x=-x;
}
char ch=getchar();
for (;blank(ch);ch=getchar());
for (;!blank(ch);ch=getchar())*s++=ch;
*s=0;
}
#ifdef _WIN32
scanf("%I64d",&x);
#else
#ifdef __linux
scanf("%lld",&x);
#else
puts("error:can't recognize the system!");
#endif
#endif
}
//fwrite->write
struct Ostream_fwrite{
char *buf,*p1,*pend;
Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
void out(char ch){
if (p1==pend){
fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
}
*p1++=ch;
}
void print(int x){
static char s[15],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1);
}
void println(int x){
static char s[15],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1); out('\n');
}
void print(ll x){
static char s[25],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1);
}
void println(ll x){
static char s[25],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1); out('\n');
}
void print(double x,int y){
static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
if (x<-1e-12)out('-'),x=-x;x*=mul[y];
ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
}
void println(double x,int y){print(x,y);out('\n');}
void print(char *s){while (*s)out(*s++);}
void println(char *s){while (*s)out(*s++);out('\n');}
void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
~Ostream_fwrite(){flush();}
}Ostream;
inline void print(int x){Ostream.print(x);}
inline void println(int x){Ostream.println(x);}
inline void print(char x){Ostream.out(x);}
inline void println(char x){Ostream.out(x);Ostream.out('\n');}
inline void print(ll x){Ostream.print(x);}
inline void println(ll x){Ostream.println(x);}
inline void print(double x,int y){Ostream.print(x,y);}
inline void println(double x,int y){Ostream.println(x,y);}
inline void print(char *s){Ostream.print(s);}
inline void println(char *s){Ostream.println(s);}
inline void println(){Ostream.out('\n');}
inline void flush(){Ostream.flush();}
//puts->write
char Out[OUT_SIZE],*o=Out;
inline void print1(int x){
static char buf[15];
char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
while(x)*p1++=x%10+'0',x/=10;
while(p1--!=buf)*o++=*p1;
}
inline void println1(int x){print1(x);*o++='\n';}
inline void print1(ll x){
static char buf[25];
char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
while(x)*p1++=x%10+'0',x/=10;
while(p1--!=buf)*o++=*p1;
}
inline void println1(ll x){print1(x);*o++='\n';}
inline void print1(char c){*o++=c;}
inline void println1(char c){*o++=c;*o++='\n';}
inline void print1(char *s){while (*s)*o++=*s++;}
inline void println1(char *s){print1(s);*o++='\n';}
inline void println1(){*o++='\n';}
inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}
struct puts_write{
~puts_write(){flush1();}
}_puts;
inline void print2(int x){printf("%d",x);}
inline void println2(int x){printf("%d\n",x);}
inline void print2(char x){printf("%c",x);}
inline void println2(char x){printf("%c\n",x);}
inline void print2(ll x){
#ifdef _WIN32
printf("%I64d",x);
#else
#ifdef __linux
printf("%lld",x);
#else
puts("error:can't recognize the system!");
#endif
#endif
}
inline void println2(ll x){print2(x);printf("\n");}
inline void println2(){printf("\n");}
#undef ll
#undef OUT_SIZE
#undef BUF_SIZE
};

inline void Add_Edge(int u, int v, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void DFS(int w, int f) {
fa[w][0] = f;
in[w] = ++div_cnt;
dep[w] = dep[f] + 1;
if (to[i] != f) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = cost[i];
DFS(to[i], w);
}
}
out[w] = div_cnt;
}

inline int LCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (register int j=19;~j;j--) {
if (dep[fa[u][j]] >= dep[v]) {
u = fa[u][j];
}
}
if (u == v) return v;
for (register int j=19;~j;j--) {
if (fa[u][j] != fa[v][j]) {
u = fa[u][j];
v = fa[v][j];
}
}
return fa[u][0];
}

inline bool judge(int lim) {
memset(delta,0,sizeof(delta));
int cnt = 0, MN = 0, MX = 0;
for (register int i=1;i<=m;i++) {
if (q[i].len > lim) {
cnt++;
MN = max(MN, q[i].len - lim);
delta[q[i].lca] -= 2;
delta[q[i].u] ++;
delta[q[i].v] ++;
}
}
for (register int i=n;i;i--)
delta[i] += delta[i+1];

for (register int i=1;i<=n;i++) {
if (delta[in[i]] - delta[out[i]+1] >= cnt) {
MX = max(sur[i], MX);
}
}
return MX >= MN;
}

int main(){
using namespace fastIO;
int l=0,r=0,mid,ret;
for (int i=1,u,v,w;i<n;i++) {
l = max(l, w);
}
DFS(1,1);
for (int j=1;j<=19;j++) {
for (int i=1;i<=n;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
for (int i=1,u,v,lca;i<=m;i++) {
q[i].len = dis[u] + dis[v] - (dis[lca] << 1);
r = max(r, q[i].len);
q[i].u = in[u]; q[i].v= in[v]; q[i].lca = in[lca];
}

l = r - l; ret = r;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid)) ret = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d\n",ret);
return 0;
}


—– UPD 2016.11.11 —–

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

const int N = 300000+9;
const int M = N << 1;

int dep[N],fa[N][20],in[N],out[N],dis[N],n,m,div_cnt;
struct Query{int u,v,lca,len;}q[N];

static const int BUF_SIZE = 1000000;
static char buf[BUF_SIZE],*p1=0,*p2=0;
if (p1 == p2){
if (p2==p1) return -1;
} return *p1++;
}

return ret*f;
}

inline void Add_Edge(int u, int v, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void DFS(int w, int f) {
fa[w][0] = f;
in[w] = ++div_cnt;
dep[w] = dep[f] + 1;
if (to[i] != f) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = cost[i];
DFS(to[i], w);
}
}
out[w] = div_cnt;
}

inline int LCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (register int j=19;~j;j--) {
if (dep[fa[u][j]] >= dep[v]) {
u = fa[u][j];
}
}
if (u == v) return v;
for (register int j=19;~j;j--) {
if (fa[u][j] != fa[v][j]) {
u = fa[u][j];
v = fa[v][j];
}
}
return fa[u][0];
}

inline bool judge(int lim) {
memset(delta,0,sizeof(delta));
int cnt = 0, MN = 0, MX = 0;
for (register int i=1;i<=m;i++) {
if (q[i].len > lim) {
cnt++;
MN = max(MN, q[i].len - lim);
delta[q[i].lca] -= 2;
delta[q[i].u] ++;
delta[q[i].v] ++;
}
}
for (register int i=n;i;i--)
delta[i] += delta[i+1];

for (register int i=1;i<=n;i++) {
if (delta[in[i]] - delta[out[i]+1] >= cnt) {
MX = max(sur[i], MX);
}
}
return MX >= MN;
}

int main(){
int l=0,r=0,mid,ret;
for (int i=1,u,v,w;i<n;i++) {
l = max(l, w);
}
DFS(1,1);
for (int j=1;j<=19;j++) {
for (int i=1;i<=n;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
for (int i=1,u,v,lca;i<=m;i++) {
q[i].len = dis[u] + dis[v] - (dis[lca] << 1);
r = max(r, q[i].len);
q[i].u = in[u]; q[i].v= in[v]; q[i].lca = in[lca];
}

l = r - l; ret = r;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid)) ret = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d\n",ret);
return 0;
}


## 【BZOJ 2095】[Poi2010] Bridges

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 2000+9;
const int M = 10000+9;
const int INF = 1e9;

struct Edge{int u,v,w1,w2;}edge[M];
int n,m,MX,MN=INF,in[N],out[N],cur[M];
queue<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 void Add_Edge(int u, int v, int f) {
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}

inline bool BFS(){
memset(dis,-1,sizeof(dis));
dis[S] = 0; que.push(0);

while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}

return ~dis[T];
}

int DFS(int w, int f) {
if (w == T) {
return f;
} else {
int ret = 0;
for (int &i=cur[w],tmp;i && f;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1) {
tmp = DFS(to[i], min(f, flow[i]));
ret += tmp; f -= tmp;
flow[i] -= tmp; flow[i^1] += tmp;
}
}
return ret;
}
}

inline int Dinic(){
int ret = 0;
while (BFS()) {
ret += DFS(S,INF);
}
return ret;
}

inline bool judge(int lim){
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
S = 0; T = N - 1; TT = 1;
int tot = 0;

for (int i=1;i<=m;i++) {
if (lim < edge[i].w1) {
continue;
} else if (lim < edge[i].w2) {
in[edge[i].v]++;
out[edge[i].u]++;
} else {
in[edge[i].v]++;
out[edge[i].u]++;
}
}

for (int i=1;i<=n;i++) {
if (abs(in[i]-out[i]) & 1) {
return false;
} else if (in[i] < out[i]) {
tot += out[i] - in[i];
} else if (in[i] > out[i]) {
}
}

return Dinic() == tot;
}

int main(){
for (int i=1;i<=m;i++) {
if (edge[i].w1 > edge[i].w2) {
swap(edge[i].w1, edge[i].w2);
swap(edge[i].u, edge[i].v);
}
MX = max(MX, edge[i].w2);
MN = min(MN, edge[i].w1);
}

int l = MN, r = MX, mid, ret = -1;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid)) ret = mid, r = mid - 1;
else l = mid + 1;
}
if (~ret) printf("%d\n",ret);
else puts("NIE");
return 0;
}


## 【NOIP十连测】[D3T1] 平均数

std也是二分，然后搞归并排序

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

const int N = 100000+9;
const double EPS = 0.00001;

LL arr[N],k;
double tmp[N];
int n,Rank[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;
}

namespace Fenwick_Tree{
#define BIT Fenwick_Tree
#define lowbit(x) ((x)&-(x))
int cnt[N],tot,lim;

inline void init(int w){
memset(cnt,0,sizeof(cnt));
tot = 1; lim = n+1;
for (int i=w;i<=lim;i+=lowbit(i)) {
cnt[i]++;
}
}

inline int query(int sta) {
int ret = 0;
for (int i=sta;i;i-=lowbit(i)) {
ret += cnt[i];
}
}

inline void insert(int w) {
tot++;
for (int i=w;i<=lim;i+=lowbit(i)) {
cnt[i]++;
}
}
};

bool judge(double sta) {
for (register int i=1;i<=n;++i) {
tmp[i] = arr[i] - sta*i;
}
tmp[n+1] = 0;
sort(tmp+1,tmp+1+n+1);
for (register int i=0;i<=n;++i) {
Rank[i] = lower_bound(tmp+1,tmp+1+n+1,arr[i]-sta*i) - tmp;
}
LL ret = 0;
BIT::init(Rank[0]);
for (int i=1;i<=n;i++) {
ret += BIT::query(Rank[i]);
BIT::insert(Rank[i]);
}
return ret >= k;
}

int main(){
k = (LL)n*(n+1) / 2 - k + 1;
for (int i=1;i<=n;i++) {
}
double L = 0, R = 1e9, mid;
while (R - L > EPS) {
mid = (L + R) / 2;
if (judge(mid)) {
R = mid;
} else {
L = mid;
}
}
printf("%.4lf",(R+L)/2);
return 0;
}


## 【NOIP十连测】[D1T1] String Master

std是O(n^3)的算法？

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

const int N = 300+9;
const int SGZ = 27;

int n,k;
char S[N],T[N];
queue<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 judge(int len) {
for (int d=0,cur=0,p1,p2,tmp;d<=n-len;d++,cur=0) {
while (!que.empty()) que.pop(); que.push(0); p1 = 0, p2 = p1 + d;
for (int i=1;i<len;i++)
tmp = (S[++p1] != T[++p2]),
cur += tmp, que.push(tmp);
while (p2 < n) {
tmp = (S[++p1] != T[++p2]);
cur += tmp, cur -= que.front();
que.pop(), que.push(tmp);
if (cur <= k) return true;
}
}
for (int d=0,cur=0,p1,p2,tmp;d<=n-len;d++,cur=0) {
while (!que.empty()) que.pop(); que.push(0); p1 = 0, p2 = p1 + d;
for (int i=1;i<len;i++)
tmp = (T[++p1] != S[++p2]),
cur += tmp, que.push(tmp);
while (p2 < n) {
tmp = (T[++p1] != S[++p2]);
cur += tmp, cur -= que.front();
que.pop(), que.push(tmp);
if (cur <= k) return true;
}
}
return false;
}

int main(){
freopen("master.in","r",stdin);
freopen("master.out","w",stdout);
scanf("%s%s",S+1,T+1);
int l=1,r=n,ret=0;
while (l <= r) {
int mid = l + r >> 1;
if (judge(mid)) ret = mid, l = mid+1;
else r = mid-1;
}
printf("%d\n",ret);
return 0;
}


## 【Codeforces 715B】Complete The Graph

1）暴力最短路，复杂度O(nmlogn)

2）神奇二分，复杂度O(mlognlogm)

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

const LL N = 1000+9;
const LL M = 20000+9;
const LL INF = 1e14;

queue<LL> que;

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 void Add_Edge(LL u, LL v, LL d) {
static LL TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; cost[TT] = d;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; cost[TT] = d;
}

inline LL SPFA(){
for (int i=1;i<=n;i++) dis[i] = INF;
dis[S] = 0; que.push(S), inq[S] = 1;

while (!que.empty()) {
LL w = que.front(); que.pop(); inq[w] = 0;
for (LL i=head[w];i;i=nxt[i]) if (~cost[i] && dis[to[i]] > dis[w]+cost[i]) {
dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
}
} return dis[T];
}

int main(){
for (LL i=1,tmp;i<=m;i++) {
if (!tmp) tmp = -1, sign[i] = 1;
}
if (SPFA() < L) cout<<"NO", exit(0);
for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = 1;
if ((ty=SPFA()) > L) cout<<"NO", exit(0);
for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = INF;
LL w = T,len_tmp; while (w != S) {if(sign[sur[w]/2]) cost[sur[w]] = cost[sur[w]^1] = 1; w = to[sur[w]^1];}
while ((len_tmp=SPFA()) < L)
for (w=T;w!=S;w=to[sur[w]^1]) if (sign[sur[w]/2]) {
cost[sur[w]] += L - len_tmp, cost[sur[w]^1] += L - len_tmp; break;}
cout<<"YES"<<endl;
for (LL i=1;i<=m;i++)
if (sign[i] && cost[i*2] == -1) printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,L+1);
else printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,cost[i*2]);
return 0;
}


## 【Codeforces 713B】Searching Rectangles

CF上做的第一道交互题！

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

int n,x[5],y[5],vout[10];

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 int judge(int _x1,int _y1,int _x2,int _y2) {
printf("? %d %d %d %d\n",_x1,_y1,_x2,_y2);
fflush(stdout);
}

inline bool BETTER(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){
if (!vout[1]) return true;
LL s1 = (LL)(vout[3]-vout[1] + 1)*(vout[4]-vout[2] + 1) + (LL)(vout[7]-vout[5] + 1)*(vout[8]-vout[6] + 1);
LL s2 = (LL)(x2 - x1 + 1) * (y2 - y1 + 1) + (LL)(x4 - x3 + 1) * (y4 - y3 + 1);
return s2 < s1;
}

int main(){
int l = 1, r = n, mid, ret;
while (l <= r) {
mid = l + r >> 1;
if (judge(1,1,mid,n) >= 1) ret = mid, r = mid-1;
else l = mid+1;
} x[1] = ret;
l = ret, r = n, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(1,1,mid,n) >= 2) ret = mid, r = mid-1;
else l = mid+1;
} x[3] = ret;
l = 1, r = n, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid,1,n,n) >= 1) ret = mid, l = mid+1;
else r = mid-1;
} x[2] = ret;
l = 1, r = x[2], ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid,1,n,n) >= 2) ret = mid, l = mid+1;
else r = mid - 1;
} x[4] = ret;

l = 1, r = n, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(1,1,n,mid) >= 1) ret = mid, r = mid-1;
else l = mid+1;
} y[1] = ret;
l = y[1], r = n, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(1,1,n,mid) >= 2) ret = mid, r = mid-1;
else l = mid+1;
} y[3] = ret;
l = 1, r = n, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(1,mid,n,n) >= 1) ret = mid, l = mid+1;
else r = mid-1;
} y[2] = ret;
l = 1, r = y[2], ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (judge(1,mid,n,n) >= 2) ret = mid, l = mid+1;
else r = mid-1;
} y[4] = ret;

sort(x+1,x+5); sort(y+1,y+5);
for (int s=1;s<=4;s++) for (int i=s+1;i<=4;i++) for (int j=1;j<=4;j++) for (int k=j+1;k<=4;k++)
if (judge(x[s],y[j],x[i],y[k]) == 1) { int x1,x2,y1,y2;
for (int u=1;u<=4;u++) if (u != i && u != s) {x1=u; break;}
for (int u=x1+1;u<=4;u++) if (u != i && u != s) {x2=u; break;}
for (int u=1;u<=4;u++) if (u != j && u != k) {y1 = u; break;}
for (int u=y1+1;u<=4;u++) if (u != j && u != k) {y2=u;break;}
if (x[x1] > x[i] || x[x2] < x[s] || y[y1] > y[k] || y[y2] < y[j])
if (judge(x[x1],y[y1],x[x2],y[y2]) == 1 && BETTER(x[s],y[j],x[i],y[k],x[x1],y[y1],x[x2],y[y2]))
vout[1]=x[s],vout[2]=y[j],vout[3]=x[i],vout[4]=y[k],vout[5]=x[x1],vout[6]=y[y1],vout[7]=x[x2],vout[8]=y[y2];
}
putchar('!');
for (int i=1;i<=8;i++) printf(" %d",vout[i]);
return 0;
}