正題

題目鏈接:https://www.luogu.com.cn/problem/P2354

---

解題思路

以$1～n?m$的數字組成的$n?m$的矩陣，求一條路徑使得路徑上的數排序后字典序最小。

---

解題思路

考慮從小到大依次枚舉來判斷是否可行。

每次判斷一個點是否可以經過然后加入一個必經點。

考慮這個必經點的限制條件，一個$(x,y)$的必經點使得你無法走到任何一個$(a,b)(a>x,b<y)$或者$(a,b)(a<x,b>y)$

因為必經點最多只有$n+m+1$個，所以每行維護一個$minn$和$maxn$來表示該行對$y$的限制即可，然后加入必經點時暴力修改即可。

時間復雜度$:O(nm+(n+m+1)n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #define lowbit(x) (x&-x) #define t(i,j) (a[(i-1)*m+j]) using namespace std; const int N=5100; long long x0,a0,b0,c0,d0; int n,m,q,k,a[N*N],num[N*N],minn[N],maxn[N]; int read() {int x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; } void print(int x){if (x>9) print(x/10); putchar(x%10+48); return; } int main() {freopen("data.out","w",stdout);scanf("%lld%lld%lld%lld%lld",&x0,&a0,&b0,&c0,&d0);scanf("%d%d%d",&n,&m,&q);k=n*m;for(int i=1;i<=k;i++){x0=(a0*x0*x0+b0*x0+c0)%d0;a[i]=i;swap(a[i],a[x0%i+1]);}for(int i=1;i<=q;i++){int u,v;u=read();v=read();swap(a[u],a[v]);}for(int i=1;i<=n;i++)minn[i]=1,maxn[i]=m;for(int i=1;i<=k;i++)num[a[i]]=i;memset(a,0,sizeof(a));int z=0;for(int i=1;i<=k;i++){int x=(num[i]-1)/m+1,y=(num[i]-1)%m+1;if(y>=minn[x]&&y<=maxn[x]){printf("%d ",i);for(int j=x+1;j<=n;j++)minn[j]=max(minn[j],y);for(int j=1;j<x;j++)maxn[j]=min(maxn[j],y);}} }

---

話說

考場上傻逼逼的寫了個$60pts$的二維樹狀數組代碼就丟這了

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #define lowbit(x) (x&-x) #define t(i,j) (a[(i-1)*m+j]) using namespace std; const int N=5100; long long x0,a0,b0,c0,d0; int n,m,q,k,a[N*N],num[N*N]; int read() {int x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; } void print(int x){if (x>9) print(x/10); putchar(x%10+48); return; } void change(int x,int y){for(int i=x;i<=n;i+=lowbit(i))for(int j=y;j<=m;j+=lowbit(j))t(i,j)++;return; } int ask(int x,int y){int ans=0;if(!x||!y)return 0;for(int i=x;i;i-=lowbit(i))for(int j=y;j;j-=lowbit(j))ans+=t(i,j);return ans; } int main() {scanf("%lld%lld%lld%lld%lld",&x0,&a0,&b0,&c0,&d0);scanf("%d%d%d",&n,&m,&q);k=n*m;for(int i=1;i<=k;i++){x0=(a0*x0*x0+b0*x0+c0)%d0;a[i]=i;swap(a[i],a[x0%i+1]);}for(int i=1;i<=q;i++){int u,v;u=read();v=read();swap(a[u],a[v]);}for(int i=1;i<=k;i++)num[a[i]]=i;memset(a,0,sizeof(a));int z=0;for(int i=1;i<=k;i++){int x=(num[i]-1)/m+1,y=(num[i]-1)%m+1;y=m-y+1;if(!ask(x-1,y-1)&&(ask(n,y)+ask(x,m)-ask(x,y)==z)){change(x,y);z++;print(i);putchar(' ');}} }

總結

以上是生活随笔為你收集整理的P2354,jzoj3757-[NOI2014]随机数生成器【贪心,暴力】的全部內容，希望文章能夠幫你解決所遇到的問題。

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