題目鏈接：點(diǎn)擊查看

題目大意：交互題猜密碼，設(shè)原密碼為 $x$，猜的密碼為 $y$，如果沒猜到，密碼會自適應(yīng)變成 $z$，滿足 $x\oplus z=y$ ，最多猜 $n$ 次，對于本題而言，所有數(shù)字是在 $k$ 進(jìn)制下進(jìn)行的

題目分析：相對于 $easy$ 版本而言，當(dāng)異或推廣到 $k$ 進(jìn)制時(shí)，就不存在自反性了，所以本題還是要稍微推一下公式找找共性

這里的異或就不能稱之為異或了，下文中，$\oplus$ 將視為 “k進(jìn)制不進(jìn)位加法”，同樣對應(yīng)一個 $?$ 為 “k進(jìn)制不退位減法”，意義為名稱所述。本題中的異或其實(shí)就是“k進(jìn)制不進(jìn)位加法”，需要提前知道的是，這兩個運(yùn)算同樣具有基本運(yùn)算的交換律和結(jié)合律的性質(zhì)。

開始推公式，假設(shè)原答案為 $x$，猜的密碼為 $y$，新密碼為 $z$，因?yàn)闈M足 $x\oplus z=y$，兩側(cè)同時(shí)“不進(jìn)位減去x”，得到 $z=y?x$

假設(shè)第 $i$ 次詢問的值為 $q_i$，密碼為 $password$，第一次詢問后，原密碼變成了 $q_1?password$；第 $k$ 次詢問后，原密碼變成了 $q_k?(q_{k?1}?...(q_2?(q_1?password)))$，這里還是令 $q_1=0$

所以假如我們第 $i$ 次猜，想要猜原密碼是否和 $x$ 相等，也就是 $password==x$ 是否成立，就必須令 $q_i=q_{i?1}?(q_{i?2}?...(q_2?(q_1?x)))$

現(xiàn)在問題是如何快速求出 $q_i$。根據(jù)結(jié)合律，不難將 $x$ 單獨(dú)拿出來，然后整個式子就變成了：$q_i=q_{i?1}?(q_{i?2}?...(q_2?q_1))opx$，這里的 $op$ 代表的是一個符號，這里先按下不表。不難看出 $op$ 前面的部分可以線性維護(hù)得到。而后面單獨(dú)拆出來的 $x$，因?yàn)橛龅綔p法拆括號時(shí)需要變號，“不進(jìn)位減法” 在這里也是同理，所以當(dāng)詢問的下標(biāo)為奇數(shù)時(shí)，$op$ 為 $?$，當(dāng)詢問的下標(biāo)為偶數(shù)時(shí)，$op$ 為 $\oplus$

然后自己模擬一下 $\oplus$ 和 $?$ 這兩個運(yùn)算就可以了，按照上面的理論，將 $n$ 個數(shù)字都枚舉一遍， 時(shí)間復(fù)雜度是 $O(nlo{g}_{k}n)$ 的

代碼：

// Problem: D2. RPD and Rap Sheet (Hard Version) // Contest: Codeforces - Codeforces Round #730 (Div. 2) // URL: https://codeforces.com/contest/1543/problem/D2 // Memory Limit: 256 MB // Time Limit: 5000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; int k; int add(int a,int b) {int ans=0,base=1;while(a||b) {int tmp=(a%k+b%k)%k;ans+=tmp*base;base*=k;a/=k,b/=k;}return ans; } int sub(int a,int b) {int ans=0,base=1;while(a||b) {int tmp=(a%k-b%k+k)%k;ans+=tmp*base;base*=k;a/=k,b/=k;}return ans; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {int n,sum=0;read(n),read(k);for(int i=0;i<n;i++) {int cur=1;if(i==0) {cur=0;} else if(i&1) {cur=sub(sum,i);} else {cur=add(sum,i);}printf("%d\n",cur);fflush(stdout);int ans;scanf("%d",&ans);if(ans==1) {break;} else {sum=sub(cur,sum);}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1543D2 RPD and Rap Sheet (Hard Version)(交互+模拟)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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