題意
給你兩個數l，m，大小為m的陣列a，求[0,l]之間滿足以下條件的數x的個數:
對于任何i輸入[0,m-1],f(x+i)%2=a[i]；f(k)：代表k在二進制下1的個數
m的范圍<=100，l<=1e18,a[i] = 0/1
思路
顯然l的范圍1e18,大概率就是數位DP了
- 觀察到m是<=100的，因此x+m只會改變后7位置，對于前面的位數，則只會進1，使得前面連續的0變成1；
- 那么只要對前半部分進行數位DP,dp[pos][lim][cnt][d]代表位置在pos處，lim代表有無達到上限，cnt為1代表前面有奇數個1為0代表偶數個1，d代表從pos起向前有偶數還是奇數個1；
- 對于第七位以后的部分，直接暴力計算就好了，統計以下是否進位；
代碼
#include <bits/stdc++.h>
using namespace std;
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
#define INF (ll)1e18
#define mod 998244353
#define maxn 110
#define lc 1338557220
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll x, rs[maxn], p;
vector<ll> pw = {23, 19, 17, 13, 11, 9, 7, 5, 4};
ll ask(ll a, ll b) {
cout << "?" _ a _ b << nf;
ll x;
cin >> x;
return x;
}
void clm(ll x) {
cout << "!" _ x << nf;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
/* #if !ONLINE_JUDGE && !EVAL
ifstream cin("input.txt");
ofstream cout("output.txt");
#endif */
// kudos for automatic wa
cin >> t;
while (t--) {
for (i = 1; i <= 23; i++) {
k = ask(x + i, lc + i);
for (j = 0; j < 9; j++) {
if (k % pw[j] == 0) rs[j] = (-i % pw[j] + pw[j]) % pw[j];
}
}
k = 1;
p = 1;
for (j = 0; j < 9; j++) {
// cout << "p =" _ p << nf;
while (p % pw[j] != rs[j]) p += k;
k *= pw[j];
}
clm(p);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/526845.html
標籤：其他
上一篇：牛客-劍指offer題解第一階段