CF 640(div4)

链接：https://codeforces.com/contest/1352

A:拆分总数为不为0的位的数量，然后输出每一个不为0的数乘以它的权重即可。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 int t,a[10];
 6 char c[10];
 7 int main(void)
 8 {
 9     cin>>t;
10     while(t--)
11     {
12         cin>>c;
13         int l=strlen(c);
14         int cnt=0;
15         for(int i=0;i<l;i++)
16         {
17             if(c[i]!='0')
18             {
19                 cnt++;
20                 a[cnt]=(c[i]-'0');
21                 for(int j=1;j<=l-i-1;j++)a[cnt]*=10;
22             }
23         }
24         cout<<cnt<<endl;
25         for(int i=1;i<=cnt;i++)cout<<a[i]<<" ";
26         cout<<endl;
27     }
28     return 0;
29 }

B:要求拆分成的k个数全为奇数或者偶数，那么我们直接假定k-1个数为1，判断剩下的数是否大于0且也为奇数；或者假定k-1个数为2，判断剩下的数大于0 且为偶数即可。

代码：

 1 #include <iostream>
 2 using namespace std;
 3 int t,n,k;
 4 int main(void)
 5 {
 6     cin>>t;
 7     while(t--)
 8     {
 9         cin>>n>>k;
10         int ans;
11         ans=n-(k-1);
12         if(ans>0&&ans%2==1)
13         {
14             cout<<"YES"<<endl;
15             for(int i=1;i<=k-1;i++)cout<<"1 "<<endl;
16             cout<<ans<<endl;
17             continue;
18         }
19         ans=n-2*(k-1);
20         if(ans>0&&ans%2==0)
21         {
22             cout<<"YES
";
23             for(int i=1;i<=k-1;i++)cout<<"2 ";
24             cout<<ans<<endl;
25             continue;
26         }
27         cout<<"NO"<<endl;
28     }
29     return 0;
30 }

C:n>k时直接输出k就行；否则每n个数就会跳过一个数，可以算出有多少组，加上剩下的数就是答案。注意处理下细节。

代码：

 1 #include <iostream>
 2 using namespace std;
 3 long long t,n,k;
 4 int main(void)
 5 {
 6     cin>>t;
 7     while(t--)
 8     {
 9         cin>>n>>k;
10         if(n>k)
11         {
12             cout<<k<<endl;
13             continue;
14         }
15         if(n==k)
16         {
17             cout<<k+1<<endl;
18             continue;
19         }
20         long long ans=k/(n-1)*n+k%(n-1);
21         if(k%(n-1)==0)ans--;
22         cout<<ans<<endl;
23     }
24     return 0;
25 }

D:左头记为head,右头记为rear,对数组双向处理，每次更新吃掉的最大值，一直到head超过rear。

代码：

 1 #include <iostream>
 2 using namespace std;
 3 int t,n,s[1100],a,b,num,head,rear,cur;
 4 void solve(void)
 5 {
 6     int tem=0;
 7     while(tem+s[head]<=cur&&head<=rear)
 8     {
 9         tem+=s[head];
10         a+=s[head++];
11     }
12     num++;
13     if(head>rear)return;
14     cur=tem+s[head];
15     a+=s[head++];
16     if(head>rear)return;
17     tem=0;
18     while(tem+s[rear]<=cur&&head<=rear)
19     {
20         tem+=s[rear];
21         b+=s[rear--];
22     }
23     num++;
24     if(head>rear)return;
25     cur=tem+s[rear];
26     b+=s[rear--];
27 }
28 int main(void)
29 {
30     cin>>t;
31     while(t--)
32     {
33         cin>>n;
34         for(int i=1;i<=n;i++)cin>>s[i];
35         cur=0,a=0,b=0,num=0,head=0,rear=n;
36         while(head<=rear)solve();
37         cout<<num<<" "<<a<<" "<<b<<endl;
38     }
39     return 0;
40 }

E:本来以为O(n²)要超时的，但意外的没有。。利用前缀和求出任意两个位置之间所有数的和，每次判断得到的和是否在所给数中出现过，有则给答案加上。注意细节，当和超过n的时候直接跳过。

代码：

#include <iostream>
using namespace std;
int t,n,f[10000];
int main(void)
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        int a[10000]={0};
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            a[x]++;
            f[i]=f[i-1]+x;
        }
        int ans=0;
        for(int i=1;i<n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                int p=f[j]-f[i-1];
                if(p>n)continue;
                if(a[p]>0)
                {
                    ans+=a[p];
                    a[p]=0;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

F:直接依次处理n0、n1、n2，注意一些坑点即可。

代码：

 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 int t,n0,n1,n2;
 5 int main(void)
 6 {
 7     cin>>t;
 8     while(t--)
 9     {
10         int k;
11         cin>>n0>>n1>>n2;
12         k=n1;
13         string s;
14         if(n0>0)s+="0";
15         for(int i=1;i<=n0;i++)s+="0";
16         if(n1>0){
17                 if(n0==0)s+="0";
18         if(n1%2==0)
19         {
20             s="1"+s;
21             n1--;
22         }
23         s+="1";
24         n1--;
25         for(int i=1;2*i<=n1;i++)s+="01";
26         }
27         if(n2>0){
28         if(k==0)s+="1";
29         for(int i=1;i<=n2;i++)s+="1";
30         }
31         cout<<s<<endl;
32     }
33     return 0;
34 }

G:先将所有奇数排成下降序列，加上4、2，最后将剩下的偶数排成上升序列。

代码：

 1 #include <iostream>
 2 using namespace std;
 3 int t,n;
 4 int main(void)
 5 {
 6     cin>>t;
 7     while(t--)
 8     {
 9         cin>>n;
10         if(n<4)
11         {
12             cout<<"-1"<<endl;
13             continue;
14         }
15         int k=n-1;
16         if(n%2==1)
17         {
18             k++;n--;
19         }
20         for(int i=k;i>=1;i-=2)
21         {
22             cout<<i<<" ";
23         }
24         cout<<"4 2 ";
25         for(int i=6;i<=n;i+=2)
26         {
27             cout<<i<<" ";
28         }
29         cout<<endl;
30     }
31     return 0;
32 }