Gym 102091 2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest(组队训练)

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的最深深度

然后询问直接用深度搞就行,特别地需要判一下是否属于同一棵子树

Gym 102091 2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest(组队训练)
  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.

签到题

Gym 102091 2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest(组队训练)
 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.

签到题

Gym 102091 2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest(组队训练)
 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小

然后按数位计数就行了

Gym 102091 2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest(组队训练)
 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模板题

Gym 102091 2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest(组队训练)
 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

Gym 102091 2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest(组队训练)
 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就能过了

Gym 102091 2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest(组队训练)
 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小,线段树上二分

Gym 102091 2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest(组队训练)
  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

Gym 102091 2018-2019 ACM-ICPC, Asia Nakhon Pathom Regional Contest(组队训练)
 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

 

上一篇:Ubuntu修改时区和设置24小时时间格式


下一篇:Linux时区修改