T1

题面

“封印大典启动，请出Nescafe魂珠！”随着圣主applepi一声令下，圣剑护法rainbow和魔杖护法freda将Nescafe魂珠放置于封印台上。封印台是一个树形的结构，魂珠放置的位置就是根节点(编号为0)。还有n个其他节点(编号1-n)上放置着封印石，编号为i的封印石需要从魂珠上获取Ei的能量。能量只能沿着树边从魂珠传向封印石，每条边有一个能够传递的能量上限Wi，魂珠的能量是无穷大的。作为封印开始前的准备工作，请你求出最多能满足多少颗封印台的能量需求？

注意：能量可以经过一个节点，不满足它的需求而传向下一个节点。每条边仅能传递一次能量。

解法

考虑直接贪心的选点，每次选取权值最小的点，如果他可以被选，将他到根经过的所有边减去其权值

正确性

考虑若最小点P没有被选，设当前选取的权值最大的点为M，若P,M不在同一条链上，则P也会被扫描，所以只需考虑P,M在同一条链上的情况

那么若M在P下方，则不选M更佳，若M在P上方，只需考虑在M下方P上方的点，由P的最小性可得若选M可选这些点，选P也可以选

证毕！

；贪心方法不能直接对整条链贪心

代码

#pragma optimize("-O2")#include
    
      #include
     
       #include
      
       #include
       
         using namespace std; #define _ 1005 pair
        
          nodeval[_], fa[_], dvt[_]; int tot, n, awsl=0; int vis[_], dep[_];int cmp(pair
         
           a, pair
          
            b){ if(a.first!=b.first) return a.first
           
            b.second ;}void dfs(int i){ while(i!=0){ vis[i]=1 ; dvt[++tot]=make_pair(nodeval[i].first, i); i=fa[i].first ; vis[i]=1 ; } }int check(int node, int iv){ while(node){ if(fa[node].second < iv) return false ; node = fa[node].first ; } return true ;}void minu(int node, int iv){ while(node){ fa[node].second-=iv ; node = fa[node].first; }}int main(){ scanf("%d", &n); for(int i=1;i<=n;++i){ int x,y,z; scanf("%d%d%d", &x, &y, &z); nodeval[i]=make_pair(y, i); fa[i]=make_pair(x, z); } sort(nodeval+1, nodeval+n+1, cmp); //puts(":Start") ; for(int i=1;i<=n;++i){ if(check(nodeval[i].second, nodeval[i].first)) minu(nodeval[i].second, nodeval[i].first), ++awsl; } //puts(":end") ; cout<
            
             <
            
           
          
         
        
       
      
     
    

知识点小结

贪心

T2

题面

“圣主applepi于公元2011年9月创造了Nescafe，它在散发了16吃光辉之后与公元2011年11月12日被封印为一颗魂珠，贮藏于Nescafe神塔之中。公元2012年9月，圣主带领四大护法重启了Nescafe，如今已经是Nescafe之魂的第30吃传播了。不久，它就要被第二次封印，而变成一座神杯。。。”applepi思索着Nescafe的历史，准备着第二次封印。

Nescafe由n种元素组成(编号为1~n)，第i种元素有一个封印区[ai,bi]。当封印力度E小于ai时，该元素获得ai的封印能量；当封印力度E在ai到bi之间时，该元素将获得E的封印能量；而当封印力度E大于bi时，该元素将被破坏从而不能获得任何封印能量。现在圣主applepi想选择恰当的E，使得封印获得的总能量尽可能高。为了封印的最后一击尽量完美，就请你写个程序帮他计算一下吧！

解法

发现答案只有可能是左端点或右端点，暴力即可

正确性

若不在端点上，提到最近的端点不会更差；没有考虑左端点，代码、方法不熟练

代码

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std ;#define int long long#define _ 300005int ans=0, n, p, sa, sp ;int a[_], b[_];struct rec{int x,y;}c[_];bool operator <(rec a,rec b){ return a.x
        
         b.y; }signed main(){    scanf("%d", &n) ;    for(int i=1;i<=n;i++){        scanf("%d%d",&a[i],&b[i]);        sa+=a[i];        c[i].x=a[i],c[i].y=1;        c[n+i].x=b[i],c[n+i].y=-1;     }    sort(c+1,c+2*n+1);    for(int i=1;i<=2*n;i++)        if(c[i].y==1) {            sp++,sa-=c[i].x;            if(ans
        
       
      
     
    

知识点小结

思维

T3

题面

解法

看见循环同构串就先复制一下接在末尾

扫描每一个以i开头串，动态维护其中可匹配串的开头位置，然后每次二分一遍即可，比标算简单

正确性

显然；vector二分没有值会RE，字符串匹配要看清能否重用一个字符，注意调试

代码

#pragma GCC optimize(2)#pragma GCC optimize(3)#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std ;char str1[105], str2[300005] ;int len1, len2;int tot, lst, qwq, ans=0; char strs[105][105] ;int leng[105] ;unsigned long long hsv[105] ;vector
         
           rgh[51] ;vector
          
            H[100], E[100];unsigned long long hsh[200005] ;#define put(X) for(int awsl=0;awsl
           
            = nowpos) nowpos = r+leng[i] ; else { /*cout<<"Break at "<
            <<", and the pos is "<
             
              <
             
           
          
         
        
       
      
     
    

知识点小结

Hash