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 */