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的最深深度
然后询问直接用深度搞就行，特别地需要判一下是否属于同一棵子树
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 const int maxn = 100005;
5 int st[17][maxn], lo[maxn], a[maxn], n, m, base;
6 vector<int> g[maxn];
7
8 struct node
9 {
10 int val, dep, maxdep;
11 }tr[maxn << 1];
12
13 int find(int l, int r)
14 {
15 int t = lo[r - l + 1];
16 return max(st[t][l], st[t][r - (1 << t) + 1]);
17 }
18
19 int makedag(int nd, int l, int r, int dep)
20 {
21 //printf("? %d %d %d\n", l, r, dep);
22 tr[nd].dep = dep;
23 int maxval = find(l, r);
24 int lpos = lower_bound(g[maxval].begin(), g[maxval].end(), l) - g[maxval].begin();
25 int rpos = upper_bound(g[maxval].begin(), g[maxval].end(), r) - g[maxval].begin() - 1;
26 vector<int> tmp; tmp.clear(); tmp.push_back(l - 1);
27 vector< pair<int, int> > inter; inter.clear();
28 for(int i = lpos; i <= rpos; ++ i)
29 {
30 int p = g[maxval][i];
31 tmp.push_back(p);
32 tr[p].dep = dep + 1;
33 //printf("! %d %d %d\n", dep, p, tr[p].dep);
34 }
35 tmp.push_back(r + 1);
36 for(int i = 1; i <= rpos - lpos + 2; i ++)
37 if(tmp[i] - 1 > tmp[i - 1])
38 {
39 base ++; int t = base;
40 int v = makedag(base, tmp[i - 1] + 1, tmp[i] - 1, dep + 2);
41 inter.push_back(make_pair(t, v));
42 }else inter.push_back(make_pair(0, 0));
43 int ret = 0;
44 for(int i = 1; i <= rpos - lpos + 1; i ++)
45 {
46 int p = tmp[i];
47 tr[p].maxdep = max(inter[i - 1].second, inter[i].second);
48 tr[p].maxdep = max(tr[p].maxdep, tr[p].dep);
49 ret = max(ret, tr[p].maxdep);
50 }
51 return ret;
52 }
53
54 int abs(int x){return x < 0 ? -x : x;}
55
56 int lg[maxn], rg[maxn];
57 stack<int> s;
58
59 int main()
60 {
61 lo[1] = 0; for(int i = 2; i <= 100000; ++ i) lo[i] = lo[i >> 1] + 1;
62 scanf("%d%d", &n, &m); a[0] = a[n + 1] = n + 100;
63 for(int i = 1; i <= n; ++ i)
64 {
65 scanf("%d", &a[i]);
66 g[a[i]].push_back(i);
67 st[0][i] = a[i];
68 }
69 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());
70 for(int k = 1; (1 << k) <= n; ++ k)
71 for(int i = 1; i + (1 << k) - 1 <= n; ++ i)
72 st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
73 base = n + 1; makedag(base, 1, n, 0);
74 while(!s.empty()) s.pop(); s.push(0);
75 for(int i = 1; i <= n; ++ i)
76 {
77 while(a[i] > a[s.top()]) s.pop();
78 lg[i] = s.top() + 1;
79 s.push(i);
80 }
81 while(!s.empty()) s.pop(); s.push(n + 1);
82 for(int i = n; i >= 1; -- i)
83 {
84 while(a[i] > a[s.top()]) s.pop();
85 rg[i] = s.top() - 1;
86 s.push(i);
87 }
88 while(m --)
89 {
90 int x, y; scanf("%d%d", &x, &y);
91 if(y == 0)printf("%d\n", (tr[x].maxdep - tr[x].dep) >> 1);
92 else
93 {
94 if(a[x] < a[y]) swap(x, y);
95 if(a[x] == a[y] || y < lg[x] || y > rg[x]) printf("0\n");
96 else printf("%d\n", abs(tr[x].dep - tr[y].dep) >> 1);
97 }
98 }
99 return 0;
100 }
View Code
B.
unsolved
C.
签到题
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 const int maxn = 5005;
5
6 pair<int, int> st[maxn];
7 int n, m, a[maxn], ans[maxn];
8
9 int main()
10 {
11 scanf("%d%d", &n, &m);
12 for(int i = 1; i <= n; i ++)
13 {
14 scanf("%d", &a[i]);
15 st[i] = make_pair(a[i], i);
16 }
17 sort(st + 1, st + n + 1);
18 int ret = 0;
19 for(int i = 1; i <= n; ++ i) ans[i] = 0;
20 for(int i = 1; i <= n; ++ i)
21 {
22 int pos = st[i].second;
23 int val = -1;
24 for(int j = max(1, pos - m); j <= min(n, pos + m); ++ j)
25 if(a[j] < a[pos]) val = max(val, ans[j]);
26 ans[pos] = val + 1;
27 ret = max(ret, ans[pos]);
28 }
29 printf("%d\n", ret);
30 return 0;
31 }
View Code
D.
签到题
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 const int maxn = 2000005;
5 int T, n, a[maxn];
6
7 int abs(int x){return x < 0 ? -x : x;}
8
9 int main()
10 {
11 scanf("%d", &T);
12 while(T --)
13 {
14 scanf("%d", &n);
15 for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
16 sort(a + 1, a + n + 1);
17 int cnt = 0, now = 0;
18 for(int i = 1; i <= n; ++ i)
19 {
20 if(now == 0 || abs(now - a[i]) > 10)
21 {
22 cnt ++;
23 now = a[i] + 10;
24 }
25 }
26 printf("%d\n", cnt);
27 }
28 return 0;
29 }
View Code
E.
unsolved
F.
题解：
同UOJ275，利用Lucas定理转化，将C(n,m)中的n,m写成7进制数，存在某一位n的数位比m小
然后按数位计数就行了
1 #include<cstdio>
2 #define mo 1000000007
3 using namespace std;
4 int T;
5 long long n;
6 long long a[70],qr[70],g[70];
7 int main()
8 {
9 scanf("%d",&T);
10 for (int oo=1;oo<=T;++oo)
11 {
12 scanf("%lld",&n);
13 a[0]=0;
14 long long tmp=n;
15 while (tmp)
16 a[++a[0]]=tmp%7,
17 tmp/=7;
18 qr[0]=1;
19 g[0]=1;
20 for (int i=1;i<=a[0]+1;++i)
21 qr[i]=qr[i-1]*7LL%mo,
22 g[i]=1LL*g[i-1]*28%mo;
23 long long ans=0,p=0,q=1;
24 for (int i=a[0];i>=1;--i)
25 {
26 for (int j=0;j<=a[i]-1;++j)
27 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;
28 p=(p*7LL+a[i])%mo;
29 q=q*(a[i]+1LL)%mo;
30 }
31 long long cnt=1;
32 for (int i=1;i<=a[0];++i) cnt=cnt*(a[i]+1LL)%mo;
33 printf("Case %d: %lld\n",oo,((ans+n+1-cnt)%mo+mo)%mo);
34 }
35 }
View Code
G.
题解：
SCC模板题
1 #include<bits/stdc++.h>
2 #define maxn 205
3 using namespace std;
4 int T,n,m;
5 vector<int> g[maxn],scc[maxn];
6 stack<int> s;
7 int pre[maxn],low[maxn],belong[maxn];
8 int t,cnt;
9 void dfs(int u)
10 {
11 pre[u]=low[u]=++t;
12 s.push(u);
13 for(int i=0;i<g[u].size();++i)
14 {
15 int v=g[u][i];
16 if(!pre[v])dfs(v),low[u]=min(low[u],low[v]);
17 else if(!belong[v])low[u]=min(low[u],pre[v]);
18 }
19 if(low[u]==pre[u])
20 {
21 ++cnt;
22 while(1)
23 {
24 int x=s.top();s.pop();
25 belong[x]=cnt;
26 scc[cnt].push_back(x);
27 if(x==u)break;
28 }
29 }
30 }
31 int main()
32 {
33 scanf("%d",&T);
34 while(T--)
35 {
36 scanf("%d%d",&n,&m);
37 for(int i=1;i<=n;++i)g[i].clear(),scc[i].clear(),pre[i]=low[i]=belong[i]=0;
38 t=cnt=0;
39 while(!s.empty())s.pop();
40 for(int u,v,i=1;i<=m;++i)
41 {
42 scanf("%d%d",&u,&v);
43 u++;v++;
44 g[u].push_back(v);
45 }
46 for(int i=1;i<=n;++i)if(!pre[i])dfs(i);
47 printf("%d\n",cnt);
48 }
49 }
View Code
H.
题解：
观察（榜）发现可能有一些奥妙重重的性质
可以直接枚举0~2^21 check
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 int T;
5 ll A,B,C,NA,NB,NC;
6 int main()
7 {
8 scanf("%d",&T);
9 while(T--)
10 {
11 cin>>NA>>NB>>NC>>A>>B>>C;
12 for(int i=0;i<(1<<21);++i)
13 {
14 ll t=1ll*i*i*i;
15 if(t%NA==A&&t%NB==B&&t%NC==C)
16 {
17 cout<<i<<endl;
18 break;
19 }
20 }
21 }
22 }
View Code
I.
unsolved
J.
题解：
考虑利用三次方差因式分解提出一个1e-15，然后单独统计前面的部分
这样会被卡常
忽略高阶的1e-15就能过了
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 const double eps = 1e-15;
5 const double mi = 1.0 / 3.0;
6 double sum = 0;
7 int x, y;
8
9 void pri(int p)
10 {
11 char s[10];
12 int cc = 0;
13 s[3] = s[2] = s[1] = 48;
14 while(p > 0)
15 {
16 s[++ cc] = 48 + (p % 10);
17 p /= 10;
18 }
19 for(int i = 3; i >= 1; i --) putchar(s[i]);
20 puts("");
21 }
22
23 int main()
24 {
25 while(scanf("%d%d", &x, &y) == 2 && 1ll * x + 1ll * y > 0)
26 {
27 sum = 0;
28 for(int i = x; i <= y; ++ i)
29 {
30 double p1 = (double)i + eps;
31 double p2 = (double)i;
32 double tmp = 3.0 * pow(p1 * p2, mi);
33 //printf("%d %.5Lf\n", i, (double)1.0 / tmp);
34 sum += (double)1.0 / tmp;
35 }
36 int cnt = 15;
37 while(sum + eps < 1) {cnt ++; sum *= 10.0;}
38 while(sum >= 10 + eps) {cnt --; sum /= 10.0;}
39 printf("%.5lfE-", sum); pri(cnt);
40 }
41 return 0;
42 }
View Code
K.
题解：
动态维护第k小，线段树上二分
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 const int maxn = 100005;
5 const int maxm = 1000005;
6
7 struct FastIO
8 {
9 static const int S=5<<20;
10 int wpos;char wbuf[S];
11 FastIO():wpos(0){}
12 inline int xchar()
13 {
14 static char buf[S];
15 static int len=0,pos=0;
16 if(pos==len)pos=0,len=fread(buf,1,S,stdin);
17 if(pos==len)return -1;
18 return buf[pos++];
19 }
20 inline int xuint()
21 {
22 int c=xchar(),x=0;
23 while(~c&&c<=32)c=xchar();
24 for(;'0'<=c&&c<='9';c=xchar())x=x*10+c-'0';
25 return x;
26 }
27 }io;
28
29 int vsh[maxn], vs[maxn], vc, vsc, lsh[maxn << 1], ls[maxn << 1], lsc, cc, T, n;
30 struct event
31 {
32 int tp, bg, ed, val;
33 void read()
34 {
35 tp = io.xuint();
36 //scanf("%d", &tp);
37 bg = io.xuint();
38 val = io.xuint();
39 if(tp == 1) ed = io.xuint();
40 lsh[++ cc] = bg;
41 if(tp == 1)lsh[++ cc] = ed + 1;
42 if(tp == 1) vsh[++ vc] = val;
43 }
44 }ev[maxn];
45 vector<int> g[maxn << 1];
46 struct node
47 {
48 int ls, rs, l, r, sum;
49 void clear(int x, int y){ls = rs = sum = 0; l = x; r = y;}
50 }tr[maxm << 1];
51
52 void mt(int x, int y)
53 {
54 tr[cc].clear(x, y);
55 if(x == y) return;
56 int t = cc, mid = (x + y) >> 1;
57 cc ++; tr[t].ls = cc; mt(x, mid);
58 cc ++; tr[t].rs = cc; mt(mid + 1, y);
59 }
60
61 void add(int rt, int pos, int val)
62 {
63 if(tr[rt].l == tr[rt].r)
64 {
65 tr[rt].sum += val;
66 return;
67 }
68 int mid = (tr[rt].l + tr[rt].r) >> 1;
69 if(pos <= mid) add(tr[rt].ls, pos, val);
70 else add(tr[rt].rs, pos, val);
71 tr[rt].sum = tr[tr[rt].ls].sum + tr[tr[rt].rs].sum;
72 }
73
74 int query(int rt, int las)
75 {
76 //printf("!!! %d %d\n", rt, las);
77 if(tr[rt].l == tr[rt].r) return tr[rt].l;
78 int ls = tr[rt].ls, rs = tr[rt].rs;
79 if(tr[ls].sum >= las) return query(ls, las);
80 else return query(rs, las - tr[ls].sum);
81 }
82
83 int main()
84 {
85 //freopen("K.in", "r", stdin);
86 T = io.xuint();
87 //scanf("%d", &T);
88 for(int cas = 1; cas <= T; ++ cas)
89 {
90 n = io.xuint();
91 //scanf("%d", &n);
92 cc = 0; vc = 0;
93 for(int i = 1; i <= (n << 1); ++ i) g[i].clear();
94 for(int i = 1; i <= n; ++ i) ev[i].read();
95 sort(lsh + 1, lsh + cc + 1);
96 sort(vsh + 1, vsh + vc + 1);
97 ls[lsc = 1] = lsh[1]; vs[vsc = 1] = vsh[1];
98 for(int i = 2; i <= cc; ++ i) if(lsh[i] != lsh[i - 1]) ls[++ lsc] = lsh[i];
99 for(int i = 2; i <= vc; ++ i) if(vsh[i] != vsh[i - 1]) vs[++ vsc] = vsh[i];
100 for(int i = 1; i <= n; ++ i)
101 if(ev[i].tp == 1)
102 {
103 int pos = lower_bound(ls + 1, ls + lsc + 1, ev[i].ed + 1) - ls;
104 int vp = lower_bound(vs + 1, vs + vsc + 1, ev[i].val) - vs;
105 g[pos].push_back(vp);
106 }
107 cc = 1; mt(1, vsc);
108 printf("Case %d:\n", cas);
109 int xx = 1;
110 for(int i = 1; i <= n; ++ i)
111 {
112 int now = lower_bound(ls + 1, ls + lsc + 1, ev[i].bg) - ls;
113 while(xx <= now)
114 {
115 for(int p : g[xx]) add(1, p, -1);
116 xx ++;
117 }
118 if(ev[i].tp == 1) add(1, lower_bound(vs + 1, vs + vsc + 1, ev[i].val) - vs, 1);
119 if(ev[i].tp == 2)
120 {
121 if(ev[i].val > tr[1].sum) puts("-1");
122 else printf("%d\n", vs[query(1, ev[i].val)]);
123 }
124 }
125 }
126 return 0;
127 }
View Code
L.
题解：
二分边长二维前缀和check
卡读入，要fastio
1 #include<bits/stdc++.h>
2 #define maxn 1005
3 using namespace std;
4 int T;
5 int n,m;
6 int a[maxn][maxn],sum[maxn][maxn];
7 bool check(int x,int y,int r)
8 {
9 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;
10 }
11 int solve(int x,int y)
12 {
13 int l=0,r=min(n-x+1,m-y+1),ans=0;
14 while(l<=r)
15 {
16 int mid=(l+r)>>1;
17 if(check(x,y,mid))ans=mid,l=mid+1;
18 else r=mid-1;
19 }
20 return ans;
21 }
22 struct FastIO
23 {
24 static const int S=5<<20;
25 int wpos;char wbuf[S];
26 FastIO():wpos(0){}
27 inline int xchar()
28 {
29 static char buf[S];
30 static int len=0,pos=0;
31 if(pos==len)pos=0,len=fread(buf,1,S,stdin);
32 if(pos==len)return -1;
33 return buf[pos++];
34 }
35 inline int xuint()
36 {
37 int c=xchar(),x=0;
38 while(~c&&c<=32)c=xchar();
39 for(;'0'<=c&&c<='9';c=xchar())x=x*10+c-'0';
40 return x;
41 }
42 }io;
43 int main()
44 {
45 T=io.xuint();
46 while(T--)
47 {
48 n=io.xuint();m=io.xuint();
49 for(int i=1;i<=n;++i)
50 for(int j=1;j<=m;++j)a[i][j]=io.xuint();
51 for(int i=1;i<=n;++i)
52 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];
53 int ans=0;
54 for(int i=1;i<=n;++i)
55 for(int j=1;j<=m;++j)
56 {
57 ans=max(ans,solve(i,j));
58 }
59 printf("%d\n",ans);
60 }
61 }
View Code