大佬都说这次莫尼塞巨水然而我还是gg
业火的向日葵(sun.cpp/c/pas)
题目背景 Background
只是有一天，qiancl 看到一道题，发现不会(:зゝ∠)，后来发现这道题化简一下可以拿来出题，题
目名字是乱打的，不要太在意
题目描述 Description
梵高是个有事没事上厕所也画向日葵的家伙，某天他到街上卖他的向日葵，得到了 N 枚硬币，他把
这些硬币叠成了 M 堆，现在要解决的问题如下：
(I) 每个硬币都长的一模一样，但是面值不同
(II) 梵高有强迫症，他打算把这些硬币按面值从大到小用完
(III)你可以把任意一堆中位于顶端的硬币移动到其他某堆的顶端，若你移动的该枚硬币是当前所有硬
币中面值最大的，梵高会直接把他用掉
(IV)求出用掉所有硬币最少需要的步数，直接用掉不计入步数
(V) 由于出题人很良心，上面这个问题比较难，这里你只要解决下面这个较简单的版本：
<u>硬币面值两两不同，且</u> <u>M=2</u>
输入描述(sun.in) Input Description
第一行两个正整数 n1,n2，分别表示两堆硬币的个数
接下来 n1 个整数按从顶到底的顺序排列，表示第一堆硬币的面值
接下来 n2 个整数按从顶到底的顺序排列，表示第二堆硬币的面值
输出描述(sun.out) Output Description
一行一个整数表示最少步数
样例输入 Sample Input
3 3
1 4 5
2 7 3
样例输出 Sample Output
6
数据范围及提示 Data Size & Hint
对于 20%的数据，有 1<=n1+n2<=100
对于 40%的数据，有 1<=n1+n2<=1000
对于 100%的数据，有 1<=n1+n2<=100000
t1 大佬都是把两个栈合并，第一个栈倒叙，然后用一个指针（初始值为n）把它到当前最大值之间的数+1（这里要用到树状数组或者线段树）并把它移动到该位置。（原题 [JLOI2013]删除物品)
<来自fdd的
非官方题解>T1
“这不是线段树裸题吗”
——zhoudong
暴力：乖巧的模拟
时间复杂度：O(在此不予探究)
正解：更乖巧的线段树||树状数组
具体操作：
把两个栈连在一起（显然看出栈顶相连），变成一个区间，从大到小枚举，取走的硬币权值为零，剩下的为一。每次的代价是当前位置到最大值的区间和（这个用数据结构维护），然后累加。
时间复杂度：O(nlogn)T1
“这不是线段树裸题吗”
——zhoudong
暴力：乖巧的模拟
时间复杂度：O(在此不予探究)
正解：更乖巧的线段树||树状数组
具体操作：
把两个栈连在一起（显然看出栈顶相连），变成一个区间，从大到小枚举，取走的硬币权值为零，剩下的为一。每次的代价是当前位置到最大值的区间和（这个用数据结构维护），然后累加。
时间复杂度：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分爆蛋，还不如我数组模拟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在十进制下各个数位的平方和，求区间[a, b]中有多少n满足 k * F(n)= n
输入描述(coffin.in) Input Description
一行三个正整数 k,a,b
输出描述(coffin.out) Output Description
一行一个整数表示满足条件的 n 的个数
样例输入 Sample Input
51 5000 10000
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
测试数据
对应数据范围
其中 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???)
具体操作：
经过一番复杂的计算发现最大的f(n)不会超过9918=1458，因此我们枚举即可
由于代码长度过于可爱，于是将标程和暴力代码进行了对比
（左图：标程；右图：暴力）
原题是BZOJ4292然而已经变成这样了
时间复杂度：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*（数字9）9*（平方） 18（18位）
//所以枚举f[n]是一个很好的选择
for(int i=mx;i*k>=l;i--)//枚举f[]n]
{
if(check(i*k)==i)//如果原数拆开等于f[N]
ans++;
}
cout<<ans;
}//考场上写的是40多分的比暴力还暴力的暴力。。
通往天国的倒计时(countdown.cpp/c/pas)
题目背景 Background
由于模拟赛的良心，相信大家都已经过了 t2，于是放这道 t3 给大家放松一下
题目描述 Description
qiancl 得到了一个长度为 n 的序列 a i ，他用这个序列构出了一个大小为 nn 的矩阵 gij* ，构造方法为： gij=gcd(ai, a j)，比如ai=4,3,6,2，gij=请看下页
然而 qiancl 丢失了原本的序列 a i ，而且矩阵里的每个数都被打乱了，请你还原原来的序列 a i
输入描述(countdown.in) Input Description
第一行一个整数 n，接下来一行 n*n 个数表示矩阵里的每个数，随机排列
输出描述(countdown.out) Output Description
一行 n 个整数从小到大排列表示还原出的序列
样例输入 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
数据范围及提示 Data Size & Hint
对于 20%的数据，n<=3
对于另 20%的数据，n<=6, gij <=10
对于 100%的数据，n<=400,1<= gij <=100w
此题一开始以为只要判奇偶就好了我还白开心了，最后发现a[i]序列大多是有重复的 然后就gg
正解大概就是排完序后的第一第二大数可以确定为原序列，然后删去他们的gcd，然后下一个大的数，然后。。。
很好奇这些思路是怎么被大佬们一秒想出来的
依旧是<fdd> T3
“T3最水”
——majun
暴力：枚举
具体操作：
枚举整个矩阵
时间复杂度：O(贼大)
更优秀的暴力：枚举
具体操作：
枚举对角线
用命分析得矩阵的对角线就是a数组
时间复杂度：O(不会算)
正解：瞎蒙冷静分析认真思考
具体操作:
观察易得整个矩阵中最大的数一定是a数组中的最大数（自行证明），于是将它存入答案数组重复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老爷机会挂。。
}//标程真的短的可怜。。
***
对于大佬们所说的水题蒟蒻表示我也就只能在当天抄完他们的代码了
网友评论