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结束分割线