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

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2296

解题报告

我们假设高位是$9876543201$,低$6$位随意
那么每一次加上$x$,导致高位至多增加$1$
所以一定有解,至于是多少倍?我们可以二分

Code

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

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

inline int read() {
	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--) {
		LL x = read();
		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;
}

【CodeChef PARADE】Annual Parade

相关链接

题目传送门:https://www.codechef.com/problems/PARADE
神犇题解:http://blog.csdn.net/jasonvictoryan/article/details/53395098

解题报告

这题先只考虑一个询问的情况

这显然可以使用拆点+二分图最大权匹配去做
具体来说:每个点拆成出度和入度两个点,然后出度放左边,入度放右边
考虑每找到一条增广路,就是在原图中走了一条边
那么不管是连接了两条路径,或是新走到一个点,都会使总费用减少一个$C$
但每走一次增广路,都会花费一些费用$v$
显然我们应该在$v > C$的时候停止增广

现在考虑多个询问
因为是费用流算法,所以单次增广的费用$v_i$是单调不减的
于是我们可以记录每一次增广的$v_i$。对于询问就二分,然后求前缀和就好
当然不想二分,也可以先排个序然后扫一遍,反正总的时间复杂度主要还是卡在费用流那里

【BZOJ 4722】由乃

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4722
神犇题解Ⅰ:http://blog.csdn.net/werkeytom_ftd/article/details/54429577
神犇题解Ⅱ:http://www.cnblogs.com/wxxlouisa/p/6139165.html

解题报告

这题看起来一眼不可做啊!
仔细想一想,发现确实不会做

看完题解后:果然是乱搞题!
先不管修改操作的话,如果询问的区间长度超过13的话,一定有解
相关证明可以参见:http://blog.csdn.net/werkeytom_ftd/article/details/54429577

现在考虑修改操作
因为单次询问最多涉及13个数
所以只需要支持单点查询+区间修改就可以了
于是用线段树打标记什么的就可以啦!

然而我们惊讶的发现,我们打的Tag在最后计算的时候会很大
More Formally:次数会爆 $ long long$
于是用不了快速幂了 QwQ
然后又不会了

于是接着去膜拜题解
发现我们可以用类似快速幂一样的东西搞出来
我们最终要求的是:$ {a_i}^{{3^x}}$
于是我们预处理出 $ f(i,j)$ 表示 $ {a_i}^{{3^{{2^j}}}}$
于是像快速幂一样搞一搞就可以啦!

最后我们求出了这13个数是什么,怎么判断有没有解呢?
我们可以 Meet in middle !

【Tsinsen 1342】能量棒

相关链接

题目传送门:http://www.tsinsen.com/A1342
参考代码:http://paste.ubuntu.com/23803611/

解题报告

这题乍看需要 $ O({n^2})$ 的DP的样子
然而可以用 Tree 这道题一样,给每一次转移附加一个值 $ k$
然后直接转移,记录一下转移了多少次,根据次数的多少来调整 $ k$
然后再用上决策单调性来优化DP的话
这样似乎就可以在 $ O(n{\log ^{\rm{2}}}n)$ 的时间复杂度内解决这个问题了!

值得一提的是,毛爷爷讲了一下这个方法的适用范围:
DP的那个函数必须是一个凸包
不过毛爷爷也说了:
只要拍一拍,拍不出错就行啦!

【BZOJ 4538】[HNOI2016] 网络

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4538
神犇题解:http://krydom.com/bzoj4538/

解题报告

这题我先说一种怪怪的做法 QwQ
考虑使用主席树,第一维是权值(用BIT搞成后缀和),第二维是DFS序
这样的话,对于询问我们可以在第一维的权值上进行二分
对于每一次二分 $ a$ ,我们可以通过判断覆盖该点的区间个数是否等于所有不小于 $ a$ 的区间个数是否相等

这样话,原问题转化为:在主席树上的区间加减问题
这一块的时空复杂度是 $ O(n{\log ^3}n)$ 的
然后考虑上二分的 $ log$ 这样的话,复杂度就是 $ O(n{\log ^4}n)$ 的
这种做法是自己YY的,感觉很有道理的样子
然而懒得写代码了,也不知道对不对

另外的话,再说一说正解吧!
考虑一条路径,说白了就是查询路径上的点的时候不查到该路径
查询非该路径上的点的时候查询到该路径
这时考虑树链剖分的话,该路径对应的 $ {log(n)}$ 个区间应该忽略,其他部分添加上这个路径的信息
因为是一整块区间抠掉 $ {log(n)}$ 个区间,所以剩余部分也只会有 $ {log(n)}$ 个区间
于是树链剖分暴力搞一搞就可以辣!
时空复杂度比之前的做法应该要稍微优越一点

【BZOJ 2654】tree

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2654
神犇题解:http://blog.csdn.net/PoPoQQQ/article/details/47980565

题解

感觉这个题很好玩的样子!
考虑给每一个白边加上一个固定的权值
那么使用白边的数量可以用这个权值来调整
唯一需要注意的就是,这种变化可能不是线性的
也就是说可能会有断层的情况,需要特殊处理一下

值得注意的是,这种方法具有较高的可移植性:
在某一套小火车的模拟题中,一道很恶心的DP也可以用此方法来解决

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];
 
inline int read(){
    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(){
    n = read(); m = read(); STA = read();
    for (int i=1;i<=m;i++) {
        e[i].u = read() + 1; e[i].v = read() + 1;
        e[i].val = read(); e[i].col = read() ^ 1;
    } 
     
    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] 小凸玩矩阵

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4443
数据生成器:http://paste.ubuntu.com/23621596/
神犇题解:http://krydom.com/bzoj4443/

题解

考虑最值的话,肯定想到二分
又因为每行/每列只能选一个
那就是二分图匹配辣!

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 head[N],to[M],nxt[M],flow[M],cur[N],dis[N],TT;
int n,m,K,S,T,val[N/2][N/2],tot,TMP[M];
queue<int> que;

inline int read(){
	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();
		for (int i=head[w];i;i=nxt[i]) {
			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()) {
		memcpy(cur,head,sizeof(head));
		ret += DFS(S,INF);
	} 
	return ret;
}

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

int main(){
	n = read(); m = read(); K = read();
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			val[i][j] = TMP[++tot] = read();
		}
	}
	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] 运输计划

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4326

这货的做法就是二分之后,用DFS序判断一下
然而这货居然卡常…….
其实是↑上面这个纸张不会用指针 ╮(╯▽╰)╭
用了加强的流读入才能在UOJ上A
另外前排膜拜Menci,指针用得贼溜:https://oi.men.ci/noip2015-transport/

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

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

int head[N],to[M],nxt[M],cost[M],sur[M],delta[N];
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
    //fread->read
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            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';}
    inline void read(int &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;
    }
    inline void read(ll &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;
    }
    inline void read(double &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;
    }
    inline void read(char *s){
        char ch=nc();
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
        *s=0;
    }
    inline void read(char &c){
        for (c=nc();blank(c);c=nc());
        if (IOerror){c=-1;return;}
    }
    //getchar->read
    inline void read1(int &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;
    }
    inline void read1(ll &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;
    }
    inline void read1(double &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;
    }
    inline void read1(char *s){
        char ch=getchar();
        for (;blank(ch);ch=getchar());
        for (;!blank(ch);ch=getchar())*s++=ch;
        *s=0;
    }
    inline void read1(char &c){for (c=getchar();blank(c);c=getchar());}
    //scanf->read
    inline void read2(int &x){scanf("%d",&x);}
    inline void read2(ll &x){
        #ifdef _WIN32
            scanf("%I64d",&x);
        #else
        #ifdef __linux
            scanf("%lld",&x);
        #else
            puts("error:can't recognize the system!");
        #endif
        #endif
    }
    inline void read2(double &x){scanf("%lf",&x);}
    inline void read2(char *s){scanf("%s",s);}
    inline void read2(char &c){scanf(" %c",&c);}
    inline void readln2(char *s){gets(s);}
    //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; 
	for (register int i=head[w];i;i=nxt[i]) {
		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;
	read(n); read(m);
	for (int i=1,u,v,w;i<n;i++) {
		read(u); read(v); read(w);
		l = max(l, w);
		Add_Edge(u, v, 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++) {
		read(u); read(v); lca = LCA(u, v);
		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 —–
找高一神犇学习了一下fread的使用技巧,现在最大的一个点只用500ms辣!

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 300000+9;
const int M = N << 1;
 
int head[N],to[M],nxt[M],cost[M],sur[M],delta[N];
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];

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

inline int read(){
	char c=Read(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=Read();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=Read();}
	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; 
    for (register int i=head[w];i;i=nxt[i]) {
        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;
    n = read(); m = read();
    for (int i=1,u,v,w;i<n;i++) {
        u = read(); v = read(); w = read();
        l = max(l, w);
        Add_Edge(u, v, 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++) {
        u = read(); v = read(); lca = LCA(u, v);
        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

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2095

这个题目啊!瞄一眼就知道是二分吧?
接下来就是给你一些有向边&无向边,让你判断是否存在欧拉回路

对于有向边,没有悬念,直接记录对于出度入度的贡献
只与有向边嘛,不妨先随便定一个向,然后考虑使用网络流进行调整
具体细节可以参见:http://blog.csdn.net/wzq_qwq/article/details/48651379

#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];
int S,T,dis[N],flow[M],head[N],nxt[M],to[M],TT; 
queue<int> que;

inline int read(){
	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()) {
		memcpy(cur,head,sizeof(head));
		ret += DFS(S,INF);
	}
	return ret;
}

inline bool judge(int lim){
	memset(in,0,sizeof(in));
	memset(out,0,sizeof(out));
	memset(head,0,sizeof(head));
	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]++;
			Add_Edge(edge[i].u, edge[i].v, 2);
		}
	}
	
	for (int i=1;i<=n;i++) {
		if (abs(in[i]-out[i]) & 1) {
			return false;
		} else if (in[i] < out[i]) {
			Add_Edge(S,i,out[i]-in[i]);	
			tot += out[i] - in[i];
		} else if (in[i] > out[i]) {
			Add_Edge(i,T,in[i]-out[i]);
		}
	}
	
	return Dinic() == tot;
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=m;i++) {
		edge[i].u = read();
		edge[i].v = read();
		edge[i].w1 = read();	
		edge[i].w2 = read();
		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] 平均数

题目传送门:http://oi.cyo.ng/wp-content/uploads/2016/10/test3_problem.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2016/10/solution.pdf

这题被挖出是大原题了:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1711
另外™鬼畜出题人硬生生把NOIP搞成NOI Professional有意思吗?
YLUL)A7V{OMTL8]~RL2VL$8

std也是二分,然后搞归并排序
不过我有一种更自然的方法,复杂度一样,常数较大:
首先求出前缀和,记为ai
二分最后的答案记为x
不难发现,平均值大于x的需要满足一下条件:\(\frac{{{a_i} – {a_j}}}{{i – j}} \le x\)
然后化简一下得到:\({a_i} – x \cdot i \le {a_j} – x \cdot j\)
换一句话来说,把ai-x*i作为新序列求逆序对的个数就好啦!
结果被卡常了…..
管他的,51nod上能过

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

inline int read(){
	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];
		}
		return tot - ret;
	}
	
	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(){
	n = read(); cin>>k;
	k = (LL)n*(n+1) / 2 - k + 1;
	for (int i=1;i<=n;i++) {
		arr[i] = arr[i-1] + read();
	}
	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

题目传送门:http://oi.cyo.ng/wp-content/uploads/2016/10/noip_test1_statements.pdf

std是O(n^3)的算法?
明明NOIP范围内可以O(n^2logn)搞的!
就是二分长度,然后用滑动窗口搞一搞

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

inline int read(){
	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);
	n = read(); k = read();
	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

题目传送门:http://codeforces.com/contest/716/problem/D
官方题解:http://codeforces.com/blog/entry/47169

这题很好玩,有两种写法。

1)暴力最短路,复杂度O(nmlogn)
做法就是每一次找最短路,然后改一改

2)神奇二分,复杂度O(mlognlogm)
将可更改的边拉出来,排成一溜
二分一个点k,使1~k的边为1,其余边为INF
终止条件:k时最短路<=l,k-1时最短路>L
于是第k条边就是关键边,只用考虑这条边的长度即可
感觉好神!

考试的时候,我写的是第一种

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

LL head[N],to[M],nxt[M],cost[M],U[M],V[M],dis[N],n,m,L,S,T,sign[M],ty,inq[N],sur[N];
queue<LL> que;

inline LL read(){
	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(){
	n = read(); m = read(); L = read(); S = read() + 1; T = read() + 1;
	for (LL i=1,tmp;i<=m;i++) {
		U[i] = read()+1, V[i] = read()+1; tmp = read();
		if (!tmp) tmp = -1, sign[i] = 1;
		Add_Edge(U[i],V[i],tmp);
	}
	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

题目传送门:http://codeforces.com/contest/714/problem/D

CF上做的第一道交互题!
然而考场上并没能A掉QAQ
就是二分出几个关键点,然后暴力问一问

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

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

inline int read(){
	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);
	return read();
}

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(){
	n = read();
	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;
}