中国(北方)大学生程序设计训练赛(第一周)

2019-11-06 06:47:26

字体：大中小

来源：转载

供稿：网友

PRoblem D: 数学题

题目链接：DDDDDD 取个倒数就可以变成乘法了… 二分答案然后chick的时候双指针卡精度…要用 long double

Problem E: Water Problem

题目链接

矩阵快速幂维护 f(x) f(x-1) sin(π*x/2) cos(π*x/2) 转移矩阵 1,1,0,0 1,0,0,0 0,0,0,-1 1,0,1,0

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>using namespace std;typedef long long LL;const int MAXN = 4;const LL MOD = 1e9+7;typedef long long LL;typedef struct{ LL mat[MAXN][MAXN]; void Init() { memset(mat, 0, sizeof(mat)); for(int i=0; i<MAXN; i++) mat[i][i] = 1; }} Matrix;Matrix p = {1,1,0,0, 1,0,0,0, 0,0,0,-1, 1,0,1,0 };Matrix Mul_Matrix(Matrix a, Matrix b){ Matrix c; for(int i=0; i<MAXN; i++) { for(int j=0; j<MAXN; j++) { c.mat[i][j] = 0; for(int k=0; k<MAXN; k++) { c.mat[i][j] += (a.mat[i][k] * b.mat[k][j]+MOD) % MOD; c.mat[i][j] %= MOD; } } } return c;}Matrix quick_Mod_Matrix(LL m){ Matrix ans, b = p; ans.Init(); while(m) { if(m & 1) ans = Mul_Matrix(ans, b); m>>=1; b = Mul_Matrix(b, b); } return ans;}int main(){ int T; LL n, a, b; while(~scanf("%lld%lld%lld",&a,&b,&n)){ if(n == 1) { printf("%lld/n",a); continue; } if(n == 2) { printf("%lld/n",b); continue; } Matrix tmp = quick_Mod_Matrix(n-2); LL ans = b*tmp.mat[0][0] % MOD; ans = (ans + a*tmp.mat[1][0]%MOD+MOD) % MOD; ans = (ans + 1*tmp.mat[2][0]%MOD+MOD) % MOD; printf("%lld/n",ans); }return 0;}

Problem F: 等差区间

—-题目链接—- F. 区间 [L,R] 内的数排序后构成等差数列可分两种情况 1.公差为 0 2.公差不为 0 ⟺ 区间内无相同元素且相邻两项差构成的数列的GCD ×（R−L) = (区间最大值-区间最小值）所以RMQ查询区间最大值最小值以及（各个数的上一个相同数的下标的最大值）以及区间GCD

#include <bits/stdc++.h>#define rep(i,a,n) for (int i=a;i<=n;i++)#define per(i,a,n) for (int i=n;i>=a;i--)#define pb push_back#define mp make_pair#define all(x) (x).begin(),(x).end()#define fi first#define se second#define SZ(x) ((int)(x).size())using namespace std;typedef vector<int> vi;typedef long long ll;typedef pair<int,int> pii;const ll mod=1000000007;const ll inf=(1LL<<60);const double pi=acos(-1);ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}inline void pcas(int ca) {printf("Case %d: ",ca);}const int maxn=1e5+10;int n,q;int a[maxn],dmx[maxn][30],dmi[maxn][25],pre[maxn][25],gcd[maxn][25];int b[maxn],mat[maxn*10];void RMQ_init(){ memset(mat,0,sizeof mat); for(int i = 0; i < n; ++i) dmx[i][0]=dmi[i][0]=a[i]; for(int i = 0; i < n; ++i) { pre[i][0]=mat[a[i]]; mat[a[i]]=i; } for(int j = 1; (1<<j)<=n; ++j) for(int i = 0; i +(1<<j)-1<n; ++i) { dmi[i][j]=min(dmi[i][j-1],dmi[i+(1<<(j-1))][j-1]); dmx[i][j]=max(dmx[i][j-1],dmx[i+(1<<(j-1))][j-1]); pre[i][j]=max(pre[i][j-1],pre[i+(1<<(j-1))][j-1]); gcd[i][j]=__gcd(gcd[i][j-1],gcd[i+(1<<(j-1))][j-1]); }}void RMQ(int l,int r,int &mx,int &mi,int &ok,int& gc){ int k=0; while((1<<(k+1))<=r-l+1)k++; mx=max(dmx[l][k],dmx[r-(1<<k)+1][k]); mi=min(dmi[l][k],dmi[r-(1<<k)+1][k]); ok=max(pre[l][k],pre[r-(1<<k)+1][k]); l++; k=0; while((1<<(k+1))<=r-l+1)k++; gc=__gcd(gcd[l][k],gcd[r-(1<<k)+1][k]);}int main(){ while(~scanf("%d%d",&n,&q)){ rep(i,0,n-1) { scanf("%d",&a[i]); if(i) gcd[i][0]=abs(a[i]-a[i-1]); } RMQ_init(); int l,r,mx,mi,sub1,sub2; while(q--) { scanf("%d%d",&l,&r); l--,r--; int ok,temp; RMQ(l,r,mx,mi,ok,temp); if(mx==mi||l==r) { puts("Yes"); } else { if(ok<=l){ if((ll)temp*(r-l)==(ll)(mx-mi)) puts("Yes"); else puts("No"); } else puts("No"); } } } return 0;}

上一篇：crontab 和 notify-send

下一篇：Redis关于对象的储存