牛客网埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛

只写了几道水题太菜了https://www.nowcoder.com/acm/contest/91#question

A题模拟我们只要记录每个土堆与b相比是多还是少少的话向相邻的索要相邻的也没有的话继续找下一个多的话同样从左到右遍历一遍就好了

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 #include <iostream>
 6 #include <sstream>
 7 #include <algorithm>
 8 #include <string>
 9 #include <queue>
10 #include <map>
11 #include <vector>
12 #include <set>
13 #include <utility>
14 #include <stack>
15 using namespace std;
16 const int maxn = 2e5+50,inf = 0x3f3f3f3f, mod = 998244353;
17 const double epx = 1e-6;
18 const double PI = acos(-1.0);
19 typedef long long ll;
20 ll a[maxn],b[maxn];
21 int main()
22 {
23     int n,t;
24     scanf("%d",&t);
25     while(t--)
26     {
27         scanf("%d",&n);
28         for(int i=1; i<=n; i++)
29         {
30             scanf("%lld",&a[i]);
31         }
32         ll sum=0,ans=0;
33         for(int i=1; i<=n; i++)
34         {
35             scanf("%lld",&b[i]);
36             ll temp=a[i]-b[i];
37             ans+=abs(sum);
38             sum+=temp;
39         }
40         printf("%lld
",ans);
41     }
42 }

View Code

F题找规律试着推几个数就知道满足条件的话二进制表示中不能有两个1相邻

　　二进制位数二进制

　　　　　　1 1

　　　　　　2 10

　　　　　　3 100 101

　　　　　　4 1000 1001 1010

　　　　　　5 10000 10001 10010 10100 10101

　　　　　　6 100000 100001 100010 100100 100101 101000 101001 101010

　　　　　　f[6]=f[1]+f[2]+f[3]+f[4]+1 f[5]=f[1]+f[3]+f[2]+1 f[n]=f[n-1]+f[n-2]

然后找一下就完了

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 #include <iostream>
 6 #include <sstream>
 7 #include <algorithm>
 8 #include <string>
 9 #include <queue>
10 #include <map>
11 #include <vector>
12 #include <set>
13 #include <utility>
14 #include <stack>
15 using namespace std;
16 const int maxn = 2e5+50,inf = 0x3f3f3f3f, mod = 998244353;
17 const double epx = 1e-6;
18 const double PI = acos(-1.0);
19 typedef long long ll;
20 ll a[maxn],sum[maxn];
21 ll poww(ll n,ll m)
22 {
23     ll ans = 1;
24     while(m > 0)
25     {
26         if(m & 1)ans = (ans * n);
27         m = m >> 1;
28         n = (n * n);
29     }
30     return ans;
31 }
32 int main()
33 {
34     ll n,t;
35     a[1]=a[2]=sum[1]=1;
36     sum[2]=2;
37     for(int i=3;i<=60;i++)
38     {
39         a[i]=a[i-1]+a[i-2];
40         sum[i]=sum[i-1]+a[i];
41     }
42     cin>>t;
43     while(t--)
44     {
45         cin>>n;
46         ll ans=0;
47         for(int i=60;i>=0;i--)
48         {
49             //cout<<sum[i]<<endl;
50             if(n>sum[i])
51             {
52                 ans+=poww(2,i);
53                 n-=sum[i];
54                 n--;
55             }
56         }
57         cout<<ans<<endl;
58     }
59 }

View Code

L 题 dp[i][j]表示前i个数子序列和对k取余为j的子序列长度

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 #include <iostream>
 6 #include <sstream>
 7 #include <algorithm>
 8 #include <string>
 9 #include <queue>
10 #include <map>
11 #include <vector>
12 #include <set>
13 #include <utility>
14 #include <stack>
15 using namespace std;
16 const int maxn = 2e5+50,inf = 0x3f3f3f3f, mod = 998244353;
17 const double epx = 1e-6;
18 const double PI = acos(-1.0);
19 typedef long long ll;
20 int a[maxn];
21 int main()
22 {
23     int n,k;
24     cin>>n>>k;
25     for(int i=0;i<n;i++)
26     {
27         cin>>a[i];
28         a[i]%=k;
29     }
30     int dp[n+10][k+10];
31     memset(dp,0,sizeof(dp));
32     dp[0][a[0]]=1;
33     for(int i=1;i<n;i++)
34     {
35         for(int j=0;j<k;j++)
36         {
37             int temp=(a[i]+j)%k;
38             if(dp[i-1][j]!=0)
39                 dp[i][temp]=max(dp[i-1][j]+1,dp[i][temp]);
40             else
41                 dp[i][temp]=max(dp[i][temp],dp[i-1][temp]);
42         }
43     }
44     cout<<dp[n-1][0]<<endl;
45 }

View Code

牛客网 埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛

牛客网埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛