Day1：二分答案，三分查找，快速幂，欧拉筛素数 | 题目：火星人，Bridge，GCD，Prime Path

二分答案

【JSOI 2008】火星人

对于第一个操作用\(hash + 二分\)来求得，二三直接平衡树维护即可。

【Bridge】

混合图欧拉回路模板，还是挺有意思OTZ...

具体就是首先调整图的定向，使得有欧拉回路（入度=出度）。

然后，将所有\(in>out\)的点向超级汇点连一个容量为\((in - out)>>1\)的边，超级源点向所有\((out > in)\)的点连一条容量是\((out - in)>>1\)的边，对于图中所有定向为\((x,y)\)的无向边连一个容量为1的边。

接着跑网络流，看是否满流判断有解还是无解。

最后把在网络流中建出的容量为1的边中经过流量的边反向，就跑出了一个欧拉回路有向图。

#include<bits/stdc++.h>

using namespace std;

#define debug(x) cout<<"#X:"<<x<<endl;

const int maxn = 200010;

const int INF = 0x3f3f3f3f;

inline int read(){

	int q=0,f=1;char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;ch=getchar();

	}

	while(isdigit(ch)){

		q=q*10+ch-'0';ch=getchar();

	}

	return q*f;

}

struct edge{

	int to;

	int nxt;

	int w;

}e[maxn];

int cnt = 1;

int head[maxn];

inline void add(int u,int v,int w) {

	e[++cnt].to = v;

	e[cnt].nxt = head[u];

	head[u] = cnt;

	e[cnt].w = w;

}

inline void Add(int u,int v,int w) {

	add(u,v,w);

	add(v,u,0);

}

int S,T;

int dis[maxn];

queue<int>q;

int cur[maxn];

inline bool bfs() {

	for(int i = S;i <= T; ++i) {

		dis[i] = -1;

	}

	dis[S] = 0;

	q.push(S);

	while(!q.empty()){

		int u = q.front();

		q.pop();

		for(int i = head[u];i;i=e[i].nxt) {

			int y = e[i].to;

			if(e[i].w && dis[y] == -1) {

				dis[y] = dis[u] + 1;

				q.push(y);

			}

		}

	}

	return dis[T] != -1;

}

inline int dfs(int x,int f) {

	if(x == T) return f;

	int w;

	int used = 0;

	for(int i = cur[x];i;i=e[i].nxt) {

		int y = e[i].to;

		if(e[i].w && dis[y] == dis[x] + 1){

			w = dfs(y,min(e[i].w,f - used));

			e[i].w -= w;

			e[i ^ 1].w += w;

			used += w;

			if(e[i].w)cur[x] = i;

			if(used == f) return f;

		}

	}

	if(!used) dis[x] = -1;

	return used;

}

inline int dinic(){

	int ans = 0;

	while(bfs()) {

		for(int i = S;i <= T; ++i) {

			cur[i] = head[i];

		}

		ans += dfs(S,INF);

	}

	return ans;

}

int in[maxn];

int out[maxn];

int n,m;

int u[maxn];

int v[maxn];

int w1[maxn];

int sum;

int w2[maxn];

inline bool check(int mid) {

	memset(head,0,sizeof(head));

	memset(in,0,sizeof(in));

	memset(out,0,sizeof(out));

	cnt = 1;

	S = 0,T = n + 1;

	sum = 0;

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

		if(w1[i] <= mid) out[u[i]]++,in[v[i]]++;

		if(w2[i] <= mid) Add(v[i],u[i],1);

	}

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

		if(abs(in[i] - out[i]) & 1) return 0;

	}

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

		int c = in[i] - out[i];

		if(c > 0) {

			sum += (c >> 1);

		}

		if(c > 0){

			Add(S,i,c>>1);

		}

		if(c < 0){

			Add(i,T,(-c)>>1);

		}

	}

	int res = dinic();

	return res == sum;

}

int l,r;

int main() {

	n = read(),m = read();

	l = INF;

	r = -INF;

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

		u[i] = read(),v[i] = read(),w1[i] = read(),w2[i] = read();

		if(w1[i] > w2[i]) swap(w1[i],w2[i]),swap(u[i],v[i]);

		l = min(l,w1[i]);

		r = max(r,w2[i]);

	}

	//debug(1);

	while(l <= r) {

		int mid = (l + r) >> 1;

		//debug(mid);

		if(check(mid)){

			r = mid - 1;

		}

		else {

			l = mid + 1;

		}

	}

	if(!check(l)){

		puts("NIE");

	}

	else printf("%d\n",l);

	return 0;

}

三分查找

似乎好像会啊...OTZ

期末考试算不算？？

其实比二分有点就是函数可以不单调。

每次把区间三分（l,l+(r-l)/3,r-(r-l)/3,r)比较哪个更靠近最值，然后取舍区间即可。

快速幂

啊啊还是总结一下模板算了...

inline int pow(int x,int y) {

    int res = 1;

    while(y) {

        if(y & 1) res = res * x;

        x = x * x;

        y >>= 1;

    }

    return res;

}

欧拉筛素数

一个欧拉筛啊。。。

inline void init(){

	int tot = 0;

	memset(check, 0, sizeof(check));

	for (int i = 2; i < MAXL; ++i)

	{

	  if (!check[i])

	  {

	    prime[tot++] = i;

	  }

	  for (int j = 0; j < tot; ++j)

	  {

	    if (i * prime[j] > MAXL)

	    {

	      break;

	    }

	    check[i*prime[j]] = 1;

	    if (i % prime[j] == 0)

	    {

	      break;

	    }

	  }

	}

}

欧拉函数

inline void init(){

int tot = 0;

phi[1] = 1;

memset(check, 0, sizeof(check));

for (int i = 2; i < MAXL; ++i)

{

  if (!check[i])

  {

    prime[tot++] = i;

    phi[i] = i - 1;

  }

  for (int j = 0; j < tot; ++j)

  {

    if (i * prime[j] > MAXL)

    {

      break;

    }

    check[i*prime[j]] = 1;

    if (i % prime[j] == 0)

    {

      phi[i*prime[j]] = phi[i] * prime[j];

      break;

    }else

    {

      phi[i*prime[j]] = phi[i] * (prime[j]-1);

    }

  }

}

}

【bzoj 2095】GCD

对于每个素数，影响的只有\([1,n/p]\)筛出欧拉素数之后前缀和处理。

#include <bits/stdc++.h>

const int maxn = 10000010;

using namespace std;

int phi[maxn];

int prime[maxn];

bool vis[maxn];

long long ans;

int n;

int cnt;

inline void init() {

	phi[1] = 1;

	for(int i = 2;i <= n; ++i) {

		if(!vis[i]) {

			phi[i] = i - 1;

			prime[++cnt] = i;

		}

		for(int j = 1;j <= cnt; ++j) {

			int tmp = prime[j];

			if(i * tmp > n) break;

			vis[i * tmp] = 1;

			if(i % tmp == 0) {

				phi[i * tmp] = phi[i] * tmp;

			}

			else {

				phi[i * tmp] = phi[i] * phi[tmp];

			}

		}

	}

}

long long s[maxn];

int main (){

	cin >> n;

	init();

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

		s[i] = s[i - 1] + phi[i];

	}

	for(int i = 1;i <= cnt;  ++i) {

		ans += (s[n / prime[i]]<<1) - 1;

	}

	cout<<ans<<endl;

	return 0;

}

【poj 3126】Prime Path

bfs+素数判定OTZ懒得写了...

Day1结束分割线

巴特西

训练计划Day1

Day1：二分答案，三分查找，快速幂，欧拉筛素数 | 题目：火星人，Bridge，GCD，Prime Path

最新文章

热门文章