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

        这把打得真是水，简直不能忍，题数就差了2题，木有出线，我要背锅。。

1012 

        这题我并没有码，讲讲思路就好了。要求一个式子最大值，分析一下发现可以贪心搞，把最大2个数、最小2个数、绝对值最小2个数找出来，注意不用sort，然后暴力试这6个数就好了。学弟很给力1A了。

1006 

        如果字符串中全是f，那么就是(len+1)/2。如果是c和f，随便把一个c循环到开头，检查两个c之间和最后一个c到末尾的f是否达到2个以上。然而我写了bug坑了几发。

#include 
   
         #include 
    
          #include 
     
           #include 
      
           #include 
       
            #include 
        
          #include 
         
           #include 
          
         
        
       
      
     
    
   

        这题怎么看怎么像斐波那契数，但是解法却无关。从小到大，递推(可以理解为dp)求出每个串有多少个c，第一个c离左边多少，最后一个c离右边多少，还有长度。si很自然地就是si-2和si-1拼起来，答案就是左半部分的答案ans(i-2)+右半部分的答案ans(i-1)+横跨两边的组数，用递推出来的信息算一下就好了。

#include 
   
         #include 
    
          #include 
     
           #include 
      
           #include 
       
            #include 
        
          #include 
         
           #include 
          
         
        
       
      
     
    
   

1003 

        求一个无向图的最小割，必须恰好包含给出的生成树的一条边。做法是以生成树为骨架，多出来边uv，就把u-v在生成树上的路径上所有边加上权1，到最后最小边权就是答案。用离线LCA算法+打标实现。到最后dfs一次读取标记的信息，得到每条边的权，找出最小值即可。唉，这个处理方法前几天CF做过的，而且是自己想出的，比赛时居然卡题了，逗比如我。。。

#include 
   
       #include 
    
        #include 
     
         #include 
      
         #include 
       
          #include 
        
          using namespace std; #define ll long long const int mod=1000000007; ll INF=1000000000000000000LL; #define maxn 20010 //输入挂 void scanf_(int &num){ char in; bool neg=false; while(((in=getchar()) > '9' || in<'0') && in!='-') ; if(in=='-') { neg=true; while((in=getchar()) >'9' || in<'0'); } num=in-'0'; while(in=getchar(),in>='0'&&in<='9') num*=10,num+=in-'0'; if(neg) num=0-num; }int n,m; int tote; int a[maxn]; int b[maxn]; int res[maxn]; int cnt[maxn]; int head[maxn];int pre[maxn<<1];int to[maxn<<1];void add(int x,int y){ to[tote]=y; pre[tote]=head[x]; head[x]=tote++; } bool vis[maxn]; int ans; //这个dfs为了读取标记信息。 void dfs2(int k){ vis[k]=1; cnt[k]+=res[k]; for(int i=head[k];~i;i=pre[i]){ int x=to[i]; if(vis[x])continue; dfs2(x); cnt[k]+=cnt[x]; } if(k!=1)ans=min(ans,cnt[k]);} int ff[maxn];int _find(int u){ if(ff[u]==u)return u; int res=_find(ff[u]); return res;}void _union(int a,int b){ //把a并到b上 int fa=_find(a); int fb=_find(b); ff[a]=b;}//询问有关 const int maxm=200010;int qhead[maxn];int qpre[maxm<<1];int qto[maxm<<1];int totq;void qadd(int x,int y){ qto[totq]=y; qpre[totq]=qhead[x]; qhead[x]=totq++; } bool finish[maxn];//离线LCA void LCA(int u){ vis[u]=1; for(int i=head[u];~i;i=pre[i]){ int v=to[i]; if(vis[v])continue; LCA(v); _union(v,u); } finish[u]=1; //解决关于u的问题。 for(int i=qhead[u];~i;i=qpre[i]){ int v=qto[i]; if(finish[v]){ int lca=_find(v); if(u!=lca){ res[u]++; res[lca]--; } if(v!=lca){ res[v]++; res[lca]--; } } } }void init(){ memset(head,-1,sizeof(head)); memset(cnt,0,sizeof(cnt)); memset(res,0,sizeof(res)); memset(finish,0,sizeof(finish)); memset(qhead,-1,sizeof(qhead)); memset(vis,0,sizeof(vis)); tote=0; totq=0; // for(int i=1;i<=n;i++){ ff[i]=i; }} int main(){ int t; cin>>t; int cas=0; while(t--){ cas++; cin>>n>>m; init(); for(int i=1;i
        
       
      
     
    
   

        这题待补。。

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