QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87823#21. GCD-sumSenseAnone5 2ms3804kbC++142.9kb2023-03-14 14:18:582023-03-14 14:18:59

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-14 14:18:59]
  • 评测
  • 测评结果:5
  • 用时:2ms
  • 内存:3804kb
  • [2023-03-14 14:18:58]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
int n;
ll arr[500005];
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
namespace Subtask1{
	int dp[32780][16];
	inline int Calc(int S)
	{
		int Val=0;
		for(int i=1;i<=n;i++) if((S>>(i-1))&1) Val=gcd(Val,arr[i]);
		return Val;
	}
	void Main()
	{
		for(int i=1;i<=n;i++) read(arr[i]);
		for(int i=0;i<(1<<n);i++) for(int j=0;j<=n;j++) dp[i][j]=-1e9;
		dp[0][0]=0;
		for(int S=1;S<(1<<n);S++)
		{
			for(int i=1;i<=n;i++)
			{
				for(int T=S;T;T=(T-1)&S)
				{
					if(dp[S^T][i-1]!=-1e9)
					{
						int res=dp[S^T][i-1]+Calc(T);
						dp[S][i]=max(dp[S][i],res);
					}
				}	
			}
		}
		int U=(1<<n)-1;
		for(int i=1;i<=n;i++) printf("%d\n",dp[U][i]);
		exit(0);
	}
}
namespace SubtaskDaoLi{
	bool vis[2005];
	ll Pre[10005],Suf[10005];
	vector <ll> V;
	void Main()
	{
		ll All=0;
		for(ll i=1;i<=n;i++) read(arr[i]),V.push_back(arr[i]),All=gcd(All,arr[i]);
		printf("%lld\n",All); sort(V.begin(),V.end());
		ll Now=All,pos=0,Oth=0;
		for(ll i=2;i<=n;i++)
		{
			for(ll j=0;j<(ll)V.size();j++) Pre[j]=gcd(Pre[j-1],vis[V[j]]?0:V[j]);
			Suf[V.size()]=0;
			for(ll j=V.size()-1;j>=0;j--) Suf[j]=gcd(Suf[j+1],vis[V[j]]?0:V[j]);
			ll lst=-1;
			for(ll j=V.size()-1;j>V.size()-4&&j>=0;j++)
			{
				ll k=j+1;
				while(k<V.size()&&vis[V[k]]) k++;
				if(gcd(lst==-1?0:Pre[lst],k==V.size()?0:Suf[k])+V[j]+Oth>Now) Now=gcd(Pre[lst],Suf[k])+V[j]+Oth,pos=j;
				if(j!=(ll)V.size()-1&&V[j]!=V[j+1]&&!vis[V[j]]) lst=j;
				j=k-1;
			}
			printf("%lld\n",Now); vis[V[pos]]=true; Oth+=V[pos];
			if(i!=n) V.erase(V.begin()+pos);
		}
	}
} 
int main() {
//	freopen("divide.in","r",stdin);
//	freopen("divide.out","w",stdout);
	read(n);
	if(n<=15) Subtask1::Main(); 
	if(n<=2000) SubtaskDaoLi::Main();
	return 0;
}
/*
瑶草一何碧,春入武陵溪。溪上桃花无数,花上有黄鹂。我欲穿花寻路,直入白云深处,浩气展虹霓。只恐花深里,红露湿人衣。
坐玉石,欹玉枕。拂金徽。谪仙何处,无人伴我白螺杯。我为灵芝仙草,不为朱唇丹脸,长啸亦何为。醉舞下山去,明月逐人归。

不是连续段,连 n^3 都不会了! 
不是连续段,连 n^3 都不会了! 
不是连续段,连 n^3 都不会了! 

猜一个结论:每个划分都最多只有一组元素个数>=2(不考虑相同元素)
有相同元素那就保留在集合里可以拿但是算的时候不算它 
那可就会n^2了啊 

6
2 4 8 10 5 6
1
11
19
25
31
35

6
2 6 6 3 6 5
1
7
13
19
24
28

居然过大样例了??? 
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 3472kb

input:

7
18 30 10 23 1 3 13

output:

1
31
54
72
85
95
98

result:

ok 7 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 3564kb

input:

7
11 12 12 15 30 6 10

output:

1
31
46
58
72
84
96

result:

ok 7 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

7
14 19 17 12 5 24 3

output:

1
25
44
61
75
87
94

result:

ok 7 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

7
13 15 19 21 27 28 30

output:

1
31
59
86
107
126
153

result:

ok 7 lines

Test #5:

score: 0
Accepted
time: 2ms
memory: 3504kb

input:

7
4 8 12 13 13 13 24

output:

1
25
41
54
67
79
87

result:

ok 7 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

7
21 6 17 20 5 22 27

output:

1
28
50
71
91
108
118

result:

ok 7 lines

Test #7:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

7
11 17 16 30 24 21 23

output:

1
31
55
78
99
116
142

result:

ok 7 lines

Test #8:

score: 0
Accepted
time: 1ms
memory: 3504kb

input:

7
13 20 16 4 29 26 5

output:

1
30
56
76
92
105
113

result:

ok 7 lines

Test #9:

score: 0
Accepted
time: 2ms
memory: 3740kb

input:

7
25 17 12 16 13 30 30

output:

1
31
61
86
103
119
143

result:

ok 7 lines

Test #10:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

7
4 8 12 13 13 13 24

output:

1
25
41
54
67
79
87

result:

ok 7 lines

Test #11:

score: 0
Accepted
time: 2ms
memory: 3504kb

input:

7
25 6 29 7 22 14 30

output:

1
31
60
85
107
121
133

result:

ok 7 lines

Test #12:

score: 0
Accepted
time: 2ms
memory: 3564kb

input:

7
21 24 20 30 2 5 21

output:

1
31
55
76
97
117
123

result:

ok 7 lines

Test #13:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

7
21 19 26 1 28 7 27

output:

1
29
56
82
103
122
129

result:

ok 7 lines

Test #14:

score: 0
Accepted
time: 2ms
memory: 3508kb

input:

7
26 11 28 24 30 23 24

output:

1
31
59
85
109
142
166

result:

ok 7 lines

Test #15:

score: 0
Accepted
time: 2ms
memory: 3564kb

input:

7
4 8 12 13 13 13 24

output:

1
25
41
54
67
79
87

result:

ok 7 lines

Subtask #2:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #16:

score: 0
Time Limit Exceeded

input:

15
11 28 29 11 13 18 23 1 5 20 24 20 23 3 2

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #31:

score: 0
Runtime Error

input:

100
268 467 21 173 158 287 36 446 36 340 311 283 58 77 464 119 460 198 405 331 214 331 255 157 418 319 354 289 330 64 11 484 186 129 130 368 370 468 292 180 427 76 87 156 13 379 268 170 3 15 263 52 296 242 7 296 376 148 221 270 218 131 326 198 399 132 270 55 299 444 134 222 278 486 409 72 38 193 359...

output:


result:


Subtask #4:

score: 0
Runtime Error

Test #51:

score: 0
Runtime Error

input:

1270
1 2 6 7 8 9 10 11 13 14 16 18 19 20 22 23 25 26 28 30 31 32 33 37 38 40 42 43 44 45 46 47 48 49 50 52 53 55 56 57 58 59 62 63 64 67 68 69 70 71 72 74 75 77 78 80 85 86 87 88 89 90 92 96 97 98 99 100 101 103 104 105 107 108 109 113 119 122 124 126 128 132 134 135 137 140 143 144 149 150 151 154 ...

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%