牛客练习赛125

A

排序一下找到数字

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
#include<bits/stdc++.h>
using namespace std;
int a[5];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int c;
        for(int i=0;i<=4;i++)

        {
            int x;
            cin>>x;
                        if(i==0)
            {
                c=x;
            }
            a[i]=x;
        }
        sort(a,a+5);
        int sum=0;
        int id=-1;
        for(int i=0;i<=4;i++)
        {
            if(a[i]==c)
            {              
id=i;             
     sum++;           
            }
        }
        if(sum==5)
        {
            cout<<0<<'\n';
        }
        else
        {
            cout<<5-id-1<<'\n';
        }
    }
}

B

欧拉筛一下，然后判断每个素数最多可以减少多少次，奇数一点行

偶数再判一下

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
//每个质数都可以通过减去一些数字来到不是素数
//计算出减去多少次
//显然答案只能是0，1，-1
//写个欧拉筛就可以
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
//欧拉筛函数
const int maxn=1e6+100;
int a[maxn];
bool vis[maxn];
int prime[maxn];
int b[maxn];
void Euler_sieve(int n)
{
    int i,j,k;
    k=0;//保存素数的个数
    for(i=2;i<=n;i++)
    {
        if(vis[i]==0)//i是素数，则存起来
            prime[k++]=i;
        for(j=0;j<k;j++)//进行倍增，用i去乘以i之前(包括i)的素数
        {
            if(i*prime[j]>n)//倍增结果超出范围，退出
                break;
            vis[ i*prime[j] ]=1;//将倍增结果进行标记
            if(i%prime[j]==0)//i是前面某个素数的倍数时，也需要退出
                break;
        }
    }
}
int main()
{
    Euler_sieve(110000);
    int t;
    cin>>t;
    vis[1]=1;
    vis[0]=1;
    while(t--)
    {
        int n;
        cin>>n;
        ll sum=0;
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            a[i]=x;
            sum=0;
            while(!vis[x])
            {
                ans++;
                sum++;
                x--;
            }
            b[i]=sum;
        }
        if(ans&1)
        {
            cout<<0<<'\n';
        }
        else if(ans==0)
        {
            cout<<-1<<'\n';
        }
        else
        {
            bool flag=0;
           for(int i=1;i<=n;i++)
           {
               if(b[i]&1)
               {
                   flag=1;
                   cout<<1<<'\n';
                   break;
               }   
           }
            if(!flag)
            {
                cout<<-1<<'\n';
            }
        }
    }
}

C

结论不难猜，实现也还行

就是枚举位数加每一位数字

注意到

11101

就是1101+1101

就是首位+中间*11+末位

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
#include<bits/stdc++.h>
using namespace std;

using ll = long long;

ll pw[20] = {1};

void solve() {
	ll y; cin >> y;
	int ans = 0;
	for(int a = 1; a <= 9; ++ a) {
		for(int b = 0; b <= 9; ++ b) {
			for(int len = 0; len <= 18; ++ len) {
				ll x = y - b - a * pw[len];
				if(x < 0) continue;
				if(x % 11 == 0) {
					int t = 0;
					while(x > 10) x /= 10, ++ t;
					ans += (len >= t);
				}
				
			}
		}
	}
	cout << ans << '\n';
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	for(int i = 1; i <= 18; ++ i) pw[i] = pw[i - 1] * 10; 
	
	int T;
	cin >> T;
	
	while(T --) {
		solve();
	}
	return 0;
}

D

离散化+dp

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
#include<bits/stdc++.h>
using namespace std;
 
#define endl '\n'
typedef long long LL;
 
void solve(){  
    int n,m;
    cin >> n >> m;
    vector<vector<LL>> a(n + 1,vector<LL>(m + 1));
    vector<vector<LL>> c(n + 1,vector<LL>(m + 1));
    map<int,vector<pair<int,int>>> mp;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            cin >> a[i][j];
            mp[a[i][j]].push_back({i,j});
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            cin >> c[i][j];
        }
    }
    LL res = 0;
    auto work = [&](vector<pair<int,int>> &a)->void{
        LL cnt = 0;
        vector<int> v;
        for(auto it : a)
        {
            v.push_back(it.first);
            v.push_back(it.second);
        }
        sort(v.begin(),v.end());
        auto find = [&](int x)->int
        {
            return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
        };
        int sz = v.size();
        vector<vector<int>> w(sz + 1,vector<int>(sz + 1));
        vector<vector<LL>> dp(sz + 1,vector<LL>(sz + 1)); 
        for(auto &it : a)
        {
            w[find(it.first)][find(it.second)] = c[it.first][it.second];
        }
        for(int i = 1;i <= sz;i++)
        {
            for(int j = 1;j <= sz;j++)
            {
                dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]) + w[i][j];
            }
        }
        res = max(res,dp[sz][sz]);
    };
    for(auto it : mp)
    {
        work(it.second);
    }
    cout << res << endl;
} 
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
 
    return 0;
}