首先造出所要求的得到的環(huán)。如果將位置一一對應上，答案就是不在所要求位置的人數(shù)。因為顯然這是個下界，并且腦補一下能構(gòu)造出方案達到這個下界。

　　剩下的問題是找到一種對應方案使錯位數(shù)最少。可以暴力旋轉(zhuǎn)這個環(huán)，然而是n²的。誒是不是特別熟悉……這好像很像卷積？然而好像沒有什么優(yōu)美的函數(shù)能方便的計算出兩個排列的不匹配數(shù)，所以就別想NTT了。（是不是只有我這種弱智會往這上面想啊）

　　應該可以類似暴力的移動開頭利用偏移量之類的來計算，然而容易被繞暈。注意到每個人向右移動到目標位置的最少次數(shù)之間的關(guān)系是不變的，相同的總是相同不同的總是不同，直接統(tǒng)計即可。

　　注意還可以將環(huán)翻轉(zhuǎn)，需要再搞一次。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } #define N 50010 #define P 998244353 int n,a[N],b[N],q[N],cnt[N<<1],ans=0; bool flag[N]; void solve() {memset(cnt,0,sizeof(cnt));for (int i=1;i<=n;i++) cnt[(q[i]-i+n)%n]++;for (int i=0;i<n;i++) ans=max(ans,cnt[i]); } int main() { #ifndef ONLINE_JUDGEfreopen("1053.in","r",stdin);freopen("1053.out","w",stdout);const char LL[]="%I64d\n"; #elseconst char LL[]="%lld\n"; #endifn=read();for (int i=1;i<=n;i++) a[i]=read(),b[i]=read();int x=a[1],from=1;q[1]=1;flag[1]=1;for (int i=2;i<=n;i++){if (flag[x]) {cout<<-1;return 0;}q[i]=x;flag[x]=1;if (a[x]==from) from=x,x=b[x];else if (b[x]==from) from=x,x=a[x];else {cout<<-1;return 0;}}if (x!=1) {cout<<-1;return 0;}solve();reverse(q+1,q+n+1);solve();cout<<n-ans;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Gloid/p/9800973.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的Luogu1053 NOIP2005篝火晚会的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。