中山市城市建设档案馆网站,小说排行榜百度,wordpress子菜单,wordpress动态效果传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
定义a⊕kba\oplus_k ba⊕kb为a,ba,ba,b在kkk进制下的不进位加法。系统会随机生成一个数xxx#xff0c;你猜这个数#xff0c;假设当前猜的数为yyy#xff0c;如果猜对了就返回111#xff0c;否则要猜的…传送门
文章目录题意思路题意
定义a⊕kba\oplus_k ba⊕kb为a,ba,ba,b在kkk进制下的不进位加法。系统会随机生成一个数xxx你猜这个数假设当前猜的数为yyy如果猜对了就返回111否则要猜的数会变成zzz其中x⊕kzbx\oplus_k zbx⊕kzb。其随机生成的数0≤xn0\le x n0≤xn你可以询问nnn次。 n≤2e5,k≤100n\le2e5,k\le100n≤2e5,k≤100
思路
由easyeasyeasy版本的异或自反性得到启发能否在kkk进制的情况下也能利用某种方式来消除上一次询问对原始答案造成的影响呢 考虑将xxx移动到右边即zb⊖kxzb\ominus_k xzb⊖kx这样就可以得到zzz了。 设原始答案为preprepre当前猜的数为guessguessguess当前变成的答案为nownownow那么有pre⊕knowguesspre\oplus_k nowguesspre⊕knowguess。 一开始还是从0开始先将guess0guess0guess0之后得到now0⊖kprenow0\ominus_k prenow0⊖kpre之后就可以按照对应的形式比如下一次需要判断111是否合法那么就让preprepre的位置变成111即让guess(1−1)⊖k1guess(1-1)\ominus_k 1guess(1−1)⊖k1这个时候nowpre⊖k1nowpre\ominus_k 1nowpre⊖k1让后再让preprepre的位置为222即guess2⊖k(2−1)guess2\ominus_k(2-1)guess2⊖k(2−1)现在now2⊖kprenow2\ominus_kprenow2⊖kpre这样一直循环下去即可可以证明这样是一定可以找到答案的。 综上答案就是ifi0guess0if\ \ i0 \ \ guess0if i0 guess0ifimod21guess(i−1)⊖kiif\ \ i\bmod 21 \ \ guess(i-1)\ominus_kiif imod21 guess(i−1)⊖ki ifimod20guessi⊖k(i−1)if\ \ i\bmod20 \ \ guessi\ominus_k(i-1)if imod20 guessi⊖k(i−1)
复杂度nlogknnlog_knnlogkn
// 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(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,k;int query(int x) {printf(%d\n,x);fflush(stdout);int now; scanf(%d,now);return now;
}int get1(int l,int r) {int ans0;int fun1;while(l||r) {ans(l%kr%k)%k*fun;l/k; r/k;fun*k;}return ans;
} int get2(int l,int r) {int ans0;int fun1;while(l||r) {ans(r%k-l%kk)%k*fun;l/k; r/k;fun*k;}return ans;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int _; scanf(%d,_);while(_--) {scanf(%d%d,n,k);for(int i0;in;i) {if(i0) {int xquery(0);if(x) break;} else {int x;if(i%21) xquery(get2(i,i-1));else xquery(get2(i-1,i));if(x) break;}}}return 0;
}
/**/
