Codeforces Bubble Cup 8 - Finals [Online Mirror] 解题报告-白红宇的个人博客

Codeforces Bubble Cup 8 - Finals [Online Mirror] 解题报告

发布日期：2021-11-16 12:56:57 浏览次数：2 分类：技术文章

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

从一头往另一头扫一遍，再逆着回来就好了。因为贼每走一步，横坐标的奇偶性都会改变。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int i;int main(){	printf("2000\n");	for (i=1;i<=1000;i++) printf("%d 1 %d 2\n",i,i);	for (i=1000;i>0;i--) printf("%d 1 %d 2\n",i,i);	return 0;}

每走一步，树增加了一层，节点数是上一层的2倍。但是到了第n+1层开始，就会出现红/蓝边数量达到n的情况，这样的节点不能翻倍，计算一下组合数把这种情况减去就行了。算组合数的时候递推计算，用到了逆元。

#include 
   
     #include 
    
      #include 
     
       #include 
      
       #include 
       
        #include 
        
         using namespace std; #define ll long longconst int mod=1000000007;void ExEuclid(ll a,ll b,ll &x,ll &y,ll &q){ if(b==0){ x=1;y=0;q=a; return; } ExEuclid(b,a%b,y,x,q); y-=x*(a/b); } ll inv(ll num){ ll x,y,q; ExEuclid(num,mod,x,y,q); if(q==1)return (x+mod)%mod; } int main(){ int n; while(cin>>n){ ll ans=1; ll cur=1; ll C=1; for(int i=1;i<=n*2;i++){ cur*=2; cur%=mod; if(i>n){ cur-=2*C; cur+=mod; cur+=mod; cur%=mod; C*=i; C%=mod; C*=inv(i-n); C%=mod; } ans+=cur; ans%=mod; } cout<
         
          <

首先有一个可以推出来的结论，你只移动到输入数据中出现的那些位置，可以得到最优解（不需要移动到数据中没有出现的位置去）。所以就可以用离散化+dp+滚动数组来解决了。dp(i,j)表示第i轮时，位置在j（离散化后）的最优解（第一维滚动只开2）。注意状态转移时，本应是多个状态转移到一个状态，这样复杂度太高会超时，需要利用递推维护多个状态的最优值，一次性转移到一个状态。

顺便说一下，后来发现这个题可以贪心，每次维护一个范围，每次开始前移动到这个范围内，灯亮，花费为最少。

#include 
   
     #include 
    
      #include 
     
       #include 
      
       #include 
       
        #include 
        
         using namespace std; #define ll long longconst int mod=1000000007;ll INF=1000000000000000000LL;int l[5010];int r[5010];ll dp[2][100010];int pos[100010];int k;int main(){ int n,x; while(cin>>n>>x){ memset(dp,-1,sizeof(dp)); ll ans=INF; k=0; pos[k++]=x; for(int i=1;i<=n;i++){ scanf("%d%d",&l[i],&r[i]); pos[k++]=l[i]; pos[k++]=r[i]; } sort(pos,pos+k); k=unique(pos,pos+k)-pos; for(int i=0;i
         
          r[i]){ part1=pos[j]-r[i]; } if(j>0){ part2=min(part2+pos[j]-pos[j-1],dp[(i-1)%2][j]); }else{ part2=dp[(i-1)%2][j]; } dp[i%2][j]=min(dp[i%2][j],part1+part2); } part2=INF; for(int j=k-1;j>=0;j--){ ll part1=0; if(pos[j]
          
           r[i]){ part1=pos[j]-r[i]; } if(j

首先为了迅速求得树上许多点对之间的距离，需要使用nlogn的在线LCA（倍增法）。然后需要知道每条单向边被逆行了多少次，这时可用打标记的方法，起点+1终点-1，又由于它是树型结构，统计时用dfs。最后的计算利用了等比数列求和公式和快速幂。

#include 
   
     #include 
    
      #include 
     
       #include 
      
       #include 
       
        #include 
        
         using namespace std; #define ll long longconst int mod=1000000007;ll INF=1000000000000000000LL;#define max_size 100010 ll Quick_Pow(ll a,ll n){ ll ret=1; ll temp=a%mod; while (n){ if (n&1) ret=ret*temp%mod; temp=temp*temp%mod; n>>=1; } return ret; } int d[max_size],p[max_size][18]; int head[max_size]; int cnt;int a[max_size];int b[max_size];int x[max_size];bool downpoint[max_size];bool uppoint[max_size];int downres[max_size];int upres[max_size];bool vis2[max_size];struct Edge{ int v; int pre; }eg[max_size]; void add(int x,int y){ eg[cnt].v=y; eg[cnt].pre=head[x]; head[x]=cnt++; } void dfs(int k){ int m,x,i,j; for(i=head[k];i!=0;i=eg[i].pre){ x=eg[i].v; p[x][0]=k; m=k; d[x]=d[k]+1; for(j=0;p[m][j]!=0;j++){ p[x][j+1]=p[m][j]; m=p[m][j]; } dfs(x); } } int find_lca(int x,int y){ int m,k; if(x==y)return x; if(d[x]
         
          >=1; k++; } if(x==y)return x; k=0; while(x!=y){ if(p[x][k]!=p[y][k]||p[x][k]==p[y][k]&&k==0){ x=p[x][k]; y=p[y][k]; k++; } else{ k--; } } return x; }struct oriEdge{ int v; int flag; oriEdge(int v,int flag):v(v),flag(flag){ } oriEdge(){ }};vector
          
            E[max_size]; bool vis[max_size]; int siz[max_size]; int predfs(int u){ vis[u]=1; int sz=E[u].size(); siz[u]=1; for(int i=0;i
           
            >n){ cnt=1; for(int i=1;i
            
             >k; int Last=1; for(int i=1;i<=k;i++){ int s; scanf("%d",&s); int LCA=find_lca(Last,s); ll cur=0; if(Last!=LCA){ upres[Last]++; upres[LCA]--; } if(s!=LCA){ downres[s]++; downres[LCA]--; } Last=s; } dfs2(1); cout<
             
              <

注意题目给的数据范围，边的长度最长是9，但是每多经过一个点，速度变为1/10。也就是说，需要经过尽可能少的点。另外，边长度可以是0，也就是说，如果最后经过了一系列长度为0的边，是不会增加时间的。我的做法是多次bfs，先找出哪些点到终点可以全是0边，然后在这些点中，找一个离起点最近的，再贪心找到路径。实现比较挫，bfs了好多次，也跪了好多次，最后才过。。。

#include 
   
     #include 
    
      #include 
     
       #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std; #define ll long longconst int INF = 1000000000;const int maxm=100010;const int maxn=100010;int head[maxn];int pre[maxm<<1];int from[maxm<<1];int to[maxm<<1];int len[maxm<<1];int vis[maxn];int tote;int k;int lv[maxn];int _lv[maxn];bool finish[maxn];bool finish2[maxn];int cost[maxn];int lvcost[maxn];int fa[maxn];int _fa[maxn];void init(){ memset(head,-1,sizeof(head)); tote=0; k=0;}void addedge(int u,int v,int l){ to[tote]=v; from[tote]=u; len[tote]=l; pre[tote]=head[u]; head[u]=tote++; // to[tote]=u; from[tote]=v; len[tote]=l; pre[tote]=head[v]; head[v]=tote++;}int ans[maxn];int path[maxn];void clearQueue(queue
           
             &que){ while(que.size())que.pop();}int print(int u){ int re=0; if(!finish[u])printf("%d",cost[u]); if(u)re=print(from[fa[u]])+1; path[k++]=u; return re;}int main(){ init(); int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ int u,v,l; scanf("%d%d%d",&u,&v,&l); addedge(u,v,l); } queue
            
              que; que.push(0); vis[0]=1; while(que.size()){ int u=que.front(); que.pop(); for(int i=head[u];~i;i=pre[i]){ int v=to[i]; if(vis[v])continue; vis[v]=1; lv[v]=lv[u]+1; que.push(v); } } clearQueue(que); memset(vis,0,sizeof(vis)); que.push(n-1); vis[n-1]=1; while(que.size()){ int u=que.front(); que.pop(); finish[u]=1; for(int i=head[u];~i;i=pre[i]){ int v=to[i]; if(len[i])continue; //only 0 edge if(vis[v])continue; vis[v]=1; _lv[v]=_lv[u]+1; que.push(v); _fa[v]=i; } } int MIN=INF; for(int i=0;i

转载地址：https://blog.csdn.net/squee_spoon/article/details/48273969 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Codeforces Round #319 (Div. 1) div1 A B C

下一篇：Codeforces Round #317 [AimFund Thanks-Round] (Div. 1) B

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章