2016弱校联萌十一专场10.3 遗憾题合集-白红宇

2016弱校联萌十一专场10.3 遗憾题合集

阅读量：6256 次

发布时间：2019-06-22

本文共 5379 字，大约阅读时间需要 17 分钟。

http://acm-icpc.aitea.net/index.php?2016%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95

C.We don't wanna work!

@siludose 你要的代码，做好了参考看

SB模拟，xjb模拟

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             using namespace std;typedef long long LL;const int MAXN = 1e6+5;struct Node{ string s; int time; int d;} a[MAXN];bool cmp(Node a, Node b){ if(a.d == b.d) return a.time > b.time; return a.d > b.d;}struct cmp2{ bool operator()(const Node a, const Node b)const { if(a.d == b.d) return a.time > b.time; return a.d > b.d; }};struct cmp1{ bool operator()(const Node a, const Node b)const { if(a.d == b.d) return a.time < b.time; return a.d < b.d; }};set
              
               se1;set
               
                se2;map
                
                 mp;string s;int main(){ int n, m; while(~scanf("%d",&n)) { se1.clear(); se2.clear(); mp.clear(); double tp = 1.0*n*0.2; int nn = (int)tp; int tn = n; for(int i=1; i<=tn; i++) { a[i].time = i; cin>>a[i].s>>a[i].d; mp[a[i].s] = a[i]; } sort(a+1, a+1+tn, cmp); for(int i=1; i<=nn; i++) se1.insert(a[i]); for(int i=nn+1; i<=n; i++) se2.insert(a[i]); scanf("%d",&m); Node tmp; for(int i=tn+1; i<=tn+m; i++) { char op; cin>>op; if(op == '-') { cin>>s; tmp = mp[s]; if(se1.erase(tmp)) nn--; se2.erase(tmp); if(nn>(int)(1.0*(n-1)*0.2)) { nn--; tmp=*se1.begin(); se1.erase(tmp); se2.insert(tmp); cout<
                 
                  >a[i].s>>a[i].d; a[i].time=i; mp[a[i].s]=a[i]; //cout<
                  
                   <<" "<
                   
                    <
                    
                     (*se2.begin()).d||a[i].d==(*se2.begin()).d&&a[i].time>(*se2.begin()).time) { se1.insert(a[i]); cout<
                     
                      tmp.d||a[i].d==tmp.d&&a[i].time>tmp.time) { se1.erase(tmp); se1.insert(a[i]); se2.insert(tmp); cout<
                      
                       0) { if(a[i].d>tmp.d||a[i].d==tmp.d&&a[i].time>tmp.time) { se1.insert(a[i]); cout<

E.Similarity of Subtrees

真心佩服那帮用递归栈都能不爆栈的大神。。。不说了，伤心题

题目要求求出相似点对对数，相似指2对子树在不同且对应深度的结点都一样

可以看做可加的向量：(d0,d1, ... ,dn)其中dk是指深度为k的结点个数

父结点的向量是其本身(1,0,0, ... )+(0,所有子结点的向量之和)

不过要是直接向量上会o(n^2)滚粗

所以搞成hash值:d0*a^0+d1*a^1+d2*a^2+...

然后发现数字太大了，要模

a>100000就可以，没有哪个向量分量超过100000

对结果模的数m>1000000000，且必须是素数，感觉不设这么大会有hash冲突

可以map搞o(nlogn)或者hash_map搞o(n)

比赛中要注意要是这种数据都能爆栈，就用非递归+stack<int>硬杠

此题还可以bfs硬撑

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              using namespace std;typedef long long LL;const LL maxn=1e6+10,p=9901,mod=1e9+7;vector
              
               G[maxn];LL hash_v[maxn];map
               
                mp;map
                
                 ::iterator it;void dfs(LL u){ hash_v[u]=1; for(LL i=0; i
                 
                  second*(it->second-1)/2; printf("%lld\n",ans); } return 0;}

View Code

F.Escape from the Hell

题意：有人在悬崖上的1条绳子上，

有n罐能量饮料，喝的当天可以向上爬ai米，但是若没有爬到顶点，之后会下滑bi米，不喝则不会动

与此同时，有只蜘蛛第i天会不下滑地向上ci米，且上升到人身上就会致死

问人能否逃离，第几天逃离

题解：枚举最后1天喝哪种饮料，并从饮料集合去除

把其他饮料按照a(i)-b(i)的大小排序，负数的一定没用

设sdis(i)=sdis(i-1)+c(i) pdis(i)=pdis(i)+a(i)-b(i)

找到最小的x使得

任何i<x都是pdis(i)>sdis(i)并且pdis(x-1)+a(x)>=L，就是逃离成功

枚举过的那个元素不用再重复枚举

G.Shere the Ruins Presevation

题意：把点集以1条平行于y轴且不相切任何点的直线分成2个点集，然后用栅栏把2个点集围成最小面积

题解：感觉就是对整个点集以凸包的围法画边，把整条x轴按照点集在x上的分量离散化

把整个图形按顺序分割出三角形，再把那些三角形根据占用x轴的区间把面积写在树状数组

查询时相邻区间查询因为分割而少掉的面积，最大的那个减去总面积就是解

andrew's monotone chain?

J.compressed formula

题意：把不同ri字符串重复si次之后前后连接，表达式就按平常的计算顺序做，问字符串对应表达式结果模1000000007

题解：还是有规律的，从左向右遇乘则预存左乘数s1，右乘数s2归0；遇加/减则把当前2个乘数乘了往左边s0加，2个乘数s1,s2初始化，s1看前面符号设1或-1

字符串的排布

1.只有数字，像68，则就是68686868..... 这样循环，s2=s2*10^字符串长度+字符串对应数字，矩阵乘法可以归并大量重复运算

2.数字和乘，像68*233，则就是68*23368*23368*233..... 这样循环，s2=s2*10^左字符串长度+左字符串对应数字

s1=s1*s2*右左连接的字符串对应数字^(重复次数-1)*右字符串

有多个乘？把中间的乘数独立出来，跟上述乘数一样快速幂

3.数字、乘和加/减，像3*4+5*6+7*8，则就是3*4+5*6+7*83*4+5*6+7*83*4+5*6+7*8......

中间的乘数计算结果独立出来，第1个左乘法公式和最后1个右乘法公式独立出来，其他的都快速幂

K.non-redundent drive

一棵无向树，有一定加油量加油站n个，一定距离的路，越长耗油越多，不能在半路耗完油，但可以在到达加油站时油正好到0再加油，一条路最多走1次，问最多走过多少个点

把答案分割为2部分：从一个点出发耗油量，到达一个点的余油量，用树分治的话可以覆盖所有点对，故使用

至于边对有顺序之分的问题，可以正着遍历子树1次，反着遍历子树1次，每次记录dp[i]，深度为i的点向上走时到根最多剩多少油

dp[i]序号从小到大，值是递增的，所以其实取最深的最大值是可以的。

如何得到这个位置？直接遍历dp数组，到最深的非-1值处向浅处刷，查询从上到下的路线时对每个点2分求答案

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define lson l,m,ls[rt]#define rson m+1,r,rs[rt]#define inf 1e9using namespace std;#define ll long longconst int maxn = 203000;vector
                
                 
                   >G[maxn];int done[maxn] , sum[maxn] , fN;int max(int a,int b){ return a>b?a:b;}int min(int a,int b){ return a
                  
                   = fN ) return dfs2(v,u); } return u;}int ans;int val[maxn];int dp[maxn] , len;//vector
                   
                    
                      >p;void dfs4(int u,int pa,int d,int co,int mi){ mi = min( mi , co ); co += val[u]; int l = 1, r = len; while( l <= r ){ int m=((l+r)>>1); if( dp[m] + mi >= 0 ){ ans = max(ans,d + m); l = m+1; }else r = m-1; } for(int i=0;i
                     
                      = 0 ){ if( len < d ){ for(int i=len+1;i<=d;i++) dp[i] = -inf; len = d; } dp[d] = max( dp[d] , co ); maxlen = max(maxlen,d); mi = 0; } for(int i=0;i
                      
                       =0;j--) dp[j] = max(dp[j],dp[j+1]); } len = 1; dp[1] = val[u]; for(i=G[u].size()-1;i>=0;i--){ int v = G[u][i].first , w = G[u][i].second; if( done[v] ) continue; dfs4(v,u,1,-w,-w); maxlen = -1; dfs3(v,u,2,val[u]-w,-w); for(j=maxlen-1;j>=0;j--) dp[j] = max(dp[j],dp[j+1]); } ans = max( ans , len );// printf("u %d ans %d len %d\n",u,ans,len);}void dfs(int u){ fN = dfs1(u,-1); int r = dfs2(u,-1); sol(r); done[r] = 1; for(int i=0;i