2016 ACM ICPC Asia Region - Tehran

2016 ACM ICPC Asia Region - Tehran

A - Tax

题目描述：算税。

solution

模拟。

B - Key Maker

题目描述：给出\(n\)个序列，给定一个序列，问\(n\)个序列中有多少个序列满足对应位的值小于或等于给定序列的值。

solution

模拟。

C - IOI 2017 Logo

题目描述：有\(m\)件作品，\(n\)个人投票，每个人可以选三件作品，分别给\(1, 2, 3\)分，每件作品按总分排序，总分相同按得\(3\)分的数量排序，还是相同，则按得\(2\)分得数量排序。输出第一的编号（可能有多个）

solution

模拟。

D - MicroRNA Ranking

题目描述：给出\(m\)个\(n\)的全排列，求一个\(n\)的全排列\(a_i\)，满足对于\(i<j\)，至少在一半的全排列中，\(a_i\)排在\(a_j\)的前面，求字典序最小的\(a_i\)，或无解。

solution

统计出\(cnt[i][j]\)表示\(i\)排在\(j\)前面的次数，如果\(cnt[i][j]\)小于一半，则\(j\)到\(i\)连一条边，表示\(j\)要排在\(i\)的前面。构出的图如果有环，或者不连通则无解。然后求字典序最小的拓扑序（用优先队列维护即可）。

时间复杂度：\(O(n^2(m+logn))\)

E - Möbius Strip

题目描述：普通的莫比乌斯带称为\(1\)型，拧了两次的为\(2\)型，即拧了\(n\)次为\(n\)型。现在有一个剪的操作：沿着莫比乌斯带的宽度\(1/3\)处划线，然后沿线剪下来，得到两个莫比乌斯带。现在给出两组莫比乌斯带，经过若干次剪的操作，使得两组相等。

solution

当\(n\)为偶数时，剪出来的两个莫比乌斯带都是\(n\)型；当\(n\)为奇数时，剪出来的一个是\(n\)型，一个是\(2n+2\)型。所以将奇数的都剪一遍，然后判断两组莫比乌斯带是不是相等（偶数数字相等即可，数量不必相等，奇数要完全相等）。

时间复杂度：\(O(n)\)

F - Expression

题目描述：带分式的表达式计算。

solution

大模拟。

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

typedef long long LL;
typedef vector<LL> vint;
const int cut=int(1e8);
const int maxn=510;

class gjd
{
	vint a;
	int len;

	public:

	gjd(int x=0)
	{
		a.clear();
		a.push_back(0);
		if (x==0)
		{
			a.push_back(0);
			len=1;
			return;
		}
		len=0;
		while (x)
		{
			++len;
			a.push_back(x%cut);
			x/=cut;
		}
	}

	gjd(string st)
	{
		a.clear();
		a.push_back(0);
		len=(st.length()-1)/8+1;
		for (int i=1; i<=len; ++i)
		{
			int en=int(st.length())-(i-1)*8;
			int start=max(0, int(st.length())-i*8);
			int num=0;
			for (int j=start; j<en; ++j)
				num=num*10+st[j]-'0';

			a.push_back(num);
		}
	}

	inline bool checkzero()
	{
		return (len==1 && a[1]==0);
	}

	bool operator <= (const gjd &b) const
	{
		if (len!=b.len) return len<b.len;
		for (int i=len; i; --i)
			if (a[i]!=b.a[i]) return a[i]<b.a[i];
		return true;
	}

	gjd operator + (const gjd &b) const
	{
		gjd ans;
		ans.len=max(len, b.len);
		ans.a.assign(ans.len+6, 0);

		for (int i=1; i<=len; ++i) ans.a[i]=a[i];
		for (int i=1; i<=b.len; ++i) ans.a[i]+=b.a[i];

		for (int i=1; i<=ans.len; ++i)
		{
			ans.a[i+1]+=ans.a[i]/cut;
			ans.a[i]%=cut;
		}
		if (ans.a[ans.len+1]) ++ans.len;
		ans.a.resize(ans.len+1);
		//ans.a.shrink_to_fit();
		return ans;
	}

	gjd operator - (const gjd &b) const
	{
		gjd ans=(*this);
		for (int i=1; i<=b.len; ++i) ans.a[i]-=b.a[i];
		for (int i=1; i<ans.len; ++i)
		{
			if (ans.a[i]<0)
			{
				ans.a[i]+=cut;
				ans.a[i+1]--;
			}
		}
		while (ans.len>1 && ans.a[ans.len]==0) --ans.len;
		ans.a.resize(ans.len+1);
		//ans.a.shrink_to_fit();
		return ans;
	}

	gjd operator * (const gjd &b) const
	{
		gjd ans;
		ans.len=len+b.len-1;
		ans.a.assign(ans.len+6, 0);

		for (int i=1; i<=len; ++i)
			for (int j=1; j<=b.len; ++j)
				ans.a[i+j-1]+=a[i]*b.a[j];
		for (int i=1; i<=ans.len; ++i)
		{
			ans.a[i+1]+=ans.a[i]/cut;
			ans.a[i]%=cut;
		}
		while (ans.a[ans.len+1])
		{
			++ans.len;
			ans.a[ans.len+1]=ans.a[ans.len]/cut;
			ans.a[ans.len]%=cut;
		}
		while (ans.len>1 && ans.a[ans.len]==0) --ans.len;
		ans.a.resize(ans.len+1);
		//ans.a.shrink_to_fit();
		return ans;
	}

	gjd operator / (const gjd &b) const
	{
		if (len<b.len) return gjd(0);
		gjd ans;
		ans.len=len-b.len+1;
		ans.a.assign(ans.len+6, 0);

		for (int i=ans.len; i; --i)
		{
			int L=0, R=cut;
			while (L+1<R)
			{
				int mid=(L+R)>>1;
				ans.a[i]=mid;
				if (b*ans<=(*this)) L=mid;
				else R=mid;
			}
			ans.a[i]=L;
		}
		while (ans.len>1 && ans.a[ans.len]==0) --ans.len;
		ans.a.resize(ans.len+1);
		//ans.a.shrink_to_fit();
		return ans;
	}

	gjd operator % (const gjd &b) const
	{
		return (*this)-(*this)/b*b;
	}

	void print()
	{
		printf("%lld", a[len]);
		for (int i=len-1; i; --i)
		{
			int x=a[i];
			for (int j=cut/10; j; j/=10)
			{
				printf("%d", x/j);
				x%=j;
			}
		}
	}
};

gjd gcd(gjd , gjd );

class frac
{
	gjd numerator, denominator;

	public:

	frac(int a=0, int b=1)
	{
		numerator=gjd(a);
		denominator=gjd(b);
	}

	frac(gjd a, gjd b)
	{
		numerator=a;
		denominator=b;
	}

	frac operator + (const frac &b) const
	{
		gjd tnum=numerator*b.denominator+b.numerator*denominator;
		gjd tde=denominator*b.denominator;
		//gjd d=gcd(tnum, tde);
		//return frac(tnum/d, tde/d);
		return frac(tnum, tde);
	}

	frac operator * (const frac &b) const
	{
		gjd tnum=numerator*b.numerator;
		gjd tde=denominator*b.denominator;
		//gjd d=gcd(tnum, tde);
		//return frac(tnum/d, tde/d);
		return frac(tnum, tde);
	}

	frac operator / (frac b) const
	{
		swap(b.numerator, b.denominator);
		return (*this)*b;
	}

	void print()
	{
		gjd d=gcd(numerator, denominator);
		(numerator/d).print();
		putchar('/');
		(denominator/d).print();
		putchar('\n');
	}
};

int n, m;
char st[maxn][maxn];
int len[maxn];

gjd gcd(gjd b, gjd c)
{
	if (c.checkzero()) return b;
	else return gcd(c, b%c);
}
void getst(int nid)
{
	char ch;
	while ((ch=getchar())!='-' && ch!='+' && ch!='*' && ch!=' ' && (ch<'0' || ch>'9'));
	len[nid]=1;
	st[nid][1]=ch;
	while ((ch=getchar())=='-' || ch=='+' || ch=='*' || ch==' ' || (ch>='0' && ch<='9')) st[nid][++len[nid]]=ch;
}
void read()
{
	m=0;
	for (int i=1; i<=n; ++i)
	{
		getst(i);
		m=max(m, len[i]);
	}
	for (int i=1; i<=n; ++i)
		for (int j=len[i]+1; j<=m; ++j)
			st[i][j]=' ';
}
frac getnum(int x, int &y, int lim)
{
	string str="";
	while (y<=lim && isdigit(st[x][y])) str+=st[x][y++];
	return frac(gjd(str), gjd(1));
}
frac dfs(int up, int down, int le, int ri)
{
	stack<frac> num;
	stack<int> oper;
	while (!num.empty()) num.pop();
	while (!oper.empty()) oper.pop();

	int nid=0;
	for (int j=le; j<=ri; ++j)
	{
		for (int i=up; i<=down; ++i)
			if (st[i][j]!=' ')
			{
				nid=i;
				break;
			}

		if (nid!=0) break;
	}
	for (int j=le; j<=ri; )
	{
		if (st[nid][j]==' ') { ++j;  continue; }

		if (st[nid][j]>='0' && st[nid][j]<='9') num.push(getnum(nid, j, ri));
		else
		if (st[nid][j]=='-')
		{
			int k=j;
			while (k<=ri && st[nid][k]=='-') ++k;
			num.push(dfs(up, nid-1, j, k-1)/dfs(nid+1, down, j, k-1));
			j=k;
		}
		else
		{
			int level=st[nid][j]=='*';
			while (!oper.empty() && oper.top()>=level)
			{
				frac c=num.top();
				num.pop();
				frac b=num.top();
				num.pop();

				if (oper.top()) num.push(b*c);
				else num.push(b+c);
				oper.pop();
			}
			oper.push(level);
			++j;
		}
	}
	while (!oper.empty())
	{
		frac c=num.top();
		num.pop();
		frac b=num.top();
		num.pop();
		if (oper.top()) num.push(b*c);
		else num.push(b+c);
		oper.pop();
	}
	return num.top();
}
int main()
{
	while (scanf("%d", &n)==1 && n)
	{
		read();
		dfs(1, n, 1, m).print();
	}
	return 0;
}

G - Elections

题目描述：有\(n\)座城市，每个城市的选票为\(a_i\)，能赢得每个城市的选票的概率为\(p_i\)，若得到的总票数大于总票数的一半，则胜利，问胜利的概率。

solution

背包\(dp\)

时间复杂度：\(O(nm)\)(\(m\)为总票数)

H - Explosion at Cafebazaar

题目描述：有\(n\)个点，\(m\)条边的有向图，每个点初始时有\(1bit\)的信息，然后每个时刻复制自己的信息给每一个相邻的点，然后删掉自己的信息，最后接受信息。问最后有多少个点会信息爆炸。

solution

强连通缩点。如果一个点内的环有度大于\(2\)的点，则这个点信息爆炸；否则这个点能到的点（这个点要是一个环）信息爆炸。信息爆炸的点能到的点也是信息爆炸。

时间复杂度：\(O(m+n)\)

I - Linear Galaxy

题目描述：在\(x\)轴上有\(2^n+1\)个点，从中选出\(2^{n-1}+1\)个点，加边（边权为两点间的距离）构成一个简单环，求出最短边的最大值。

J - Rahyab

题目描述：给出一个有向图，一个起点，一个终点，现在有\(C\)个人要从起点走到终点，每个人确定自己走的线路，一个人的花费等于他走的边中最多人经过的边的人数的平方。求所有人总花费的最小值。

solution

显然，最终的线路只会相同，分离，不会边相交。所有可以用网络流求出从起点到终点的边不相交的路径数，将人平均分配到这几条路径上。

时间复杂度：\(O(n^2m)\)(远小于)

K - Base Stations

题目描述：给出平面上的\(n\)个点，每个点有一个\(k\)值，求一个距离最远的\(k\)值不同的点对的距离的平方。

solution

\(KD-TREE\)

时间复杂度：\(O(n\sqrt{n})\)

L - Skeletons

题目描述：不太明白。