题目链接
莫干山网络赛
D - Find Integer
思路
根据费马大定理(虽然没有证明，但是这个数据是肯定成立的)，n>2的时候无无解，然后就找n=2的时候，发现是勾股数。
然后这里提供一种勾股数的求法
1.a=2n+1的奇数且a>1，若$a^2+b^2=c^2 \&\&a<b<c 则b=2nn+2n,c=2nn+2n+1$
2.a=2n的偶数且a>2，若$a^2+b^2=c^2\&\&a<b<c 则b=nn-1,c=nn+1$
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
int t;
scanf("%d",&t);
while(t--){
ll n,a;
scanf("%lld %lld",&n,&a);
if(n>2)printf("-1 -1\n");
else{
if(n==0)printf("-1 -1\n");
else if(n==1)printf("1 %lld\n",a+1);
else if(n==2){
if(a<3)printf("-1 -1\n");
else if(a&1){
a--;
a/=2;
ll b=2*a*a+2*a;
ll c=2*a*a+2*a+1;
printf("%lld %lld\n",b,c);
}else {
a/=2;
ll b=a*a-1;
ll c=a*a+1;
printf("%lld %lld\n",b,c);
}
}
}
}
}
|
G - Neko’s loop
思路
首先因为k确定，也就是步数确定，那么我们就把这个换分解成gcd(n,k)个环，长度为len=n/gcd(n,k)。
然后考虑选择哪条环就可以了，一共有3种情况。
1.环的总和小于0，就是每次跑完一圈快乐值都会减少，那么我们直接取这个环上长度为min(m,len)最大值，就不需要跑完，也就是长度为m或者len的最大值即可。
2.环的总和大于0，可以跑完m/len圈且剩下的m%len长度的最大值
3.环的总和大于0，可以跑完m/len-1圈且最后获取该环的最大值
这三种情况都需要统计序列长度为x的最大连续子段和，我们使用单调队列来实现。例如当前的环是
1 5 -6 -3 4 扩充两倍 1 5 -6 -3 4 1 5 - 6 -3 4 1 5
求前缀和1 6 0 -3 4 5 10 4 1 5 6 11
然后我们用一个数组来模拟栈，假设长度为3
遍历到1，首先栈中压入{1}
遍历到2发现pre[2]=6比pre[1]=1大，则继续压入栈中{1,2},并且计算一次答案ans=max(ans,pre[i]-pre[st])
遍历到3,发现pre[3]=0，比pre[st]即栈顶小，此时我们把-6压入栈中，其他都出栈{3}
遍历到4，此时判断栈顶元素的位置i-3是否大于我们需要的长度若大于，则出战，否则继续上述的操作
根据单调队列就可以求出序列长度为x的最大连续字段和，复杂度O(n)，然后我们枚举每条链g，
因为g*len=n所以这个复杂度应该就是O(n)
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
int val[N];
int que[N];
ll sum[N];
int gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll solve(int n,int len)
{
ll ans = 0;
int st=1,ed=0;
for(int i=1;i<=n;i++){
while(st<=ed&&i-que[st]>len)st++;
while(st<=ed&&sum[que[ed]]>sum[i])ed--;
if(st<=ed)ans=max(ans,sum[i]-sum[que[st]]);
que[++ed]=i;
}
return ans;
}
int main(){
int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++)
{
ll n,s,m,k;
scanf("%lld %lld %lld %lld",&n,&s,&m,&k);
for(int i=0;i<n;i++)scanf("%d",&val[i]);
int g = gcd(n,k);
int len = n/g;
int can = m/len;
ll ans = 0;
for(int i=0;i<g;i++){
for(int j=1,t=i;j<=2*len;j++,t=(t+k)%n)sum[j]=sum[j-1]+val[t];
if(sum[len]<=0)ans=max(ans,solve(2*len,min(m,1ll*len)));
else
{
ll res0 = 1ll*can*sum[len]+solve(2*len,m%len);
ans=max(ans,res0);
if(can!=0)
{
ll res1 = (can-1)*sum[len]+solve(2*len,len);
ans=max(ans,res1);
}
}
}
printf("Case #%d: %lld\n",cas,max(0ll,s-ans));
}
}
|
E - GuGu Convolution
思路
读完题目之后就会发现我们要求的是
如何求$b_n$?
考虑使用递推式
然后使用矩阵[A,1][B,A]就可以求出$b_n$了
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
int A,B;
int mod;
struct martix{
int a[2][2];
friend martix operator * (const martix a,const martix b){
martix ret;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++){
ret.a[i][j]=0;
}
ll x;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
ret.a[i][j]=(ret.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%mod;
return ret;
}
}ma;
martix quick_pow(martix x,ll k){
martix res;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++){
res.a[i][j]=i==j;
}
while(k){
if(k&1)res=res*x;
x=x*x;
k>>=1;
}
return res;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
ll n;
scanf("%d %d %lld %d",&A,&B,&n,&mod);
martix unit;
ll Bnum=B,C=1,w=1;
unit.a[0][0]=A;unit.a[0][1]=1;
unit.a[1][0]=B;unit.a[1][1]=A;
for(int i=2;1ll*i*i<=Bnum;i++){
int num = 0;
if(B%i!=0)continue;
while(B%i==0)B/=i,num++;
for(int j=0;j<num/2;j++)C*=i;
if(num&1)w*=i;
}
if(B>1)w*=B;
unit=quick_pow(unit,n);
printf("1 %d %d\n",(1ll*unit.a[0][1]*C+mod)%mod,w);
}
}
|