大佬都說這次莫尼塞巨水然而我還是gg
業(yè)火的向日葵(sun.cpp/c/pas)
題目背景 Background
只是有一天，qiancl 看到一道題，發(fā)現(xiàn)不會(:зゝ∠)，后來發(fā)現(xiàn)這道題化簡一下可以拿來出題，題
目名字是亂打的，不要太在意
題目描述 Description
梵高是個有事沒事上廁所也畫向日葵的家伙，某天他到街上賣他的向日葵，得到了 N 枚硬幣，他把
這些硬幣疊成了 M 堆，現(xiàn)在要解決的問題如下：
(I) 每個硬幣都長的一模一樣，但是面值不同
(II) 梵高有強迫癥，他打算把這些硬幣按面值從大到小用完
(III)你可以把任意一堆中位于頂端的硬幣移動到其他某堆的頂端，若你移動的該枚硬幣是當前所有硬
幣中面值最大的，梵高會直接把他用掉
(IV)求出用掉所有硬幣最少需要的步數(shù)，直接用掉不計入步數(shù)
(V) 由于出題人很良心，上面這個問題比較難，這里你只要解決下面這個較簡單的版本：
<u>硬幣面值兩兩不同，且</u> <u>M=2</u>
輸入描述(sun.in) Input Description
第一行兩個正整數(shù) n1,n2，分別表示兩堆硬幣的個數(shù)
接下來 n1 個整數(shù)按從頂?shù)降椎捻樞蚺帕校硎镜谝欢延矌诺拿嬷?/p>
接下來 n2 個整數(shù)按從頂?shù)降椎捻樞蚺帕?，表示第二堆硬幣的面?/p>
輸出描述(sun.out) Output Description
一行一個整數(shù)表示最少步數(shù)
樣例輸入 Sample Input
3 3
1 4 5
2 7 3
樣例輸出 Sample Output
6
數(shù)據(jù)范圍及提示 Data Size & Hint
對于 20%的數(shù)據(jù)，有 1<=n1+n2<=100
對于 40%的數(shù)據(jù)，有 1<=n1+n2<=1000
對于 100%的數(shù)據(jù)，有 1<=n1+n2<=100000
t1 大佬都是把兩個棧合并，第一個棧倒敘，然后用一個指針（初始值為n）把它到當前最大值之間的數(shù)+1（這里要用到樹狀數(shù)組或者線段樹）并把它移動到該位置。（原題 [JLOI2013]刪除物品)
<來自fdd的
非官方題解>T1
“這不是線段樹裸題嗎”
——zhoudong
暴力：乖巧的模擬
時間復雜度：O(在此不予探究)
正解：更乖巧的線段樹||樹狀數(shù)組
具體操作：
把兩個棧連在一起（顯然看出棧頂相連），變成一個區(qū)間，從大到小枚舉，取走的硬幣權值為零，剩下的為一。每次的代價是當前位置到最大值的區(qū)間和（這個用數(shù)據(jù)結構維護），然后累加。
時間復雜度：O(nlogn)T1
“這不是線段樹裸題嗎”
——zhoudong
暴力：乖巧的模擬
時間復雜度：O(在此不予探究)
正解：更乖巧的線段樹||樹狀數(shù)組
具體操作：
把兩個棧連在一起（顯然看出棧頂相連），變成一個區(qū)間，從大到小枚舉，取走的硬幣權值為零，剩下的為一。每次的代價是當前位置到最大值的區(qū)間和（這個用數(shù)據(jù)結構維護），然后累加。
時間復雜度：O(nlogn)
/*#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
queue <int> q1,q2;
int p[200005];
bool a[200005],b[200005];
void insert(queue<int> &q,int x)
{
queue<int> q2;
while(!q.empty())
{
int u=q.front();
q2.push(u);
q.pop();
}
q.push(x);
while(!q2.empty())
{
int u=q2.front();
q.push(u);
q2.pop();
}
}
bool cmp(int a,int b) {return a>b;}
int main()
{
freopen("sun.in","r",stdin);
freopen("sun.out","w",stdout);
int n1,n2,x,ans=0;
scanf("%d%d",&n1,&n2);
for(int i=1;i<=n1;i++)
{
scanf("%d",&x);
p[i]=x;
a[x]=1;
q1.push(x);
}
for(int i=n1;i>=1;i--)
q1.push(p[i]);
for(int i=1;i<=n2;i++)
{
scanf("%d",&x);
p[i+n1]=x;
b[x]=1;
q2.push(x);
}
// for(int i=n1+n2;i>=n1+1;i--)
// q2.push(p[i]);
sort(p+1,p+1+n1+n2,cmp);
// for(int i=1;i<=n1+n2;i++)
// printf("%d ",p[i]);
for(int i=1;i<=n1+n2;i++)
{
// cout<<"aaa";
if(a[p[i]])
{
while(q1.front()!=p[i]&&!q1.empty())
{
int u=q1.front();
a[u]=0;
b[u]=1;
insert(q2,u);
// cout<<1<<"->"<<2<<" "<<u<<endl;
q1.pop();
ans++;
}
q1.pop();
}
else if(b[p[i]])
{
while(q2.front()!=p[i]&&!q2.empty())
{
// cout<<p[i]<<endl;
int u=q2.front();
a[u]=1;
b[u]=0;
insert(q1,u);
// cout<<2<<"->"<<1<<" "<<u<<endl;
q2.pop();
ans++;
}
q2.pop();
}
}
printf("%d",ans);
}*//*以上為考上好不容易想起的stl（并在最后時刻交了上去。。
然而20分爆蛋，還不如我數(shù)組模擬50分。。。
/*
3 3
1 4 5
2 7 3
*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
struct arr
{
int id,num;
}a[200000];
int n1,n2,c[200000];
bool cmp(arr a,arr b){return a.num>b.num;}
void add(int x,int v)
{
for(;x<=n1+n2;x+=x&-x)
{
c[x]+=v;
}
}
int sol(int x)
{
int ans=0;
for(;x;x-=x&-x) ans+=c[x];
return ans;
}
signed main()
{
freopen("sun.in","r",stdin);
freopen("sun.out","w",stdout);
int ans=0;
scanf("%lld%lld",&n1,&n2);
for(int i=1;i<=n1;i++)
{
scanf("%lld",&a[i].num);
a[i].id=n1-i+1;
add(n1-i+1,1);
}
for(int i=n1+1;i<=n1+n2;i++)
{
scanf("%lld",&a[i].num);
a[i].id=i;
add(i,1);
}
sort(a+1,a+1+n1+n2,cmp);
// for(int i=1;i<=n1+n2;i++)cout<<a[i].num<<" ";
int now=n1;
for(int i=1;i<=n1+n2;i++)
{
if(a[i].id>now)
{
ans+=sol(a[i].id-1)-sol(now);
now=a[i].id-1;
}
else
{
ans+=sol(now)-sol(a[i].id);
now=a[i].id;
}
add(a[i].id,-1);
// printf("%lld\n",ans);
}
printf("%lld",ans);
}
紺碧之棺(coffin.cpp/c/pas)
題目背景 Background
qiancl 得到了一張藏寶圖，上面寫了一道謎題
題目描述 Description
定義 F (n)為n在十進制下各個數(shù)位的平方和，求區(qū)間[a, b]中有多少n滿足 k * F(n)= n
輸入描述(coffin.in) Input Description
一行三個正整數(shù) k,a,b
輸出描述(coffin.out) Output Description
一行一個整數(shù)表示滿足條件的 n 的個數(shù)
樣例輸入 Sample Input
51 5000 10000
樣例輸出 Sample Output
3
數(shù)據(jù)范圍及提示 Data Size & Hint
測試數(shù)據(jù)
對應數(shù)據(jù)范圍
其中 12 個測試點
1<=k,a,b<=105
其中 6 個測試點
233<=k<=250,且 1<=a,b<=108
剩下 32 個測試點
1<=k,a,b<=1018
樣例中滿足的 3 個 n 分別是 7293，7854，7905
感覺這題可能是做出來可能性最大的水題了。。。莫尼塞的時候還是要仔細觀察啊
T2
“17行太長了，我能把它壓成兩行”
——gaojun
暴力：枚舉）
時間復雜度：O(慢得沒意義)
正解：枚舉****(WTF???)
具體操作：
經(jīng)過一番復雜的計算發(fā)現(xiàn)最大的f(n)不會超過9918=1458，因此我們枚舉即可
由于代碼長度過于可愛，于是將標程和暴力代碼進行了對比
（左圖：標程；右圖：暴力）
原題是BZOJ4292然而已經(jīng)變成這樣了
時間復雜度：O(nlogn)
還是看代碼吧
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[300000];
int k,l,r;
int check(int x)
{
int xx=x,len=0,sum=0;
while(xx)
{
a[++len]=xx%10;
xx/=10;
}
for(int i=1;i<=len;i++)
sum+=a[i]*a[i];
return sum;
}
signed main()
{
freopen("coffin.in","r",stdin);
freopen("coffin.out","w",stdout);
int ans=0;
scanf("%lld%lld%lld",&k,&l,&r);
int mx=min(r/k,(long long)9*9*18);
//因為f[n]的最大值不可能大于9*（數(shù)字9）9*（平方） 18（18位）
//所以枚舉f[n]是一個很好的選擇
for(int i=mx;i*k>=l;i--)//枚舉f[]n]
{
if(check(i*k)==i)//如果原數(shù)拆開等于f[N]
ans++;
}
cout<<ans;
}//考場上寫的是40多分的比暴力還暴力的暴力。。
通往天國的倒計時(countdown.cpp/c/pas)
題目背景 Background
由于模擬賽的良心，相信大家都已經(jīng)過了 t2，于是放這道 t3 給大家放松一下
題目描述 Description
qiancl 得到了一個長度為 n 的序列 a i ，他用這個序列構出了一個大小為 nn 的矩陣 gij* ，構造方法為： gij=gcd(ai, a j)，比如ai=4,3,6,2，gij=請看下頁
然而 qiancl 丟失了原本的序列 a i ，而且矩陣里的每個數(shù)都被打亂了，請你還原原來的序列 a i
輸入描述(countdown.in) Input Description
第一行一個整數(shù) n，接下來一行 n*n 個數(shù)表示矩陣里的每個數(shù)，隨機排列
輸出描述(countdown.out) Output Description
一行 n 個整數(shù)從小到大排列表示還原出的序列
樣例輸入 Sample Input
4
2 1 2 3 4 3 2 6 1 1 2 2 1 2 3 2
樣例輸出 Sample Output
2 3 4 6
數(shù)據(jù)范圍及提示 Data Size & Hint
對于 20%的數(shù)據(jù)，n<=3
對于另 20%的數(shù)據(jù)，n<=6, gij <=10
對于 100%的數(shù)據(jù)，n<=400,1<= gij <=100w
此題一開始以為只要判奇偶就好了我還白開心了，最后發(fā)現(xiàn)a[i]序列大多是有重復的 然后就gg
正解大概就是排完序后的第一第二大數(shù)可以確定為原序列，然后刪去他們的gcd，然后下一個大的數(shù)，然后。。。
很好奇這些思路是怎么被大佬們一秒想出來的
依舊是<fdd> T3
“T3最水”
——majun
暴力：枚舉
具體操作：
枚舉整個矩陣
時間復雜度：O(賊大)
更優(yōu)秀的暴力：枚舉
具體操作：
枚舉對角線
用命分析得矩陣的對角線就是a數(shù)組
時間復雜度：O(不會算)
正解：瞎蒙冷靜分析認真思考
具體操作:
觀察易得整個矩陣中最大的數(shù)一定是a數(shù)組中的最大數(shù)（自行證明），于是將它存入答案數(shù)組重復n次即可
時間復雜度：O(能過)
/*#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
struct arr
{
int x,num;
}a[2000000];
int b[1000];
bool v[2000005];
int main()
{
freopen("countdown.in","r",stdin);
freopen("countdown.out","w",stdout);
int n,x,ans=0,cnt=0;
scanf("%d",&n);
for(int i=1;i<=n*n;i++)
{
scanf("%d",&x);
if(!v[x]) a[++cnt].x=x,a[cnt].num=1,v[x]=1;
else
{
for(int j=1;j<=cnt;j++)
if(a[j].x==x)
{
a[j].num++;
break;
}
}
}
for(int i=1;i<=cnt;i++)
{
if(a[i].num%2==1)
b[++ans]=a[i].x;
}
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
printf("%d ",b[i]);
}*/
#include <algorithm>
#include <iostream>
#include <cstdio>
//#define int long long
using namespace std;
int p[200000],ans[1000],v[2000000];
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
bool cmp(int a,int b){return a>b;}
signed main()
{
freopen("countdown.in","r",stdin);
freopen("countdown.out","w",stdout);
int n,cnt=0;
scanf("%lld",&n);
for(int i=1;i<=n*n;i++)
scanf("%lld",&p[i]),v[p[i]]++;
sort(p+1,p+1+n*n,cmp);
// for(int i=1;i<=n;i++)
// cout<<v[p[i]]<<endl;
for(int i=1;i<=n*n;i++)
{
if(v[p[i]])
{
// cout<<p[i]<<endl;
v[p[i]]--;
ans[++cnt]=p[i];
for(int j=1;j<=cnt-1;j++)
{
int u=gcd(ans[cnt],ans[j]);
// printf("v[%d]=%d\n",u,v[u]);
v[u]-=2;
}
}
}
for(int i=n;i>=1;i--)
cout<<ans[i]<<" ";//wsm此處printf老爺機會掛。。
}//標程真的短的可憐。。
***
對于大佬們所說的水題蒟蒻表示我也就只能在當天抄完他們的代碼了