Rui and her functions

發布時間: 2017年3月27日 15:45?? 最后更新: 2017年3月28日 12:43?? 時間限制: 10000ms?? 內存限制: 256M

描述

Rui is magnificently gifted. Why does she not play with me tonight? Oh, she is obsessing

about?n?functions with?n?quartette of positive coefficients, denoted by?ai,bi,ci,di(1≤i≤n)

respectively.

The i-th function fi is defined as?fi(x)=(ai×bxi+ci)moddi. She asked Doc to find the

smallest?xi?in?[1,m]?for each function such that?fi(xi)?achieves the minimum of?fi?in?[1,m].

That is say:?fi(xi)=min{x∈[1,m]|fi(x)=mint∈[1,m]{fi(t)}}.

However n is large and Doc told her that possible?xi?for each function is unique (and Rui

is unique as well), and?x1≤x2≤x3≤?≤xn?(and that is as amazing as Rui).

Now she needs to find?xi?by herself.

輸入

There are several test cases (no more than 64) and please process till EOF.
The first line in each case contains two integers?n?and?m,?1≤n,m≤100000. Each of the
following?n?lines contains four integers?ai,bi,ci,di?respectively, where?0<ai,bi,ci≤di≤109.

輸出

For each test case, print first the identifier of the test case, then n lines follow. The?i-th
line contains the number?xi?for?i-th function?fi.

樣例輸入1?復制 3 5 373911025 1525760443 652804587 1767005941 120055457 159868670 59429374 196292251 1200581 955324 141748 2705431 樣例輸出1 Case #1 1 2 4 總感覺這道題目描述的不好，或者是我一直沒有理解好。這個題目說的是每個f函數，x在[1,m]區間上的取值,f(x)都是不同的

然后讓你求出每個f(x)取得最小值情況下的x，這個題有點特殊，數據保證了x1<=x2<=...<=xn我覺得這個數據不是隨機出的，而是故意滿足了這個條件。

由于x的單調性，我們可以這樣考慮，如果我們先求出了下標n/2對應的函數對應的x,那么對于所有下標小于n/2的f函數，就只需要考慮[1,x[n/2]]之內的數就可以了，因為這些函數

的最小值對應的x不可能大于x[n/2]了，這樣的話，再判斷左右兩邊的f函數對應的x時，要檢索的范圍就縮小了一半。

因此，上來就用二分

void solve(int lp,int rp,int l,int r)//左閉右開 表示的是要求區間[lp,rp)內的函數對應的最小值，這些最小值的取值再[l,r)里面

那么我們先求pos = (lp+rp)/2位置的函數，假設求得了x的下標為under

那么下一次分治的時候，

左邊的區間變成了[lp,pos) 定義域變成了[l,under+1)因為x之間可以相等

右邊的函數下標區間變成了[pos+1,rp),定義域變成了[under,r)

注意！！！！！

快速冪不能一直使用，否則會TTTTTTT，555555555我在這地方T了20次！！！歸根到底還是菜啊

解決方案是，在定義域內檢索最小值的時候，先用快速冪求出第一項，然后遞歸得到以后的

#include <iostream> #include <algorithm> #include <cstdio> using namespace std; typedef long long LL; const int MAX = 100009; const LL INF = 1e18; LL a[MAX],b[MAX],c[MAX],d[MAX],ans[MAX]; int n,m; LL mod_pow(LL x,LL n,LL mod) {LL res = 1;while(n > 0){if(n&1) res = res*x%mod;x = x*x%mod;n >>= 1;}return res; } /* LL calc(int x,int i) {LL mod = d[i];return ((a[i]%mod*mod_pow(b[i],x,mod))%mod + c[i]%mod) % mod; } */ void solve(int lp,int rp,int l,int r)//左閉右開 {//返回中間位置if(lp >= rp) return ;int pos = (lp + rp) / 2;LL sm = INF;int under;int lb = l;int up = r;LL tmp = mod_pow(b[pos],lb,d[pos]);for(int i = lb;i < up;i++){if(i != lb) tmp = tmp*b[pos]%d[pos];LL cc = ((a[pos]%d[pos]*tmp)%d[pos] + c[pos]%d[pos]) % d[pos];if(sm > cc)sm = cc,under = i;}ans[pos] = under;solve(lp,pos,l,under+1);solve(pos+1,rp,under,r); } main() {int cas = 0;while(~scanf("%d%d",&n,&m)){for(int i = 0;i < n;i++)scanf("%lld%lld%lld%lld",a+i,b+i,c+i,d+i);LL sm = INF;printf("Case #%d\n",++cas);solve(0,n,1,m+1);for(int i = 0;i < n;i++) printf("%lld\n",ans[i]);} return 0;} /* 1 1 373911025 1525760443 652804587 1767005941*/

總結

以上是生活随笔為你收集整理的2016陕西省省赛 ACM Rui and her functions B 二分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。