2019FJUT第一场周赛 题解

题解"/>

2019FJUT第一场周赛 题解

A
先用全排列打了个表

可以发现有三个小数部分是0.66667，也就是2/3，这样子看不出来什么，我们把后者乘个3，都变成正整数看看

数感好的可以直接看出来 ans=n*n-1,那么答案也就是ans/3.0

数感差的(本人） 只能看出来是个递推式 ans[i]=ans[i-1]+2*i-1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
double a[105];
void db()
{a[1]=1;for(int i=2; i<=11; i++){a[i]=i;double sum=0;sum+=abs(a[i]-a[1]);while(next_permutation(a+1,a+1+i)){for(int k=2; k<=i; k++)sum+=abs(a[k]-a[k-1]);}ll ans=1;for(ll k=1; k<=i; k++)ans*=k;cout<<"n="<<i<<"    ans="<<sum/ans<<endl;}
}
int main()
{///db();int t;cin>>t;while(t--){int n;cin>>n;double ans=(n*n-1)/3.0;printf("%.7f\n",ans);}return 0;
}

B
ans= a^ b
如我们求ans的长度时候如果是k进制，直接logk(ans)+1
比如ans=8 我们要求2进制下的长度就是 log2(8)+1=4 8的二进制值为1000 显然正确
但是我们知道在c/c++中log的底只有2 ，e，10，所以这里用一下换底公式即可
ans=logk(ans)=b * logk(a)=b * ( log(a) / log(k) )
故答案即为ans+1

///8 2 2 -> 7
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{ll t;cin>>t;while(t--){double a,b,k;cin>>a>>b>>k;double sum=log(a)/log(k);cout<<(ll)(sum*b+1)<<endl;}return 0;
}

C
看到递推式以及范围，矩阵快速幂无疑了，
并且是一个模板题
如果n<10 直接输出n%k
n>=10 跑矩阵快速幂即可
简单构造一下矩阵
初始状态是
【f9 f8 f7 f6 f5 f4 f3 f2 f1 f0】
构造的矩阵为

a0   1     0     0    0    0     0    0   0    0
a1   0     1     0    0    0     0    0   0    0
a2   0     0     1    0    0     0    0   0    0
a3   0     0     0    1    0     0    0   0    0
a4   0     0     0    0    1     0    0   0    0
a5   0     0     0    0    0     1    0   0    0
a6   0     0     0    0    0     0    1   0    0
a7   0     0     0    0    0     0    0   1    0
a8   0     0     0    0    0     0    0   0    1
a9   0     0     0    0    0     0    0   0    0

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a) memset(a,0,sizeof a)
ll mod,n;
struct node
{ll a[15][15];
}qq;
node jz(node a,node b)
{node now;me(now.a);for(int i=0;i<10;i++){for(int j=0;j<10;j++){ll x=0;for(int k=0;k<10;k++){x+=a.a[i][k]*b.a[k][j]%mod;}now.a[i][j]=x%mod;}}return now;
}
void qsm(ll n)
{node hsy;for(int i=0;i<10;i++)hsy.a[0][i]=(9-i)%mod;for(int i=1;i<10;i++)qq.a[i-1][i]=1;while(n){if(n&1) hsy=jz(hsy,qq);qq=jz(qq,qq);n/=2;}cout<<hsy.a[0][0]%mod<<endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);while(cin>>n>>mod){me(qq.a);for(int i=0;i<10;i++)cin>>qq.a[i][0];if(n<10)cout<<n%mod<<endl;elseqsm(n-9);}return 0;
}

D
找出第一个比给定的数大的下标，直接暴力肯定T，因此直接线段树维护区间最大值即可。
当查询的k大于整个序列的最大值时候，直接输出no response

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
struct node
{ll l,r,maxn;
} t[4*100005];
int f=0;
void build(ll s,ll l,ll r)
{t[s].l=l;t[s].r=r;if(l==r){scanf("%lld",&t[s].maxn);///cout<<l<<" "<<r<<" "<<f<<endl;///f++;return ;}ll mid=(l+r)>>1;build(s*2,l,mid);build(s*2+1,mid+1,r);t[s].maxn=max(t[s*2].maxn,t[s*2+1].maxn);}
ll query(ll s,ll k)
{if(t[s].l==t[s].r)return t[s].l;ll mid=t[s].l+t[s].r>>1;if(k>t[s*2].maxn)return query(s*2+1,k);elsereturn query(s*2,k);
}
void updata(ll s,ll x,ll y)
{if(t[s].l==t[s].r && t[s].l==x){t[s].maxn+=y;return ;}ll mid=t[s].l+t[s].r>>1;if(x<=mid)updata(s*2,x,y);elseupdata(s*2+1,x,y);t[s].maxn=max(t[s*2].maxn,t[s*2+1].maxn);
}
int main()
{cin>>n>>m;build(1,1,n);///cout<<f<<666<<endl;while(m--){ll op;scanf("%lld",&op);if(op==1){ll k;scanf("%lld",&k);if(k>t[1].maxn)puts("no response");elsecout<<query(1,k)<<endl;}else{ll x,y;scanf("%lld%lld",&x,&y);updata(1,x,y);}}return 0;
}

E
四个for会T，看数据范围不超过1e6，可以用数组标记来优化掉一个for，
三个for枚举前三个数，看是不是有他们的乘积，要注意的是，前面用过的数要删去，不然会重，而且选中的三个数要删去，并且要在循环后补回来，结果炸int。
举个简单的小数据
5
1 1 1 1 1
答案应该是5
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
上面数字指下标

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll v[1000005];
ll a[1000005];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i],v[a[i]]++;}ll num=0;for(int i=1;i<=n;i++){v[a[i]]--;for(int j=i+1;j<=n;j++){v[a[j]]--;for(int k=j+1;k<=n;k++){v[a[k]]--;ll sum=a[i]*a[j]*a[k];if(sum<=1000000 && v[sum]>0)num+=v[sum];/// cout<<i<<" "<<num<<endl;}for(int l=j+1;l<=n;l++)v[a[l]]++;}for(int l=i+1;l<=n;l++)v[a[l]]++;}cout<<num<<endl;return 0;
}