2022西安E,L 济南A，思维练习

西安

E

题意：给定一个函数，请你求出从某个范围内的函数最大值。

思路：打表发现和三进制有关系，然后发现函数的数值就是在三进制意义下位数+各位上的数之和。

所以根据这一特性来模拟写就可以。可能代码会比较难写。

#include
//#pragma-GCC-optimize("-Ofast");
#define int long long
#define ll __int128
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define pause system("pause")
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
const int inf=1e18;
const int up=1e6;
const double pi=acos(-1);
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int a){return qpow(a,mod-2);}
int t,n,f[N];
string get3(int x)
{
    string res="";
    while(x)
    {
        int y=x%3;
        res+=to_string(y);
        x/=3;
    }
    reverse(res.begin(),res.end());
    return res;
}
int cal(string s,int len)
{
    int res=0;
    for(int i=0;i<len;i++)
    {
        res+=(s[i]-'0');
        res++;
    }
    return res;
}
int tran(string s)
{
    int res=0;
    for(int i=0;i<s.size();i++)
    {
        int x=s[i]-'0';
        res=res*3+x;
    }
    return res;
}
signed main()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        int L,R,ans=0,res=0;cin>>L>>R;
        string l=get3(L),r=get3(R);
        ans=cal(r,r.size());
        if(l.size()<r.size())
        {
            string s="";
            for(int i=0;i<r.size();i++)
            {
                string tmp=s;
                if(r[i]=='0'){s+=r[i];continue;}
                if(r[i]=='1')
                {
                    if(i==0)
                    {
                        for(int j=1;j<r.size();j++) tmp+='2';
                        if(tran(tmp)<L) continue;
                        res=cal(tmp,r.size()-1);
                    }
                    else
                    {
                        tmp+='0';
                        for(int j=i+1;j<r.size();j++) tmp+='2';
                        if(tran(tmp)<L) continue;
                        res=cal(tmp,r.size());
                    }
                }
                else if(r[i]=='2')
                {
                    tmp+='1';
                    for(int j=i+1;j<r.size();j++) tmp+='2';
                    if(tran(tmp)<L) continue;
                    res=cal(tmp,r.size());
                }
                //cout<<"s="<=max(ans,res);s+=r[i];
            }
        }
        else
        {
            string s="";
            int flag=0;
            for(int i=0;i<r.size();i++)
            {
                if(l[i]!=r[i]||flag)
                {
                    flag=1;
                    string tmp=s;
                    for(int j=i;j<r.size();j++)
                    {
                        if(r[j]!='0')
                        {
                            if(r[j]=='2') tmp+='1';
                            else tmp+='0';
                            for(int k=j+1;k<r.size();k++)  tmp+='2';
                            break;
                        }
                        tmp+=r[j];
                    }
                    if(tran(tmp)<L) continue;
                    res=cal(tmp,r.size());
                    ans=max(ans,res);
                }
                s+=r[i];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

L. Tree
题意：请你将树划分为尽可能少的链和反链

思路：链和反链是可以互相结合的两种东西，反链承包当前的所有叶子节点，链则是自上向下搞定一条路径。

我们每次使用反链搞定叶子节点时又会生成一些新的叶子节点，根据这个特性，我们想到枚举用的反链的次数和目前裸露的叶子节点个数来获得答案

而所谓的当前裸露的叶子节点个数就是：使用了i次反链，反向深度为i-1的节点的个数。

#include 
using namespace std;
constexpr int N=1e6+5;
struct node
{
    int nex,to;
}edge[N<<1];
int head[N],tot;
void add(int from,int to)
{
    edge[++tot].to=to;
    edge[tot].nex=head[from];
    head[from]=tot;
}
int n,p[N],f[N],buc[N];
void dfs(int now,int fa)
{
      f[now]=1;
      for(int i=head[now];i;i=edge[i].nex)
      {
          int to=edge[i].to;
          if(to==fa)
            continue;
          dfs(to,now);
          f[now]=max(f[now],f[to]+1);
      }
      buc[f[now]]++;
}
void solve()
{
      cin>>n;
      for(int i=1;i<=n;i++)
      {
          head[i]=0;
          buc[i]=0;
      }
      for(int i=1;i<=tot;i++)
        edge[tot].nex=edge[tot].to=0;
      tot=0;
      for(int i=2,a;i<=n;i++)
      {
          cin>>a;
          add(a,i);
          add(i,a);
      }
      dfs(1,0);
      int ans=N;
      for(int i=1;i<=n;i++)
        ans=min(ans,i+buc[i]-1);
      cout<<ans<<"\n";
}
int main()
{
      int T;
      cin >> T;
      while(T--)
        solve();
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

济南A

A. Tower

题意：给定n个塔，每个塔有自己的高度，你从中移除m个塔之后，对于剩下的塔进行无限次操作。
每次操作你可以选择一个塔，对其高度进行
1.除二
2.减一
3.加一

如果你想在确保所有塔高度不为0的情况下，把所有塔的高度变得相同，请你求出最小步数

思路：每个塔变成自己/2的各个状态是所用的步数是固定的，所以我们只需要枚举出所有塔的所有状态进行计数即可，注意删除其中步数前m个最多的。

补题发现真的好遗憾，距离正确答案只差了一点点了，计数函数写的完全没错，就是主函数里没想到是这样去枚举状态的。还有一个周杭州，但求不留遗憾。

#include 

using namespace std;
#define int long long
#define endl '\n'

const int N = 1e5+100;
map<int,int>mp;
int dis[N];
int a[N];
int n,m;
int check(int x)
{
    for(int i=1;i<=n;i++)
        dis[i]=0;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]<x)
            dis[i]=x-a[i];
        else if(a[i]==x)
            dis[i]=0;
        else
        {
            int cnt=0;
            int temp=a[i];
            while(temp)
            {
                if(temp/2<=x)
                {
                    dis[i]=min(cnt+temp-x,cnt+1+x-temp/2);
                    break;
                }
                temp/=2;
                cnt++;
            }
        }
        sum+=dis[i];
    }
    sort(dis+1,dis+n+1);
    for(int i=n;i>=n-m+1;i--)
    {
        sum-=dis[i];
    }
    return sum;
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        mp.clear();
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            int temp=a[i];
            while(temp)
            {
                mp[temp]=1;
                temp/=2;
            }
        }
        int minn=2e9;
        for(auto x:mp)
        {
            minn=min(minn,check(x.first));
        }
        cout<<minn;
        if(t)
            cout<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

Codeforces Global Round 24
B（辗转相减法求GCD）
题意：给定n个数，多次任意两个数相减（保证差为正数）的情况下，求出最终会产生多少个数（原本给定的n个数也包含在内）。

思路：根据辗转相减求GCD的原理，可以知道最终产生的最小值就是n个数的GCD，然后用

#include 

using namespace std;
const int N = 1e5+100;
int a[N];
int main()
{
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        int g;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        g=a[1];
        for(int i=1;i<=n;i++)
        {
            g=std::__gcd(a[i],g);
        }
        cout<<a[n]/g<<endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

C（二分图原理，构造）

需要满足的就是确定两个点权集合，其中一个绝对大于另一个即可（A中任何一个元素大于B中任何一个元素成为A绝对大于B）

分成这样两个集合之后，这两个集合是可以进行完全匹配的。

那么如何获得题目中所谓的完全匹配下边数的最大值呢？显然就是要枚举集合划分的各种情况。由小到大来设置断点即可。

#include 

using namespace std;
#define int long long
#define endl '\n'
const int N = 2e5+100;
int a[N];
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        map<int,int>mp;
        int sum=n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            mp[a[i]]++;
        }
        sort(a+1,a+n+1);
        int ans=0;
        vector<int>v;
        for(auto x:mp)
        {
            v.push_back(x.second);
        }
        int res=0;
        for(auto x:v)
        {
            sum-=x;
            res+=x;
            ans=max(ans,sum*res);
        }
        if(a[1]==a[n])
            cout<<n/2<<endl;
        else
        cout<<ans<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43