正文

2017-2018 ACM-ICPC, NEERC, Northern Subregional Contest

IP云
IP云V管理员/2 阅读
11/30
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

A. Auxiliary Project

完全背包。 

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<string>

#include<ctype.h>

#include<math.h>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<bitset>

#include<algorithm>

#include<time.h>

using namespace std;

void fre() {  }

#define MS(x, y) memset(x, y, sizeof(x))

#define ls o<<1

#define rs o<<1|1

typedef long long LL;

typedef unsigned long long UL;

typedef unsigned int UI;

template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }

template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }

const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;

template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }

int casenum, casei;

int n;

int f[1000005];

int g[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int main()

{

	freopen("auxiliary.in", "r", stdin);

	freopen("auxiliary.out", "w", stdout);

	while(~scanf("%d",&n))

	{

		MS(f, -1);

		f[0] = 0;

		for(int i = 0; i <= n; ++i)

		{

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

			{

				if(i - g[j] >= 0 && f[i - g[j]] >= 0)

				{

					gmax(f[i], f[i - g[j]] + j);

				}

			}

		}

		printf("%d\n", f[n]);

	}

	return 0;

}

/*

【trick&&吐槽】

【题意】

【分析】

【时间复杂度&&优化】

*/

B. Boolean Satisfiability

设$t$为出现过的变量个数，若同时存在某个变量以及其反变量，则答案为$2^t$，否则答案为$2^t-1$。 

#include<cstdio>

#include<cstring>

typedef long long ll;

const int N=100010;

bool v[N],neg[N];

char s[N];

int n,i;

int main(){

	freopen("boolean.in", "r", stdin);

	freopen("boolean.out", "w", stdout);

	scanf("%s",s+1);

	n=strlen(s+1);

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

		if(s[i]=='|')i++;

		else if(s[i]=='~'){

			neg[s[i+1]]=1;

			i+=2;

		}else{

			v[s[i]]=1;

			i++;

		}

	}

	ll ans=1,flag=1;

	for(i=1;i<N;i++){

		if(v[i]||neg[i])ans*=2;

		if(v[i]&&neg[i])flag=0;

	}

	printf("%I64d",ans-flag);

}

C. Consonant Fencity

$O(2^{19})$枚举所有辅音字母的大小写即可。 

#include<cstdio>

#include<cstring>

typedef long long ll;

const int N=1000010;

char s[N];

int n,i,j,mx,now,ans,S;

bool is[26],big[26];

int g[26][26],w[26][26],q[26],m;

int main(){

	freopen("consonant.in", "r", stdin);

	freopen("consonant.out", "w", stdout);

	scanf("%s",s);

	n=strlen(s);

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

		g[s[i-1]-'a'][s[i]-'a']++;

	}

	is['a'-'a']=1;

	is['e'-'a']=1;

	is['i'-'a']=1;

	is['o'-'a']=1;

	is['u'-'a']=1;

	is['w'-'a']=1;

	is['y'-'a']=1;

	for(i=0;i<26;i++)if(!is[i])q[m++]=i;

	for(i=0;i<26;i++)for(j=0;j<26;j++){

		if(is[i]||is[j])g[i][j]=0;

	}

	for(i=0;i<m;i++)for(j=0;j<m;j++)w[i][j]=g[q[i]][q[j]];

	for(S=0;S<1<<m;S++){

		now=0;

		for(i=0;i<m;i++)for(j=0;j<m;j++)if(((S>>i)^(S>>j))&1)now+=w[i][j];

		if(now>mx)mx=now,ans=S;

	}

	//printf("mx=%d\n",mx);

	S=ans;

	for(i=0;i<26;i++)big[i]=0;

	for(i=0;i<m;i++)if(S>>i&1)big[q[i]]=1;

	for(i=0;i<n;i++)if(big[s[i]-'a'])putchar(s[i]-'a'+'A');else putchar(s[i]);

}

D. Dividing Marbles

留坑。

E. Equal Numbers

令$goal=lcm(a_1,a_2,...,a_n)$，那么对于每种数，可以变成另一个存在的倍数，或者直接变成$goal$。

按照代价从小到大合并即可。 

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<string>

#include<ctype.h>

#include<math.h>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<bitset>

#include<algorithm>

#include<time.h>

using namespace std;

void fre() {  }

#define MS(x, y) memset(x, y, sizeof(x))

#define ls o<<1

#define rs o<<1|1

typedef long long LL;

typedef unsigned long long UL;

typedef unsigned int UI;

template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }

template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }

const int N = 1e6 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;

template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }

int casenum, casei;

int n;

map<int, int>mop;

vector<int>vt[2];

int f[N];

int main()

{

	freopen("equal.in", "r", stdin);

	freopen("equal.out", "w", stdout);

	while(~scanf("%d",&n))

	{

		mop.clear();

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

		{

			int x;

			scanf("%d", &x);

			++mop[x];

		}

		int top = 1e6;

		for(int i = 0; i <= 1; ++i)vt[i].clear();

		for(auto it : mop)

		{

			int i = it.first;

			vt[0].push_back(it.second);

			for(int j = i + i; j <= top; j += i)if(mop.count(j))

			{

				vt[1].push_back(it.second);

				break;

			}

		}

		int ans = mop.size();

		MS(f, 63); f[0] = ans;

		int sum = 0;

		int sz = vt[1].size();

		sort(vt[1].begin(), vt[1].end());

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

		{

			sum += vt[1][j];

			gmin(f[sum], ans - j - 1);

		}

		sum = 0;

		sz = vt[0].size();

		sort(vt[0].begin(), vt[0].end());

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

		{

			sum += vt[0][j];

			gmin(f[sum], ans - j);

		}

		for(int i = 0; i <= n; ++i)

		{

			if(i)gmin(f[i], f[i - 1]);

			printf("%d ", f[i]);

		}

		puts("");

	}

	return 0;

}

/*

【trick&&吐槽】

6

3 4 1 2 1 2

【题意】

【分析】

【时间复杂度&&优化】

*/

F. Fygon 2.0

建立有向图，边$a\rightarrow b$表示$a\leq b$，那么每个SCC中的变量都要相等。

缩完点之后得到一个$n$个点的DAG，那么在渐进意义下，去掉等号时间复杂度不变，总复杂度为$n!$，而实际复杂度为拓扑序的个数，状压DP即可。

时间复杂度$O(n2^n)$。 

#include<cstdio>

typedef long long ll;

const int N=50;

int n,m,i,j,k;

int g[N][N],f[N],e[N];

char s[100];

int vis[500],mark[N];

ll dp[1<<20];

inline int id(char x){

	if(x=='1')return -1;

	if(x=='n')return -1;

	if(vis[x]==-1)vis[x]=m++;

	return vis[x];

}

inline void add(int x,int y){//x<=y

	if(x<0||y<0)return;

	g[x][y]=1;

}

int F(int x){return f[x]==x?x:f[x]=F(f[x]);}

inline void merge(int x,int y){

	if(F(x)!=F(y))f[f[x]]=f[y];

}

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int main(){

	freopen("fygon20.in", "r", stdin);

	freopen("fygon20.out", "w", stdout);

	scanf("%d",&n);

	n--;

	for(i=0;i<500;i++)vis[i]=-1;

	while(n--){

		scanf("%s",s);//for

		scanf("%s",s);

		int A=id(s[0]);

		scanf("%s",s);//in

		scanf("%s",s);

		int L=id(s[6]);

		scanf("%s",s);

		int R=id(s[0]);

		add(L,A);

		add(A,R);

	}

	for(k=0;k<m;k++)for(i=0;i<m;i++)for(j=0;j<m;j++)g[i][j]|=g[i][k]&&g[k][j];

	for(i=0;i<m;i++)f[i]=i;

	for(i=0;i<m;i++)for(j=0;j<m;j++)if(g[i][j]&&g[j][i])merge(i,j);

	for(i=0;i<m;i++)mark[i]=-1;

	n=0;

	for(i=0;i<m;i++)if(mark[F(i)]<0){

		mark[f[i]]=n++;

	}

	for(i=0;i<m;i++)for(j=0;j<m;j++)if(mark[f[i]]!=mark[f[j]]&&g[i][j])e[mark[f[i]]]|=1<<mark[f[j]];

	dp[0]=1;

	for(i=0;i<1<<n;i++)if(dp[i])for(j=0;j<n;j++)if(!(i>>j&1)&&!(e[j]&i))dp[i|(1<<j)]+=dp[i];

	ll U=dp[(1<<n)-1],D=1;

	for(i=2;i<=n;i++)D*=i;

	ll gc=gcd(U,D);

	U/=gc,D/=gc;

	printf("%d %lld/%lld",n,U,D);

}

/*

2

for i in range(1, n):

lag

4

for i in range(1, n):

for j in range(1, i):

for k in range(j, j):

lag

4

for i in range(1, n):

for j in range(1, i):

for k in range(i, j):

lag

*/

G. Grand Test

求出DFS树，对于一条非树边$(u,v)$，暴力将$u$到$v$路径上的树边染上这条非树边的颜色。

若一条树边被染了两次色，则说明对应的两个简单环有公共边。

仅保留两个简单环，任取两个度数至少为$3$的点作为起点和终点，然后爆搜出所有路径即可，一定恰好有$3$条简单路径。

时间复杂度$O(n+m)$。 

#include<cstdio>

#include<algorithm>

#include<set>

using namespace std;

typedef pair<int,int>P;

const int N=100010,M=200010;

int Case,n,m,i,x,y,g[N],v[M<<1],nxt[M<<1],ed;

int vis[N],dfn,flag,f[N],d[N];

P col[N],A,B;

int S,T,p[N];

set<P>e;

inline void add(int x,int y){

	d[x]++;

	v[++ed]=y;nxt[ed]=g[x];g[x]=ed;

}

void dfs(int x,int y){

	f[x]=y;

	vis[x]=++dfn;

	for(int i=g[x];i;i=nxt[i]){

		int u=v[i];

		if(u==y)continue;

		if(!vis[u]){

			dfs(u,x);

		}else if(vis[u]<vis[x]){

			int j=x;

			if(flag)continue;

			while(j!=u){

				if(col[j].first){

					flag=1;

					A=P(x,u);//down up

					B=col[j];

					break;

				}

				col[j]=P(x,u);

				j=f[j];

			}

		}

	}

}

inline void push(int x,int y){

	if(x>y)swap(x,y);

	e.insert(P(x,y));

}

inline void go(int x,int y){

	push(x,y);

	while(x!=y){

		push(x,f[x]);

		x=f[x];

	}

}

void dfs2(int x,int y,int z){

	p[z]=x;

	if(x==T){

		printf("%d",z);

		for(int i=1;i<=z;i++)printf(" %d",p[i]);

		puts("");

		return;

	}

	for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs2(v[i],x,z+1);

}

void solve(){

	scanf("%d%d",&n,&m);

	for(i=1;i<=n;i++)g[i]=vis[i]=f[i]=0;

	ed=dfn=flag=0;

	for(i=1;i<=n;i++)col[i]=P(0,0);

	while(m--){

		scanf("%d%d",&x,&y);

		add(x,y);

		add(y,x);

	}

	for(i=1;i<=n;i++)if(!vis[i]){

		dfs(i,0);

	}

	if(!flag){

		puts("-1");

		return;

	}

	e.clear();

	go(A.first,A.second);

	go(B.first,B.second);

	for(i=1;i<=n;i++)g[i]=d[i]=0;

	ed=0;

	for(set<P>::iterator it=e.begin();it!=e.end();it++){

		x=it->first;

		y=it->second;

		add(x,y);

		add(y,x);

	}

	S=T=0;

	for(i=1;i<=n;i++)if(d[i]>2){

		if(!S)S=i;

		else T=i;

	}

	printf("%d %d\n",S,T);

	dfs2(S,0,1);

}

int main(){

	freopen("grand.in", "r", stdin);

	freopen("grand.out", "w", stdout);

	scanf("%d",&Case);

	while(Case--)solve();

}

/*

6 6

3 6

3 4

1 4

1 2

1 3

2 3

*/

H. Hidden Supervisors

贪心求出每个连通块的最大匹配、根的匹配情况以及内部还未匹配的点数。

对于所有根已经匹配的连通块，将其直接连到$1$上最优。

对于剩下的连通块，按内部未匹配点数从大到小依次贪心连边即可。

时间复杂度$O(n\log n)$。 

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<string>

#include<ctype.h>

#include<math.h>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<bitset>

#include<algorithm>

#include<time.h>

using namespace std;

void fre() {  }

#define MS(x, y) memset(x, y, sizeof(x))

#define ls o<<1

#define rs o<<1|1

typedef long long LL;

typedef unsigned long long UL;

typedef unsigned int UI;

template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }

template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }

const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;

template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }

int casenum, casei;

int n;

int fa[N];

int match[N];

vector<int>son[N];

vector<int>nomatch;

int ANS;

void dfs(int x)

{

	match[x] = 0;

	for(auto y : son[x])

	{

		dfs(y);

		if(!match[y] && !match[x])

		{

			match[y] = x;

			match[x] = y;

			++ANS;

		}

		if(!match[y])nomatch.push_back(y);

	}

}

struct A

{

	int sz;

	int rt;

	vector<int>vt;

	bool operator < (const A & b)const

	{

		return sz > b.sz;

	}

}a[N];

int main()

{

	freopen("hidden.in", "r", stdin);

	freopen("hidden.out", "w", stdout);

	while(~scanf("%d",&n))

	{

		vector<int>rt;

		rt.push_back(1);

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

		{

			son[i].clear();

		}

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

		{

			scanf("%d", &fa[i]);

			if(fa[i] == 0)

			{

				rt.push_back(i);

			}

			else

			{

				son[fa[i]].push_back(i);

			}

		}

		ANS = 0;

		int rtsz = rt.size();

		int g = 0;

		vector<int>one;

		for(int i = 0; i < rtsz; ++i)

		{

			nomatch.clear();

			int x = rt[i];

			dfs(x);

			if(x == 1 || match[x])

			{

				fa[x] = 1;

				for(auto y : nomatch)

				{

					one.push_back(y);

				}

				if(x == 1 && !match[1])

				{

					one.push_back(1);

				}

			}

			else

			{

				++g;

				a[g].sz = nomatch.size();

				a[g].rt = x;

				a[g].vt = nomatch;

			}

		}

		sort(a + 1, a + g + 1);

		//

		//printf("treenum = %d\n", g);

		//

		for(int i = 1; i <= g; ++i)

		{

			int x = a[i].rt;

			if(one.size())

			{

				int ff = one.back();

				fa[x] = ff;

				one.pop_back();

				++ANS;

			}

			else

			{

				fa[x] = 1;

				one.push_back(x);

			}

			for(auto y : a[i].vt)

			{

				one.push_back(y);

			}

		}

		printf("%d\n", ANS);

		for(int i = 2; i <= n; ++i)printf("%d ", fa[i]);

		puts("");

	}

	return 0;

}

/*

【trick&&吐槽】

【题意】

【分析】

【时间复杂度&&优化】

*/

I. Intelligence in Perpendicularia

答案$=$包围盒周长$-$图形周长。 

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<string>

#include<ctype.h>

#include<math.h>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<bitset>

#include<algorithm>

#include<time.h>

using namespace std;

void fre() {  }

#define MS(x, y) memset(x, y, sizeof(x))

#define ls o<<1

#define rs o<<1|1

typedef long long LL;

typedef unsigned long long UL;

typedef unsigned int UI;

template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }

template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }

const int N = 1e3 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;

template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }

int casenum, casei;

int n;

const LL INF = 1e9;

LL maxx, minx, maxy, miny;

struct A

{

	LL x, y;

}a[N];

int main()

{

	freopen("intel.in", "r", stdin);

	freopen("intel.out", "w", stdout);

	scanf("%d", &n);

	maxx = -INF, maxy = -INF, minx = INF, miny = INF;

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

		scanf("%lld%lld", &a[i].x, &a[i].y);

		gmax(maxx, a[i].x);

		gmax(maxy, a[i].y);

		gmin(minx, a[i].x);

		gmin(miny, a[i].y);

	}a[n] = a[0];

	LL ans = 0;

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

		ans += abs(a[i].x - a[i + 1].x) + abs(a[i].y - a[i + 1].y);

	}

	ans -= (maxx - minx) * 2 + (maxy - miny) * 2;

	printf("%lld\n", ans);

	return 0;

}

/*

【trick&&吐槽】

【题意】

【分析】

【时间复杂度&&优化】

*/

J. Joker

分块维护凸壳。

K. Kotlin Island

枚举行列分别切了几刀即可。 

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<string>

#include<ctype.h>

#include<math.h>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<bitset>

#include<algorithm>

#include<time.h>

using namespace std;

void fre() {  }

#define MS(x, y) memset(x, y, sizeof(x))

#define ls o<<1

#define rs o<<1|1

typedef long long LL;

typedef unsigned long long UL;

typedef unsigned int UI;

template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }

template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }

const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;

template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }

int casenum, casei;

int n, m, g;

char s[105][105];

bool solve()

{

	MS(s, 0);

	int y = (n - 1) / 2;

	int x = (m - 1) / 2;

	for(int i = 0; i <= y; ++i)

	{

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

		{

			if( (i + 1) * (j + 1) == g)

			{

				for(int ii = 1; ii <= n; ++ii)

				{

					for(int jj = 1; jj <= m; ++jj)

					{

						if(ii % 2 == 0 && ii <= i * 2 || jj % 2 == 0 && jj <= j * 2)

						{

							s[ii][jj] = '#';

						}

						else

						{

							s[ii][jj] = '.';

						}

					}

				}

				return 1;

			}

		}

	}

	return 0;

}

int main()

{

	freopen("kotlin.in", "r", stdin);

	freopen("kotlin.out", "w", stdout);

	while(~scanf("%d%d%d",&n, &m, &g))

	{

		if(!solve())puts("Impossible");

		else

		{

			for(int i = 1; i <= n; ++i)puts(s[i] + 1);

		}

	}

	return 0;

}

/*

【trick&&吐槽】

【题意】

【分析】

【时间复杂度&&优化】

*/

L. Little Difference

若$n=2^k$形式则有无穷多个解，否则只能是$n=a^k$或$n=a^x(a+1)^y$的形式。

枚举$x,y$后二分$a$即可。 

#include<cstdio>

typedef long long ll;

const ll lim=1000000000000000010LL;

ll n;

int ans;

inline ll mul(ll a,ll b){

	if(a>lim/b)return lim;

	a*=b;

	if(a>lim)a=lim;

	return a;

}

inline ll po(ll a,int b){

	ll t=1;

	while(b--){

		t=mul(t,a);

		if(t>=lim)return lim;

	}

	return t;

}

inline ll get1(int k){

	ll l=2,r=n,mid;

	while(l<=r){

		mid=(l+r)>>1;

		ll t=po(mid,k);

		if(t==n)return mid;

		if(t<n)l=mid+1;else r=mid-1;

	}

	return 2;

}

inline ll get2(int i,int j){

	ll l=2,r=n,mid;

	while(l<=r){

		mid=(l+r)>>1;

		ll t=mul(po(mid,i),po(mid+1,j));

		if(t==n)return mid;

		if(t<n)l=mid+1;else r=mid-1;

	}

	return 2;

}

int main(){

	freopen("little.in", "r", stdin); freopen("little.out", "w", stdout);

	scanf("%lld",&n);

	if(n<=2)return puts("-1"),0;

	if(n==(n&-n))return puts("-1"),0;

	//a^k

	for(int _=0;_<2;_++){

		for(int k=1;k<=70;k++){

			ll t=get1(k);//t>=2

			if(po(t,k)==n){

				if(_==0)ans++;

				else{

					printf("%d",k);

					for(int o=1;o<=k;o++)printf(" %lld",t);

					puts("");

				}

			}

		}

		for(int i=1;i<=70;i++)for(int j=1;j<=70;j++){

			ll t=get2(i,j);//t>=2

			if(mul(po(t,i),po(t+1,j))==n){

				if(_==0)ans++;

				else{

					printf("%d",i+j);

					for(int o=1;o<=i;o++)printf(" %lld",t);

					for(int o=1;o<=j;o++)printf(" %lld",t+1);

					puts("");

				}

			}

		}

		if(_==0)printf("%d\n",ans);

	}

}

/*

8589934592

2176782336

1000000000000000000

*/

相关阅读

目录[+]