Noip2016 十连测 填坑【Updating】

tonyfang posted @ 2016年10月29日 19:37 in 随笔 with tags c++ OI , 969 阅读

【Noip2016 十连测填坑专场】

蓝色Title表示还未填坑完成,红色Title表示完成

Round 1

A. String Master

给出两个长度为$n$的字串,求修改$k$次之后的最长公共子串最长是多少

$n, k \leq 300$

【题解】暴力模拟即可,复杂度$O(n^3)$。

# include <stdio.h>
# include <algorithm>
using namespace std;

const int M=310;
int n, k;
char s[M], t[M];
int ans = 0;
int main() {
	scanf("%d%d", &n, &k);
	scanf("%s%s", s+1, t+1);
	
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j) {
			int cnt = 0, len = 0;
			for (int i1=i, i2=j; i1<=n && i2<=n; ++i1, ++i2) {
				if(s[i1] != t[i2]) {
					if(cnt == k) break;
					++cnt;
				}
				++len;
			}
			if(len>ans) ans=len;
		}
	
	printf("%d\n", ans);
	return 0;
}

B. Tourist Attractions

找出$n$个点的图的四元环个数

$n \leq 1500$

【题解】

首先,四元环$a-b-c-d$中,$b-c$对答案的贡献为$(deg_b-1)(deg_c-1)-count(b,c)$,其中$count(b,c)$表示经过$b-c$的三元环个数。

三元环个数只要枚举另外一个顶点即可。所以复杂度是$O(n^3)$。

设$S_b$表示所有与$b$有关的边的集合,所以,三元环个数就是$card(S_b~and~S_c)$。所以我们二进制压位进行运算即可。压20位即可。时间复杂度$O(\frac{n^3}{20})$。

# include <stdio.h>
# include <string.h>
# include <algorithm>
# define COUNT __builtin_popcount
using namespace std;
const int M = 1510;
int n, du[M];
int a[M][M];
char A[M];
typedef long long ll;
typedef unsigned long long ull;
ll ans = 0;
bool vis[M];
int b[M][81], B[81];
int f[1<<20];
/*
inline void dfs(int x, int step) {
	if(step==3) {
		ans=ans+du[x];
		if(a[x][b[0]] == '1') --ans;
		if(a[x][b[1]] == '1') --ans;
		return ;
	}
	for (int i=1; i<=n; ++i) 
		if(!vis[i] && a[x][i]=='1') {
			b[step] = i;
			vis[i] = 1;
			dfs(i, step+1);
			vis[i] = 0;
		}
}
*/
int main() {
	//freopen("tour.in", "r", stdin);
	//freopen("tour.out", "w", stdout);
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) {
		scanf("%s", A+1);
		b[i][0]=0;
		for (int j=1; j<=n; ++j) {
			a[i][j] = A[j] - '0';
			if((j-1)%20==0) b[i][++b[i][0]]=a[i][j];
			else b[i][b[i][0]]=(b[i][b[i][0]]*2)+a[i][j];
			if(a[i][j]) du[i]++;
		}
	}
	for (int i=1; i<(1<<20); ++i) f[i] = COUNT(i);
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j)
			if(a[i][j] == 1) {
				ll t=0;
				int to=max(b[i][0], b[j][0]);
				for (int k=1; k<=to; ++k) B[k]=b[i][k]&b[j][k];
				for (int k=1; k<=to; ++k) t=t+f[B[k]];
				ans = ans + (ll)(du[i]-1)*(du[j]-1) - t;
			}
	/*
	for (int i=1; i<=n; ++i) {
		b[0]=i;
		vis[i] = 1;
		dfs(i, 1);
		vis[i] = 0;
	}
	*/
	printf("%lld\n", ans);
	return 0;
}

C. Walk

有$n$个点,$m$条边,点有点权,连单向边$(i,j)$当且仅当$v_i~and~v_j = v_j$,边权均为1,求从1号点到达其他点的最短路程。

$n \leq 200000, m \leq 300000, v_i \leq 2^{20}$

【题解】

新增$2^20$个点对应权值,每个点向对应的权值的点连边,以及连上$m$条边,其他边在spfa时暴力连上即可(不然会MLE),直接一遍spfa(bfs)。时间复杂度$O(20 \times 2^20 + n + m)$。

 

# include <stdio.h>
# include <vector>
# include <queue>
# define PB push_back
# define MP make_pair
# define pii pair<int,int>
# define to first
# define we second
// # include <bits/stdc++.h>
using namespace std;

const int N = 200010 + (1<<20) + 1;
vector< pii > G[N];
bool vis[N];
int d[N], val[N];
int n, m;
queue<int>Q;

inline void add(int u, int v, int l) {
//	printf("%d %d %d\n", u, v, l);
	G[u].PB(MP(v, l));
}

int main() {
	int Mx=0;
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; ++i) {
		scanf("%d", &val[i]); Mx=max(Mx, val[i]);
		add(i, val[i]+n+1, 1);
		add(val[i]+n+1, i, 0);
		d[i] = 1000000001;
	}
	for (int i=1, u, v; i<=m; ++i) {
		scanf("%d%d", &u, &v);
		add(u, v, 1);
	}
	int tsz=1;
	while(tsz<Mx) tsz<<=1;
	for (int i=n+1; i<=tsz+n; ++i) d[i]=1000000001;
	while(!Q.empty()) Q.pop();
	Q.push(1);vis[1]=1;d[1]=0;
	while(!Q.empty()) {
		int top=Q.front();Q.pop();vis[top]=0;
//		top>n ? printf("num %d\n", top-n-1) : printf("point %d\n", top);
		for (int i=0; i<G[top].size(); i++) {
			if(d[top]+G[top][i].we<d[G[top][i].to]) {
				d[G[top][i].to]=d[top]+G[top][i].we;
				if(!vis[G[top][i].to]) {
					vis[G[top][i].to]=1;
					Q.push(G[top][i].to);
				}
			}
		}
		if(top>n) {
			for (int i=0; i<=19; ++i)
				if((top-n-1)&(1<<i)) {
					int so=(top-n-1)-(1<<i)+n+1;
					if(d[top]<d[so]) {
						d[so]=d[top];
						if(!vis[so]) {
							vis[so]=1;
							Q.push(so);
						}
					}
				}
		}
	}
	for (int i=1; i<=n; ++i) printf("%d\n", d[i] == 1000000001 ? -1 : d[i]);
	return 0;
}

Round 2

Round 3

A. 平均数

一个长度为$n$的数列,询问所有连续子序列中的平均数中,第k小的值。

$n \leq 100000$。

【题解】二分答案$x$,则将所有$a_i$减去$x$,要寻找的就是区间值<0的有多少段,加上前缀和之后用归并排序解决(逆序对)

 

# include <stdio.h>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int n;
int a[100010];
double ta[100010];
double tmp[100010];
ll ret = 0, k;

inline void merges(int l, int mid, int r) {
	int i=l, j=mid+1, k=l;
	while(i<=mid && j<=r) {
		if(ta[i] > ta[j]) {
			tmp[k++] = ta[j++];
			ret += mid-i+1;
		} else tmp[k++] = ta[i++];
	}
	while(i<=mid) tmp[k++] = ta[i++];
	while(j<=r) tmp[k++] = ta[j++];
	for (int i=l; i<=r; ++i) ta[i] = tmp[i];
}

inline void merge(int l, int r) {
	if(l<r) {
		int mid = l+r>>1;
		merge(l, mid);
		merge(mid+1, r);
		merges(l, mid, r);
	}
}

inline bool check(double x) {
	ret = 0;
	ta[0] = 0.0;
	for (int i=1; i<=n; ++i) ta[i] = ta[i-1] + a[i] - x;
	merge(0, n);
	return ret >= k;
}

int main() {
	freopen("ave.in", "r", stdin);
	freopen("ave.out", "w", stdout);
	scanf("%d%lld", &n, &k);
	for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
	double mid, l = 0.0, r = 1000000000.0, ans = 0.0;
	while(r-l > 1e-6) {
		mid = (l+r) / 2.0;
		if(check(mid)) r = mid, ans = mid;
		else l = mid;
	}
	printf("%.4lf\n", ans);
	return 0;
}

Round 4

Round 5

Round 6

Round 7

Round 8

Round 9

A. 小P的2048

给出一个2048游戏($n \times n$),要你模拟$m$次操作,到无效操作后停止,问你一共得分。

$1 \leq m \leq 10^6, 2 \leq n \leq 8$

【题解】模拟即可,复杂度$O(mn^2)$。

# include <stdio.h>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int n, m;
ll a[9][9], b[9];
int oktest = 0, space;
ll score = 0;

inline void out() {
	puts("=======================");
	for (int i=1; i<=n; ++i, puts(""))
		for (int j=1; j<=n; ++j) printf("%lld ", a[i][j]);
	printf("SPACE = %d\n", space);
	puts("=======================");
}

inline void cntspace() {
	space = 0;
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j) space += (a[i][j] == 0);
}

int main() {
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);
	int temx, temy, temz;
	scanf("%d%d", &n, &m);
	space = n*n-2;
	scanf("%d%d%d", &temx, &temy, &temz);
	a[temx][temy] = temz;
	scanf("%d%d%d", &temx, &temy, &temz);
	a[temx][temy] = temz;
	while(m--) {
//		out();
		scanf("%d%d%d", &temx, &temy, &temz);
		bool havechange = 0;
		if(temx == 3) {
			// right
			for (int i=1; i<=n; ++i) {
				int cur = n+1;
				for (int j=1; j<=n; ++j) b[j] = 0;
				for (int j=n; j>=1; --j) {
					if(a[i][j] == 0) continue;
					int last;
					for (last = j-1; last >= 1; --last)
						if(a[i][last] != 0) break;
					if(last == 0) {
						b[--cur] = a[i][j];
						break;
					}
					if(a[i][j] != a[i][last]) {
						b[--cur] = a[i][j];
						j=last;
					} else {
						b[--cur] = a[i][j] * 2ll;
						score += b[cur];
						j=last-1;
					}
					++j;
				}
				for (int j=1; j<=n; ++j) {
					if(b[j] != a[i][j]) 
						havechange = 1;
					a[i][j] = b[j];
				}
			}
			cntspace();
		} else if(temx == 2) {
			// left
			for (int i=1; i<=n; ++i) {
				int cur = 0;
				for (int j=1; j<=n; ++j) b[j] = 0;
				for (int j=1; j<=n; ++j) {
					if(a[i][j] == 0) continue;
					int last;
					for (last = j+1; last <= n; ++last)
						if(a[i][last] != 0) break;
					if(last == n+1) {
						b[++cur] = a[i][j];
						break;
					}
					if(a[i][j] != a[i][last]) {
						b[++cur] = a[i][j];
						j=last;
					} else {
						b[++cur] = a[i][j] * 2ll;
						score += b[cur];
						j=last+1;
					}
					--j;
				}
				for (int j=1; j<=n; ++j) {
					if(b[j] != a[i][j]) 
						havechange = 1;
					a[i][j] = b[j];
				}
			}
			cntspace();
//			puts("=asdfasdfasdfasdf");
//			out();
		} else if(temx == 1) {
			// down
			for (int i=1; i<=n; ++i) {
				int cur = n+1;
				for (int j=1; j<=n; ++j) b[j] = 0;
				for (int j=n; j>=1; --j) {
					if(a[j][i] == 0) continue;
					int last;
					for (last = j-1; last >= 1; --last)
						if(a[last][i] != 0) break;
					if(last == 0) {
						b[--cur] = a[j][i];
						break;
					}
					if(a[j][i] != a[last][i]) {
						b[--cur] = a[j][i];
						j = last;
					} else {
						b[--cur] = a[j][i] * 2ll;
						score += b[cur];
						j = last-1;
					}
					++j;
				}
				for (int j=1; j<=n; ++j) {
					if(b[j] != a[j][i]) 
						havechange = 1;
					a[j][i] = b[j];
				}
			}
			cntspace();
		} else {
			// up
			for (int i=1; i<=n; ++i) {
				int cur = 0;
				for (int j=1; j<=n; ++j) b[j] = 0;
				for (int j=1; j<=n; ++j) {
					if(a[j][i] == 0) continue;
					int last;
					for (last = j+1; last <= n; ++last)
						if(a[last][i] != 0) break;
					if(last == n+1) {
						b[++cur] = a[j][i];
						break;
					}
					if(a[j][i] != a[last][i]) {
						b[++cur] = a[j][i];
						j=last;
					} else {
						b[++cur] = a[j][i] * 2ll;
						score += b[cur];
						j=last+1;
					}
					--j;
				}
				for (int j=1; j<=n; ++j) {
					if(b[j] != a[j][i]) 
						havechange = 1;
					a[j][i] = b[j];
				}
			}
			cntspace();
		}
		if (! havechange) break;
		int pos = 1+temy%space, px, py;
		for (int i=1; i<=n; ++i)
			for (int j=1; j<=n; ++j) 
				if(a[i][j] == 0) {
					pos --;
					if(pos == 0) {
						px = i;
						py = j;
						i = n+1, j = n+1;
					}
				}
		a[px][py] = temz;
		++ oktest;
	}
	printf("%d\n%lld\n", oktest, score);
	return 0;
}

B. 小P的序列

给出一个序列,问其的子序列中,美丽值最大的子序列的美丽值是多少。

美丽值的定义为,将序列划分为最少的单调上升/下降连续序列,且第一个连续序列不能是上升的,设这样划分完的最小个数为$x$,那么美丽值计算公式为$\frac{\sum a_i}{x}$。

$n \leq 10^5, a_i \leq 10^9$

【题解】猜想最优的$x$不多于2,那么头尾dp几遍就行了。复杂度$O(nlogn)$。其中dp用线段树维护。

# include <stdio.h>
# include <algorithm>
# include <vector>
using namespace std;

# define rank rnk
int n, a[100010];
vector<int> vec;
int rank[100010], N;

typedef long long ll;
typedef long double ld;

ld ans;
ll f[100010], g[100010], uf[100010], ug[100010]; 
ll w[1000010]; 

inline void change(int x, int L, int R, int pos, ll del) {
	if(L == R) {
		w[x] = max(w[x], del);
		return ;
	}
	int mid = L+R>>1;
	if(pos <= mid)
		change(x<<1, L, mid, pos, del);
	else change(x<<1|1, mid+1, R, pos, del);
	w[x] = max(w[x<<1], w[x<<1|1]);
}

inline ll ask(int x, int L, int R, int askl, int askr) {
	if(askl <= L && R <= askr) return w[x];
	int mid = L+R>>1;
	if(askr <= mid) return ask(x<<1, L, mid, askl, askr);
	else if(askl > mid) return ask(x<<1|1, mid+1, R, askl, askr);
	else {
		ll t1 = ask(x<<1, L, mid, askl, mid), t2 = ask(x<<1|1, mid+1, R, mid+1, askr);
		return max(t1, t2);
	}
}

inline void cmax(ll x, int t) {
	ld tx = (ld)x/t;
	if(tx > ans) ans = tx;
}


int main() {
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) {
		scanf("%d", &a[i]);
		vec.push_back(a[i]);
	}	
	sort(vec.begin(), vec.end());
	vector<int>::iterator it = unique(vec.begin(), vec.end());
	vec.erase(it, vec.end());
	for (int i=1; i<=n; ++i) { 
		rank[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
		N = max(N, rank[i]);
	}
	
	// f 从头,单调上升 
	for (int i=1; i<=1000000; ++i) w[i] = -1e17; 
	f[1] = a[1];
	change(1, 1, n, rank[1], f[1]); 
	for (int i=2; i<=n; ++i) { 
		if(rank[i] > 1) f[i] = ask(1, 1, n, 1, rank[i]-1);
		if (f[i] == -1e17) f[i] = 0; 
		f[i] = f[i] + a[i];
		change(1, 1, n, rank[i], f[i]);
	}
	//for (int i=1; i<=n; ++i) printf("%d ", f[i]);
	//puts("");
	// g 从头,单调下降 
	for (int i=1; i<=1000000; ++i) w[i] = -1e17; 
	g[1] = a[1];
	change(1, 1, n, rank[1], g[1]); 
	for (int i=2; i<=n; ++i) { 
		if(rank[i] < N) g[i] = ask(1, 1, n, rank[i]+1, N);
		if (g[i] == -1e17) g[i] = 0; 
		g[i] = g[i] + a[i];
		change(1, 1, n, rank[i], g[i]);
	}
	//for (int i=1; i<=n; ++i) printf("%d ", g[i]);
	//puts("");
	// uf 从尾,单调上升(也就是从头看单调下降)
	for (int i=1; i<=1000000; ++i) w[i] = -1e17;
	uf[n] = a[n];
	change(1, 1, n, rank[n], uf[n]);
	for (int i=n-1; i>=1; --i) {
		if (rank[i] < N) uf[i] = ask(1, 1, n, rank[i]+1, N);
		if (uf[i] == -1e17) uf[i] = 0; 
		uf[i] = uf[i] + a[i];
		change(1, 1, n, rank[i], uf[i]);
	}
	//for (int i=1; i<=n; ++i) printf("%d ", uf[i]);
	//puts("");
	// ug 从尾,单调下降(也就是从头看单调上升)
	for (int i=1; i<=1000000; ++i) w[i] = -1e17;
	ug[n] = a[n];
	change(1, 1, n, rank[n], ug[n]);
	for (int i=n-1; i>=1; --i) {
		if (rank[i] > 1) ug[i] = ask(1, 1, n, 1, rank[i]-1);
		if (ug[i] == -1e17) ug[i] = 0; 
		ug[i] = ug[i] + a[i];
		change(1, 1, n, rank[i], ug[i]);
	}
	//for (int i=1; i<=n; ++i) printf("%d ", ug[i]);
	//puts("");
	// 前传
	for (int i=2; i<=n; ++i)
		f[i] = max(f[i], f[i-1]),
		g[i] = max(g[i], g[i-1]);
	
	for (int i=n-1; i>=1; --i)
	    uf[i] = max(uf[i], uf[i+1]),
		ug[i] = max(ug[i], ug[i+1]); 
		
	// 只有一段的情况 
	bool only = 0;
	for (int i=1; i<=n; ++i)
		if(g[n] == a[i]) {
			only = 1;
			break;
		}
	
	if(only) ans = g[n];
	else ans = (ld)g[n]/2.0; 
	
	cmax(f[n], 1); 
	
	// 有中间点 
	for (int i=1; i<n; ++i) {
		cmax(f[i] + uf[i+1], 2);
		cmax(f[i] + ug[i+1], 2);
	}
	
	printf("%.3lf\n", (double)ans); 
}

Round 10

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter