Noip2016 六校模拟 AHSDFZ Round 1

tonyfang posted @ 2016年11月04日 22:25 in 随笔 with tags c++ OI , 676 阅读

A. gou

苟先生有一个长度为$n$字符串,不过他的朋友富先生对他的字符串做了一些小手脚,不仅打乱了顺序而且还把一些字符变成了*,而且这个字符串混进了$m$个字符串中,苟先生想知道哪些可能是他的字符串。

$1 \leq n, m \leq 100$

【题解】每个字母都不能多于标准串的就是可能的串

 

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

using namespace std;

int n, m;
char opt[100010];
int a[27], b[27];

int main() {
	freopen("gou.in", "r", stdin);
	freopen("gou.out", "w", stdout);
	scanf("%d", &n);
	scanf("%s", opt+1);
	for (int i=1; i<=n; ++i)
		a[opt[i]-'a']++;
	scanf("%d", &m);
	while(m--) {
		scanf("%s", opt+1);
		memset(b, 0, sizeof(b));
		for (int i=1; i<=n; ++i) {
			if(opt[i] != '*')
				b[opt[i] - 'a']++;
		}
		bool flag = 0;
		for (int i=0; i<26; ++i)
			if(b[i] > a[i]) {
				flag = 1;
				break;
			}
		if(flag) printf("0");
		else printf("1");
	}
	return 0;
}

B. fu

出于某些原因,苟先生在追杀富先生。富先生所在的地方是一个$n \times m$的网格,苟先生排出了他的狼狗大军,共有$k$条狗,第$i$条狗所在的位置为$(x_i,y_i)$。每条狗每个时刻都可以向8个方向前进一步。如果一个格子最快的一条狗需要$t$时刻才能到,那么这个格子就是$t-$危险的,现在给你$t$,询问有多少个$t-$危险的格子。

$n, m \leq 10^9, t \leq n+m, k \leq 2000$。

【题解】

转化成正方形面积并相减即可。时间复杂度$O(klogk)$

正方形面积并用扫描线+线段树解决。

 

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

using namespace std;

typedef long long ll;
ll n, m, t;
int k;
struct point {
	ll x, y;
}g[2010];

struct option {
	int time, x, y, opt;
}op[4010]; int opn = 0;

inline bool cmp(option a, option b) { return a.time < b.time; }

const int SZ = 2000010;
int len[SZ], ch[SZ][2], flag[SZ], tcnt = 0, root = 0;

inline void newnode(int &x) {
	x = ++tcnt;
	len[x] = ch[x][0] = ch[x][1] = flag[x] = 0;
}

inline void add(int &x, int l, int r, int L, int R, int del) {
	if(!x) newnode(x);
	if(L <= l && r <= R) {
		flag[x] += del;
		if(flag[x]) len[x] = r-l+1;
		else len[x] = len[ch[x][0]] + len[ch[x][1]];
		return ;
	}
	int mid = (l+r) >> 1;
	if(R <= mid) add(ch[x][0], l, mid, L, R, del);
	else if(L > mid) add(ch[x][1], mid+1, r, L, R, del);
	else {
		add(ch[x][0], l, mid, L, R, del);
		add(ch[x][1], mid+1, r, L, R, del);
	}
	if(flag[x]) len[x] = r-l+1;
	else len[x] = len[ch[x][0]] + len[ch[x][1]];
}

inline void outtree(int x, int l, int r) {
	printf("%d %d %d\n", x, l, r);
	if(ch[x][0]) outtree(ch[x][0], l, (l+r)>>1);
	if(ch[x][1]) outtree(ch[x][1], ((l+r)>>1)+1, r);
}

inline ll calc(int x) {
	ll res = 0; root = 0;
	opn = 0; tcnt = 0;
	for (int i=1; i<=k; ++i) {
		op[++opn] = (option) {max(1ll, g[i].y-x), max(1ll, g[i].x-x), min(g[i].x+x, n), 1};
		op[++opn] = (option) {min(m, g[i].y+x)+1, max(1ll, g[i].x-x), min(g[i].x+x, n), -1};
	}
	sort(op+1, op+opn+1, cmp);
	
//	printf("opn = %d\n", opn);
//	for (int i=1; i<=opn; ++i) {
//		printf("%d %d %d %d\n", op[i].time, op[i].x, op[i].y, op[i].opt);
//	}
	
	memset(ch, 0, sizeof(ch));
	memset(len, 0, sizeof(len));
	memset(flag, 0, sizeof(flag));
	
	for (int i=1, j; i<=opn; i=j) {
		res += (ll) len[root] * (op[i].time - op[i-1].time);
		for (j=i; op[j].time == op[i].time; ++j) 
			add(root, 1, n, op[j].x, op[j].y, op[j].opt);
//		outtree(root, 1, n);
	}
	return res;
}

int main() {
	freopen("fu.in", "r", stdin);
	freopen("fu.out", "w", stdout);
	scanf("%lld%lld%d%lld", &n, &m, &k, &t);
	for (int i=1; i<=k; ++i)
		scanf("%lld%lld", &g[i].x, &g[i].y);
	printf("%lld\n", calc(t) - calc(t-1));
	return 0;
}

C. gui

苟先生的狼狗大军没有追上富先生,所以他把它们都解雇了,决定去雇佣一些更好的狗,不过狗可是很贵的。苟先生有$w$元钱,有$n$条狗可以雇佣,第i条狗有一个能力值$q_i$和一个需求$s_i$,也就是说给它的钱不能少于$s_i$。对于两条狗$i$和$j$,给它们的钱的比值必须等于$\frac{q_i}{q_j}$(当然钱可以不为整数)。苟先生希望雇佣到尽量多的狗,并花尽量少的钱。

$ n \leq 10^6$

【题解】

首先可以证明,$\sum k \times q_i$的系数$k$一定是某一个狗的$\frac{s_i}{q_i}$。

然后按照这个排序,按照$q_i$排序来获得“坑”的顺序。

接着就是一个个往里面填坑。显然满足二分性质,二分即可。复杂度$O(nlog^2n)$。

也可以直接用线段树在$O(nlogn)$时间内维护,待填坑。

 

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

using namespace std;

const int M = 1000010;
typedef long long ll;
int n;
long double ansm = 0;
struct dog {
	int s, p, id, iid;
}d[M];
ll money = 0;

inline bool cmp1(dog a, dog b) {
	return (ll)a.s*b.p < (ll)b.s*a.p;
}

inline bool cmp2(dog a, dog b) {
	return a.p < b.p;
}

ll c[4*M];
int b[4*M], cs[M];
int is[M];

inline int lowbit(int x) {return x&(-x);}

inline void add(int pos, int del) {
	for (int i=pos; i<=n; i+=lowbit(i))
		c[i] += del;
}

inline ll sum(int pos) {
	ll ret=0;
	while(pos>0) {
		ret += c[pos];
		pos -= lowbit(pos);
	}
	return ret;
}

inline void addb(int pos, int del) {
	for (int i=pos; i<=n; i+=lowbit(i))
		b[i] += del;
}

inline int sumb(int pos) {
	int ret=0;
	while(pos>0) {
		ret += b[pos];
		pos -= lowbit(pos);
	}
	return ret;
}

int main() {
	freopen("gui.in", "r", stdin);
	freopen("gui.out", "w", stdout);
	memset(c, 0, sizeof(c));
	memset(b, 0, sizeof(b));
	scanf("%d%lld", &n, &money);
	for (int i=1; i<=n; ++i) 
		scanf("%d%d", &d[i].s, &d[i].p), d[i].iid = i;
	sort(d+1, d+n+1, cmp2);
	for (int i=1; i<=n; ++i) d[i].id = i, is[d[i].id]=d[i].iid;
	sort(d+1, d+n+1, cmp1);
	
//	for (int i=1; i<=n; ++i) {
//		printf("%d %d %d %d\n", d[i].s, d[i].p, d[i].id, d[i].iid);
//	}

	ansm = (long double)money + 1;
	int ans=0, ansn;
	for (int i=1; i<=n; ++i) {
		long double k = (long double)d[i].s/d[i].p;
		add(d[i].id, d[i].p);
		addb(d[i].id, 1);
		int l=1, r=n, anss=0;
		while(1) {
			if(r-l<=3) {
				for (int j=r; j>=l; --j)
					if(k*sum(j) <= (long double)money) {
						anss=j;
						break;
					}
				break;
			}
			int mid=l+r>>1;
			if(k*sum(mid) <= (long double)money) l=mid;
			else r=mid;
		}
		int bn = sumb(anss);
//		printf("bn = %d\n", bn);
		double curm = k*sum(anss);
		if(bn>ans) {
			ans=bn;
			ansn=i;
			ansm = curm;
		} else if(ans==bn && ansm>curm) {
			ans=bn;
			ansn=i;
			ansm=curm;
		}
	}
	
	memset(c, 0, sizeof(c));
	memset(b, 0, sizeof(b));
	for (int i=1; i<=ansn; ++i) {
		add(d[i].id, d[i].p);
		addb(d[i].id, 1);
	}
	
	long double k = (long double)d[ansn].s/d[ansn].p;
	int l=1, r=n, anss=0;
	while(1) {
		if(r-l<=3) {
			for (int j=r; j>=l; --j)
				if(k*sum(j) <= (long double)money) {
					anss=j;
					break;
				}
			break;
		}
		int mid=l+r>>1;
		if(k * sum(mid) <= (long double)money) l=mid;
		else r=mid;
	}
	
	for (int i=1; i<=n; ++i)
		cs[i] = sumb(i);
	printf("%d\n", ans);
	for (int i=1; i<=n; ++i) {
		if(cs[i]-cs[i-1] == 1) printf("%d\n", is[i]);
	}
	puts("");
	return 0;
}
/*
4 100
5 1000
10 100
8 10
20 1
*/

 


登录 *


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