mcfx's blog - 2016年10月

BZOJ 3993: [SDOI2015]星际战争

admin — Wed, 26 Oct 2016 23:55:00 +0800

###Description
3333年，在银河系的某星球上，X军团和Y军团正在激烈地作战。在战斗的某一阶段，Y军团一共派遣了N个巨型机器人进攻X军团的阵地，其中第i个巨型机器人的装甲值为Ai。当一个巨型机器人的装甲值减少到0或者以下时，这个巨型机器人就被摧毁了。X军团有M个激光武器，其中第i个激光武器每秒可以削减一个巨型机器人Bi的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪，一个激光武器只能攻击一些特定的敌人。Y军团看到自己的巨型机器人被X军团一个一个消灭，他们急需下达更多的指令。为了这个目标，Y军团需要知道X军团最少需要用多长时间才能将Y军团的所有巨型机器人摧毁。但是他们不会计算这个问题，因此向你求助。

###Input
第一行，两个整数，N、M。
第二行，N个整数，A1、A2…AN。
第三行，M个整数，B1、B2…BM。
接下来的M行，每行N个整数，这些整数均为0或者1。这部分中的第i行的第j个整数为0表示第i个激光武器不可以攻击第j个巨型机器人，为1表示第i个激光武器可以攻击第j个巨型机器人。

###Output
一行，一个实数，表示X军团要摧毁Y军团的所有巨型机器人最少需要的时间。输出结果与标准答案的绝对误差不超过10-3即视为正确。

###Sample Input
2 2
3 10
4 6
0 1
1 1

###Sample Output
1.300000

###HINT
战斗开始后的前0.5秒，激光武器1攻击2号巨型机器人，激光武器2攻击1号巨型机器人。1号巨型机器人被完全摧毁，2号巨型机器人还剩余8的装甲值；
接下来的0.8秒，激光武器1、2同时攻击2号巨型机器人。2号巨型机器人被完全摧毁。
对于全部的数据，1<=N, M<=50，1<=Ai<=105，1<=Bi<=1000，输入数据保证X军团一定能摧毁Y军团的所有巨型机器人

###Solution
考虑二分答案，假设当前答案为time，那么从源点到Bi连容量为time*Bi的边，从Ai到汇点连容量为Ai的边，Bi,Ai间连inf，跑最大流即可

###Code
```c++
#include<bits/stdc++.h>

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back

const int N=200,M=3000;

struct edge
{
	int to,ne;
	double w;
}e[M*2+2];

int p[N+1],em=2,dep[N+1],q[N],qe,fa[N+1];
double fl[N+1];
bool vis[N+1];

inline void add(int a,int b,double w)
{
	e[em].to=b,e[em].w=w,e[em].ne=p[a],p[a]=em++;
	e[em].to=a,e[em].w=0,e[em].ne=p[b],p[b]=em++;
}

bool dfs(int s,int t)
{
	if(s==t)return 1;
	for(int j=p[s];j;j=e[j].ne)
		if(!vis[e[j].to]&&e[j].w&&dep[e[j].to]>dep[s])
		{
			vis[e[j].to]=1;
			fl[e[j].to]=min(e[j].w,fl[s]);
			fa[e[j].to]=j^1;
			if(dfs(e[j].to,t))return 1;
		}
	return 0;
}

inline double dinic(int s,int t)
{
	double flow=0;
	while(1)
	{
		memset(dep,0,sizeof(dep));
		q[0]=s,qe=1,dep[s]=1;
		for(int i=0;i^qe;i++)
		{
			for(int j=p[q[i]];j;j=e[j].ne)
				if(!dep[e[j].to]&&e[j].w)
				{
					dep[e[j].to]=dep[q[i]]+1;
					q[qe++]=e[j].to;
				}
		}
		if(!dep[t])break;
		while(1)
		{
			memset(vis,0,sizeof(vis));
			fl[s]=0x7fffffff;
			dfs(s,t);
			if(!vis[t])break;
			flow+=fl[t];
			for(int i=t;i!=s;i=e[fa[i]].to)
				e[fa[i]].w+=fl[t],e[fa[i]^1].w-=fl[t];
		}
	}
	return flow;
}

int n,m,a[50],b[50],atk[50][50];

inline bool judge(double time)
{
	int s=n+m,t=n+m+1;
	memset(p,0,sizeof(p));
	em=2;
	double s1=0,s2;
	for(int i=0;i<m;i++)
		add(s,i,time*b[i]);
	for(int i=0;i<n;i++)
		add(i+m,t,a[i]),s1+=a[i];
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
			if(atk[i][j])
				add(i,j+m,1e20);
	s2=dinic(s,t);
	if(abs(s1-s2)<1e-4)return 1;else return 0;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		scanf("%d",a+i);
	for(int i=0;i<m;i++)
		scanf("%d",b+i);
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
		{
			int k;
			scanf("%d",&k);
			atk[i][j]=k;
		}
	double l=0,r=1e4;
	while(r-l>1e-4)
	{
		if(judge((l+r)/2))
			r=(l+r)/2;
		else
			l=(l+r)/2;
	}
	printf("%.6lf\n",r);
}
```

BZOJ 2656: [Zjoi2012]数列(sequence)

admin — Fri, 21 Oct 2016 00:08:00 +0800

###Description
小白和小蓝在一起上数学课，下课后老师留了一道作业，求下面这个数列的通项公式：
![1.jpg][1]
小白作为一个数学爱好者，很快就计算出了这个数列的通项公式。于是，小白告诉小蓝自己已经做出来了，但为了防止小蓝抄作业，小白并不想把公式公布出来。于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的，想出了一个绝妙的方法：即让小蓝说一个正整数N，小白则说出 的值，如果当N很大时小白仍能很快的说出正确答案，这就说明小白的确得到了公式。但这个方法有一个很大的漏洞：小蓝自己不会做，没法验证小白的答案是否正确。作为小蓝的好友，你能帮帮小蓝吗？

###Input
输入文件第一行有且只有一个正整数T，表示测试数据的组数。
第2～T+1行，每行一个非负整数N。

###Output
输出文件共包含T行。
第i行应包含一个不含多余前缀0的数，它的值应等于An(n为输入数据中第i+1行被读入的整数)

###Sample Input
3
1
3
10

###Sample Output
1
2
3

###HINT
T<=20,N<=10^100

###Solution
首先手推几个较小的值，可以发现当i为奇数时，递归算几次A(i)，会产生一些相同的值
那么直接记忆化就行了
至于证明，我也不会（从二进制的角度考虑的话，似乎大概就logn种值）

###Code
```c++
#include<cstdio>
#include<cstring>
#include<tr1/unordered_map>

#define bas 1000000000
#define rep(a,b) if(a<(b))a=(b)

struct hjd
{
	int a[20],len;
	hjd(){
		len=0;
		memset(a,0,sizeof(a));
	}
	hjd(const hjd &x)
	{
		len=x.len;
		memset(a,0,sizeof(a));
		for(int i=0;i<len;i++)a[i]=x.a[i];
	}
	hjd(int x){
		len=1;
		memset(a,0,sizeof(a));
		a[0]=x;
	}
	bool operator ==(const hjd &x)const
	{
		if(len^x.len)return 0;
		for(int i=0;i<len;i++)
			if(a[i]^x.a[i])return 0;
		return 1;
	}
	inline void div2()
	{
		for(int i=len-1;i>0;i--)
		{
			if(a[i]&1)a[i-1]+=bas;
			a[i]>>=1;
		}
		a[0]>>=1;
		if(!a[len-1])len--;
	}
	inline void plus(const hjd &x)
	{
		rep(len,x.len);
		for(int i=0;i<len;i++)
		{
			a[i]+=x.a[i];
			if(a[i]>bas)a[i]-=bas,a[i+1]++;
		}
		if(a[len])len++;
	}
	inline void print()
	{
		printf("%d",a[len-1]);
		for(int i=len-2;i>=0;i--)
			printf("%09d",a[i]);
		printf("\n");
	}
};

struct hjd_hash
{
	size_t operator ()(const hjd &x)const//乱搞哈希 
	{
		int ans=0;
		for(int i=0;i<x.len;i++)
			ans^=x.a[i];
		return ans;
	}
};

std::tr1::unordered_map<hjd,hjd,hjd_hash> s;
int aaa=0;
hjd calc(hjd x)
{
	hjd ret;
	if(!x.len)return ret;
	while((~x.a[0]&1)&&(x.len!=1||x.a[0]!=1))x.div2();//除去2 
	if(s.find(x)!=s.end())return s[x];//记忆化 
	hjd y=x;
	x.div2();
	ret=calc(x);
	x.plus(1);
	ret.plus(calc(x));//计算A(x) 
	s[y]=ret;
	return ret;
}

char buf[200];

int main()
{
	s[1]=1;
	int T,n,uu[9],y=1;
	for(int i=0;i<9;i++)
		uu[i]=y,y*=10;
	scanf("%d",&T);
	while(T--)
	{
		s.clear();
		s[1]=1;
		scanf("%s",buf);
		n=strlen(buf);
		hjd tmp;
		for(int i=n-1,j=0,ll=1;i>=0;i--)//输入，倒序 
		{
			tmp.len=ll;
			tmp.a[ll-1]+=(buf[i]-'0')*uu[j];
			j++;
			if(j==9)j=0,ll++;
		}
		hjd t2=calc(tmp);
		if(!t2.len)
			printf("0\n");
		else
		{
			t2.print();
		}
	}
}
```

[1]: /usr/uploads/2016/10/1978638953.jpg

BZOJ 3884: 上帝与集合的正确用法

admin — Sun, 16 Oct 2016 00:59:00 +0800

###Description
根据一些书上的记载，上帝的一次失败的创世经历是这样的：
第一天，	上帝创造了一个世界的基本元素，称做“元”。
第二天，	上帝创造了一个新的元素，称作“α”。“α”被定义为“元”构成的集合。容易发现，一共有两种不同的“α”。
第三天，	上帝又创造了一个新的元素，称作“β”。“β”被定义为“α”构成的集合。容易发现，一共有四种不同的“β”。
第四天，	上帝创造了新的元素“γ”，“γ”被定义为“β”的集合。显然，一共会有16种不同的“γ”。
如果按照这样下去，上帝创造的第四种元素将会有65536种，第五种元素将会有2^65536种。这将会是一个天文数字。
然而，上帝并没有预料到元素种类数的增长是如此的迅速。他想要让世界的元素丰富起来，因此，日复一日，年复一年，他重复地创造着新的元素……
然而不久，当上帝创造出最后一种元素“θ”时，他发现这世界的元素实在是太多了，以致于世界的容量不足，无法承受。因此在这一天，上帝毁灭了世界。
至今，上帝仍记得那次失败的创世经历，现在他想问问你，他最后一次创造的元素“θ”一共有多少种？
上帝觉得这个数字可能过于巨大而无法表示出来，因此你只需要回答这个数对p取模后的值即可。
你可以认为上帝从“α”到“θ”一共创造了10^9次元素，或10^18次，或者干脆∞次。
一句话题意：
![1.png][1]

###Input
接下来T行，每行一个正整数p，代表你需要取模的值

###Output
T行，每行一个正整数，为答案对p取模后的值

###Sample Input
3
2
3
6

###Sample Output
0
1
4

###HINT
对于100%的数据，T<=1000,p<=10^7

###Solution
首先考虑欧拉定理，如果把这个数设为S，可以发现$$2^S=2^{S\ mod\ \phi(p)}$$ （当p是2的倍数时可以先除去所有2处理）
那么问题就转化为了求$$S\ mod\ \phi(p)$$，同样考虑，最终$$\phi(p)$$会等于1，直接处理即可
由于除了第一次，每次都会除去至少一个2，所以单次时间复杂度为$$O(logp)$$

###Code
```c++
#include<cstdio>
 
#define pmax 10000000
int prime[1000000],pm,fi[pmax+1],ans[pmax+1];
bool np[pmax+1],ga[pmax+1];
 
inline int pow(int a,long long t,int mod)
{
    long long p=1,q=a,f=1;
    for(;f<=t;f<<=1)
    {
        if(f&t)p=p*q%mod;
        q=q*q%mod;
    }
    return p;
}
 
void exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=(a/b)*x;
}
 
inline int gen(int x,int t)
{
    if(x==1)return 0;
    int a,b,p;
    if(x>t)exgcd(x,t,a,b);else exgcd(t,x,b,a);
    p=(long long)ans[x]*t%(x*t)*b%(x*t);
    if(p<0)p+=x*t;
    return p;
}
 
int getans(int x)
{
    int t=1;
    while(~x&1)x>>=1,t<<=1;
    if(!ga[x])ga[x]=1,ans[x]=pow(2,1000ll*fi[x]+getans(fi[x]),x);
    return gen(x,t);
}
 
int main()
{
    for(int i=2;i<=pmax;i++)
    {
        if(!np[i])prime[pm++]=i,fi[i]=i-1;
        for(int j=0;j<pm&&i*prime[j]<=pmax;j++)
        {
            np[i*prime[j]]=1;
            if(i%prime[j])
            {
                fi[i*prime[j]]=fi[i]*(prime[j]-1);
            }
            else
            {
                fi[i*prime[j]]=fi[i]*prime[j];
                break;
            }
        }
    }
    ga[1]=1,ans[1]=0;
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%d\n",getans(n));
    }
}
```

[1]: /usr/uploads/2016/10/774614809.png

Codeforces 723E.One-Way Reform

admin — Mon, 03 Oct 2016 22:55:00 +0800

###Description
There are n cities and m two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connects the city with itself. It is possible that there is no way to get from one city to some other city using only these roads.

The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the number of roads that begins in the city equals to the number of roads that ends in it.

有一个无向图，n个点，m条边，无自环，无重边，现在要给每个边定方向，使得入度等于出度的点最多

###Input
The first line contains a positive integer t (1 ≤ t ≤ 200) — the number of testsets in the input.

Each of the testsets is given in the following way. The first line contains two integers n and m (1 ≤ n ≤ 200, 0 ≤ m ≤ n·(n - 1) / 2) — the number of cities and the number of roads in Berland.

The next m lines contain the description of roads in Berland. Each line contains two integers u and v (1 ≤ u, v ≤ n) — the cities the corresponding road connects. It's guaranteed that there are no self-loops and multiple roads. It is possible that there is no way along roads between a pair of cities.

It is guaranteed that the total number of cities in all testset of input data doesn't exceed 200.

Pay attention that for hacks, you can only use tests consisting of one testset, so t should be equal to one.

###Output
For each testset print the maximum number of such cities that the number of roads that begins in the city, is equal to the number of roads that ends in it.

In the next m lines print oriented roads. First print the number of the city where the road begins and then the number of the city where the road ends. If there are several answers, print any of them. It is allowed to print roads in each test in arbitrary order. Each road should be printed exactly once.

###Example
input
2
5 5
2 1
4 5
2 3
1 3
3 5
7 2
3 7
4 2
output
3
1 3
3 5
5 4
3 2
2 1
3
2 4
3 7

###Solution
将度数为奇的边间连上边，然后每次从任一点出发，走过一条边就定为走的方向，直到回到出发点。当所有边被定向后停止操作
那么对于度数为偶数的边，其入度一定等于出度，输出时去掉新加的边

###Code
```c++
#include<bits/stdc++.h>

struct edge
{
    int to,ne;
    bool v;
}e[50000];

int p[201],em=2,deg[201],n,m;
bool ok[50000];

inline void add(int a,int b,bool v)
{
    e[em].to=b,e[em].v=v,e[em].ne=p[a],p[a]=em++;
}

inline void solve()
{
    scanf("%d%d",&n,&m);
    em=2;
    memset(p,0,n*4+4);
    memset(deg,0,n*4+4);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b,1);
        add(b,a,1);
        deg[a]++;
        deg[b]++;
    }
    int lst=0,ans=n;
    for(int i=1;i<=n;i++)
        if(deg[i]&1)
        {
            if(lst)
                add(i,lst,0),add(lst,i,0),deg[i]++,deg[lst]++;
            else
                lst=i;
            ans--;
        }
    memset(ok,0,em);
    lst=1;
    printf("%d\n",ans);
    while(1)
    {
        while(lst<=n&&!deg[lst])lst++;
        if(lst>n)break;
        int k=lst;
        while(1)
        {
            bool f=1;
            for(int i=p[k];i;i=e[i].ne)
                if(!ok[i])
                {
                    f=0,ok[i]=1,ok[i^1]=1;
                    if(e[i].v)printf("%d %d\n",k,e[i].to);
                    deg[k]--;
                    deg[e[i].to]--;
                    k=e[i].to;
                    break;
                }
            if(f)break;
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
}
```