1. 首頁 > 生活百科 > >

ICPC 第 45 屆國際大學生程序設計競賽亞洲區域賽（濟南）-L Bit Sequence

生活百科

題意給你兩個數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了

  1. 觀察到m是<=100的，因此x+m只會改變后7位置 ， 對于前面的位數 ， 則只會進1，使得前面連續的0變成1；
  2. 那么只要對前半部分進行數位DP,dp[pos][lim][cnt][d]代表位置在pos處，lim代表有無達到上限，cnt為1代表前面有奇數個1為0代表偶數個1，d代表從pos起向前有偶數還是奇數個1；
  3. 對于第七位以后的部分，直接暴力計算就好了，統計以下是否進位；
代碼#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 1338557220ll 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 && !EVALifstream cin("input.txt");ofstream cout("output.txt");#endif */// kudos for automatic wacin >> 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;}【ICPC 第 45 屆國際大學生程序設計競賽亞洲區域賽（濟南）-L Bit Sequence】

    推薦閱讀