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
*/
2023年4月19日 16:39
We are offering the PDF based on internet searches for outdated examination tests from previous years and those question banks or study materials that were downloaded and shared alone online.We are offering the pdf based on boardmodelpaper.com internet searches based on previous years' old examination tests and those question banks, and all users of BoardModelPapers may use those sample papers or Previous Paper Pdf of class-wise study material and blueprint for reference purposes only.