Noip2016 六校模拟 AHSDFZ Round 1
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
*/
评论 (0)
