CF掉分日记 6.6 6.8-白红宇

CF掉分日记 6.6 6.8

阅读量：4662 次

发布时间：2019-06-09

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

---恢复内容开始---

　　写的效果依旧不好还没写完前四题比赛就结束了而且这些普及组的题目我大多还是缺少简单算法的灵性总是把问题搞复杂化。

6.5 A 第一道题非常水简单分析发现是一个快速幂的逆过程。logn时间内解决。

B 这是一个比平成的模拟要难上一点点的模拟因为有可能爆ll 所以写之前要把该考虑到的情况考虑好再写。

C 一眼不可做也看不懂题目是什么意思，还是看不懂弃掉以后看见了再写

　 D 感觉能写一段序列分成k段第一段乘1 第二段乘2... 求最大值显然dp 然后 f[i][j] 表示前 i个数字分成j段的最大值这个dp 是n^2k的相当难受貌似斜率优化可以到nk 然后？然后还是挂掉。

乱搞出来一个贪心是我从后往前拿第k 段 k-1段每次我都选取最大的那个后缀和 nlogn 发现一直wa 没有考虑到一些因素并不是后缀和最大的是最优的因为当前数字造成的贡献不只只有前面的而且还是有后面的，所以说不太会写，考虑设p1 p2 ...pk 为每一段的断点显然p1=1; pi<pi+1 取bi为 i~n的和也就是后缀和那么此时sum=1*(bp1-bp2)+2*(bp2-bp3)+..k*bk; 得到.bp1 + bp2 + bp3 + bp4 ... bpk;

发现我们只需取最大的这几个bp值即可注意p1是强制取1的。

剩下的题目没看结束了。。。

6.8 A 是一道非常水的题目注意好关系就能AC

B 猛一看感觉是不可写的但是实际上画个图发现每次放棋子只能放在上一个棋子的右边或者下边注意维护好轮换放即可。

C 是一道比较有意思的题目看起来也不可做深入理解发现只会有两种情况 1 枚举每次放哪个数字了如果当前手牌中没有的话就一直取数字直至把这个数字取出来然后模拟放回去。

或者是在这个队伍之中就直接模拟排序好如果可以成功那么一定优于第一种决策。这样就OK了！

D 好像是一个排列计数看了一下不会写弃掉了现在再看 n<=2e5 看完题解发现是一个很妙的树形dp

题目：

哦原来是这样的对于一个无根树来说我们以任意的角度来看的话我们可以想象成每个点都可以是根，所以可以以1为根然后发现 1 任何位置都是可以放的。

考虑1的子树由于子树必须是在一个圆弧之上显然。所以子树们和父亲们放的位置决定了父亲的初始方案数仔细思考1可以放n个位置我们让其按照一个方式放的话也把所有方案数遍历到了。

好题于是就有转移了。下面放代码：

//#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        #include
                        #define INF 2147483646#define ll long long#define min(x,y) (x>y?y:x)#define max(x,y) (x>y?x:y)#define RI register ll#define up(p,i,n) for(ll i=p;i<=n;++i)#define db double#define mod 998244353using namespace std;char buf[1<<15],*fs,*ft;inline char getc(){ return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}inline void put(ll x){ x<0?x=-x,putchar('-'):0; int num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar('\n');return;}const int MAXN=200010;int n,len;ll fac[MAXN],sz[MAXN],f[MAXN];//f[i] 表示以i为根的子树内部的方案数int vis[MAXN];int lin[MAXN<<1],nex[MAXN<<1],ver[MAXN<<1];inline void add(int x,int y){ ver[++len]=y; nex[len]=lin[x]; lin[x]=len;}inline void dfs(int x){ vis[x]=1;sz[x]=1;ll sum=1; for(int i=lin[x];i;i=nex[i]) { int tn=ver[i]; if(vis[tn])continue; dfs(tn);sum=sum*f[tn]%mod; ++sz[x]; } //f[x]=fac[sz[x]]; if(x!=1)f[x]=fac[sz[x]]; else f[x]=fac[sz[x]-1]; f[x]=f[x]*sum%mod;}int main(){ //freopen("1.in","r",stdin); n=read();fac[0]=1; for(int i=1;i

View Code

剩下的题目就不说了。。不太会写也没有时间了。

转载于:https://www.cnblogs.com/chdy/p/10993226.html

你可能感兴趣的文章