倪文迪陪你学蓝桥杯2021冬休み毎日一题:1.21日(2018省赛A组第9题)

2021年冬休み毎日1題、2017~2019年の省試合本題.本文の内容は倪文迪(華東理工大学コンピュータ学部ソフトウェア192クラス)と羅勇軍先生から提供された.次の毎日の問題は、新しいブログを送ります.毎日ブログのブルーブリッジカップのコラムを見てください.https://blog.csdn.net/weixin_43914593/category_10721247.html
C++、Java、Pythonの3言語のコードを提供します.
文書ディレクトリ

1、題名説明

2、題解

3、Pythonコード

4、C++コード

5、Javaコード

2018省試合A組第9題「倍数問題」、タイトルリンク:http://oj.ecustacm.cn/problem.php?id=1366 https://www.dotcpp.com/oj/problem2277.html
1、テーマの説明
ネギはあなたにn個の数をあげて、このn個の数の中から3個の数を見つけてほしいです.この3つの数の和がKの倍数であり、これと最大となるようにします.データは必ず解があることを保証します.入力:最初の行は2つの正の整数n,Kを含む.2行目のn個の正の整数は、与えられたn個の数を表す.1<=n≪出力|Output|emdw≫:求める和を表す1行の整数を出力します.
2、問題解
まず暴力法から考える.n個の数の中から任意の3個の数を探し出して和を求めて、kの倍数であるかどうかを見て、その中の最大の和は答えです.n個の数から3個の数をとると,n(n−1)(n−2)n(n−1)(n−2)n(n−1)(n−2)種の場合があり,n  テーマはリュックサック(ネット上でリュックサックを使う問題解)に似ているように見えますが、リュックサックは必ずすべてのn n nとk kを同時に遍歴しなければなりません.複雑度はO(n k)O(nk)O(nk)より大きく、タイムアウトします.どうする?「3つの数の和はKの倍数」というテーマの要求に気づいた.3つの数をa,b,cとし,条件を満たすのは,(a+b+c)%k=0(a+b+c)%k=0(a+b+c)%k=0(a+b+c)%k=0,すなわち3つの数の和がkに対して残数を求める結果は0である.  または、 (a%k+b%k+c%k)%k=0(a%k+b%k)%k+c%k)%k=0(a%k+b%k+c%k)%k=0残数はk k k個しかなく,n nはk k kよりずっと大きいため,複雑度エネルギーは大幅に低下する.これは数論題だったのか.  具体的には、 (1)n n個の数をk k kに対して余剰を求め、%k%k%kの結果によってクラスを分け、その余剰数に対応する最大3個の数を記録する.
0
a
b
c
1
.
.
.
2
.
.
.
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
k-1
.
.
.
  https://blog.csdn.net/weixin_44290841/article/details/105788802)%k
3、Pythonコード
次のPythonコードは、上記の説明を完全に繰り返しています.

#http://oj.ecustacm.cn/ User: 08195555
n, k = map(int,input().split())
r = [[0] * 3 for i in range(k)]     #    ，            a、b、c

a = input().split()
#                              
for i in range(len(a)):    
    re = int(a[i]) % k
    if int(a[i]) > r[re][0]:
            r[re][2], r[re][1], r[re][0] = r[re][1], r[re][0], eval(a[i])
    elif int(a[i]) > r[re][1]:
            r[re][2], r[re][1] = r[re][1], eval(a[i])
    elif int(a[i]) > r[re][2]:
            r[re][2] = eval(a[i])
 
Max = 0
#       
for i in range(k):
    for j in range(i, k):
        tmp = (k - i + k - j) % k
        v1 = r[i][0]       #a    
        if i == j:
            v2 = r[i][1]   #  b    a     
            if i == tmp:   #  c    a   
                v3 = r[i][2]
            else:
                v3 = r[tmp][0]
        else:              #  b    a     
            v2 = r[j][0]
            if i == tmp:
                v3 = r[i][1]
            elif j == tmp:
                v3 = r[j][1]
            else:
                v3 = r[tmp][0]
        if v1 + v2 + v3 > Max:
            Max = v1 + v2 + v3
 
print(Max)

4、C++コード
倪文迪の言葉:「主にkから着手して、すべての数を先に並べ替えて、%kの結果によってクラスを分けることができる.それから暴力はその中の2つを列挙して、もう1つは3つの和%kが0の性質によって得られる.スタックの特殊性のため、並べ替えた後、後にスタックに入るのは必ず大きいので、最大である.列挙する時、3つを減らすことなく、少し時間を圧縮することができる.」  の下には倪文迪が提供したコードがあります.彼は同余配列を保存し、上のpythonコードの普通の配列ではなく、スタック配列を使用するテクニックを使用しています.コードと照らしてよく理解してください.

#include
using namespace std;
const int N = 1010;
stack<int> st[N];  //        
int a[100010];
int main(){
     
	int n, k; cin >> n >> k;
	for(int i=1;i<=n;i++)  cin >> a[i];

	sort(a + 1, a + n + 1);         //       ，          
	for(int i = 1 ; i <= n ; i++)   //       ，       
		st[a[i] % k].push(a[i]);

	int res = 0;
	for(int i = 0 ; i < k ; i++){
     
		if(!st[i].size())
            continue;
		for(int j = i ; j < k ; j++){
     
			if(!st[j].size())
                continue;
			int rm = (k - i - j + k) % k, tmp = 0, ans1, ans2, ans3;
			if(rm < j)
                continue;
			if(st[i].size()){
     
				ans1 = st[i].top();
				tmp += ans1;
                st[i].pop();
				if(st[j].size()){
     
					ans2 = st[j].top();
					tmp += ans2;
					st[j].pop();
					if(st[rm].size()){
     
						ans3 = st[rm].top();
						tmp += ans3;
						st[rm].pop();
						res = max(res, tmp);
						st[rm].push(ans3);
					}
					st[j].push(ans2);
				}
				st[i].push(ans1);
			}
		}
	}
	cout << res << endl;
	return 0;
}

5、Javaコード

//http://oj.ecustacm.cn/ User: mingyuemy
import java.io.*;
import java.util.*;
public class Main{
             
    public static void main(String[] args) throws IOException {
     
        StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken();
        int n=(int)st.nval;
        st.nextToken();
        int k=(int)st.nval;
        int[][] a=new int[k][3];
        for(int i=0;i<n;i++) {
     
            st.nextToken();
            int t=(int)st.nval;
            int r=t%k;
            if(t>a[r][0]) {
     
                a[r][2]=a[r][1];
                a[r][1]=a[r][0];
                a[r][0]=t;
            }else if(t>a[r][1]) {
     
                a[r][2]=a[r][1];
                a[r][1]=t;
            }else if(t>a[r][2]) {
     
                a[r][2]=t;
            }
        }
         
        long ans=0;
        for(int x=0;x<k;x++) {
     
            for(int y=0;y<k;y++) {
     
                int z=(k+k-x-y)%k;
                int v1=0,v2=0,v3=0;
                v1=a[x][0];
                if(y==x) {
     
                    v2=a[y][1];
                    if(z==x) {
     
                        v3=a[z][2];
                    }else {
     
                        v3=a[z][0];
                    }
                }else {
     
                    v2=a[y][0];
                    if(z==x) {
     
                        v3=a[z][1];
                    }else if(z==y) {
     
                        v3=a[z][1];
                    }else {
     
                        v3=a[z][0];
                    }
                }
                if(v1+v2+v3>ans) ans=v1+v2+v3;
            }
        }
        System.out.println(ans);         
    } 
}