AcWing周赛 6

A：水题。

https://www.acwing.com/problem/content/3736/

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N=110;
 6 int w[N];
 7 int main()
 8 {
 9     int n;
10     cin>>n;
11     int sum=0;
12     for(int i=0;i<n;i++) cin>>w[i],sum+=w[i];
13     int res=0;
14     if(sum%2==0){
15         for(int i=0;i<n;i++)
16             if(w[i]%2==0)
17                 res++;
18     }else{
19         for(int i=0;i<n;i++)
20             if(w[i]%2==1)
21                 res++;
22     }
23     cout<<res;
24     return 0;
25 }

B：https://www.acwing.com/problem/content/3737/

f ( i )表示大于等于 i 的且只包含4和7的最小的数，求f(l)+f(l+1)+...+f(r)的值。

首先枚举出全部的可能的数，可以发现1~1e9只会有2+2^2+...+2^10个数，即最多2048个数。

而且最终的答案是可以分区间来计算的，故只会计算2^11次。

考试的时候的代码：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 LL a[12];
 7 LL cal(){//计算数组a对应的值
 8     LL res=0;
 9     for(LL i=10;i>=0;i--){
10         if(a[i]==1)
11             res=res*10+4;
12         else if(a[i]==2)
13             res=res*10+7;
14         else
15             res=res*10;
16     }
17 }
18 int main()
19 {
20     LL l,r;
21     cin>>l>>r;
22     a[0]=1;
23     LL res=0;
24     for(LL i=l;i<=r;){//i表示现在的左端点
25         LL t=cal();
26         if(t>=r) res+=(r-i+1)*t,i=r+1;
27         else if(t>=i) res+=(t-i+1)*t,i=t+1;
28         a[0]++;
29         for(LL j=0;j<=10;j++)//不好用二进制，所以用三进制，用1表示4，2表示7
30             if(a[j]==3)
31             {
32                 a[j]=1;
33                 a[j+1]+=1;
34             }
35     }
36     cout<<res;
37     return 0;
38 }

更简洁的代码（取自yxc）：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 using namespace std;
 6 typedef long long LL;
 7 vector<LL> S;
 8 void dfs(LL u,LL n){
 9     S.push_back(n);
10     if(u==10) return ;
11     dfs(u+1,n*10+4);
12     dfs(u+1,n*10+7);
13 }
14 int main(void){
15     dfs(0,0);
16     sort(S.begin(),S.end());
17     LL l,r;
18     cin>>l>>r;
19     LL res=0;
20     for(int i=1;i<=S.size();i++){
21         LL a=S[i-1]+1,b=S[i];
22         S[i]*max(0LL,min(r,b)-max(l,a));
23         res+=S[i]*max(0LL,min(r,b)-max(l,a)+1);
24     }
25     cout<<res;
26     return 0;
27 }

C：状态压缩DP，太复杂了，不会。

https://www.acwing.com/problem/content/3738/

抄自yxc：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 
 5 #define x first
 6 #define y second
 7 
 8 using namespace std;
 9 
10 typedef pair<int, int> PII;
11 
12 const int N = 22, M = 1 << N;
13 
14 int n, m;
15 int e[N];
16 int f[M];
17 PII g[M];
18 
19 int main()
20 {
21     cin >> n >> m;
22 
23     if (m == n * (n - 1) / 2)
24     {
25         puts("0
");
26         return 0;
27     }
28 
29     for (int i = 0; i < n; i ++ ) e[i] = 1 << i;
30 
31     while (m -- )
32     {
33         int a, b;
34         cin >> a >> b;
35         a --, b -- ;
36         e[a] |= 1 << b;
37         e[b] |= 1 << a;
38     }
39 
40     memset(f, 0x3f, sizeof f);
41     for (int i = 0; i < n; i ++ ) f[e[i]] = 1, g[e[i]] = {0, i};
42     for (int i = 0; i < 1 << n; i ++ )
43     {
44         if (f[i] == 0x3f3f3f3f) continue;
45         for (int j = 0; j < n; j ++ )
46         {
47             if (i >> j & 1)
48             {
49                 int k = i | e[j];
50                 if (f[k] > f[i] + 1)
51                 {
52                     f[k] = f[i] + 1;
53                     g[k] = {i, j};
54                 }
55             }
56         }
57     }
58 
59     int k = (1 << n) - 1;
60     cout << f[k] << endl;
61     while (k)
62     {
63         cout << g[k].y + 1 << ' ';
64         k = g[k].x;
65     }
66     return 0;
67 }