- solved:9/12
- A:solved
- B:/
- C:solved
- D:solved
- E:/
- F:solved
- G:solved
- H:solved
- I:/
- J:solved
- K:solved
- L:solved
A.
题解:
按高度从高到低, 每次将区间中最高点给选出来, 然后将左右能连边的区间看成虚点, 从最高点向虚点连边, 再从虚点向该区间中最高点连边;
这样就变成了一个分层的 DAG, 奇数层虚点(第 1 层为超级根), 偶数层实点;
这个玩意的结构很类似树, 所以我们可以用类似搞树的方法搞这个
然后直接统计每个点的深度和每个子 DAG 的最深深度
然后询问直接用深度搞就行, 特别地需要判一下是否属于同一棵子树
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn = 100005;
- int st[17][maxn], lo[maxn], a[maxn], n, m, base;
- vector<int> g[maxn];
- struct node
- {
- int val, dep, maxdep;
- }tr[maxn <<1];
- int find(int l, int r)
- {
- int t = lo[r - l + 1];
- return max(st[t][l], st[t][r - (1 << t) + 1]);
- }
- int makedag(int nd, int l, int r, int dep)
- {
- //printf("? %d %d %d\n", l, r, dep);
- tr[nd].dep = dep;
- int maxval = find(l, r);
- int lpos = lower_bound(g[maxval].begin(), g[maxval].end(), l) - g[maxval].begin();
- int rpos = upper_bound(g[maxval].begin(), g[maxval].end(), r) - g[maxval].begin() - 1;
- vector<int> tmp; tmp.clear(); tmp.push_back(l - 1);
- vector<pair<int, int>> inter; inter.clear();
- for(int i = lpos; i <= rpos; ++ i)
- {
- int p = g[maxval][i];
- tmp.push_back(p);
- tr[p].dep = dep + 1;
- //printf("! %d %d %d\n", dep, p, tr[p].dep);
- }
- tmp.push_back(r + 1);
- for(int i = 1; i <= rpos - lpos + 2; i ++)
- if(tmp[i] - 1> tmp[i - 1])
- {
- base ++; int t = base;
- int v = makedag(base, tmp[i - 1] + 1, tmp[i] - 1, dep + 2);
- inter.push_back(make_pair(t, v));
- }else inter.push_back(make_pair(0, 0));
- int ret = 0;
- for(int i = 1; i <= rpos - lpos + 1; i ++)
- {
- int p = tmp[i];
- tr[p].maxdep = max(inter[i - 1].second, inter[i].second);
- tr[p].maxdep = max(tr[p].maxdep, tr[p].dep);
- ret = max(ret, tr[p].maxdep);
- }
- return ret;
- }
- int abs(int x){return x <0 ? -x : x;}
- int lg[maxn], rg[maxn];
- stack<int> s;
- int main()
- {
- lo[1] = 0; for(int i = 2; i <= 100000; ++ i) lo[i] = lo[i>> 1] + 1;
- scanf("%d%d", &n, &m); a[0] = a[n + 1] = n + 100;
- for(int i = 1; i <= n; ++ i)
- {
- scanf("%d", &a[i]);
- g[a[i]].push_back(i);
- st[0][i] = a[i];
- }
- for(int i = 1; i <= n; ++ i) g[i].push_back(0), g[i].push_back(n + 1), sort(g[i].begin(), g[i].end());
- for(int k = 1; (1 <<k) <= n; ++ k)
- for(int i = 1; i + (1 << k) - 1 <= n; ++ i)
- st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
- base = n + 1; makedag(base, 1, n, 0);
- while(!s.empty()) s.pop(); s.push(0);
- for(int i = 1; i <= n; ++ i)
- {
- while(a[i]> a[s.top()]) s.pop();
- lg[i] = s.top() + 1;
- s.push(i);
- }
- while(!s.empty()) s.pop(); s.push(n + 1);
- for(int i = n; i>= 1; -- i)
- {
- while(a[i]> a[s.top()]) s.pop();
- rg[i] = s.top() - 1;
- s.push(i);
- }
- while(m --)
- {
- int x, y; scanf("%d%d", &x, &y);
- if(y == 0)printf("%d\n", (tr[x].maxdep - tr[x].dep)>> 1);
- else
- {
- if(a[x] <a[y]) swap(x, y);
- if(a[x] == a[y] || y < lg[x] || y> rg[x]) printf("0\n");
- else printf("%d\n", abs(tr[x].dep - tr[y].dep)>> 1);
- }
- }
- return 0;
- }
- View Code
B.
unsolved
C.
签到题
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn = 5005;
- pair<int, int> st[maxn];
- int n, m, a[maxn], ans[maxn];
- int main()
- {
- scanf("%d%d", &n, &m);
- for(int i = 1; i <= n; i ++)
- {
- scanf("%d", &a[i]);
- st[i] = make_pair(a[i], i);
- }
- sort(st + 1, st + n + 1);
- int ret = 0;
- for(int i = 1; i <= n; ++ i) ans[i] = 0;
- for(int i = 1; i <= n; ++ i)
- {
- int pos = st[i].second;
- int val = -1;
- for(int j = max(1, pos - m); j <= min(n, pos + m); ++ j)
- if(a[j] <a[pos]) val = max(val, ans[j]);
- ans[pos] = val + 1;
- ret = max(ret, ans[pos]);
- }
- printf("%d\n", ret);
- return 0;
- }
- View Code
D.
签到题
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn = 2000005;
- int T, n, a[maxn];
- int abs(int x){return x <0 ? -x : x;}
- int main()
- {
- scanf("%d", &T);
- while(T --)
- {
- scanf("%d", &n);
- for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
- sort(a + 1, a + n + 1);
- int cnt = 0, now = 0;
- for(int i = 1; i <= n; ++ i)
- {
- if(now == 0 || abs(now - a[i])> 10)
- {
- cnt ++;
- now = a[i] + 10;
- }
- }
- printf("%d\n", cnt);
- }
- return 0;
- }
- View Code
E.
unsolved
F.
题解:
同 UOJ275, 利用 Lucas 定理转化, 将 C(n,m)中的 n,m 写成 7 进制数, 存在某一位 n 的数位比 m 小
然后按数位计数就行了
- #include<cstdio>
- #define mo 1000000007
- using namespace std;
- int T;
- long long n;
- long long a[70],qr[70],g[70];
- int main()
- {
- scanf("%d",&T);
- for (int oo=1;oo<=T;++oo)
- {
- scanf("%lld",&n);
- a[0]=0;
- long long tmp=n;
- while (tmp)
- a[++a[0]]=tmp%7,
- tmp/=7;
- qr[0]=1;
- g[0]=1;
- for (int i=1;i<=a[0]+1;++i)
- qr[i]=qr[i-1]*7LL%mo,
- g[i]=1LL*g[i-1]*28%mo;
- long long ans=0,p=0,q=1;
- for (int i=a[0];i>=1;--i)
- {
- for (int j=0;j<=a[i]-1;++j)
- ans=(ans+1LL*((p*7LL+j)%mo*qr[i-1])%mo*qr[i-1]%mo+(qr[i-1]+1LL)*qr[i-1]%mo*((mo+1)/2)%mo-1LL*q*(j+1)%mo*g[i-1]%mo)%mo;
- p=(p*7LL+a[i])%mo;
- q=q*(a[i]+1LL)%mo;
- }
- long long cnt=1;
- for (int i=1;i<=a[0];++i) cnt=cnt*(a[i]+1LL)%mo;
- printf("Case %d: %lld\n",oo,((ans+n+1-cnt)%mo+mo)%mo);
- }
- }
- View Code
G.
题解:
SCC 模板题
- #include<bits/stdc++.h>
- #define maxn 205
- using namespace std;
- int T,n,m;
- vector<int> g[maxn],scc[maxn];
- stack<int> s;
- int pre[maxn],low[maxn],belong[maxn];
- int t,cnt;
- void dfs(int u)
- {
- pre[u]=low[u]=++t;
- s.push(u);
- for(int i=0;i<g[u].size();++i)
- {
- int v=g[u][i];
- if(!pre[v])dfs(v),low[u]=min(low[u],low[v]);
- else if(!belong[v])low[u]=min(low[u],pre[v]);
- }
- if(low[u]==pre[u])
- {
- ++cnt;
- while(1)
- {
- int x=s.top();s.pop();
- belong[x]=cnt;
- scc[cnt].push_back(x);
- if(x==u)break;
- }
- }
- }
- int main()
- {
- scanf("%d",&T);
- while(T--)
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;++i)g[i].clear(),scc[i].clear(),pre[i]=low[i]=belong[i]=0;
- t=cnt=0;
- while(!s.empty())s.pop();
- for(int u,v,i=1;i<=m;++i)
- {
- scanf("%d%d",&u,&v);
- u++;v++;
- g[u].push_back(v);
- }
- for(int i=1;i<=n;++i)if(!pre[i])dfs(i);
- printf("%d\n",cnt);
- }
- }
- View Code
H.
题解:
观察 (榜) 发现可能有一些奥妙重重的性质
可以直接枚举 0~2^21 check
- #include<bits/stdc++.h>
- #define ll long long
- using namespace std;
- int T;
- ll A,B,C,NA,NB,NC;
- int main()
- {
- scanf("%d",&T);
- while(T--)
- {
- cin>>NA>>NB>>NC>>A>>B>>C;
- for(int i=0;i<(1<<21);++i)
- {
- ll t=1ll*i*i*i;
- if(t%NA==A&&t%NB==B&&t%NC==C)
- {
- cout<<i<<endl;
- break;
- }
- }
- }
- }
- View Code
I.
unsolved
J.
题解:
考虑利用三次方差因式分解提出一个 1e-15, 然后单独统计前面的部分
这样会被卡常
忽略高阶的 1e-15 就能过了
- #include<bits/stdc++.h>
- using namespace std;
- const double eps = 1e-15;
- const double mi = 1.0 / 3.0;
- double sum = 0;
- int x, y;
- void pri(int p)
- {
- char s[10];
- int cc = 0;
- s[3] = s[2] = s[1] = 48;
- while(p> 0)
- {
- s[++ cc] = 48 + (p % 10);
- p /= 10;
- }
- for(int i = 3; i>= 1; i --) putchar(s[i]);
- puts("");
- }
- int main()
- {
- while(scanf("%d%d", &x, &y) == 2 && 1ll * x + 1ll * y> 0)
- {
- sum = 0;
- for(int i = x; i <= y; ++ i)
- {
- double p1 = (double)i + eps;
- double p2 = (double)i;
- double tmp = 3.0 * pow(p1 * p2, mi);
- //printf("%d %.5Lf\n", i, (double)1.0 / tmp);
- sum += (double)1.0 / tmp;
- }
- int cnt = 15;
- while(sum + eps <1) {cnt ++; sum *= 10.0;}
- while(sum>= 10 + eps) {cnt --; sum /= 10.0;}
- printf("%.5lfE-", sum); pri(cnt);
- }
- return 0;
- }
- View Code
K.
题解:
动态维护第 k 小, 线段树上二分
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn = 100005;
- const int maxm = 1000005;
- struct FastIO
- {
- static const int S=5<<20;
- int wpos;char wbuf[S];
- FastIO():wpos(0){}
- inline int xchar()
- {
- static char buf[S];
- static int len=0,pos=0;
- if(pos==len)pos=0,len=fread(buf,1,S,stdin);
- if(pos==len)return -1;
- return buf[pos++];
- }
- inline int xuint()
- {
- int c=xchar(),x=0;
- while(~c&&c<=32)c=xchar();
- for(;'0'<=c&&c<='9';c=xchar())x=x*10+c-'0';
- return x;
- }
- }io;
- int vsh[maxn], vs[maxn], vc, vsc, lsh[maxn <<1], ls[maxn << 1], lsc, cc, T, n;
- struct event
- {
- int tp, bg, ed, val;
- void read()
- {
- tp = io.xuint();
- //scanf("%d", &tp);
- bg = io.xuint();
- val = io.xuint();
- if(tp == 1) ed = io.xuint();
- lsh[++ cc] = bg;
- if(tp == 1)lsh[++ cc] = ed + 1;
- if(tp == 1) vsh[++ vc] = val;
- }
- }ev[maxn];
- vector<int> g[maxn <<1];
- struct node
- {
- int ls, rs, l, r, sum;
- void clear(int x, int y){ls = rs = sum = 0; l = x; r = y;}
- }tr[maxm << 1];
- void mt(int x, int y)
- {
- tr[cc].clear(x, y);
- if(x == y) return;
- int t = cc, mid = (x + y)>> 1;
- cc ++; tr[t].ls = cc; mt(x, mid);
- cc ++; tr[t].rs = cc; mt(mid + 1, y);
- }
- void add(int rt, int pos, int val)
- {
- if(tr[rt].l == tr[rt].r)
- {
- tr[rt].sum += val;
- return;
- }
- int mid = (tr[rt].l + tr[rt].r)>> 1;
- if(pos <= mid) add(tr[rt].ls, pos, val);
- else add(tr[rt].rs, pos, val);
- tr[rt].sum = tr[tr[rt].ls].sum + tr[tr[rt].rs].sum;
- }
- int query(int rt, int las)
- {
- //printf("!!! %d %d\n", rt, las);
- if(tr[rt].l == tr[rt].r) return tr[rt].l;
- int ls = tr[rt].ls, rs = tr[rt].rs;
- if(tr[ls].sum>= las) return query(ls, las);
- else return query(rs, las - tr[ls].sum);
- }
- int main()
- {
- //freopen("K.in", "r", stdin);
- T = io.xuint();
- //scanf("%d", &T);
- for(int cas = 1; cas <= T; ++ cas)
- {
- n = io.xuint();
- //scanf("%d", &n);
- cc = 0; vc = 0;
- for(int i = 1; i <= (n <<1); ++ i) g[i].clear();
- for(int i = 1; i <= n; ++ i) ev[i].read();
- sort(lsh + 1, lsh + cc + 1);
- sort(vsh + 1, vsh + vc + 1);
- ls[lsc = 1] = lsh[1]; vs[vsc = 1] = vsh[1];
- for(int i = 2; i <= cc; ++ i) if(lsh[i] != lsh[i - 1]) ls[++ lsc] = lsh[i];
- for(int i = 2; i <= vc; ++ i) if(vsh[i] != vsh[i - 1]) vs[++ vsc] = vsh[i];
- for(int i = 1; i <= n; ++ i)
- if(ev[i].tp == 1)
- {
- int pos = lower_bound(ls + 1, ls + lsc + 1, ev[i].ed + 1) - ls;
- int vp = lower_bound(vs + 1, vs + vsc + 1, ev[i].val) - vs;
- g[pos].push_back(vp);
- }
- cc = 1; mt(1, vsc);
- printf("Case %d:\n", cas);
- int xx = 1;
- for(int i = 1; i <= n; ++ i)
- {
- int now = lower_bound(ls + 1, ls + lsc + 1, ev[i].bg) - ls;
- while(xx <= now)
- {
- for(int p : g[xx]) add(1, p, -1);
- xx ++;
- }
- if(ev[i].tp == 1) add(1, lower_bound(vs + 1, vs + vsc + 1, ev[i].val) - vs, 1);
- if(ev[i].tp == 2)
- {
- if(ev[i].val> tr[1].sum) puts("-1");
- else printf("%d\n", vs[query(1, ev[i].val)]);
- }
- }
- }
- return 0;
- }
- View Code
L.
题解:
二分边长二维前缀和 check
卡读入, 要 fastio
- #include<bits/stdc++.h>
- #define maxn 1005
- using namespace std;
- int T;
- int n,m;
- int a[maxn][maxn],sum[maxn][maxn];
- bool check(int x,int y,int r)
- {
- return sum[x+r-1][y+r-1]-sum[x-1][y+r-1]-sum[x+r-1][y-1]+sum[x-1][y-1]<=1;
- }
- int solve(int x,int y)
- {
- int l=0,r=min(n-x+1,m-y+1),ans=0;
- while(l<=r)
- {
- int mid=(l+r)>>1;
- if(check(x,y,mid))ans=mid,l=mid+1;
- else r=mid-1;
- }
- return ans;
- }
- struct FastIO
- {
- static const int S=5<<20;
- int wpos;char wbuf[S];
- FastIO():wpos(0){}
- inline int xchar()
- {
- static char buf[S];
- static int len=0,pos=0;
- if(pos==len)pos=0,len=fread(buf,1,S,stdin);
- if(pos==len)return -1;
- return buf[pos++];
- }
- inline int xuint()
- {
- int c=xchar(),x=0;
- while(~c&&c<=32)c=xchar();
- for(;'0'<=c&&c<='9';c=xchar())x=x*10+c-'0';
- return x;
- }
- }io;
- int main()
- {
- T=io.xuint();
- while(T--)
- {
- n=io.xuint();m=io.xuint();
- for(int i=1;i<=n;++i)
- for(int j=1;j<=m;++j)a[i][j]=io.xuint();
- for(int i=1;i<=n;++i)
- for(int j=1;j<=m;++j)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
- int ans=0;
- for(int i=1;i<=n;++i)
- for(int j=1;j<=m;++j)
- {
- ans=max(ans,solve(i,j));
- }
- printf("%d\n",ans);
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-3046321.html