qwq听说是一场普及组难度的比赛，所以我就兴高采烈地过来了qwq
然后发现题目确实不难qwq。。。。。但是因为蒟蒻我太蒻了，考的还是很差啦qwq
orz那些AK的dalao们qwq
赛后闲来无事，弄一篇解题报告好了qwq
T1 无序组数
和数学相关的一个题目吧，因为题目的数据范围很小，所以可以先预处理出每个数的约数个数（包括1和它本身）
然后下面自然是(sum[a]*sum[b])减去重复的了qwq
然后重复的话自然是最大公约数的因数个数组合，因为不能重复，那么就是(sum[gcd(a,b)]*(sum[gcd(a,b)]-1)/2).
qwq 代码是参考一位大佬改的，蒟蒻我写的比较麻烦，而且因为比较麻烦所以出了点锅，OI赛制中RE掉了......
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
long long sum[100010];
int n=100010,k;
int main()
{
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j+=i)
sum[j]++;
cin>>k;
while(k--)
{
int a,b;
cin>>a>>b;
int kkk=__gcd(a,b);
printf("%lld
",1LL*(sum[a]*sum[b]-sum[kkk]*(sum[kkk]-1)/2));
}
return 0;
}
T2 路径数量
这题是个递推，然而我打了搜索。。。。啊，我太蒻了qwq，在这里放上Mayfly dalao的递推代码qwq（顺便orz一下）
其中(sum[x][y])表示到节点x,经过y条边的方案数，如果(a[i][j])是真的话，就更新它。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
long long sum[50][50],a[50][50];
int n,k;
int main()
{
sum[1][0]=1;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int q=1;q<=k;q++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j])
sum[j][q]+=sum[i][q-1];
cout<<sum[n][k]<<endl;
return 0;
}
T3 数列下标
或许可以用STL水过？不过我是用单调栈维护的.......就是从右边往左边扫，维护最大值和对应下标qwq
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
int n;
long long a[1000010];
stack<pair<int,long long> >st;
int ans[1000010];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
st.push(make_pair(0,1e10));
for(int i=n;i>=1;i--)
{
while(a[i]>=st.top().second) st.pop();
ans[i]=st.top().first;
st.push(make_pair(i,a[i]));
}
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
cout<<endl;
return 0;
}
T4 星光晚餐
就是只有完全平方数才有奇数个约数个数啊，所以直接((long long)sqrt(x))就好了qwq
T5 括号序列
经过严谨的思(xia)考(cai)，我们可以发现，每多两对匹配不了的括号，ans数量就要+1
所以说。。。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,sum=0,ans=0;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
char cur;
cin>>cur;
if(cur==')')
{
if(sum<=0)
ans++;
else sum--;
}
else
sum++;
}
printf("%d
",(ans+1)/2);
}
T6 假的数学游戏
因为题目中给过了数据点（真神奇！！），所以打表就好啦qwq
至于怎么打表呢，我们要暴力地判断大小，但是因为数据太大了，没办法，只能用取(log)来判断大小。
至于(log_{10}^{x^x}=x*log_{10}^x, log_{10}^{a*b}=log_{10}^a+log_{10}^b)这些的就不多说了，应该大家都知道的qwq