ABBYY Cup 3.0 - Finals (online version)

A 开个数组记录一下

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<vector>

 #include<queue>

 #include<cmath>

 #include<map>

 using namespace std;

 #define LL long long

 #define INF 1e10

 #define N 300010

 LL sum[N];

 int a[N];

 int pa[N];

 map<int,int>f;

 int main()

 {

     int n,i,g=,x;

     cin>>n;

     for(i = ; i <= n ;i++)

     {

         cin>>a[i];

         if(a[i]>)

         sum[i] = sum[i-]+a[i];

         else

         sum[i] = sum[i-];

         f[a[i]] = i;

     }

     LL maxz=-INF;

     for(i = ; i <= n ;i++)

     {

         if(i==f[a[i]]) continue;

         LL s = sum[f[a[i]]]-sum[i-];

         if(a[i]<) s+=*a[i];

         if(maxz<s)

         {

             x = i;

             maxz = s;

         }

     }

     for(i =  ; i < x ;i++)

     pa[++g] = i;

     for(i = f[a[x]]+ ; i <= n ;i++)

     pa[++g] = i;

     for(i = x+ ; i < f[a[x]] ; i++)

     if(a[i]<)

     {

         g++;

         pa[g] = i;

     }

     cout<<maxz<<" "<<g<<endl;

     sort(pa+,pa+g+);

     for(i = ; i < g ; i++)

     cout<<pa[i]<<" ";

     if(g)

     cout<<pa[g]<<endl;

     return ;

 }

B 线段树连续的数中较大的数的位置如果比较小的小得话就+1 求和询问下就行
把L写成了1 悲剧了。。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<vector>

 #include<queue>

 #include<cmath>

 #include<map>

 using namespace std;

 #define LL long long

 #define INF 1e10

 #define N 300010

 int a[N],po[N];

 int s[N<<];

 void up(int w)

 {

     s[w] = s[w<<]+s[w<<|];

 }

 void build(int l,int r,int w)

 {

     if(l==r)

     {

         if(po[l]>po[l+])

         s[w] = ;

         else s[w] = ;

         return ;

     }

     int m = (l+r)>>;

     build(l,m,w<<);

     build(m+,r,w<<|);

     up(w);

 }

 int query(int a,int b,int l,int r,int w)

 {

     if(a<=l&&b>=r)

     {

         return s[w];

     }

     int m = (l+r)>>;

     int ans = ;

     if(a<=m)

     ans+=query(a,b,l,m,w<<);

     if(b>m)

     ans+=query(a,b,m+,r,w<<|);

     return ans;

 }

 void update(int p,int l,int r,int w)

 {

     if(l==r)

     {

         if(po[l+]<po[l])

         s[w] = ;

         else s[w] = ;

         return ;

     }

     int m = (l+r)>>;

     if(p<=m)

     update(p,l,m,w<<);

     else

     update(p,m+,r,w<<|);

     up(w);

 }

 int main()

 {

     int i,q,k,n;

     cin>>n;

     for(i =  ;i <= n ;i++)

     {

         cin>>a[i];

         po[a[i]] = i;

     }

     build(,n-,);

     cin>>q;

     while(q--)

     {

         cin>>k;

         int x,y;

         if(k==)

         {

             cin>>x>>y;

             cout<<query(x,y-,,n-,)+<<endl;

         }

         else

         {

             cin>>x>>y;

             po[a[x]] = y;

             po[a[y]] = x;

             swap(a[x],a[y]);

             if(a[x]<n)

             update(a[x],,n-,);

             int k = a[x]-;

             if(k>&&k<n)

             update(k,,n-,);

             if(a[y]<n)

             update(a[y],,n-,);

             k = a[y]-;

             if(k>&&k<n)

             update(k,,n-,);

         }

     }

     return ;

 }

C1 拿背包做的因为不知道每次都应该减最大的
C2 知道了这个结论可以先暴力出10^6 把10^12分为两部分循环前一部分这样复杂度指数级减小一般然后开个二维数组c[i][j] 一维表示前一部分数的最大值然后暴力j

这样每次减到《=0 小于0的部分再下一次循环中减去

注意点减到0的时候需注意要减的值比如3999999 第一次减到3000000的话下次不能直接循环c[2][1000000] 而是可以减一次3

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<cmath>

 #include<vector>

 #include<queue>

 using namespace std;

 #define LL long long

 #define N 1000000

 #define INF 0xfffffff

 int dp[][N+];

 int o[][N+];

 int main()

 {

     int i,j;

     LL n;

     for(i =  ;i <=  ; i++)

     {

        dp[i][] = ;

     }

     for(i = ; i <= ;  i++)

     for(j = ; j <= N ;j++)

     {

         int mm = i;

         int k = j;

         while(k)

         {

             int x = k%;

             mm = max(mm,x);

             k/=;

         }

         if(mm>=j)

         {

             dp[i][j] = dp[i][]+;

             o[i][j] = j-mm;

         }

         else

         {

             dp[i][j] = dp[i][j-mm]+;

             o[i][j] = o[i][j-mm];

         }

     }

     while(cin>>n)

     {

         if(n<=N)

         {

             cout<<dp[][n]<<endl;

             continue;

         }

         LL m = n%N,nm = n/N;

         LL s = ;

         int k = ;

         for(i = nm ; i >= ; i--)

         {

             int y = i,ma = ;

             while(y)

             {

                 int x = y%;

                 y/=;

                 ma = max(ma,x);

             }

             if(i!=nm) m = N+k;

             s += dp[ma][m];

             k = o[ma][m];

             if(k==&&i!=)

             {

                 s++;

                 k = -ma;

             }

         }

         cout<<s<<endl;

     }

     return ;

 }

巴特西

ABBYY Cup 3.0 - Finals (online version)

最新文章

热门文章