LOJ刷题记录：SHOI2016(2036-2041)

LOJ刷题记录：SHOI2016(2036-2041)

---

loj#2036. 「SHOI2015」自动刷题机

直接二分就好了。

#include 
using namespace std;const int MAXN = 200005;int x[MAXN];
int n, k;int calc(long long N)
{long long ans = 0;int cnt = 0;for (int i = 1; i <= n; i++) {// cerr << x[i] << " ";ans += x[i];if (ans < 0) ans = 0;if (ans >= N) cnt++, ans = 0;}// cerr << endl;return cnt;
}int main()
{scanf("%d%d", &n, &k);for (int i = 1; i <= n; i++) scanf("%d", &x[i]);long long L = 1, R = 1e18, mid;while (L <= R) {mid = L+((R-L)>>1);if (calc(mid) <= k) R = mid-1;else L = mid+1;}long long Low = R+1;L = 1, R = 1e18;while (L <= R) {mid = L+((R-L)>>1);if (calc(mid) >= k) L = mid+1;else R = mid-1;}long long Up = L-1;// cerr << calc(Up) << endl;if (calc(Up) != k || calc(Low) != k || Low > Up) puts("-1");else cout << Low << " " << Up << endl;return 0;
}

loj#2037. 「SHOI2015」脑洞治疗仪

以前做过…

#include 
using namespace std;const int MAXN = 200005;int dat[MAXN*4], lc[MAXN*4], rc[MAXN*4], l[MAXN*4], r[MAXN*4];
int change[MAXN*4], llen[MAXN*4], rlen[MAXN*4], len[MAXN*4], top = 0, root = 0;inline int new_node(int opl, int opr)
{ return ++top, l[top] = opl, r[top] = opr, top; }inline void pdw(int nd) // 1 nh / -1 hole
{if (!change[nd]) return;change[lc[nd]] = change[rc[nd]] = change[nd]*(lc[nd]!=0);dat[nd] = (r[nd]-l[nd]+1)*(change[nd]==1);llen[nd] = rlen[nd] = len[nd] = (r[nd]-l[nd]+1)*(change[nd]==-1);change[nd] = 0;
}inline void update(int nd)
{pdw(nd), pdw(lc[nd]), pdw(rc[nd]);if (l[nd] == r[nd]) {llen[nd] = rlen[nd] = len[nd] = (dat[nd]==0);return;}llen[nd] = llen[lc[nd]]+(dat[lc[nd]] == 0)*llen[rc[nd]];rlen[nd] = rlen[rc[nd]]+(dat[rc[nd]] == 0)*rlen[lc[nd]];len[nd] = max(max(len[lc[nd]], len[rc[nd]]), rlen[lc[nd]]+llen[rc[nd]]);dat[nd] = dat[lc[nd]]+dat[rc[nd]];
}int pat[MAXN];void build(int &nd, int l, int r)
{nd = new_node(l, r);if (l == r) dat[nd] = pat[r];else build(lc[nd], l, (l+r)/2), build(rc[nd], (l+r)/2+1, r);update(nd);
}void modify(int nd, int opl, int opr, int alc)
{if (opl > opr) return;pdw(nd);if (opl == l[nd] && opr == r[nd]) change[nd] = alc, pdw(nd);else {int mid = (l[nd]+r[nd])/2;if (opr <= mid) modify(lc[nd], opl, opr, alc);else if (opl > mid) modify(rc[nd], opl, opr, alc);else modify(lc[nd], opl, mid, alc), modify(rc[nd], mid+1, opr, alc);pdw(lc[nd]), pdw(rc[nd]), update(nd);}
}int query(int nd, int opl, int opr)
{pdw(nd);if (opl == l[nd] && opr == r[nd]) return len[nd];else {int mid = (l[nd]+r[nd])/2;pdw(lc[nd]), pdw(rc[nd]);if (opr <= mid) return query(lc[nd], opl, opr);else if (opl > mid) return query(rc[nd], opl, opr);else return max(max(query(lc[nd], opl, mid), query(rc[nd], mid+1, opr)), min(rlen[lc[nd]], mid-opl+1)+min(llen[rc[nd]], opr-mid));}
}void dfs(int nd, int tab = 0)
{if (!nd) return;for (int i = 1; i <= tab; i++) putchar(' ');printf("[%d, %d], dat = %d, llen = %d, rlen = %d, len = %d, change = %d\n", l[nd], r[nd], dat[nd], llen[nd], rlen[nd], len[nd], change[nd]);dfs(lc[nd], tab+2), dfs(rc[nd], tab+2);
}int query_sum(int nd, int opl, int opr)
{if (opl > opr) return 0;pdw(nd);int mid = (l[nd]+r[nd])/2;if (opl == l[nd] && opr == r[nd]) return dat[nd];else return query_sum(lc[nd], opl, min(opr, mid))+query_sum(rc[nd], max(opl, mid+1), opr);
}int last_pos(int nd, int k) // in node nd, the first place to have k holes
{if (l[nd] == r[nd]) return l[nd];pdw(nd), pdw(lc[nd]), pdw(rc[nd]);int lp = r[lc[nd]]-l[lc[nd]]+1-dat[lc[nd]];// cerr << l[nd] << "," << r[nd] << " ; " << k << " ; " << lp << endl;if (lp >= k) return last_pos(lc[nd], k);else return last_pos(rc[nd], k-lp);
}void fix(int ll, int lr, int nl, int nr)
{int dt = query_sum(root, ll, lr);// cerr << "-->" << max(0, nl-1)-query_sum(root, 1, nl-1)+dt << "-" << k << endl;modify(root, ll, lr, -1);if (dt == 0) return;int k = last_pos(root, nl-1-query_sum(root, 1, nl-1)+dt);modify(root, nl, min(nr, k), 1);
}inline int read()
{int a = 0, c;do c = getchar(); while (!isdigit(c));while (isdigit(c))a = a*10+c-'0', c = getchar();return a;
}int n, m;int main()
{n = read(), m = read();for (int i = 1; i <= n; i++) pat[i] = 1;build(root, 1, n);for (int i = 1; i <= m; i++) {// dfs(root);int tp, l, r, u, v;tp = read();if (tp == 0) l = read(), r = read(), modify(root, l, r, -1);else if (tp == 1) l = read(), r = read(), u = read(), v = read(), fix(l, r, u, v);else l = read(), r = read(), printf("%d\n", query(root, l, r));// for (int j = 1; j <= n; j++) cerr<" ";// cerr << endl;// dfs(root);}return 0;
}

loj#2038. 「SHOI2015」超能粒子炮・改

$$S(n, k) = \sum_{0\le i\le k}{n\choose i}\ mod\ 2333\\ = \sum_{0\le i\le k}{n\mod 2333 \choose i \mod 2333}{n/2333\choose i/2333}$$

考虑$i\ mod\ 2333$必然成周期性，在每一个周期中$i/2333$又恰好都相等，考虑分块处理，第一部分是完整的块，也就是$mod\ 2333$为$0..2332$的部分，为：

$$P = \left\lfloor\frac{k+1}{2333}\right\rfloor, Q = (k+1)\ mod\ 2333\\\sum_{0\le i < P} S(n\ mod\ 2333, 2332){n/2333\choose i} \\= S(n\ mod\ 2333, 2332)\times S(n/2333, P-1)$$

第二部分为余下的部分，也就是：

$$\sum_{0\le i < Q}{n\mod 2333\choose i \mod 2333}{n/2333\choose k/2333} \\= S(n\ mod\ 2333, Q-1){n/2333\choose k/2333}$$

这样两部分加起来美滋滋，复杂度$O(\log_{2333}^2(n) )$

#include 
using namespace std;const int mod = 2333;int c[mod+20][mod+20], f[mod+20][mod+20];inline int lucas(long long i, long long j)
{if (i < mod && j < mod) return c[i][j];return c[i%mod][j%mod]*lucas(i/mod, j/mod)%mod;
}inline int fun(long long i, long long j)
{if (i < mod && j < mod) return f[i][j];return (f[i%mod][mod-1]*fun(i/mod, (j+1)/mod-1)+lucas(i/mod, j/mod)*f[i%mod][(j+1)%mod-1])%mod;
}int main()
{c[0][0] = 1;for (int i = 1; i < mod; i++)for (register int j = 0; j <= i; j++)c[i][j] = (c[i-1][j]+(j>=1)*c[i-1][j-1])%mod;for (int i = 0; i < mod; i++) {f[i][0] = 1;for (register int j = 1; j < mod; j++)f[i][j] = (f[i][j-1]+c[i][j])%mod;}// cerr << lucas(12132, 3211) << endl;int T; scanf("%d", &T);while (T--) {long long n, m;scanf("%lld%lld", &n, &m);printf("%d\n", fun(n, m));}return 0;
}

loj#2039. 「SHOI2015」激光发生器

写了一天的码农计算几何题…

这种题呀…大概是有毒

#include 
using namespace std;const int MAXN = 105;
const double eps = 1e-9;struct point {double x, y;friend point operator + (const  point &a, const point &b){ return (point){a.x+b.x, a.y+b.y}; }friend point operator - (const point &a, const point &b){ return (point){a.x-b.x, a.y-b.y}; }friend point operator * (double lambda, const point &a){ return (point){lambda*a.x, lambda*a.y}; }friend double operator * (const point &a, const point &b){ return a.x*b.y-a.y*b.x; }inline double len() const{ return sqrt(x*x+y*y); }inline double dot(const point &a){ return x*a.x+y*a.y; }double angel(const point &a){ return acos((x*a.x+y*a.y)/len()/a.len()); }point rot(double theta){ return (point){cos(theta)*x-sin(theta)*y, sin(theta)*x+cos(theta)*y}; }
};typedef point vec;struct line {point p;vec v;inline line normal_left(const point &a){ return (line){a, v.rot(M_PI/2)}; }inline line normal_right(const point &a){ return (line){a, v.rot(-M_PI/2)}; }inline bool on_left(const point &a){ return v*(a-p) > 0; }inline bool on_right(const point &a){ return !on_left(a); }friend point operator * (const line &a, const line &b){double lambda = b.v*(b.p-a.p)/(b.v*a.v);// cerr << " " << lambda << endl;return a.p+lambda*a.v;}bool along(const point &pt){return (pt-p).dot(v) > eps;}inline bool on_line(const point &a){return (a-p).dot(a-(p+v)) <= eps;}
} px;int n;
double lambda[MAXN];
line ln[MAXN];int main()
{double a, b, c, d, x, y;scanf("%lf%lf%lf%lf", &a, &b, &c, &d);px.p = (point){a, b}, px.v = (vec){c, d};scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%lf%lf%lf%lf%lf%lf", &a, &b, &c, &d, &x, &y);ln[i].p = (point){a, b}, ln[i].v = (point){c-a, d-b}, lambda[i] = x/y;}bool pp = 0;for (int i = 1; i <= 10; i++) {point fc;double len = 1e30;int id;for (int j = 1; j <= n; j++) {point pt = px*ln[j];if (ln[j].on_line(pt) && px.along(pt)) {if ((pt-px.p).len() < len)fc = pt, len = (pt-px.p).len(), id = j;}}if (len >= 1e30) break;line nor = ln[id].on_left(px.p)?ln[id].normal_left(fc):ln[id].normal_right(fc);double ang = (px.p-fc).angel(nor.v);if ((px.p-fc)*nor.v < 0) ang = -ang;ang = ang+ang*lambda[id];px = (line){fc, (px.p-fc).rot(ang)};pp = 1;// cerr << fc.x << " " << fc.y << "," << px.v.x << " " << px.v.y << endl;printf("%d ", id);}if (pp == 0) puts("NONE");else puts("");return 0;
}

loj#2040. 「SHOI2015」零件组装机

以前做过…如果有方案，方案唯一，直接找就好了…

#include 
using namespace std;const int MAXN = 100005;inline int gcd(int a, int b)
{ return b==0?a:gcd(b, a%b); }vector<int> vec[MAXN];
int n, T, m;bool solve(int L, int R)
{if (L == R) return 1;if (L > R || vec[L].empty()) return 0;// if (vec[L].size() == R-L) return solve(L+1, R);int d = vec[L][vec[L].size()-1]-L, plc = -1, cnt = 0;for (int i = vec[L].size()-1; i >= 0; i--) {int tar = vec[L][i]; cnt++;if (gcd(tar-L, d) == tar-L && (R-L)/(tar-L) == cnt && R-tar+1 >= tar-L) {plc = tar;break;}}if (plc == -1) return 0;// cerr << L << " " << R << " " << plc << endl;for (int i = L; i < plc; i++) {int N = (R-i)/(plc-L);while (N) {if (vec[i][vec[i].size()-1] != i+(plc-L)*N) return 0;N--, vec[i].pop_back();} }return solve(L, plc-1)&&solve(plc, R);
}unordered_set<int> st[MAXN];int main()
{scanf("%d", &T);while (T--) {scanf("%d%d", &n, &m);for (int i = 0; i < n; i++) vec[i].clear();int flag = 0;for (int i = 0; i < n; i++) st[i].clear();for (int i = 1; i <= m; i++) {int u, v;scanf("%d%d", &u, &v);if (u == v) { flag = 1;  }if (u > v) swap(u,v);if (!st[u].count(v)) {st[u].insert(v);vec[u].push_back(v);} else flag = 1;}if (flag) { puts("NO"); continue; }for (int i = 0; i < n; i++)sort(vec[i].begin(), vec[i].end());if (solve(0, n-1)) puts("YES");else puts("NO");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！