題目鏈接：DDDDDD 取個倒數就可以變成乘法了… 二分答案 然后chick的時候 雙指針 卡精度…要用 long double
#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;typedef long double ld;ld a[maxn],b[maxn];double bb[maxn],aa[maxn];const ld esp=1e-8;ll n,m,k;bool ok(ld x){ ll cnt=0,now=m; rep(i,1,n) { while(now) { if(a[i]*b[now]>x) now--; else break; } cnt+=now; } return (n*m-cnt)<k;}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%lld%lld%lld",&n,&m,&k); for(int i = 1; i <= n; ++i){ scanf("%lf",&aa[i]); a[i]=aa[i]; } for(int i = 1; i <= m; ++i) { scanf("%lf",&bb[i]); b[i]=(ld)1.0/bb[i]; } sort(a+1,a+n+1); sort(b+1,b+m+1); ld l=a[1]*b[1],r=a[n]*b[m]; while(r-l>esp) { ld mid=(l+r)/2.0; if(ok(mid)) r=mid; else l=mid; } printf("%.2Lf/n",l); } return 0;}題目鏈接
矩陣快速冪 維護 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;}—-題目鏈接—- 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;}新聞熱點
疑難解答
