當天晚上，本來想參加一下比賽，結果感覺靜不下心來做題，而且最難受的是讀個題都不明白，一直在理解題意·。·
分析不難發現：
如果
n
n
n是奇數，那麼最後留下的數位一定是奇數位上的數位，如果奇數位上的數位至少存在一個奇數，那麼先手必勝。
如果
n
n
n是偶數，那麼最後留下的數位一定是偶數位上的數位，如果偶數位上的數位至少存在一個湊數，那麼後手必勝。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
cin>>n;
string s;
cin>>s;
s="."+s;
bool ok;
if(n&1)
{
ok=0;
for(int i=1;i<=n;i++)
if(i%2==1&&(s[i]-'0')%2==1) ok=1;
}
else
{
ok=1;
for(int i=1;i<=n;i++)
{
if(i%2==0&&(s[i]-'0')%2==0)
ok=0;
}
}
if(ok) cout<<1<<'\n';
else cout<<2<<'\n';
}
return 0;
}
首先只要知道每個樓梯的邊長，那麼可以用等差數列求出所有小方塊的個數。樓梯的邊長 2 n − 1 2^{n}-1 2n−1，然後只需要一個一個列舉即可。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
ll x;
cin>>x;
ll s=0;
int res=0;
ll a=1;
for(int i=1;;i++)
{
ll now=2*a-1;
s+=1ll*now*(now+1)/2;
if(s<=x) res++;
else break;
a<<=1;
}
cout<<res<<'\n';
}
return 0;
}
這題我也讀了很久才理解題意
不難發現最終答案就三種情況
{
0
,
1
,
2
}
\{0,1,2\}
{0,1,2}
0
0
0：最初所有
a
i
=
x
a_i=x
ai=x
1
1
1：存在
a
i
=
x
a_i=x
ai=x或者
∑
i
=
1
n
a
i
=
n
x
\sum_{i=1}^{n}a_i=nx
∑i=1nai=nx（如果
a
k
=
x
a_k=x
ak=x那麼它一開始就會被感染，一場比賽可以把其餘的
a
i
a_i
ai都變成
x
x
x，
a
k
a_k
ak用來調整保證改變之和為
0
0
0）
2
2
2：其餘情況答案都是2
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1010;
int a[N];
int n,x;
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
cin>>n>>x;
int s=0;
bool ok1=1;
bool ok2=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]!=x) ok1=0;
if(a[i]==x) ok2=1;
s+=a[i];
}
if(ok1) cout<<0<<'\n';
else if(ok2||s==n*x) cout<<1<<'\n';
else cout<<2<<'\n';
}
return 0;
}
分析可知先把原陣列排序，然後把前 ⌊ n 2 ⌋ \lfloor \frac{n}{2}\rfloor ⌊2n⌋的數按順序插到後 ⌈ n 2 ⌉ \lceil \frac{n}{2}\rceil ⌈2n⌉的縫隙中的構造結果肯定最優。然後可以掃一遍統計下答案即可。（如果原陣列的數不同那麼不難發現答案一定是 ⌊ n − 1 2 ⌋ \lfloor \frac{n-1}{2}\rfloor ⌊2n−1⌋）
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
int a[N],b[N],c[N];
int n;
int main()
{
IO;
int T=1;
//cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n/2;i++) b[i]=a[i];
for(int i=n/2+1;i<=n;i++) c[i-n/2]=a[i];
cout<<(n-1)/2<<'\n';
for(int i=1;i<=(n+1)/2;i++)
{
cout<<c[i]<<' ';
if(i<=n/2) cout<<b[i]<<' ';
}
cout<<'\n';
}
return 0;
}
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
int a[N],b[N],c[N];
int n;
int main()
{
IO;
int T=1;
//cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n/2;i++) b[i]=a[i];
for(int i=n/2+1;i<=n;i++) c[i-n/2]=a[i];
for(int i=1,j=1;i<=(n+1)/2;i++)
{
a[j++]=c[i];
if(i<=n/2) a[j++]=b[i];
}
int res=0;
for(int i=2;i<n;i++)
if(a[i]<a[i-1]&&a[i]<a[i+1]) res++;
cout<<res<<'\n';
for(int i=1;i<=n;i++) cout<<a[i]<<' ';
cout<<'\n';
}
return 0;
}
說點兒廢話：2020/9/20下午，在圖書館看了一下這個題，好不容易分析出如何構造能夠得出答案，然後回寢室一直調程式碼調到12點，調程式碼能力還是太菜了，不能把想法快速實現還要多練。現在已經凌晨了2020/9/21，明天早上第一節沒有課，爬起來把題解補了。
考慮將
n
n
n分解質因數，可得
n
=
p
1
a
1
×
p
2
a
2
×
…
×
p
i
a
i
n=p_1^{a_1}×p_2^{a_2}×\dots\ ×p_i^{a_i}
n=p1a1×p2a2×… ×piai
考慮這樣一組排列方式的構造
{
[
p
1
,
p
1
2
,
…
,
p
1
a
1
]
,
[
]
,
[
p
i
,
p
i
2
,
…
,
p
i
a
i
]
}
\{[p_1,p_1^2,\dots, p_1^{a_1}],[],[p_i,p_i^2,\dots, p_i^{a_i}]\}
{[p1,p12,…,p1a1],[],[pi,pi2,…,piai]}不難發現中間
[
]
[]
[]中只要包含
p
1
p_1
p1那麼無論怎麼排列一定不互質（存在相同因子
p
1
p_1
p1），因此中間括號只需要用dfs求出所有包含
p
1
p_1
p1質因子的約數即可（但是我們需要讓
n
n
n放置在最後）。根據dfs的性質，
[
]
[]
[]中的最後一個數一定有質因子
p
i
p_i
pi（當前最後一個質因數），那麼我們下一個排的時候就要排
p
i
p_i
pi因此每次需要和當前最後一個質因數交換一下位置。
根據上述構造可得當且僅當一個數的質因數是2並且質因子的指數都是1（ n = p 1 × p 2 n=p_1×p_2 n=p1×p2）才需要插入一個最小公倍數，否則都不需要插入最小公倍數
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#define p first
#define a second
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N=200010;
pii d[N];
int cnt,n,idx;
ll ans[N];
void divide(int x)
{
idx=cnt=0;
for(int i=2;i<=x/i;i++)
if(x%i==0)
{
d[++cnt].p=i;
d[cnt].a=0;
while(x%i==0) x/=i,d[cnt].a++;
}
if(x>1)
{
d[++cnt].p=x;
d[cnt].a=1;
}
}
void dfs(int u,ll now)
{
for(int i=u;i<=cnt;i++)
{
ll p=1;
for(int j=1;j<=d[i].a;j++)
{
p*=d[i].p;
if(now*p!=n) ans[++idx]=now*p;
dfs(i+1,now*p);
}
}
}
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
cin>>n;
divide(n);
for(int i=1;i<=cnt;i++)
{
ll p=1;
for(int k=1;k<=d[i].a;k++)
{
p*=d[i].p;
if(p!=n) ans[++idx]=p;//注意把n放在最後
}
//括號間的數
p=1;
for(int k=1;k<=d[i].a;k++)
{
p*=d[i].p;
dfs(i+1,p);
}
if(i<cnt) swap(d[i+1],d[cnt]);
}
for(int i=1;i<=idx;i++) cout<<ans[i]<<' ';
cout<<n<<'\n';
if(cnt==2&&d[1].a==1&&d[2].a==1) cout<<1<<'\n';
else cout<<0<<'\n';
}
return 0;
}
要加油哦~