pta甲级1005-1009+cf每日水题

1005：

简单模拟，数组打表

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define int long long
 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 5 const int N=110;
 6 int a[N];
 7 string s;
 8 int b[N];
 9 int sum;
10 string ch[N]={
11     {"zero"},
12     {"one"},
13     {"two"},
14     {"three"},
15     {"four"},
16     {"five"},
17     {"six"},
18     {"seven"},
19     {"eight"},
20     {"nine"}
21 };
22 int cnt;
23 signed main()
24 {
25     IOS;
26     getline(cin,s);
27     int num=s.length();
28     for(int i=0;i<s.length();i++)
29     {
30         a[i]=(s[i]-'0');
31         sum+=a[i];
32     }
33     if(!sum)
34     {
35         cout<<ch[0];
36         return 0;
37     }
38     else
39     {
40         while(sum>0)
41         {
42             b[cnt++]=sum%10;
43             sum=sum/10;
44         }
45         for(int i=cnt-1;i>=0;i--)
46         {
47             cout<<ch[b[i]];
48             if(i>0)
49             cout<<" ";
50         }
51     }
52     return 0;
53 }

1006

模拟+自定义字符排序

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=20;
 4 struct node{
 5     char s1[100];
 6     char s2[100];
 7     char s3[100];
 8 }p[N];
 9 bool cmp1(node a,node b)
10 { 
11     if( strcmp(a.s2,b.s2)>0) return false;
12     else return true;
13 }
14 bool cmp2(node a,node b)
15 {
16     if( strcmp(a.s3,b.s3)>0) return false;
17     else return true;
18 }
19 int main()
20 {
21     int n;
22     cin>>n;
23      for(int i=0;i<n;i++)
24      {
25          cin>>p[i].s1>>p[i].s2>>p[i].s3;
26      }
27      sort(p,p+n,cmp1);
28      cout<<p[0].s1<<" ";
29      sort(p,p+n,cmp2);
30      cout<<p[n-1].s1; 
31      return 0; 
32 }

1007

最大子序列求和，dp做法

转移方程是dp[i]=max(dp[i-1]+a[i]，dp[i])

并利用pre记录以i结尾的起始前驱

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define int long long 
 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 5 const int N=1e4+10;
 6 int dp[N];
 7 int pre[N]={0,1};
 8 int sum=-1;
 9 int id=-1;
10 int a[N];
11 int n;
12 signed main()
13 {
14     IOS;
15     cin>>n;
16     for(int i=1;i<=n;i++)
17     {
18         cin>>a[i];
19     }
20     dp[1]=a[1];
21     for(int i=2;i<=n;i++)
22     {
23         if(dp[i-1]+a[i]>a[i])
24         {
25             dp[i]=dp[i-1]+a[i];
26             pre[i]=pre[i-1];
27         }
28         else
29         {
30             dp[i]=a[i];
31             pre[i]=i;
32         }
33     }
34 /*    sum=*max_element(dp+1,dp+1+n);
35     for(int i=1;i<=n;i++)
36     {
37         if(dp[i]==sum)
38         {
39             id=i;
40             break;
41         }
42     }*/
43     for(int i=1;i<=n;i++)
44     {
45         if(sum<dp[i])
46         {
47             sum=dp[i];
48             id=i;
49         }
50     }
51     if(id<0)
52     cout<<0<<" "<<a[1]<<" "<<a[n];
53     else
54     cout<<sum<<" "<<a[pre[id]]<<" "<<a[id];
55     return 0;
56 }

1008

模拟

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define int long long
 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 5 const int N=1e2+10;
 6 int n;
 7 int sum;
 8 int a[N];
 9 signed main()
10 {
11     IOS;
12     cin>>n;
13        for(int i=1;i<=n;i++)
14        {
15            cin>>a[i];
16        }
17        sum=a[1]*6+5;
18        for(int i=2;i<=n;i++)
19        {
20            if(a[i]>a[i-1])
21            {
22                sum+=(a[i]-a[i-1])*6+5;
23            }
24            else
25            {
26                sum+=abs(a[i]-a[i-1])*4+5;
27            }
28        }
29        cout<<sum;
30     return 0;
31 }

1009：

Polynomials系列乘法，模拟

把握对细节的 处理

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int num=1010;
 4 struct node
 5 {
 6     int zhishu;
 7     double xishu;
 8 }poly[num];
 9 double ans[2010];
10 int n,m;
11 int cnt;
12 int main()
13 {
14     scanf("%d",&n);
15     for(int i=0;i<n;i++)
16     {
17         scanf("%d %lf",&poly[i].zhishu,&poly[i].xishu);
18     }
19     scanf("%d",&m);
20     for(int i=0;i<m;i++)
21     {
22         int tip;
23         double tmp;
24         scanf("%d %lf",&tip,&tmp);
25         for(int j=0;j<n;j++)
26         {
27             ans[tip+poly[j].zhishu]+=(tmp*poly[j].xishu);
28         }
29     }
30     for(int i=0;i<=2000;i++)
31     {
32         if(ans[i]!=0.0)
33         cnt++;
34     }
35     printf("%d",cnt);
36     for(int i=2000;i>=0;i--)
37     {
38         if(ans[i]!=0.0)
39         printf(" %d %.1f",i,ans[i]);
40     }
41     return 0;
42 }

cf:https://codeforc.es/contest/1734/problem/A

排完序贪心策略是找中间值使得操作最小，所以说贪心的策略是满足求三根火柴操作的x,x+1,x+2，

也就是隔两个进行扫描

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define int long long
 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 5 const int N=310;
 6 int t;
 7 int n;
 8 int a[N];
 9 int ans;
10 signed main()
11 {
12     IOS;
13     cin>>t;
14     while(t--)
15     {
16         ans=INT_MAX;
17         cin>>n;
18         for(int i=1;i<=n;i++)
19         cin>>a[i];
20         sort(a+1,a+1+n);
21         for(int i=3;i<=n;i++)
22         {
23             ans=min(ans,a[i]-a[i-2]);
24         }
25         cout<<ans<<endl;
26     }
27     return 0;
28 }